{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ef3ea7d4-4d8b-4153-80a3-7ac5f3e7b5c9"
      },
      "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": 102,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "47ee8eaf-6c75-4e1c-88e2-9fafb8cc98d4"
      },
      "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": 103,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 104,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "- transition model $P(s' | s, a)$ gives probability that action $a$ in state $s$ reaches state $s'$.\n",
        "\n",
        "$$P(result(a) = s') = \\sum_{s}P(s)P(s'|s, a)$$\n",
        "\n",
        "- **utility functions -** single number to desirability of state\n",
        "- **expected utility** - average utility value of outcomes, weighted by probability of outcome\n",
        "- **maximum expected utility** - choose action to maximize expected utility\n",
        "\"\"\"\n",
        "chapter16_2 =  \"\"\"\n",
        "- **lottery** - set of outcomes for each action, each with an associated probability\n",
        "- constraints on rational preferences. properties:\n",
        "    - orderability, transitivity, continuity, substitutability, monotonocity, decomposability\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "- **sequential decision problems** - agent's utility depends on sequence of decisions.\n",
        "- begin at start state. choose action at each time. goal state is marked +1 or -1.\n",
        "    - actions achieve intended effect with probability 0.8\n",
        "    - negative reward for all transitions (except terminal states) incentivizes agent to reach terminal state quickly.\n",
        "- **Markov decision process** - set of states; set of actions; transition model; reward function.\n",
        "- **policy** ($\\pi(s)$) - solution for what the agent should do in any state. measured by *expected* utility. **optimal policy** yields highest expected utility, $\\pi^*(s)$.\n",
        "- **finite horizon** - after a fixed time N, game is over. optimal action may depend on time left. *nonstationary*.\n",
        "- **infinite horizon** - same behavior in every state, *stationary*.\n",
        "- **discount factor**, $\\gamma$ - number between 0 and 1, preference of an agent for current rewards > future rewards.\n",
        "    - $\\gamma = 0$, distant rewards are insignificant.\n",
        "    \n",
        "    $$U_{h}([s_0, a_0, s_1, a_1, s_2,...]) = R(s_0, a_0, s_1) + \\gamma R(s_1, a_1, s_2) + \\gamma ^ 2 R(s_2,...)$$\n",
        "    \n",
        "\n",
        "$$\\pi^*(s) = argmax_{a \\in A(s)} \\sum_{s'} P(s' | s, a)[R(s, a, s') + \\gamma U(s')]$$\n",
        "\n",
        "- **action-utility function / Q-function,** $Q(s, a)$ - expected utility of taking a given action in a given state\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "**value iteration**\n",
        "\n",
        "- one bellman equation per state, $n$ unknowns. applying Bellman update infinitely often reaches a convergence.\n",
        "- **contraction** - function of one arg that when applied to 2 different inputs produces 2 output values that are \"closer together\" by some constant factor than the original input\n",
        "    - e.g. dividing by 2\n",
        "    - has one fixed point. when value is applied to any arg, value gets closer to fixed point.\n",
        "    - possible to get optimal policy even when utility function is inaccurate.\n",
        "\n",
        "⇒ **Bellman update is a contraction by a factor of** $\\gamma$ **on the space of utility vectors**\n",
        "\n",
        "**policy iteration**\n",
        "\n",
        "- policy evaluation: given $\\pi_{i}$, calculate $U_i = U^{\\pi_i}$\n",
        "- policy improvement\n",
        "- simpler than value iteration bc action in each state is fixed by policy.\n",
        "- $O(n^3)$, good for small state spaces.\n",
        "\n",
        "**modified policy iteration**\n",
        "\n",
        "- perform some number of simplified value iteratoin steps. approximate utilities.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "## module 8: markov decision processes\n",
        "\n",
        "### intro to MDP\n",
        "\n",
        "- stochastic environment — *Up* only moves up 80% of the time\n",
        "\n",
        "stochastic transition model\n",
        "\n",
        "- $T(s, a, s') = p(s' | s, a)$, only depends on $s$ and not the history of earlier states\n",
        "\n",
        "**reward function**\n",
        "\n",
        "- specify a *utility / reward function* for the agent\n",
        "- \"rewards\" can be *positive* or *negative* but are bounded by some max value\n",
        "- agent can receive a reward at each time step instead of only at goal states\n",
        "\n",
        "### MDP formulation\n",
        "\n",
        "- sequential decision problem for a fully observable environment, with a stochastic transition model with additive rewards\n",
        "- *non-deterministic* search problems\n",
        "\n",
        "formal definition:\n",
        "\n",
        "- set of states\n",
        "- set of actions\n",
        "- transition function T(s, a, s')\n",
        "- reward function R(s, a, s')\n",
        "- initial state, s0\n",
        "- optionally - ≥1 terminal states\n",
        "\n",
        " solution == **policy**: best action in current state, function $\\pi(S) = a$\n",
        "\n",
        "- policy $\\pi$ tells agent what action to take at state S\n",
        "- $\\pi^*$ is the optimal policy, depends on reward function\n",
        "\n",
        "compute *expected utility* of all possible paths generated by a policy.\n",
        "\n",
        "**sequences of rewards**\n",
        "\n",
        "- performance is the sum of the rewards for transitions taken\n",
        "\n",
        "**utilities of sequences**\n",
        "\n",
        "- prefer more over less\n",
        "- prefer now over later\n",
        "\n",
        "**discounting**: values of rewards decay exponentially (to maximize sums and prefer rewards now over later)\n",
        "\n",
        "- each time we descend a level, we multiply in the discount once\n",
        "- e.g. $U([1, 2, 3]) = 0.5^0*1 + 0.5^1*2 + 0.5^2*3$\n",
        "\n",
        "to prevent infinite utilities: finite horizon (terminate after a fixed T steps), discounting\n",
        "\n",
        "### MDP examples\n",
        "\n",
        "- $V^*(s)$ = expected utility starting in $s$ and acting optimally\n",
        "- $Q^*(s, a)$ = expected utility starting out having taken action a from state s and acting optimally afterwards\n",
        "- $\\pi^*(s)$ = optimal action from state $s$\n",
        "\n",
        "values of states\n",
        "\n",
        "### value iteration algs\n",
        "\n",
        "- start with $V_0(s) = 0$: no time steps left means an expected reward sum of 0\n",
        "- given a vector of $V_k(s)$ values, do one ply of expectimax from each state\n",
        "    \n",
        "    $V_{k + 1}(s) \\leftarrow max \\sum_{s'} T(s, a, s')[R(s, a, s') + \\gamma V_k(s')]$\n",
        "    \n",
        "- repeat until convergence. complexity is $O(S^2A)$\n",
        "\n",
        "### policy evaluation\n",
        "\n",
        "- given a policy, what values do i get?\n",
        "- no need for max operation anymore\n",
        "- pick action with highest q-value\n",
        "\n",
        "### policy iteration alg\n",
        "\n",
        "value iteration repeats the bellman updates. very slow $O(S^2A)$ per iteration. \"max\" per state rarely changes.\n",
        "\n",
        "1. **policy evaluation**: calculate utilities for some fixed policy until convergence\n",
        "    \n",
        "    for fixed current policy $\\pi$, find values with policy iteration\n",
        "    \n",
        "    - iterate until values converge\n",
        "2. **policy improvement**: update policy using one-step look-ahead with resulting converged utilities as future values.\n",
        "- repeat steps until policy converges\n",
        "\n",
        "**policy iteration**: optimal! can converge faster under some conditions.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 105,
      "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": 0
        },
        "outputId": "48019665-fd2f-4682-a9f8-5b2bd333e990"
      },
      "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": 106,
      "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\n- transition model $P(s' | s, a)$ gives probability that action $a$ in state $s$ reaches state $s'$.\n\n$$P(result(a) = s') = \\sum_{s}P(s)P(s'|s, a)$$\n\n- **utility functions -** single number to desirability of state\n- **expected utility** - average utility value of outcomes, weighted by probability of outcome\n- **maximum expected utility** - choose action to maximize expected utility\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- **lottery** - set of outcomes for each action, each with an associated probability\n- constraints on rational preferences. properties:\n    - orderability, transitivity, continuity, substitutability, monotonocity, decomposability\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- **sequential decision problems** - agent's utility depends on sequence of decisions.\n- begin at start state. choose action at each time. goal state is marked +1 or -1.\n    - actions achieve intended effect with probability 0.8\n    - negative reward for all transitions (except terminal states) incentivizes agent to reach terminal state quickly.\n- **Markov decision process** - set of states; set of actions; transition model; reward function.\n- **policy** ($\\pi(s)$) - solution for what the agent should do in any state. measured by *expected* utility. **optimal policy** yields highest expected utility, $\\pi^*(s)$.\n- **finite horizon** - after a fixed time N, game is over. optimal action may depend on time left. *nonstationary*.\n- **infinite horizon** - same behavior in every state, *stationary*.\n- **discount factor**, $\\gamma$ - number between 0 and 1, preference of an agent for current rewards > future rewards.\n    - $\\gamma = 0$, distant rewards are insignificant.\n    \n    $$U_{h}([s_0, a_0, s_1, a_1, s_2,...]) = R(s_0, a_0, s_1) + \\gamma R(s_1, a_1, s_2) + \\gamma ^ 2 R(s_2,...)$$\n    \n\n$$\\pi^*(s) = argmax_{a \\in A(s)} \\sum_{s'} P(s' | s, a)[R(s, a, s') + \\gamma U(s')]$$\n\n- **action-utility function / Q-function,** $Q(s, a)$ - expected utility of taking a given action in a given state\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n**value iteration**\n\n- one bellman equation per state, $n$ unknowns. applying Bellman update infinitely often reaches a convergence.\n- **contraction** - function of one arg that when applied to 2 different inputs produces 2 output values that are \"closer together\" by some constant factor than the original input\n    - e.g. dividing by 2\n    - has one fixed point. when value is applied to any arg, value gets closer to fixed point.\n    - possible to get optimal policy even when utility function is inaccurate.\n\n⇒ **Bellman update is a contraction by a factor of** $\\gamma$ **on the space of utility vectors**\n\n**policy iteration**\n\n- policy evaluation: given $\\pi_{i}$, calculate $U_i = U^{\\pi_i}$\n- policy improvement\n- simpler than value iteration bc action in each state is fixed by policy.\n- $O(n^3)$, good for small state spaces.\n\n**modified policy iteration**\n\n- perform some number of simplified value iteratoin steps. approximate utilities.\n\n\n## Module 8 Lecture Notes\n\n## module 8: markov decision processes\n\n### intro to MDP\n\n- stochastic environment — *Up* only moves up 80% of the time\n\nstochastic transition model\n\n- $T(s, a, s') = p(s' | s, a)$, only depends on $s$ and not the history of earlier states\n\n**reward function**\n\n- specify a *utility / reward function* for the agent\n- \"rewards\" can be *positive* or *negative* but are bounded by some max value\n- agent can receive a reward at each time step instead of only at goal states\n\n### MDP formulation\n\n- sequential decision problem for a fully observable environment, with a stochastic transition model with additive rewards\n- *non-deterministic* search problems\n\nformal definition:\n\n- set of states\n- set of actions\n- transition function T(s, a, s')\n- reward function R(s, a, s')\n- initial state, s0\n- optionally - ≥1 terminal states\n\n solution == **policy**: best action in current state, function $\\pi(S) = a$\n\n- policy $\\pi$ tells agent what action to take at state S\n- $\\pi^*$ is the optimal policy, depends on reward function\n\ncompute *expected utility* of all possible paths generated by a policy.\n\n**sequences of rewards**\n\n- performance is the sum of the rewards for transitions taken\n\n**utilities of sequences**\n\n- prefer more over less\n- prefer now over later\n\n**discounting**: values of rewards decay exponentially (to maximize sums and prefer rewards now over later)\n\n- each time we descend a level, we multiply in the discount once\n- e.g. $U([1, 2, 3]) = 0.5^0*1 + 0.5^1*2 + 0.5^2*3$\n\nto prevent infinite utilities: finite horizon (terminate after a fixed T steps), discounting\n\n### MDP examples\n\n- $V^*(s)$ = expected utility starting in $s$ and acting optimally\n- $Q^*(s, a)$ = expected utility starting out having taken action a from state s and acting optimally afterwards\n- $\\pi^*(s)$ = optimal action from state $s$\n\nvalues of states\n\n### value iteration algs\n\n- start with $V_0(s) = 0$: no time steps left means an expected reward sum of 0\n- given a vector of $V_k(s)$ values, do one ply of expectimax from each state\n    \n    $V_{k + 1}(s) \\leftarrow max \\sum_{s'} T(s, a, s')[R(s, a, s') + \\gamma V_k(s')]$\n    \n- repeat until convergence. complexity is $O(S^2A)$\n\n### policy evaluation\n\n- given a policy, what values do i get?\n- no need for max operation anymore\n- pick action with highest q-value\n\n### policy iteration alg\n\nvalue iteration repeats the bellman updates. very slow $O(S^2A)$ per iteration. \"max\" per state rarely changes.\n\n1. **policy evaluation**: calculate utilities for some fixed policy until convergence\n    \n    for fixed current policy $\\pi$, find values with policy iteration\n    \n    - iterate until values converge\n2. **policy improvement**: update policy using one-step look-ahead with resulting converged utilities as future values.\n- repeat steps until policy converges\n\n**policy iteration**: optimal! can converge faster under some conditions.\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\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 =  \"\"\"\n",
        "- **n-armed bandit** - *n* levers, each lever has a fixed but unknown probability distribution of winning\n",
        "- exploitation vs. exploration\n",
        "    - arms are independent\n",
        "- **Gittins index**\n",
        "    \n",
        "    $$\\gamma = max_{T>0}\\frac{E(\\sum_{t=1}^{T-1} \\gamma^t R_t}{E(\\sum_{t=0}^{T-1} \\gamma^t)}$$\n",
        "    \n",
        "    - O(n) time to calculate optimal decision, $n$ = # of arms\n",
        "- at tipping point, optimal policy is indifferent between $M$ and $M_{\\lambda}$\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "- **reinforcement learning** - agent interacts with world and receives **rewards**.\n",
        "    - same goal as MDP: maximize expected sum of rewards\n",
        "    - *not given* the MDP as a problem to solve but agent is *in* the MDP — doesn't know transition model or reward function\n",
        "    - learning the rules as it plays...\n",
        "\n",
        "**model-based reinforcement learning:** agent uses transition model to make decisions. if unknown, learned from observing effects.\n",
        "\n",
        "**model-free reinforcement learning**: no transition model\n",
        "\n",
        "- **action-utility learning**: Q-learning, in a given state, agent chooses action with highest Q-value\n",
        "- **policy search**: agent learns policy.\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "- fixed policy, goal is to learn states' utilities ⇒ *exploration*\n",
        "- unknown transition model $P(s' | s, a)$\n",
        "    - agent tries some stuff until it reaches terminal states. records the states and rewards received.\n",
        "- **direct utility estimation** - utility of state is expected total reward from that state onward\n",
        "- temporal-difference learning - can also use observed transitions to adjust observed state utilities\n",
        "    \n",
        "    $$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s, \\pi(s), s')] + \\gamma U^{\\pi}(s') - U^{\\pi}(s)$$\n",
        "    \n",
        "    - $\\alpha$ is learning rate parameter\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "- decides what actions to take (passive learning agent has a fixed policy)\n",
        "- uses passive learning mechanism to learn transition model\n",
        "    - one-step look-ahead to maximize expected utility. chooses that optimal action.\n",
        "- **greedy agent** - greedily takes action it believes is optimal. but sometimes choosing the optimal action every time is suboptimal. exploitation (take greatest known reward) vs. exploration (gain info to change policy).\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "$$\\pi(s) = argmax_{a} \\hat{Q}_{\\theta} (s, a)$$\n",
        "\n",
        "- Q-learning with function approx: find $\\theta$ st $\\hat{Q}_{\\theta}$ is close to optimal Q-function.\n",
        "- policy search: find $\\theta$ to get good performance. discontinuous function when actions are discrete.\n",
        "    - **softmax function** used over gradient-based search.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "- MDP: know probability distribution. reinforcement learning: need to learn distribution.\n",
        "\n",
        "**double-bandit MDP**: blue and red slot machines. probability of each reward value given.\n",
        "\n",
        "- reinforcement learning — process of taking actions & observing results to update expectations\n",
        "\n",
        "**exploration**: try unknown actions to get info\n",
        "\n",
        "**exploitation:** eventually, use what you know\n",
        "\n",
        "**regret:** mistakes, suboptimal attempts\n",
        "\n",
        "**sampling:** stochastic environment so have to try things repeatedly\n",
        "\n",
        "**difficulty:** learning is harder than solving a known MDP\n",
        "\n",
        "**basic idea** - receive feedback in form of rewards. agent's utility is defined by reward function. must (learn to) act to maximize expected rewards.\n",
        "\n",
        "- assumes a markov decision process (MDP):\n",
        "    - set of states $s \\in S$\n",
        "    - set of actions (per state) $A$\n",
        "    - model $T(s, a, s')$\n",
        "    - reward function $R(s, a, s')$\n",
        "    - looking for a policy $\\pi(s)$\n",
        "- don't know $T$ or $R$. must try actions and states to learn.\n",
        "- MDPs are offline. compute things ahead of time without doing. RL is online.\n",
        "\n",
        "**model-based learning**\n",
        "\n",
        "- approximate model based on experiences. solve for values if learned model were correct.\n",
        "1. learn empirical MDP model: count outcomes $s'$ for each $s, a$ to determine probabilities\n",
        "    - normalize to estimate $\\hat{T}(s, a, s')$\n",
        "    - discover each $\\hat{R}(s, a, s')$\n",
        "2. solve learned MDP (i.e. value iteration)\n",
        "\n",
        "### passion reinforcement learning\n",
        "\n",
        "**model-free learning**: take action, compare results between expectation and reality. adjust values appropriately.\n",
        "\n",
        "passive reinforcement learning - given fixed policy, how good is policy?\n",
        "\n",
        "- input: fixed policy $\\pi(s)$. unknown transition, rewards.\n",
        "- goal: learn state values. avg together observed sample values. *direct evaluation*.\n",
        "\n",
        "positives: easy to understand. doesn't requre knowledge of T or R. eventually computes correct avg values.\n",
        "\n",
        "negatives: wastes info about state connections. each state is learned separate, takes a long time to learn.\n",
        "\n",
        "**sample-based policy evaluation**:\n",
        "\n",
        "- improve estimate by computing average\n",
        "    \n",
        "    $V_{k+1}^{\\pi}(s) \\leftarrow \\sum_{s'}T(s, \\pi(s), s')[R(s, \\pi(s), s') + \\gamma V_k^{\\pi}(s')$\n",
        "    \n",
        "- take samples of outcomes s' and avg. won't work under reinforcement policy since we cannot guarantee an initial state of $s$.\n",
        "\n",
        "### temporal difference learning\n",
        "\n",
        "- update V(s) each time we experience a transition.\n",
        "- move values toward value of successor, running average\n",
        "\n",
        "$sample = R(s, \\pi(s), s') + \\gamma V^{\\pi}(s')$\n",
        "\n",
        "$update = V^{\\pi}(s) \\leftarrow (1 - \\alpha)V^{\\pi}(s) + (\\alpha)sample = V^{\\pi}(s) + \\alpha(sample - V^{\\pi}(s))$\n",
        "\n",
        "- $\\alpha$ is learning rate, controls how much we update new estimate from current estimate\n",
        "    - if $\\alpha = 0$, new sample has no weight. if $\\alpha = 1$ then entire state is dictated by current state.\n",
        "\n",
        "**exponential moving average:** more recent samples are more important\n",
        "\n",
        "**decreasing learning rate (alpha) can give converging avgs**\n",
        "\n",
        "problems with TD value learning\n",
        "\n",
        "- need to learn Q-values, not values (?)\n",
        "\n",
        "### active reinforcement learning (Q-learning)\n",
        "\n",
        "**full reinforcement learning**: optimal policies (like value iteration) without knowing transitions and rewards\n",
        "\n",
        "**Q-value iteration**\n",
        "\n",
        "- value iteration: find successive (depth-limited) values\n",
        "    - start with $V_0(s) = 0$\n",
        "    - given $V_k$, calculate depth $k+1$ values for all states\n",
        "- Q-values are more useful so compute them instead (q-value iteration)\n",
        "    - $Q_0(s, a) = 0$\n",
        "    - given $Q_k$, calculate depth $k + 1$ q-values for all q-states\n",
        "\n",
        "**Q-learning**: sample-based Q-value iteration\n",
        "\n",
        "$Q_{k+1}(s, a) \\leftarrow \\sum_{s'} T(s, a, s') R(s, a, s') + \\gamma max_{a'} Q_k (s', a')$\n",
        "\n",
        "- learn $Q(s, a)$ values as we go\n",
        "- incorporate new estimate into running avg\n",
        "    \n",
        "    $Q(s, a) \\leftarrow (1 - \\alpha) Q(s, a) + (\\alpha)(sample)$\n",
        "    \n",
        "    - $\\alpha = 1$ → ignore previous estimates. $\\alpha = 0$ → all weight is on previous estimates\n",
        "\n",
        "**Q-learning converges to optimal policy!** (even if you're acting suboptimally) ⇒ *off-policy learning*\n",
        "\n",
        "- caveats: need to explore enough. eventually make learning rate small enough. tweak learning rate so it decreases over time (trust previous history more).\n",
        "\n",
        "### exploration vs. exploitation\n",
        "\n",
        "**epsilon-greedy policy:** randomly generate a number. if number is smaller than $\\epsilon$, act randomly. otherwise, act on current policy.\n",
        "\n",
        "- problems: eventually will explore space but we'll repeatedly choose things we've already explored. soln - lower $\\epsilon$ over time. or encode exploration functions.\n",
        "- **exploration functions**: explore areas whose \"badness\" is not yet established, eventually stop exploring.\n",
        "    - $f(u, n) = u + k / n$.\n",
        "        - $u$ : current utility estimate\n",
        "        - $n$ : # times we've visited that state\n",
        "        - $k$ : bonus if we haven't expored that state many times\n",
        "\n",
        "Q-learning is randomly visiting new states. epsilon-greedy pushes us towards exploring states we haven't visited.\n",
        "\n",
        "**regret:** measure of total mistake cost (difference bw expected rewards (including youthful suboptimality) and optimal (expected) rewards)\n",
        "\n",
        "- minimizing regret requires optimally learning to be optimal\n",
        "- quantifies relative goodness of exploration procedures\n",
        "\n",
        "### approx. Q-learning\n",
        "\n",
        "basic Q-learning keeps a table of all q-values, but sometimes this table is too large to hold in memory.\n",
        "\n",
        "**evaluation functions**: score non-terminals in depth-limited search. weight linear sum of features (e.g. # white queens).\n",
        "\n",
        "- $eval(s) = w_1 f_1(s) + w_2 f_2(s) + ... + w_n f_n(s)$\n",
        "- **linear value functions**: features representing a state multiplied by weight\n",
        "    - adv - experience is summed up in a few powerful numbers\n",
        "    - disadv - states may share features but be very different in value\n",
        "\n",
        "$Q(s, a) = w_1 f_1(s, a) + ... + w_n f_n (s, a)$\n",
        "\n",
        "- $difference = (r + \\gamma max_{\\alpha'} Q(s', a')) - Q(s, a)$\n",
        "- $Q(s, a) \\leftarrow Q(s, a) + \\alpha (difference)$\n",
        "    - $w_i \\leftarrow w_i + \\alpha(difference) f_i (s, a)$\n",
        "    - (??) review this\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 107,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7ccf8b12-7ea4-4cb2-d121-ea321d9b6273"
      },
      "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": 108,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- **n-armed bandit** - *n* levers, each lever has a fixed but unknown probability distribution of winning\n- exploitation vs. exploration\n    - arms are independent\n- **Gittins index**\n    \n    $$\\gamma = max_{T>0}\frac{E(\\sum_{t=1}^{T-1} \\gamma^t R_t}{E(\\sum_{t=0}^{T-1} \\gamma^t)}$$\n    \n    - O(n) time to calculate optimal decision, $n$ = # of arms\n- at tipping point, optimal policy is indifferent between $M$ and $M_{\\lambda}$\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- **reinforcement learning** - agent interacts with world and receives **rewards**.\n    - same goal as MDP: maximize expected sum of rewards\n    - *not given* the MDP as a problem to solve but agent is *in* the MDP — doesn't know transition model or reward function\n    - learning the rules as it plays...\n\n**model-based reinforcement learning:** agent uses transition model to make decisions. if unknown, learned from observing effects.\n\n**model-free reinforcement learning**: no transition model\n\n- **action-utility learning**: Q-learning, in a given state, agent chooses action with highest Q-value\n- **policy search**: agent learns policy.\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n- fixed policy, goal is to learn states' utilities ⇒ *exploration*\n- unknown transition model $P(s' | s, a)$\n    - agent tries some stuff until it reaches terminal states. records the states and rewards received.\n- **direct utility estimation** - utility of state is expected total reward from that state onward\n- temporal-difference learning - can also use observed transitions to adjust observed state utilities\n    \n    $$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \u0007lpha[R(s, \\pi(s), s')] + \\gamma U^{\\pi}(s') - U^{\\pi}(s)$$\n    \n    - $\u0007lpha$ is learning rate parameter\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- decides what actions to take (passive learning agent has a fixed policy)\n- uses passive learning mechanism to learn transition model\n    - one-step look-ahead to maximize expected utility. chooses that optimal action.\n- **greedy agent** - greedily takes action it believes is optimal. but sometimes choosing the optimal action every time is suboptimal. exploitation (take greatest known reward) vs. exploration (gain info to change policy).\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n\n## Module 9 Lecture Notes\n\n- MDP: know probability distribution. reinforcement learning: need to learn distribution.\n\n**double-bandit MDP**: blue and red slot machines. probability of each reward value given.\n\n- reinforcement learning — process of taking actions & observing results to update expectations\n\n**exploration**: try unknown actions to get info\n\n**exploitation:** eventually, use what you know\n\n**regret:** mistakes, suboptimal attempts\n\n**sampling:** stochastic environment so have to try things repeatedly\n\n**difficulty:** learning is harder than solving a known MDP\n\n**basic idea** - receive feedback in form of rewards. agent's utility is defined by reward function. must (learn to) act to maximize expected rewards.\n\n- assumes a markov decision process (MDP):\n    - set of states $s \\in S$\n    - set of actions (per state) $A$\n    - model $T(s, a, s')$\n    - reward function $R(s, a, s')$\n    - looking for a policy $\\pi(s)$\n- don't know $T$ or $R$. must try actions and states to learn.\n- MDPs are offline. compute things ahead of time without doing. RL is online.\n\n**model-based learning**\n\n- approximate model based on experiences. solve for values if learned model were correct.\n1. learn empirical MDP model: count outcomes $s'$ for each $s, a$ to determine probabilities\n    - normalize to estimate $\\hat{T}(s, a, s')$\n    - discover each $\\hat{R}(s, a, s')$\n2. solve learned MDP (i.e. value iteration)\n\n### passion reinforcement learning\n\n**model-free learning**: take action, compare results between expectation and reality. adjust values appropriately.\n\npassive reinforcement learning - given fixed policy, how good is policy?\n\n- input: fixed policy $\\pi(s)$. unknown transition, rewards.\n- goal: learn state values. avg together observed sample values. *direct evaluation*.\n\npositives: easy to understand. doesn't requre knowledge of T or R. eventually computes correct avg values.\n\nnegatives: wastes info about state connections. each state is learned separate, takes a long time to learn.\n\n**sample-based policy evaluation**:\n\n- improve estimate by computing average\n    \n    $V_{k+1}^{\\pi}(s) \\leftarrow \\sum_{s'}T(s, \\pi(s), s')[R(s, \\pi(s), s') + \\gamma V_k^{\\pi}(s')$\n    \n- take samples of outcomes s' and avg. won't work under reinforcement policy since we cannot guarantee an initial state of $s$.\n\n### temporal difference learning\n\n- update V(s) each time we experience a transition.\n- move values toward value of successor, running average\n\n$sample = R(s, \\pi(s), s') + \\gamma V^{\\pi}(s')$\n\n$update = V^{\\pi}(s) \\leftarrow (1 - \u0007lpha)V^{\\pi}(s) + (\u0007lpha)sample = V^{\\pi}(s) + \u0007lpha(sample - V^{\\pi}(s))$\n\n- $\u0007lpha$ is learning rate, controls how much we update new estimate from current estimate\n    - if $\u0007lpha = 0$, new sample has no weight. if $\u0007lpha = 1$ then entire state is dictated by current state.\n\n**exponential moving average:** more recent samples are more important\n\n**decreasing learning rate (alpha) can give converging avgs**\n\nproblems with TD value learning\n\n- need to learn Q-values, not values (?)\n\n### active reinforcement learning (Q-learning)\n\n**full reinforcement learning**: optimal policies (like value iteration) without knowing transitions and rewards\n\n**Q-value iteration**\n\n- value iteration: find successive (depth-limited) values\n    - start with $V_0(s) = 0$\n    - given $V_k$, calculate depth $k+1$ values for all states\n- Q-values are more useful so compute them instead (q-value iteration)\n    - $Q_0(s, a) = 0$\n    - given $Q_k$, calculate depth $k + 1$ q-values for all q-states\n\n**Q-learning**: sample-based Q-value iteration\n\n$Q_{k+1}(s, a) \\leftarrow \\sum_{s'} T(s, a, s') R(s, a, s') + \\gamma max_{a'} Q_k (s', a')$\n\n- learn $Q(s, a)$ values as we go\n- incorporate new estimate into running avg\n    \n    $Q(s, a) \\leftarrow (1 - \u0007lpha) Q(s, a) + (\u0007lpha)(sample)$\n    \n    - $\u0007lpha = 1$ → ignore previous estimates. $\u0007lpha = 0$ → all weight is on previous estimates\n\n**Q-learning converges to optimal policy!** (even if you're acting suboptimally) ⇒ *off-policy learning*\n\n- caveats: need to explore enough. eventually make learning rate small enough. tweak learning rate so it decreases over time (trust previous history more).\n\n### exploration vs. exploitation\n\n**epsilon-greedy policy:** randomly generate a number. if number is smaller than $\\epsilon$, act randomly. otherwise, act on current policy.\n\n- problems: eventually will explore space but we'll repeatedly choose things we've already explored. soln - lower $\\epsilon$ over time. or encode exploration functions.\n- **exploration functions**: explore areas whose \"badness\" is not yet established, eventually stop exploring.\n    - $f(u, n) = u + k / n$.\n        - $u$ : current utility estimate\n        - $n$ : # times we've visited that state\n        - $k$ : bonus if we haven't expored that state many times\n\nQ-learning is randomly visiting new states. epsilon-greedy pushes us towards exploring states we haven't visited.\n\n**regret:** measure of total mistake cost (difference bw expected rewards (including youthful suboptimality) and optimal (expected) rewards)\n\n- minimizing regret requires optimally learning to be optimal\n- quantifies relative goodness of exploration procedures\n\n### approx. Q-learning\n\nbasic Q-learning keeps a table of all q-values, but sometimes this table is too large to hold in memory.\n\n**evaluation functions**: score non-terminals in depth-limited search. weight linear sum of features (e.g. # white queens).\n\n- $eval(s) = w_1 f_1(s) + w_2 f_2(s) + ... + w_n f_n(s)$\n- **linear value functions**: features representing a state multiplied by weight\n    - adv - experience is summed up in a few powerful numbers\n    - disadv - states may share features but be very different in value\n\n$Q(s, a) = w_1 f_1(s, a) + ... + w_n f_n (s, a)$\n\n- $difference = (r + \\gamma max_{\u0007lpha'} Q(s', a')) - Q(s, a)$\n- $Q(s, a) \\leftarrow Q(s, a) + \u0007lpha (difference)$\n    - $w_i \\leftarrow w_i + \u0007lpha(difference) f_i (s, a)$\n    - (??) review this\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 = \"\"\n",
        "chapter12_2 = \"\"\"\n",
        "$$P(a|b) = \\frac{P(a \\cap b)}{P(b)}$$\n",
        "\n",
        "- **joint probability distribution** - $P(a, b)$ = probabilities of all combinations of values of $a$ and $b$\n",
        "    \n",
        "    $$P(a, b) = P(a | b)P(b)$$\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "- extract distribution over subset of variables / single variable\n",
        "- **marginalization / summing out** - sum up probabilities for each value of other variables\n",
        "    \n",
        "    $$P(Y) = \\sum_{z} P(Y, Z = z)$$\n",
        "    \n",
        "- for a domain with $n$ boolean variables, input table has size $O(2^n)$\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\"\n",
        "independent if:\n",
        "\n",
        "$$P(a|b) = P(a) \\text{ or } P(b|a) = P(b) \\text{ or } P(a \\cap b) = P(a)P(b)$$\n",
        "\n",
        "- reduces amt of info necessary to split full joint distribution. complete set of variables can be divided into independent subsets.\n",
        "\"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "$$P(Y|X) = \\frac{P(X|Y)P(Y)}{P(X)}$$\n",
        "\n",
        "i.e. P(cause | effect) = P(effect | cause)P(cause) / P(effect)\n",
        "\n",
        "**conditional independence:** $P(X, Y|Z) = P(X|Z)P(Y|Z)$\n",
        "\n",
        "- size of representation is $O(n)$ instead of $O(2^n)$\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "$P(cause, effect_1, ..., effect_n) = P(cause) \\Pi_{i} P(effect_i | cause)$\n",
        "\n",
        "- simplifying assumption for when \"effect\" variables aren't independent from the cause\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\"\n",
        "- $P(w | h)$: probability of $w$ given some history $h$\n",
        "    - relative frequency counts: large corpus, count # of times we've seen $h$ and $w$ afterwards. not enough past info due to huge # of combinations.\n",
        "- **chain rule of probability:**\n",
        "    \n",
        "    $$P(X_1,...,X_n) = P(X_1)P(X_2|X_1)...P(X_N|X_{1:n-1}) = \\Pi_{k=1}^n P(X_k|X_{1:k-1})$$\n",
        "    \n",
        "    - for a join distribution with $N$ random variables, there are $N!$ ways to apply the chain rule.\n",
        "- **n-gram model -** approximate history using just the last few words\n",
        "    - bigram = only preceding word. $P(w_n | w_{1:n-1}) \\approx P(w_n | w_{n-1})$\n",
        "        - **markov assumption** - predict probability of future unit without looking too far into the past ⇒ makes it possible to estimate probabilities from data.\n",
        "- MLE estimate\n",
        "    \n",
        "    $$P(w_n|w_n-1) = \\frac{C(w_{n-1}w_n)}{\\sum_w C(w_{n-1}w)}$$\n",
        "    \n",
        "    - ratio = **relative frequency** = observed freq of sequence / observed freq of prefix\n",
        "- log probabilities so numbers aren't as smol\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "- **extrinsic evaluation** - embed language model into an app and measure app's improvement\n",
        "- **intrinsic evaluation** - measures quality of a model independent of actual application. need a **test set** with unseen data from the **training set**\n",
        "    - model with higher probability to test set is better\n",
        "- **perplexity** - inverse probability of the test set, normalized by # of words\n",
        "    \n",
        "    $$PP(W) = P(w_1w_2...w_N)^{-1/N} = (\\Pi_{i=1}^{N}(w_i|w_1...w_{i-1}))^{-1/N}$$\n",
        "    \n",
        "    - higher conditional probability ⇒ lower perplexity\n",
        "    - lower perplexity is better\n",
        "    - (also) weighted avg branching factor (# of possible next words which can follow current word)\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "- generate sentences across a distribution from a language model.\n",
        "\"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "- dependent on training corpus. incr $N$ results in better performance.\n",
        "- training corpus will miss some n-gram sequences. cannot divide by 0 and can't compute perplexity.\n",
        "- **out of vocabulary (OOV), unknown words?**\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "**Laplace smoothing:** add 1 to all n-gram counts\n",
        "\n",
        "**add-k smoothing**\n",
        "\n",
        "$$P_{add-k}(w_n | w_{n - 1}) = \\frac{C(w_{n-1}w_n) + k}{C(w_{n-1}) + kV}$$\n",
        "\n",
        "- add a fractional count $k$ instead of 1. need to choose $k$ by optimizing on a devset.\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "### probability review\n",
        "\n",
        "- **observed variables (evidence):** agent knows certain things about state of world\n",
        "- **unobserved variables (state):** agent needs to reason about other aspects\n",
        "- **model:** agent knows something about how the known variables relate to unknown variables\n",
        "\n",
        "*possible worlds* - quantifies how likely a possible world is.\n",
        "\n",
        "### distributions\n",
        "\n",
        "- distribution = table of value probabilities\n",
        "\n",
        "**joint distributions**: over a set of random variables. specifies a real number for each assignment.\n",
        "\n",
        "- $P(X_1 = x_1, X_2 = x_2,...,X_n = x_n)$\n",
        "- size of distribution if $n$ variables have domain sizes of $d$? $d^n$\n",
        "\n",
        "**probabilistic model**: joint distribution over a set of RVs\n",
        "\n",
        "**event**: set of possible outcomes\n",
        "\n",
        "**marginal distribution**: sub-tables which eliminate variables\n",
        "\n",
        "**conditional probabilities**: $P(a|b) = \\frac{P(a, b)}{P(b)} = \\frac{P(a \\cap b)}{P(b)}$\n",
        "\n",
        "### probabilitic inference & rules\n",
        "\n",
        "- probabilistic inference: compute a desired probability from other known probabilities\n",
        "    - changes with new evidence\n",
        "\n",
        "**inference by enumeration**\n",
        "\n",
        "- evidence variables, query variables, hidden variables (unobserved) ⇒ all variables\n",
        "- we want: $P(Q | e_1,...,e_k)$\n",
        "    1. select entries consistent with evidence\n",
        "    2. sum out $H$ to get joint of query and evidence (marginalization)\n",
        "        \n",
        "        $P(Q, e_1,...,e_k) = \\sum_{h_1...h_r} P(Q, h_1 ... h_r, e_1 ... e_k)$\n",
        "        \n",
        "    3. totals may not add to 1 → normalize by dividing by $Z$\n",
        "\n",
        "**product rule**: $P(y)P(x|y) = P(x, y)$\n",
        "\n",
        "**chain rule:** can always write joint distribution as incremental product of conditional distributions\n",
        "\n",
        "- $P(x_1, x_2,...,x_n) = \\Pi_{i} P(x_i | x_1...x_{i - 1})$\n",
        "\n",
        "**bayes' rule:**\n",
        "\n",
        "- $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
        "    - $P(x|y) = \\frac{P(y|x)}{P(y)} P(x)$\n",
        "\n",
        "### probabilistic inference and rules\n",
        "\n",
        "goal: compute probability of sentence or sequence of words ⇒ $P(W) = P(w_1, w_2,...,w_n)$\n",
        "\n",
        "- computing the joint probability, chain rule\n",
        "    \n",
        "    $P(w_1w_2...w_n) = \\Pi_{i} P(w_i | w_1 w_2... w_{i - 1})$\n",
        "    \n",
        "    - $P(the)$, $P(underdog | the)$, $P(Philadelphia | \\text{the underdog})$...\n",
        "- estimate these probabilities using MLE (maximum likelihood estimate)\n",
        "    - $P(won | \\text{the underdog team} = \\frac{count(\\text{the underdog team won})}{count(\\text{the underdog team})}$\n",
        "    - but this doesn't work for the whole sentence bc not enough data\n",
        "\n",
        "simplifying assumption = *markov assumption*. probability of moving to next state only depends on current state (or previous $k$ words, k is # of context words that we take into account).\n",
        "\n",
        "- $P(w_1w_2...w_n) = \\Pi_{i}^{n} P(w_i | w_{i-k}... w_{i - 1})$\n",
        "- $k$ is amt of history we should use. if $k = 0$, unigram. $k = 1$ ⇒ bigram. $k = 2$ ⇒ trigram\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 109,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0a620ac1-9c78-4d75-8dd7-d7e6c6a1a861"
      },
      "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": 110,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n$$P(a|b) = \frac{P(a \\cap b)}{P(b)}$$\n\n- **joint probability distribution** - $P(a, b)$ = probabilities of all combinations of values of $a$ and $b$\n    \n    $$P(a, b) = P(a | b)P(b)$$\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- extract distribution over subset of variables / single variable\n- **marginalization / summing out** - sum up probabilities for each value of other variables\n    \n    $$P(Y) = \\sum_{z} P(Y, Z = z)$$\n    \n- for a domain with $n$ boolean variables, input table has size $O(2^n)$\n\n\n## AIMA Chapter 12.4 Independence\n\nindependent if:\n\n$$P(a|b) = P(a) \text{ or } P(b|a) = P(b) \text{ or } P(a \\cap b) = P(a)P(b)$$\n\n- reduces amt of info necessary to split full joint distribution. complete set of variables can be divided into independent subsets.\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n$$P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}$$\n\ni.e. P(cause | effect) = P(effect | cause)P(cause) / P(effect)\n\n**conditional independence:** $P(X, Y|Z) = P(X|Z)P(Y|Z)$\n\n- size of representation is $O(n)$ instead of $O(2^n)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n$P(cause, effect_1, ..., effect_n) = P(cause) \\Pi_{i} P(effect_i | cause)$\n\n- simplifying assumption for when \"effect\" variables aren't independent from the cause\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\n\n- $P(w | h)$: probability of $w$ given some history $h$\n    - relative frequency counts: large corpus, count # of times we've seen $h$ and $w$ afterwards. not enough past info due to huge # of combinations.\n- **chain rule of probability:**\n    \n    $$P(X_1,...,X_n) = P(X_1)P(X_2|X_1)...P(X_N|X_{1:n-1}) = \\Pi_{k=1}^n P(X_k|X_{1:k-1})$$\n    \n    - for a join distribution with $N$ random variables, there are $N!$ ways to apply the chain rule.\n- **n-gram model -** approximate history using just the last few words\n    - bigram = only preceding word. $P(w_n | w_{1:n-1}) \u0007pprox P(w_n | w_{n-1})$\n        - **markov assumption** - predict probability of future unit without looking too far into the past ⇒ makes it possible to estimate probabilities from data.\n- MLE estimate\n    \n    $$P(w_n|w_n-1) = \frac{C(w_{n-1}w_n)}{\\sum_w C(w_{n-1}w)}$$\n    \n    - ratio = **relative frequency** = observed freq of sequence / observed freq of prefix\n- log probabilities so numbers aren't as smol\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- **extrinsic evaluation** - embed language model into an app and measure app's improvement\n- **intrinsic evaluation** - measures quality of a model independent of actual application. need a **test set** with unseen data from the **training set**\n    - model with higher probability to test set is better\n- **perplexity** - inverse probability of the test set, normalized by # of words\n    \n    $$PP(W) = P(w_1w_2...w_N)^{-1/N} = (\\Pi_{i=1}^{N}(w_i|w_1...w_{i-1}))^{-1/N}$$\n    \n    - higher conditional probability ⇒ lower perplexity\n    - lower perplexity is better\n    - (also) weighted avg branching factor (# of possible next words which can follow current word)\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n- generate sentences across a distribution from a language model.\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n- dependent on training corpus. incr $N$ results in better performance.\n- training corpus will miss some n-gram sequences. cannot divide by 0 and can't compute perplexity.\n- **out of vocabulary (OOV), unknown words?**\n\n\n## SLP Chapter 3.5 Smoothing\n\n**Laplace smoothing:** add 1 to all n-gram counts\n\n**add-k smoothing**\n\n$$P_{add-k}(w_n | w_{n - 1}) = \frac{C(w_{n-1}w_n) + k}{C(w_{n-1}) + kV}$$\n\n- add a fractional count $k$ instead of 1. need to choose $k$ by optimizing on a devset.\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n\n## Module 10 Lecture Notes\n\n### probability review\n\n- **observed variables (evidence):** agent knows certain things about state of world\n- **unobserved variables (state):** agent needs to reason about other aspects\n- **model:** agent knows something about how the known variables relate to unknown variables\n\n*possible worlds* - quantifies how likely a possible world is.\n\n### distributions\n\n- distribution = table of value probabilities\n\n**joint distributions**: over a set of random variables. specifies a real number for each assignment.\n\n- $P(X_1 = x_1, X_2 = x_2,...,X_n = x_n)$\n- size of distribution if $n$ variables have domain sizes of $d$? $d^n$\n\n**probabilistic model**: joint distribution over a set of RVs\n\n**event**: set of possible outcomes\n\n**marginal distribution**: sub-tables which eliminate variables\n\n**conditional probabilities**: $P(a|b) = \frac{P(a, b)}{P(b)} = \frac{P(a \\cap b)}{P(b)}$\n\n### probabilitic inference & rules\n\n- probabilistic inference: compute a desired probability from other known probabilities\n    - changes with new evidence\n\n**inference by enumeration**\n\n- evidence variables, query variables, hidden variables (unobserved) ⇒ all variables\n- we want: $P(Q | e_1,...,e_k)$\n    1. select entries consistent with evidence\n    2. sum out $H$ to get joint of query and evidence (marginalization)\n        \n        $P(Q, e_1,...,e_k) = \\sum_{h_1...h_r} P(Q, h_1 ... h_r, e_1 ... e_k)$\n        \n    3. totals may not add to 1 → normalize by dividing by $Z$\n\n**product rule**: $P(y)P(x|y) = P(x, y)$\n\n**chain rule:** can always write joint distribution as incremental product of conditional distributions\n\n- $P(x_1, x_2,...,x_n) = \\Pi_{i} P(x_i | x_1...x_{i - 1})$\n\n**bayes' rule:**\n\n- $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n    - $P(x|y) = \frac{P(y|x)}{P(y)} P(x)$\n\n### probabilistic inference and rules\n\ngoal: compute probability of sentence or sequence of words ⇒ $P(W) = P(w_1, w_2,...,w_n)$\n\n- computing the joint probability, chain rule\n    \n    $P(w_1w_2...w_n) = \\Pi_{i} P(w_i | w_1 w_2... w_{i - 1})$\n    \n    - $P(the)$, $P(underdog | the)$, $P(Philadelphia | \text{the underdog})$...\n- estimate these probabilities using MLE (maximum likelihood estimate)\n    - $P(won | \text{the underdog team} = \frac{count(\text{the underdog team won})}{count(\text{the underdog team})}$\n    - but this doesn't work for the whole sentence bc not enough data\n\nsimplifying assumption = *markov assumption*. probability of moving to next state only depends on current state (or previous $k$ words, k is # of context words that we take into account).\n\n- $P(w_1w_2...w_n) = \\Pi_{i}^{n} P(w_i | w_{i-k}... w_{i - 1})$\n- $k$ is amt of history we should use. if $k = 0$, unigram. $k = 1$ ⇒ bigram. $k = 2$ ⇒ trigram\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"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "- **Bayesian network** - represent dependencies among variables. represent *any* full joint probability distribution concisely. directed graph:\n",
        "    - each node is a random variable (discrete or continuous)\n",
        "    - directed links / arrows connect pairs of nodes. it's a DAG.\n",
        "    - each node $X_i$ has associated pobability information\n",
        "- topology specifies conditional independence relationships\n",
        "- each node holds a *conditional probability table* (p. 783)\n",
        "    - The conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of all of the other variables (nodes) ⇒ FALSE\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "$$P(x_1,...,x_n) = \\Pi_{i=1}^n P(x_i | parents(X_i))$$\n",
        "\n",
        "- **locally structured, sparse** systems - each subcomponent interacts directly with a bounded number of other components. linear growth rather than exponential growth.\n",
        "- each variable is conditionally independent of its non-descendants, given its parents\n",
        "- a variable is conditionally independent of all other nodes in the network, given its parents, children, and children's parents (markov blanket)\n",
        "    - if 2 nodes X and Y don't share a path, they are conditionally independent\n",
        "- more than 1 bayesian network can represent the same joint distribution\n",
        "\n",
        "**d-separation**\n",
        "\n",
        "- ancestral subgraph: X, Y, Z, and ancestors\n",
        "- add links between any unlinked pair of nodes that share a common child (**moral graph**)\n",
        "- replace directed links with undirected links\n",
        "- if Z blocks all paths between X ad Y, then Z d-separates X and Y (X is conditionally independent of Y, given Z)\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "- query can be answered using a bayes net by computing sums of products of conditional probabilities from the network\n",
        "- $O(2^n)$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "### independence\n",
        "\n",
        "- X and Y are independent if:\n",
        "    - $\\forall x, y P(x, y) = P(x)P(y)$\n",
        "- X and Y are conditionally independent given Z\n",
        "    - $\\forall x, y, z P(x, y | z) = P(x | z) P(y | z)$\n",
        "    - alarm is conditionally independent of fire given smoke\n",
        "- conditional independence - most basic and robust form of knowledge about uncertain environments. unconditional (absolute) independence is very rare.\n",
        "- X is conditionally independent of Y given Z iff:\n",
        "    - $\\forall x, y, z: P(x, y | z) = P(x | z) P(y | z)$\n",
        "    - OR $\\forall x, y, z: P(x|z, y) = P(x|z)$\n",
        "\n",
        "### bayes net properties\n",
        "\n",
        "assumptions: terms in the chain rule are only dependent on parent.\n",
        "\n",
        "**D-separation** (dependents, algorithm to determine if things are independent of each other)\n",
        "\n",
        "- *causal chain* - low pressure system ⇒ rain ⇒ traffic\n",
        "    - $P(x, y, z) = P(x) P(y | x) P(z | y)$\n",
        "    - is x guaranteed to be independent of z? no. to show x is not independent of z: need to show low pressure causes rain which causes traffic; high pressure causes no rain which causes no traffice\n",
        "    - is x guarantted to be independent of z given y?\n",
        "        - $P(z | x, y) = \\frac{P(x, y, z)}{P(x, y)}$\n",
        "- *common cause* - project is due so forms are busy and OH are full\n",
        "    - $P(x, y, z) = P(y)P(x | y)P(z | y)$\n",
        "- *common effect* - two things have a common effect — raining and ballgame result in traffic\n",
        "\n",
        "### reachability path\n",
        "\n",
        "given an entire bayes' net, are two variables independent?\n",
        "\n",
        "- attempt 1: shade evidence nodes, look for paths in resulting graph. if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent\n",
        "    - false ⇒ breaks with common effect\n",
        "\n",
        "**active path** if each triple is active. causal chain (a → b → c) where b is unobserved. common cause a ← b → c where b is unobserved. common effect a → b ← c where b or one of its descendants is observed.\n",
        "\n",
        "### d-separation algorithm\n",
        "\n",
        "- if all paths are inactive, then independence is guaranteed.\n",
        "- \"given T\" shades T\n",
        "- if middle node is not observed, then active (not shaded → not shaded → shaded is active)\n",
        "- a path is active if each triple is active (one inactive triple makes it inactive)\n",
        "\n",
        "![Screen Shot 2021-12-02 at 9.27.39 PM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/146b59eb-dce0-4abd-b0e2-201e7fafa6a5/Screen_Shot_2021-12-02_at_9.27.39_PM.png)\n",
        "\n",
        "### inference\n",
        "\n",
        "- inference: calculate some useful quantity from a joint probability distribution\n",
        "- posterior probability - what's the probability of PA given MI and NY...\n",
        "\n",
        "inference by enumeration\n",
        "\n",
        "- exponential table. can be slow.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 111,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "789e247d-d09e-4869-fd2c-911f8c88d7c0"
      },
      "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": 112,
      "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\n- **Bayesian network** - represent dependencies among variables. represent *any* full joint probability distribution concisely. directed graph:\n    - each node is a random variable (discrete or continuous)\n    - directed links / arrows connect pairs of nodes. it's a DAG.\n    - each node $X_i$ has associated pobability information\n- topology specifies conditional independence relationships\n- each node holds a *conditional probability table* (p. 783)\n    - The conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of all of the other variables (nodes) ⇒ FALSE\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n$$P(x_1,...,x_n) = \\Pi_{i=1}^n P(x_i | parents(X_i))$$\n\n- **locally structured, sparse** systems - each subcomponent interacts directly with a bounded number of other components. linear growth rather than exponential growth.\n- each variable is conditionally independent of its non-descendants, given its parents\n- a variable is conditionally independent of all other nodes in the network, given its parents, children, and children's parents (markov blanket)\n    - if 2 nodes X and Y don't share a path, they are conditionally independent\n- more than 1 bayesian network can represent the same joint distribution\n\n**d-separation**\n\n- ancestral subgraph: X, Y, Z, and ancestors\n- add links between any unlinked pair of nodes that share a common child (**moral graph**)\n- replace directed links with undirected links\n- if Z blocks all paths between X ad Y, then Z d-separates X and Y (X is conditionally independent of Y, given Z)\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- query can be answered using a bayes net by computing sums of products of conditional probabilities from the network\n- $O(2^n)$\n\n\n## Module 11 Lecture Notes\n\n### independence\n\n- X and Y are independent if:\n    - $\forall x, y P(x, y) = P(x)P(y)$\n- X and Y are conditionally independent given Z\n    - $\forall x, y, z P(x, y | z) = P(x | z) P(y | z)$\n    - alarm is conditionally independent of fire given smoke\n- conditional independence - most basic and robust form of knowledge about uncertain environments. unconditional (absolute) independence is very rare.\n- X is conditionally independent of Y given Z iff:\n    - $\forall x, y, z: P(x, y | z) = P(x | z) P(y | z)$\n    - OR $\forall x, y, z: P(x|z, y) = P(x|z)$\n\n### bayes net properties\n\nassumptions: terms in the chain rule are only dependent on parent.\n\n**D-separation** (dependents, algorithm to determine if things are independent of each other)\n\n- *causal chain* - low pressure system ⇒ rain ⇒ traffic\n    - $P(x, y, z) = P(x) P(y | x) P(z | y)$\n    - is x guaranteed to be independent of z? no. to show x is not independent of z: need to show low pressure causes rain which causes traffic; high pressure causes no rain which causes no traffice\n    - is x guarantted to be independent of z given y?\n        - $P(z | x, y) = \frac{P(x, y, z)}{P(x, y)}$\n- *common cause* - project is due so forms are busy and OH are full\n    - $P(x, y, z) = P(y)P(x | y)P(z | y)$\n- *common effect* - two things have a common effect — raining and ballgame result in traffic\n\n### reachability path\n\ngiven an entire bayes' net, are two variables independent?\n\n- attempt 1: shade evidence nodes, look for paths in resulting graph. if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent\n    - false ⇒ breaks with common effect\n\n**active path** if each triple is active. causal chain (a → b → c) where b is unobserved. common cause a ← b → c where b is unobserved. common effect a → b ← c where b or one of its descendants is observed.\n\n### d-separation algorithm\n\n- if all paths are inactive, then independence is guaranteed.\n- \"given T\" shades T\n- if middle node is not observed, then active (not shaded → not shaded → shaded is active)\n- a path is active if each triple is active (one inactive triple makes it inactive)\n\n![Screen Shot 2021-12-02 at 9.27.39 PM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/146b59eb-dce0-4abd-b0e2-201e7fafa6a5/Screen_Shot_2021-12-02_at_9.27.39_PM.png)\n\n### inference\n\n- inference: calculate some useful quantity from a joint probability distribution\n- posterior probability - what's the probability of PA given MI and NY...\n\ninference by enumeration\n\n- exponential table. can be slow.\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 = \"\"\"\n",
        "**naive bayes** = probabilistic classifier. class is sampled, $P(c)$ and then words are generated by sampling from $P(d|c)$, where $d$ is the document\n",
        "\n",
        "$$\\hat{c} = argmax_{c \\in C} P(d|c) P(c)$$\n",
        "\n",
        "simplifying assumptions:\n",
        "\n",
        "1. bag of words: assume position doesn't matter\n",
        "2. **naive bayes assumption:** conditional independent assumption that probabilities are independent\n",
        "    \n",
        "    $P(f_1, f_2,...,f_n | c) = P(f_1 | c) P(f_2 | c) ... P(f_n | c)$\n",
        "    \n",
        "\n",
        "$$c_{NB} = argmax_{c \\in C}log(P(c)) + \\sum_{i \\in positions}log(P(w_i | c))$$\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\"\n",
        "$$\\hat{P}(w_i | c) = \\frac{count(w_i, c) + 1}{\\sum_{w \\in V}count(w, c) + |V|}$$\n",
        "\n",
        "- parametric models have a fixed size on number of parameters.\n",
        "\"\"\"\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 = \"\"\"\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "### classficiation tasks\n",
        "\n",
        "model-based classification with naive bayes and perceptrons\n",
        "\n",
        "**spam classification**\n",
        "\n",
        "- input: email (feature vector)\n",
        "    - words, text patterns, non-text (sender in contacts?)\n",
        "- output: spam / ham\n",
        "\n",
        "**digit recognition**\n",
        "\n",
        "- input: images / pixel grids\n",
        "- output: digit 0-9\n",
        "\n",
        "### naive bayes\n",
        "\n",
        "assume all features are independent effects of the label\n",
        "\n",
        "- $P(Y, F_1,...,F_n) = P(Y) \\Pi_i P(F_i | Y)$\n",
        "\n",
        "### basic ML concepts\n",
        "\n",
        "**data:**\n",
        "\n",
        "- training set\n",
        "- held out set\n",
        "- test set\n",
        "\n",
        "**features**: attribute-value pairs which characterize each x\n",
        "\n",
        "**experimentation cycle**: learn parameters on training set, tune hyperparameters, compute accuracy on test set.\n",
        "\n",
        "**evaluation:** accuracy\n",
        "\n",
        "**overfitting and generalization**\n",
        "\n",
        "- want to avoid giving unseen events 0 probability. need to *smooth* or *regularize* estimates.\n",
        "\n",
        "**parameter estimation**: to estimate the distribution of a random variable.\n",
        "\n",
        "- $L(x, \\theta) = \\Pi_i P_{\\theta}(x_i)$\n",
        "- use the estimate which maximizes the likelihood of the data\n",
        "\n",
        "**laplace smoothing**: pretend you saw every outcome once more than you actually did\n",
        "\n",
        "- $P_{LAP}(x) = \\frac{c(x) + 1}{\\sum_x[c(x) + 1]} = \\frac{c(x) + 1}{N + |X|}$\n",
        "\n",
        "tune hyperparameters on held-out data.\n",
        "\n",
        "### perceptron\n",
        "\n",
        "- inputs ⇒ weights ⇒ weighted sum ⇒ activation function ⇒ output\n",
        "- weighted inputs: dot product of weight and input vector\n",
        "- bias = -1 * threshold. measure of how \"easy\" it is to get perceptron to output 1.\n",
        "    - if a binary perceptron has a high bias value, it's easier for the perceptron to output a 1.\n",
        "\n",
        "**learning: binary perceptron**\n",
        "\n",
        "- start with weights = 0\n",
        "- for each training instance:\n",
        "    - classify with current weights: if dot product of w and f(x) ≥ threshold, then output 1 otherwise -1\n",
        "    - if correct, no change!\n",
        "    - if wrong, adjust weight vector by adding or subtracting feature vector. subtract if $y^*$ is -1.\n",
        "- linear functions: when using perceptron learning rule, weights are updated when actual output doesn't match hypothesis output.\n",
        "- may exist multiple boundaries that separate classes\n",
        "\n",
        "### improvements to perceptrons, and SVM\n",
        "\n",
        "- **separability**: true if some parameters get the training set perfectly correct.\n",
        "- **convergence:** if training is separable, perceptron will eventually converge.\n",
        "    - also decay the learning rate as training time increases to converge.\n",
        "- **mistake bound:** max number of mistakes (binary case) related to the degree of separability. $mistakes < \\frac{k}{\\delta ^ 2}$\n",
        "\n",
        "problems with perceptron\n",
        "\n",
        "- noise: if data isn't separable, weights thrash (change drastically). averaging weight vectors over time helps.\n",
        "- mediocre generalization: finds a \"barely\" separating solution. hyperplane may not be the best separator.\n",
        "- overtraining\n",
        "\n",
        "fixing the perceptron\n",
        "\n",
        "- MIRA = margin infused relaxed alg\n",
        "    - subtract $\\tau f(x)$ instead of just $f(x)$\n",
        "\n",
        "max step size\n",
        "\n",
        "- bad to make updates that are too large ⇒ cap max possible values of $\\tau$ with some constant C\n",
        "\n",
        "non-linear separators\n",
        "\n",
        "- can map data into a higher dimension to separate it...\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 113,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ba00fa38-eaee-4d63-f4de-e1c76b9e8d5f"
      },
      "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": 114,
      "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\n**naive bayes** = probabilistic classifier. class is sampled, $P(c)$ and then words are generated by sampling from $P(d|c)$, where $d$ is the document\n\n$$\\hat{c} = argmax_{c \\in C} P(d|c) P(c)$$\n\nsimplifying assumptions:\n\n1. bag of words: assume position doesn't matter\n2. **naive bayes assumption:** conditional independent assumption that probabilities are independent\n    \n    $P(f_1, f_2,...,f_n | c) = P(f_1 | c) P(f_2 | c) ... P(f_n | c)$\n    \n\n$$c_{NB} = argmax_{c \\in C}log(P(c)) + \\sum_{i \\in positions}log(P(w_i | c))$$\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n$$\\hat{P}(w_i | c) = \frac{count(w_i, c) + 1}{\\sum_{w \\in V}count(w, c) + |V|}$$\n\n- parametric models have a fixed size on number of parameters.\n\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\n\n## Module 12 Lecture Notes\n\n### classficiation tasks\n\nmodel-based classification with naive bayes and perceptrons\n\n**spam classification**\n\n- input: email (feature vector)\n    - words, text patterns, non-text (sender in contacts?)\n- output: spam / ham\n\n**digit recognition**\n\n- input: images / pixel grids\n- output: digit 0-9\n\n### naive bayes\n\nassume all features are independent effects of the label\n\n- $P(Y, F_1,...,F_n) = P(Y) \\Pi_i P(F_i | Y)$\n\n### basic ML concepts\n\n**data:**\n\n- training set\n- held out set\n- test set\n\n**features**: attribute-value pairs which characterize each x\n\n**experimentation cycle**: learn parameters on training set, tune hyperparameters, compute accuracy on test set.\n\n**evaluation:** accuracy\n\n**overfitting and generalization**\n\n- want to avoid giving unseen events 0 probability. need to *smooth* or *regularize* estimates.\n\n**parameter estimation**: to estimate the distribution of a random variable.\n\n- $L(x, \theta) = \\Pi_i P_{\theta}(x_i)$\n- use the estimate which maximizes the likelihood of the data\n\n**laplace smoothing**: pretend you saw every outcome once more than you actually did\n\n- $P_{LAP}(x) = \frac{c(x) + 1}{\\sum_x[c(x) + 1]} = \frac{c(x) + 1}{N + |X|}$\n\ntune hyperparameters on held-out data.\n\n### perceptron\n\n- inputs ⇒ weights ⇒ weighted sum ⇒ activation function ⇒ output\n- weighted inputs: dot product of weight and input vector\n- bias = -1 * threshold. measure of how \"easy\" it is to get perceptron to output 1.\n    - if a binary perceptron has a high bias value, it's easier for the perceptron to output a 1.\n\n**learning: binary perceptron**\n\n- start with weights = 0\n- for each training instance:\n    - classify with current weights: if dot product of w and f(x) ≥ threshold, then output 1 otherwise -1\n    - if correct, no change!\n    - if wrong, adjust weight vector by adding or subtracting feature vector. subtract if $y^*$ is -1.\n- linear functions: when using perceptron learning rule, weights are updated when actual output doesn't match hypothesis output.\n- may exist multiple boundaries that separate classes\n\n### improvements to perceptrons, and SVM\n\n- **separability**: true if some parameters get the training set perfectly correct.\n- **convergence:** if training is separable, perceptron will eventually converge.\n    - also decay the learning rate as training time increases to converge.\n- **mistake bound:** max number of mistakes (binary case) related to the degree of separability. $mistakes < \frac{k}{\\delta ^ 2}$\n\nproblems with perceptron\n\n- noise: if data isn't separable, weights thrash (change drastically). averaging weight vectors over time helps.\n- mediocre generalization: finds a \"barely\" separating solution. hyperplane may not be the best separator.\n- overtraining\n\nfixing the perceptron\n\n- MIRA = margin infused relaxed alg\n    - subtract $\tau f(x)$ instead of just $f(x)$\n\nmax step size\n\n- bad to make updates that are too large ⇒ cap max possible values of $\tau$ with some constant C\n\nnon-linear separators\n\n- can map data into a higher dimension to separate it...\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 = \"\"\"\n",
        "loss function to calculate how close the classifier output is to the correct output\n",
        "\n",
        "$$L_{CE}(\\hat{y}, y) = -[ylog\\sigma(w\\cdot x + b) + (1 - y)log(1 - \\sigma(w\\cdot x + b))]$$\n",
        "\n",
        "- minimize the negative log probability — goes from 0 (no loss) to infinity (infinite loss)\n",
        "\"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "- find optimal weights and minimize loss function\n",
        "\n",
        "$$\\hat{\\theta} = argmin_{\\theta}\\frac{1}{m}\\sum_{i=1}^m L_{CE}(f(x^i; \\theta), y^i)$$\n",
        "\n",
        "- gradient descent - method to find minimum of a function by determining direction that slope rises most steeply.\n",
        "    - logistic regression - loss function is *convex*. has only one minimum.\n",
        "- amount to move in gradient descent is value of slope, weighted by **learning rate** $\\eta$. higher learning rate = move more on each step.\n",
        "\"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "- **overfitting**: learns too specific to training model.\n",
        "- **L2 regularization**: quadratic function of weight values, ridge\n",
        "- L1 (lasso) regularization\n",
        "\"\"\"\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 = \"\"\"\n",
        "- input = set of real-valued numbers\n",
        "- neural unit = weighted sum of inputs. adds a **bias term** to the sum.\n",
        "    \n",
        "    $z = w \\cdot x + b$\n",
        "    \n",
        "    $y = \\sigma(z) = \\frac{1}{1 + e^{-z}}$\n",
        "    \n",
        "- **tanh** function is a variant of sigmoid and ranges from -1 to 1\n",
        "- **ReLU**: rectified linear unit activation function. same as $z$ when $z$ is positive and 0 otherwise. $y = max(z, 0)$\n",
        "  - result for negative numbers is same as linear function\n",
        "\"\"\"\n",
        "slp_chapter7_2 = \"\"\"\n",
        "- binary perceptron: outputs 0 if $w \\cdot x + b \\leq 0$ and outputs 1 if $w \\cdot x + b > 0$\n",
        "  - not a weighted average of perceptron inputs\n",
        "  - high bias = easier to output a 1\n",
        "  - if all weights are >= 0, will NOT always fire\n",
        "- **decision boundary**: output 0 assigned to all inputs on one side and output 1 if on the other side of the line.\n",
        "- XOR is not a **linearly separable** function\n",
        "    - 00, **01**, **10,** 11 (cannot linearly separate 01 and 10 from the rest)\n",
        "- (false): linear functions can only be used for classification, all sets of data points are linearly separable, learning rule must be applied to one example at a time.\n",
        "- true: When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output.\n",
        "- can be multiple decision boundaries to separate classes\n",
        "- converges to a min-error solution when learning rate decreases as training time increases\n",
        "**neural networks**: layed network of units. makes it possible to linearly separate.\n",
        "\"\"\"\n",
        "slp_chapter7_3 = \"\"\"\n",
        "- **feedforward network** - multilayer network where units are connected with no cycles. outputs from units in each layer are passed to units in the next higher layer.\n",
        "- output of hidden layer:\n",
        "    \n",
        "    $$h = \\sigma(Wx + b)$$\n",
        "    \n",
        "- output of output layer (actual output):\n",
        "    \n",
        "    $$softmax(z_i) = \\frac{exp(z_i)}{\\sum_{j=1}^d exp(z_j)}, 1 \\leq i \\leq d$$\n",
        "    \n",
        "    - $z$ can't be the output. bc it's not a class!\n",
        "- hidden layer activation functions are typically different from the output layer\n",
        "- If we used a linear activation function, the resulting network would be equivalent to a single-layer network. (possible but becomes single-layer network basically)\n",
        "- perceptrons don't have non-linear activation functions\n",
        "\"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\"\n",
        "- **error backpropagation (backward differentiation)** - partial out loss over all intermediate layers\n",
        "- enables us to correctly update all layers in neural network\n",
        "\"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "### logistic regression\n",
        "\n",
        "- **feature representation:** for each input observation, create a vector of features\n",
        "    - count of negative words. count of positive lexicon. pronouns. \"no\"? \"!\"?\n",
        "- **classification function** computes estimated class $\\hat{y}$ via $p(y | x)$\n",
        "    - $z = \\sum_i w_ix_i + b = w \\cdot x + b$\n",
        "    - $z$ ranges from -infinity to +infinity ⇒ squish it using **sigmoid function**\n",
        "        - $y = \\frac{1}{1 + e^{-z}}$ bounds output range between 0 and 1\n",
        "        - decision boundary: $\\hat{y} = {1 \\text{ if } P(y = 1 | x) > 0.5, 0 \\text{ otherwise}}$\n",
        "- **objective function** for learning (loss function)\n",
        "- alg for **optimizing** the objective function (minimize loss function)\n",
        "\n",
        "### loss functions\n",
        "\n",
        "- how close is a classifier output to the correct output — $L(\\hat{y}, y)$\n",
        "    - e.g. mean squared error: $L_{mse}(\\hat{y}, y) = \\frac{1}{2} (\\hat{y} - y)^2$\n",
        "- **cross entropy loss** - prefer correct class label of training example to be more likely. minimize the negative probability.\n",
        "\n",
        "for one observation x, **maximize** probability of true label.\n",
        "\n",
        "$p(y | x) = y^y (1 - \\hat{y})^{1-y}$, y = 1 ($\\hat{y}$) or 0 (1 - $\\hat{y}$)\n",
        "\n",
        "- want to maximize probability of correct class, or $\\hat{y}$\n",
        "- change to logs:\n",
        "    \n",
        "    $$L_{CE}(\\hat{y}, y) = log(p (y | x)) = ylog(\\hat{y}) + (1 - y) log(1 - \\hat{y})$$\n",
        "    \n",
        "    - $\\hat{y} = \\sigma(w \\cdot x + b)$\n",
        "\n",
        "loss on all trianing examples:\n",
        "\n",
        "$log(p(\\text{training labels})) = log \\Pi_{i = 1}^m p(y^i | x^i)$\n",
        "\n",
        "### stochastic gradient descent\n",
        "\n",
        "use gradient descent to find good values for weights and bias by minimizing loss function:\n",
        "\n",
        "$\\hat{\\theta} = argmin_{\\theta} \\frac{1}{m} \\sum_{i = 1}^m L_{CE}(y^i, x^i; \\theta)$\n",
        "\n",
        "- loss vs. weight graph — trying to find weight value for which loss is minimizes. convex functions have just *one minimum,* no local minima to get stuck in. find minimum by continuously taking steps (learning rate, $\\eta$) and determining when the slope is 0.\n",
        "\n",
        "$$w^{t + 1} = w^t - \\eta \\frac{d}{dw} f(x; w)$$\n",
        "\n",
        "![Screen Shot 2021-12-04 at 11.16.05 AM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7e6d5195-3511-4da2-baaf-1ef1563cadc2/Screen_Shot_2021-12-04_at_11.16.05_AM.png)\n",
        "\n",
        "![Screen Shot 2021-12-04 at 11.19.35 AM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/98df085b-f1b9-4f7b-8de9-08c6d44659f2/Screen_Shot_2021-12-04_at_11.19.35_AM.png)\n",
        "\n",
        "**minimize avergage loss (uhh probably rewatch this, 13:00)**\n",
        "\n",
        "**mini-batch training**\n",
        "\n",
        "- stochastic gradient descent chooses a single random example and udpates weights. updates can fluctuate.\n",
        "- **batch training** computes gradient over entire dataset. better estimate for direction but longer time to compute. **mini-batch training** trained on a small batch size of 512-1024.\n",
        "\n",
        "**overfitting**\n",
        "\n",
        "**regularization** - penalize large weights, add regularization term to loss function. Lasso regression uses L1 regularization. Ridge regression uses L2 regularization.\n",
        "\n",
        "**multinomial logistic regression**\n",
        "\n",
        "- instead of binary classification - can have multiple class labels\n",
        "- generalization of sigmoid function is **softmax function**\n",
        "\n",
        "$$softmax(z_i) = \\frac{e^{z_j}}{\\sum_{j=1}^k e^{z_j}}, 1 \\leq i \\leq k$$\n",
        "\n",
        "### neural networks\n",
        "\n",
        "- multiple hidden layers — *deep learning*\n",
        "- logistic regression transforms $z$ by the sigmoid.\n",
        "- different activation functions: sigmoid, ReLU, tanh\n",
        "\n",
        "**feed-forward neural network**\n",
        "\n",
        "- multi-layer network. units are fully-connected with no cycles. outputs from each layer are passed to units in the next higher layer, no outputs are passed back to lower layers.\n",
        "\n",
        "to train a neural net and learn the best parameters:\n",
        "\n",
        "- **loss function** - cross-entropy loss\n",
        "- **optimization alg** - gradient descent\n",
        "- **way of computing gradient of loss function** - multiple layers now, error propagation!\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 115,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9a2e0b10-2dc2-47e4-9c8b-26791820ff56"
      },
      "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": 116,
      "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\nloss function to calculate how close the classifier output is to the correct output\n\n$$L_{CE}(\\hat{y}, y) = -[ylog\\sigma(w\\cdot x + b) + (1 - y)log(1 - \\sigma(w\\cdot x + b))]$$\n\n- minimize the negative log probability — goes from 0 (no loss) to infinity (infinite loss)\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n- find optimal weights and minimize loss function\n\n$$\\hat{\theta} = argmin_{\theta}\frac{1}{m}\\sum_{i=1}^m L_{CE}(f(x^i; \theta), y^i)$$\n\n- gradient descent - method to find minimum of a function by determining direction that slope rises most steeply.\n    - logistic regression - loss function is *convex*. has only one minimum.\n- amount to move in gradient descent is value of slope, weighted by **learning rate** $\\eta$. higher learning rate = move more on each step.\n\n\n## SLP Chapter 5.5 Regularization\n\n- **overfitting**: learns too specific to training model.\n- **L2 regularization**: quadratic function of weight values, ridge\n- L1 (lasso) regularization\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n\n- input = set of real-valued numbers\n- neural unit = weighted sum of inputs. adds a **bias term** to the sum.\n    \n    $z = w \\cdot x + b$\n    \n    $y = \\sigma(z) = \frac{1}{1 + e^{-z}}$\n    \n- **tanh** function is a variant of sigmoid and ranges from -1 to 1\n- **ReLU**: rectified linear unit activation function. same as $z$ when $z$ is positive and 0 otherwise. $y = max(z, 0)$\n  - result for negative numbers is same as linear function\n\n\n## SLP Chapter 7.2 The XOR problem\n\n- binary perceptron: outputs 0 if $w \\cdot x + b \\leq 0$ and outputs 1 if $w \\cdot x + b > 0$\n  - not a weighted average of perceptron inputs\n  - high bias = easier to output a 1\n  - if all weights are >= 0, will NOT always fire\n- **decision boundary**: output 0 assigned to all inputs on one side and output 1 if on the other side of the line.\n- XOR is not a **linearly separable** function\n    - 00, **01**, **10,** 11 (cannot linearly separate 01 and 10 from the rest)\n- (false): linear functions can only be used for classification, all sets of data points are linearly separable, learning rule must be applied to one example at a time.\n- true: When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output.\n- can be multiple decision boundaries to separate classes\n- converges to a min-error solution when learning rate decreases as training time increases\n**neural networks**: layed network of units. makes it possible to linearly separate.\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n- **feedforward network** - multilayer network where units are connected with no cycles. outputs from units in each layer are passed to units in the next higher layer.\n- output of hidden layer:\n    \n    $$h = \\sigma(Wx + b)$$\n    \n- output of output layer (actual output):\n    \n    $$softmax(z_i) = \frac{exp(z_i)}{\\sum_{j=1}^d exp(z_j)}, 1 \\leq i \\leq d$$\n    \n    - $z$ can't be the output. bc it's not a class!\n- hidden layer activation functions are typically different from the output layer\n- If we used a linear activation function, the resulting network would be equivalent to a single-layer network. (possible but becomes single-layer network basically)\n- perceptrons don't have non-linear activation functions\n\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\n- **error backpropagation (backward differentiation)** - partial out loss over all intermediate layers\n- enables us to correctly update all layers in neural network\n\n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n### logistic regression\n\n- **feature representation:** for each input observation, create a vector of features\n    - count of negative words. count of positive lexicon. pronouns. \"no\"? \"!\"?\n- **classification function** computes estimated class $\\hat{y}$ via $p(y | x)$\n    - $z = \\sum_i w_ix_i + b = w \\cdot x + b$\n    - $z$ ranges from -infinity to +infinity ⇒ squish it using **sigmoid function**\n        - $y = \frac{1}{1 + e^{-z}}$ bounds output range between 0 and 1\n        - decision boundary: $\\hat{y} = {1 \text{ if } P(y = 1 | x) > 0.5, 0 \text{ otherwise}}$\n- **objective function** for learning (loss function)\n- alg for **optimizing** the objective function (minimize loss function)\n\n### loss functions\n\n- how close is a classifier output to the correct output — $L(\\hat{y}, y)$\n    - e.g. mean squared error: $L_{mse}(\\hat{y}, y) = \frac{1}{2} (\\hat{y} - y)^2$\n- **cross entropy loss** - prefer correct class label of training example to be more likely. minimize the negative probability.\n\nfor one observation x, **maximize** probability of true label.\n\n$p(y | x) = y^y (1 - \\hat{y})^{1-y}$, y = 1 ($\\hat{y}$) or 0 (1 - $\\hat{y}$)\n\n- want to maximize probability of correct class, or $\\hat{y}$\n- change to logs:\n    \n    $$L_{CE}(\\hat{y}, y) = log(p (y | x)) = ylog(\\hat{y}) + (1 - y) log(1 - \\hat{y})$$\n    \n    - $\\hat{y} = \\sigma(w \\cdot x + b)$\n\nloss on all trianing examples:\n\n$log(p(\text{training labels})) = log \\Pi_{i = 1}^m p(y^i | x^i)$\n\n### stochastic gradient descent\n\nuse gradient descent to find good values for weights and bias by minimizing loss function:\n\n$\\hat{\theta} = argmin_{\theta} \frac{1}{m} \\sum_{i = 1}^m L_{CE}(y^i, x^i; \theta)$\n\n- loss vs. weight graph — trying to find weight value for which loss is minimizes. convex functions have just *one minimum,* no local minima to get stuck in. find minimum by continuously taking steps (learning rate, $\\eta$) and determining when the slope is 0.\n\n$$w^{t + 1} = w^t - \\eta \frac{d}{dw} f(x; w)$$\n\n![Screen Shot 2021-12-04 at 11.16.05 AM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7e6d5195-3511-4da2-baaf-1ef1563cadc2/Screen_Shot_2021-12-04_at_11.16.05_AM.png)\n\n![Screen Shot 2021-12-04 at 11.19.35 AM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/98df085b-f1b9-4f7b-8de9-08c6d44659f2/Screen_Shot_2021-12-04_at_11.19.35_AM.png)\n\n**minimize avergage loss (uhh probably rewatch this, 13:00)**\n\n**mini-batch training**\n\n- stochastic gradient descent chooses a single random example and udpates weights. updates can fluctuate.\n- **batch training** computes gradient over entire dataset. better estimate for direction but longer time to compute. **mini-batch training** trained on a small batch size of 512-1024.\n\n**overfitting**\n\n**regularization** - penalize large weights, add regularization term to loss function. Lasso regression uses L1 regularization. Ridge regression uses L2 regularization.\n\n**multinomial logistic regression**\n\n- instead of binary classification - can have multiple class labels\n- generalization of sigmoid function is **softmax function**\n\n$$softmax(z_i) = \frac{e^{z_j}}{\\sum_{j=1}^k e^{z_j}}, 1 \\leq i \\leq k$$\n\n### neural networks\n\n- multiple hidden layers — *deep learning*\n- logistic regression transforms $z$ by the sigmoid.\n- different activation functions: sigmoid, ReLU, tanh\n\n**feed-forward neural network**\n\n- multi-layer network. units are fully-connected with no cycles. outputs from each layer are passed to units in the next higher layer, no outputs are passed back to lower layers.\n\nto train a neural net and learn the best parameters:\n\n- **loss function** - cross-entropy loss\n- **optimization alg** - gradient descent\n- **way of computing gradient of loss function** - multiple layers now, error propagation!\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 = \"\"\"\n",
        "- how to represent the meaning of a word?\n",
        "- **synonymy**: identical or nearly identical meaning words. substitutable for one another in any sentence (**propositional meaning**)\n",
        "- **word similarity**\n",
        "- **word relatedness**\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\"\n",
        "- represent a word as a point in multi-dimensional space\n",
        "\"\"\"\n",
        "slp_chapter6_3 = \"\"\"\n",
        "**term-document matrix**: rows represent words, columns represent a document\n",
        "\n",
        "- if two documents have similar words, column vectors would be similar.\n",
        "- cells represent how often a word occurs in a document\n",
        "\"\"\"\n",
        "slp_chapter6_4 = \"\"\"\n",
        "- dot product of two vectors\n",
        "\"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\"\n",
        "- $tf_{t, d} = count(t, d)$\n",
        "    - term frequency: frequency of word $t$ in document $d$\n",
        "- document frequency: number of documents a term occurs in\n",
        "    - inverse document frequency, idf = $N / df_t$, N is the total number of documents\n",
        "\n",
        "**word2vec skip-gram model**\n",
        "\n",
        "- how likely is word $w$ to show up near $apricot$?\n",
        "- \"the quick brown fox jumps over the lazy dog?\" positive training instances with window of +/- 2\n",
        "    - (lazy, the); (fox, over); (jumps, fox); NOT (the, fox)\n",
        "\"\"\"\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",
        "### neural language models\n",
        "\n",
        "neural language models have several advantages:\n",
        "\n",
        "1. don't need smoothing\n",
        "2. can handle much longer histories\n",
        "3. generalize over contexts of similar words\n",
        "4. neural LMs have higher predictive accuracy than n-gram LMs\n",
        "\n",
        "disadv ⇒ slower to train\n",
        "\n",
        "- associate each word in vocab with vector-representation. create a notion of similarity between words.\n",
        "- express joint probability function of word sequence in terms of word vectors for words in that sequence.\n",
        "- simultaneously learn word vectors and parameters of the function.\n",
        "\n",
        "probability function is the product of conditional probabilities of next word given previous word *using a multi-layer, feed-forward neural network.*\n",
        "\n",
        "**input**: k-gram of words $w_{1:k}$\n",
        "\n",
        "**output:** probability distribution over the next word\n",
        "\n",
        "### lexical semantic models\n",
        "\n",
        "N-gram LMs represent words as a string of letters. but ideally we want a meaning representation to encode:\n",
        "\n",
        "- synonyms, antonyms, connotations (positive/negative), semantic roles, entailment\n",
        "\n",
        "*word net* - all meanings and parts of speech for a word. manually enumerated.\n",
        "\n",
        "- **hypernym** - more general. **hyponym** - more specific.\n",
        "\n",
        "### vector semantic models\n",
        "\n",
        "- automatically extract language from a corpus. **corpus** = huge collection of text.\n",
        "- each word is represented as a point in vector space. points close to each other represent semantic similarity.\n",
        "- word similarity\n",
        "- **distributional hypothesis** - two words which occur in the same environment have similar meanings.\n",
        "\n",
        "**vector-spaced retrieval**\n",
        "\n",
        "- *document -* represented as a point in space\n",
        "- **term-document matrix:** column vector represents a document. row represents a term. cell represents how often that term occurred in the document. document vectors are quite sparse (most values are 0 since they don't use all the english vocab words)\n",
        "    - document similarity comparing two document vectors. words which occur in similar documents have similar meaning.\n",
        "- **vector L2 normalization** (normalize vectors by length). if x_A = 2 and y_A = 4, normalize so x_A = 2 / (4 + 16), sum for each term's freq squared\n",
        "- **cosine distance:** angle between two vectors. smaller angle = more similar.\n",
        "\n",
        "**term-term matrix**\n",
        "\n",
        "- rows and cols are # of terms. context windows— count how often it occurs to the left and right.\n",
        "- **dependency parsing** - plural descriptors etc.. the *pictures* of the old man *are* beautiful.\n",
        "    - using syntax to define a word's context\n",
        "- instead of raw counts (words like \"the\" or \"or\" occur a lot), transform vectors using TF-IDF or PPMI.\n",
        "    - term-frequency - inverse document frequency: how often a word occurred in a document * inverse document frequency.\n",
        "\n",
        "### word embeddings\n",
        "\n",
        "- co-occurrence matrix can be very very long and quite sparse.\n",
        "- learn vectors are short and dense (almost all elements are non-zero). choose dimensionality (200 - 1000).\n",
        "    - train a classifier\n",
        "        - treat corpus elements as positive examples. randomly sample words in lexicon to get negative samples. use weights as embeddings.\n",
        "- word2vec\n",
        "    - learn embeddings as part of the process of word prediction. train classifier to predict neighboring words. inspired by neural net language models.\n",
        "    - predict each neighboring word in a context window.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 117,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6fd369cb-9f0d-4b3b-e27c-c1b612aa8acc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 118,
      "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\n- how to represent the meaning of a word?\n- **synonymy**: identical or nearly identical meaning words. substitutable for one another in any sentence (**propositional meaning**)\n- **word similarity**\n- **word relatedness**\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n- represent a word as a point in multi-dimensional space\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n**term-document matrix**: rows represent words, columns represent a document\n\n- if two documents have similar words, column vectors would be similar.\n- cells represent how often a word occurs in a document\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n- dot product of two vectors\n\n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n- $tf_{t, d} = count(t, d)$\n    - term frequency: frequency of word $t$ in document $d$\n- document frequency: number of documents a term occurs in\n    - inverse document frequency, idf = $N / df_t$, N is the total number of documents\n\n**word2vec skip-gram model**\n\n- how likely is word $w$ to show up near $apricot$?\n- \"the quick brown fox jumps over the lazy dog?\" positive training instances with window of +/- 2\n    - (lazy, the); (fox, over); (jumps, fox); NOT (the, fox)\n\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 14 Lecture Notes\n\n### neural language models\n\nneural language models have several advantages:\n\n1. don't need smoothing\n2. can handle much longer histories\n3. generalize over contexts of similar words\n4. neural LMs have higher predictive accuracy than n-gram LMs\n\ndisadv ⇒ slower to train\n\n- associate each word in vocab with vector-representation. create a notion of similarity between words.\n- express joint probability function of word sequence in terms of word vectors for words in that sequence.\n- simultaneously learn word vectors and parameters of the function.\n\nprobability function is the product of conditional probabilities of next word given previous word *using a multi-layer, feed-forward neural network.*\n\n**input**: k-gram of words $w_{1:k}$\n\n**output:** probability distribution over the next word\n\n### lexical semantic models\n\nN-gram LMs represent words as a string of letters. but ideally we want a meaning representation to encode:\n\n- synonyms, antonyms, connotations (positive/negative), semantic roles, entailment\n\n*word net* - all meanings and parts of speech for a word. manually enumerated.\n\n- **hypernym** - more general. **hyponym** - more specific.\n\n### vector semantic models\n\n- automatically extract language from a corpus. **corpus** = huge collection of text.\n- each word is represented as a point in vector space. points close to each other represent semantic similarity.\n- word similarity\n- **distributional hypothesis** - two words which occur in the same environment have similar meanings.\n\n**vector-spaced retrieval**\n\n- *document -* represented as a point in space\n- **term-document matrix:** column vector represents a document. row represents a term. cell represents how often that term occurred in the document. document vectors are quite sparse (most values are 0 since they don't use all the english vocab words)\n    - document similarity comparing two document vectors. words which occur in similar documents have similar meaning.\n- **vector L2 normalization** (normalize vectors by length). if x_A = 2 and y_A = 4, normalize so x_A = 2 / (4 + 16), sum for each term's freq squared\n- **cosine distance:** angle between two vectors. smaller angle = more similar.\n\n**term-term matrix**\n\n- rows and cols are # of terms. context windows— count how often it occurs to the left and right.\n- **dependency parsing** - plural descriptors etc.. the *pictures* of the old man *are* beautiful.\n    - using syntax to define a word's context\n- instead of raw counts (words like \"the\" or \"or\" occur a lot), transform vectors using TF-IDF or PPMI.\n    - term-frequency - inverse document frequency: how often a word occurred in a document * inverse document frequency.\n\n### word embeddings\n\n- co-occurrence matrix can be very very long and quite sparse.\n- learn vectors are short and dense (almost all elements are non-zero). choose dimensionality (200 - 1000).\n    - train a classifier\n        - treat corpus elements as positive examples. randomly sample words in lexicon to get negative samples. use weights as embeddings.\n- word2vec\n    - learn embeddings as part of the process of word prediction. train classifier to predict neighboring words. inspired by neural net language models.\n    - predict each neighboring word in a context window.\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": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "185a1f17-ed10-406e-80c8-b45bec55ea43"
      },
      "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": 119,
      "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\n- transition model $P(s' | s, a)$ gives probability that action $a$ in state $s$ reaches state $s'$.\n\n$$P(result(a) = s') = \\sum_{s}P(s)P(s'|s, a)$$\n\n- **utility functions -** single number to desirability of state\n- **expected utility** - average utility value of outcomes, weighted by probability of outcome\n- **maximum expected utility** - choose action to maximize expected utility\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- **lottery** - set of outcomes for each action, each with an associated probability\n- constraints on rational preferences. properties:\n    - orderability, transitivity, continuity, substitutability, monotonocity, decomposability\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- **sequential decision problems** - agent's utility depends on sequence of decisions.\n- begin at start state. choose action at each time. goal state is marked +1 or -1.\n    - actions achieve intended effect with probability 0.8\n    - negative reward for all transitions (except terminal states) incentivizes agent to reach terminal state quickly.\n- **Markov decision process** - set of states; set of actions; transition model; reward function.\n- **policy** ($\\pi(s)$) - solution for what the agent should do in any state. measured by *expected* utility. **optimal policy** yields highest expected utility, $\\pi^*(s)$.\n- **finite horizon** - after a fixed time N, game is over. optimal action may depend on time left. *nonstationary*.\n- **infinite horizon** - same behavior in every state, *stationary*.\n- **discount factor**, $\\gamma$ - number between 0 and 1, preference of an agent for current rewards > future rewards.\n    - $\\gamma = 0$, distant rewards are insignificant.\n    \n    $$U_{h}([s_0, a_0, s_1, a_1, s_2,...]) = R(s_0, a_0, s_1) + \\gamma R(s_1, a_1, s_2) + \\gamma ^ 2 R(s_2,...)$$\n    \n\n$$\\pi^*(s) = argmax_{a \\in A(s)} \\sum_{s'} P(s' | s, a)[R(s, a, s') + \\gamma U(s')]$$\n\n- **action-utility function / Q-function,** $Q(s, a)$ - expected utility of taking a given action in a given state\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n**value iteration**\n\n- one bellman equation per state, $n$ unknowns. applying Bellman update infinitely often reaches a convergence.\n- **contraction** - function of one arg that when applied to 2 different inputs produces 2 output values that are \"closer together\" by some constant factor than the original input\n    - e.g. dividing by 2\n    - has one fixed point. when value is applied to any arg, value gets closer to fixed point.\n    - possible to get optimal policy even when utility function is inaccurate.\n\n⇒ **Bellman update is a contraction by a factor of** $\\gamma$ **on the space of utility vectors**\n\n**policy iteration**\n\n- policy evaluation: given $\\pi_{i}$, calculate $U_i = U^{\\pi_i}$\n- policy improvement\n- simpler than value iteration bc action in each state is fixed by policy.\n- $O(n^3)$, good for small state spaces.\n\n**modified policy iteration**\n\n- perform some number of simplified value iteratoin steps. approximate utilities.\n\n\n## Module 8 Lecture Notes\n\n## module 8: markov decision processes\n\n### intro to MDP\n\n- stochastic environment — *Up* only moves up 80% of the time\n\nstochastic transition model\n\n- $T(s, a, s') = p(s' | s, a)$, only depends on $s$ and not the history of earlier states\n\n**reward function**\n\n- specify a *utility / reward function* for the agent\n- \"rewards\" can be *positive* or *negative* but are bounded by some max value\n- agent can receive a reward at each time step instead of only at goal states\n\n### MDP formulation\n\n- sequential decision problem for a fully observable environment, with a stochastic transition model with additive rewards\n- *non-deterministic* search problems\n\nformal definition:\n\n- set of states\n- set of actions\n- transition function T(s, a, s')\n- reward function R(s, a, s')\n- initial state, s0\n- optionally - ≥1 terminal states\n\n solution == **policy**: best action in current state, function $\\pi(S) = a$\n\n- policy $\\pi$ tells agent what action to take at state S\n- $\\pi^*$ is the optimal policy, depends on reward function\n\ncompute *expected utility* of all possible paths generated by a policy.\n\n**sequences of rewards**\n\n- performance is the sum of the rewards for transitions taken\n\n**utilities of sequences**\n\n- prefer more over less\n- prefer now over later\n\n**discounting**: values of rewards decay exponentially (to maximize sums and prefer rewards now over later)\n\n- each time we descend a level, we multiply in the discount once\n- e.g. $U([1, 2, 3]) = 0.5^0*1 + 0.5^1*2 + 0.5^2*3$\n\nto prevent infinite utilities: finite horizon (terminate after a fixed T steps), discounting\n\n### MDP examples\n\n- $V^*(s)$ = expected utility starting in $s$ and acting optimally\n- $Q^*(s, a)$ = expected utility starting out having taken action a from state s and acting optimally afterwards\n- $\\pi^*(s)$ = optimal action from state $s$\n\nvalues of states\n\n### value iteration algs\n\n- start with $V_0(s) = 0$: no time steps left means an expected reward sum of 0\n- given a vector of $V_k(s)$ values, do one ply of expectimax from each state\n    \n    $V_{k + 1}(s) \\leftarrow max \\sum_{s'} T(s, a, s')[R(s, a, s') + \\gamma V_k(s')]$\n    \n- repeat until convergence. complexity is $O(S^2A)$\n\n### policy evaluation\n\n- given a policy, what values do i get?\n- no need for max operation anymore\n- pick action with highest q-value\n\n### policy iteration alg\n\nvalue iteration repeats the bellman updates. very slow $O(S^2A)$ per iteration. \"max\" per state rarely changes.\n\n1. **policy evaluation**: calculate utilities for some fixed policy until convergence\n    \n    for fixed current policy $\\pi$, find values with policy iteration\n    \n    - iterate until values converge\n2. **policy improvement**: update policy using one-step look-ahead with resulting converged utilities as future values.\n- repeat steps until policy converges\n\n**policy iteration**: optimal! can converge faster under some conditions.\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- **n-armed bandit** - *n* levers, each lever has a fixed but unknown probability distribution of winning\n- exploitation vs. exploration\n    - arms are independent\n- **Gittins index**\n    \n    $$\\gamma = max_{T>0}\frac{E(\\sum_{t=1}^{T-1} \\gamma^t R_t}{E(\\sum_{t=0}^{T-1} \\gamma^t)}$$\n    \n    - O(n) time to calculate optimal decision, $n$ = # of arms\n- at tipping point, optimal policy is indifferent between $M$ and $M_{\\lambda}$\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- **reinforcement learning** - agent interacts with world and receives **rewards**.\n    - same goal as MDP: maximize expected sum of rewards\n    - *not given* the MDP as a problem to solve but agent is *in* the MDP — doesn't know transition model or reward function\n    - learning the rules as it plays...\n\n**model-based reinforcement learning:** agent uses transition model to make decisions. if unknown, learned from observing effects.\n\n**model-free reinforcement learning**: no transition model\n\n- **action-utility learning**: Q-learning, in a given state, agent chooses action with highest Q-value\n- **policy search**: agent learns policy.\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n- fixed policy, goal is to learn states' utilities ⇒ *exploration*\n- unknown transition model $P(s' | s, a)$\n    - agent tries some stuff until it reaches terminal states. records the states and rewards received.\n- **direct utility estimation** - utility of state is expected total reward from that state onward\n- temporal-difference learning - can also use observed transitions to adjust observed state utilities\n    \n    $$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \u0007lpha[R(s, \\pi(s), s')] + \\gamma U^{\\pi}(s') - U^{\\pi}(s)$$\n    \n    - $\u0007lpha$ is learning rate parameter\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- decides what actions to take (passive learning agent has a fixed policy)\n- uses passive learning mechanism to learn transition model\n    - one-step look-ahead to maximize expected utility. chooses that optimal action.\n- **greedy agent** - greedily takes action it believes is optimal. but sometimes choosing the optimal action every time is suboptimal. exploitation (take greatest known reward) vs. exploration (gain info to change policy).\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n\n## Module 9 Lecture Notes\n\n- MDP: know probability distribution. reinforcement learning: need to learn distribution.\n\n**double-bandit MDP**: blue and red slot machines. probability of each reward value given.\n\n- reinforcement learning — process of taking actions & observing results to update expectations\n\n**exploration**: try unknown actions to get info\n\n**exploitation:** eventually, use what you know\n\n**regret:** mistakes, suboptimal attempts\n\n**sampling:** stochastic environment so have to try things repeatedly\n\n**difficulty:** learning is harder than solving a known MDP\n\n**basic idea** - receive feedback in form of rewards. agent's utility is defined by reward function. must (learn to) act to maximize expected rewards.\n\n- assumes a markov decision process (MDP):\n    - set of states $s \\in S$\n    - set of actions (per state) $A$\n    - model $T(s, a, s')$\n    - reward function $R(s, a, s')$\n    - looking for a policy $\\pi(s)$\n- don't know $T$ or $R$. must try actions and states to learn.\n- MDPs are offline. compute things ahead of time without doing. RL is online.\n\n**model-based learning**\n\n- approximate model based on experiences. solve for values if learned model were correct.\n1. learn empirical MDP model: count outcomes $s'$ for each $s, a$ to determine probabilities\n    - normalize to estimate $\\hat{T}(s, a, s')$\n    - discover each $\\hat{R}(s, a, s')$\n2. solve learned MDP (i.e. value iteration)\n\n### passion reinforcement learning\n\n**model-free learning**: take action, compare results between expectation and reality. adjust values appropriately.\n\npassive reinforcement learning - given fixed policy, how good is policy?\n\n- input: fixed policy $\\pi(s)$. unknown transition, rewards.\n- goal: learn state values. avg together observed sample values. *direct evaluation*.\n\npositives: easy to understand. doesn't requre knowledge of T or R. eventually computes correct avg values.\n\nnegatives: wastes info about state connections. each state is learned separate, takes a long time to learn.\n\n**sample-based policy evaluation**:\n\n- improve estimate by computing average\n    \n    $V_{k+1}^{\\pi}(s) \\leftarrow \\sum_{s'}T(s, \\pi(s), s')[R(s, \\pi(s), s') + \\gamma V_k^{\\pi}(s')$\n    \n- take samples of outcomes s' and avg. won't work under reinforcement policy since we cannot guarantee an initial state of $s$.\n\n### temporal difference learning\n\n- update V(s) each time we experience a transition.\n- move values toward value of successor, running average\n\n$sample = R(s, \\pi(s), s') + \\gamma V^{\\pi}(s')$\n\n$update = V^{\\pi}(s) \\leftarrow (1 - \u0007lpha)V^{\\pi}(s) + (\u0007lpha)sample = V^{\\pi}(s) + \u0007lpha(sample - V^{\\pi}(s))$\n\n- $\u0007lpha$ is learning rate, controls how much we update new estimate from current estimate\n    - if $\u0007lpha = 0$, new sample has no weight. if $\u0007lpha = 1$ then entire state is dictated by current state.\n\n**exponential moving average:** more recent samples are more important\n\n**decreasing learning rate (alpha) can give converging avgs**\n\nproblems with TD value learning\n\n- need to learn Q-values, not values (?)\n\n### active reinforcement learning (Q-learning)\n\n**full reinforcement learning**: optimal policies (like value iteration) without knowing transitions and rewards\n\n**Q-value iteration**\n\n- value iteration: find successive (depth-limited) values\n    - start with $V_0(s) = 0$\n    - given $V_k$, calculate depth $k+1$ values for all states\n- Q-values are more useful so compute them instead (q-value iteration)\n    - $Q_0(s, a) = 0$\n    - given $Q_k$, calculate depth $k + 1$ q-values for all q-states\n\n**Q-learning**: sample-based Q-value iteration\n\n$Q_{k+1}(s, a) \\leftarrow \\sum_{s'} T(s, a, s') R(s, a, s') + \\gamma max_{a'} Q_k (s', a')$\n\n- learn $Q(s, a)$ values as we go\n- incorporate new estimate into running avg\n    \n    $Q(s, a) \\leftarrow (1 - \u0007lpha) Q(s, a) + (\u0007lpha)(sample)$\n    \n    - $\u0007lpha = 1$ → ignore previous estimates. $\u0007lpha = 0$ → all weight is on previous estimates\n\n**Q-learning converges to optimal policy!** (even if you're acting suboptimally) ⇒ *off-policy learning*\n\n- caveats: need to explore enough. eventually make learning rate small enough. tweak learning rate so it decreases over time (trust previous history more).\n\n### exploration vs. exploitation\n\n**epsilon-greedy policy:** randomly generate a number. if number is smaller than $\\epsilon$, act randomly. otherwise, act on current policy.\n\n- problems: eventually will explore space but we'll repeatedly choose things we've already explored. soln - lower $\\epsilon$ over time. or encode exploration functions.\n- **exploration functions**: explore areas whose \"badness\" is not yet established, eventually stop exploring.\n    - $f(u, n) = u + k / n$.\n        - $u$ : current utility estimate\n        - $n$ : # times we've visited that state\n        - $k$ : bonus if we haven't expored that state many times\n\nQ-learning is randomly visiting new states. epsilon-greedy pushes us towards exploring states we haven't visited.\n\n**regret:** measure of total mistake cost (difference bw expected rewards (including youthful suboptimality) and optimal (expected) rewards)\n\n- minimizing regret requires optimally learning to be optimal\n- quantifies relative goodness of exploration procedures\n\n### approx. Q-learning\n\nbasic Q-learning keeps a table of all q-values, but sometimes this table is too large to hold in memory.\n\n**evaluation functions**: score non-terminals in depth-limited search. weight linear sum of features (e.g. # white queens).\n\n- $eval(s) = w_1 f_1(s) + w_2 f_2(s) + ... + w_n f_n(s)$\n- **linear value functions**: features representing a state multiplied by weight\n    - adv - experience is summed up in a few powerful numbers\n    - disadv - states may share features but be very different in value\n\n$Q(s, a) = w_1 f_1(s, a) + ... + w_n f_n (s, a)$\n\n- $difference = (r + \\gamma max_{\u0007lpha'} Q(s', a')) - Q(s, a)$\n- $Q(s, a) \\leftarrow Q(s, a) + \u0007lpha (difference)$\n    - $w_i \\leftarrow w_i + \u0007lpha(difference) f_i (s, a)$\n    - (??) review this\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\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n$$P(a|b) = \frac{P(a \\cap b)}{P(b)}$$\n\n- **joint probability distribution** - $P(a, b)$ = probabilities of all combinations of values of $a$ and $b$\n    \n    $$P(a, b) = P(a | b)P(b)$$\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- extract distribution over subset of variables / single variable\n- **marginalization / summing out** - sum up probabilities for each value of other variables\n    \n    $$P(Y) = \\sum_{z} P(Y, Z = z)$$\n    \n- for a domain with $n$ boolean variables, input table has size $O(2^n)$\n\n\n## AIMA Chapter 12.4 Independence\n\nindependent if:\n\n$$P(a|b) = P(a) \text{ or } P(b|a) = P(b) \text{ or } P(a \\cap b) = P(a)P(b)$$\n\n- reduces amt of info necessary to split full joint distribution. complete set of variables can be divided into independent subsets.\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n$$P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}$$\n\ni.e. P(cause | effect) = P(effect | cause)P(cause) / P(effect)\n\n**conditional independence:** $P(X, Y|Z) = P(X|Z)P(Y|Z)$\n\n- size of representation is $O(n)$ instead of $O(2^n)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n$P(cause, effect_1, ..., effect_n) = P(cause) \\Pi_{i} P(effect_i | cause)$\n\n- simplifying assumption for when \"effect\" variables aren't independent from the cause\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\n\n- $P(w | h)$: probability of $w$ given some history $h$\n    - relative frequency counts: large corpus, count # of times we've seen $h$ and $w$ afterwards. not enough past info due to huge # of combinations.\n- **chain rule of probability:**\n    \n    $$P(X_1,...,X_n) = P(X_1)P(X_2|X_1)...P(X_N|X_{1:n-1}) = \\Pi_{k=1}^n P(X_k|X_{1:k-1})$$\n    \n    - for a join distribution with $N$ random variables, there are $N!$ ways to apply the chain rule.\n- **n-gram model -** approximate history using just the last few words\n    - bigram = only preceding word. $P(w_n | w_{1:n-1}) \u0007pprox P(w_n | w_{n-1})$\n        - **markov assumption** - predict probability of future unit without looking too far into the past ⇒ makes it possible to estimate probabilities from data.\n- MLE estimate\n    \n    $$P(w_n|w_n-1) = \frac{C(w_{n-1}w_n)}{\\sum_w C(w_{n-1}w)}$$\n    \n    - ratio = **relative frequency** = observed freq of sequence / observed freq of prefix\n- log probabilities so numbers aren't as smol\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- **extrinsic evaluation** - embed language model into an app and measure app's improvement\n- **intrinsic evaluation** - measures quality of a model independent of actual application. need a **test set** with unseen data from the **training set**\n    - model with higher probability to test set is better\n- **perplexity** - inverse probability of the test set, normalized by # of words\n    \n    $$PP(W) = P(w_1w_2...w_N)^{-1/N} = (\\Pi_{i=1}^{N}(w_i|w_1...w_{i-1}))^{-1/N}$$\n    \n    - higher conditional probability ⇒ lower perplexity\n    - lower perplexity is better\n    - (also) weighted avg branching factor (# of possible next words which can follow current word)\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n- generate sentences across a distribution from a language model.\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n- dependent on training corpus. incr $N$ results in better performance.\n- training corpus will miss some n-gram sequences. cannot divide by 0 and can't compute perplexity.\n- **out of vocabulary (OOV), unknown words?**\n\n\n## SLP Chapter 3.5 Smoothing\n\n**Laplace smoothing:** add 1 to all n-gram counts\n\n**add-k smoothing**\n\n$$P_{add-k}(w_n | w_{n - 1}) = \frac{C(w_{n-1}w_n) + k}{C(w_{n-1}) + kV}$$\n\n- add a fractional count $k$ instead of 1. need to choose $k$ by optimizing on a devset.\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n\n## Module 10 Lecture Notes\n\n### probability review\n\n- **observed variables (evidence):** agent knows certain things about state of world\n- **unobserved variables (state):** agent needs to reason about other aspects\n- **model:** agent knows something about how the known variables relate to unknown variables\n\n*possible worlds* - quantifies how likely a possible world is.\n\n### distributions\n\n- distribution = table of value probabilities\n\n**joint distributions**: over a set of random variables. specifies a real number for each assignment.\n\n- $P(X_1 = x_1, X_2 = x_2,...,X_n = x_n)$\n- size of distribution if $n$ variables have domain sizes of $d$? $d^n$\n\n**probabilistic model**: joint distribution over a set of RVs\n\n**event**: set of possible outcomes\n\n**marginal distribution**: sub-tables which eliminate variables\n\n**conditional probabilities**: $P(a|b) = \frac{P(a, b)}{P(b)} = \frac{P(a \\cap b)}{P(b)}$\n\n### probabilitic inference & rules\n\n- probabilistic inference: compute a desired probability from other known probabilities\n    - changes with new evidence\n\n**inference by enumeration**\n\n- evidence variables, query variables, hidden variables (unobserved) ⇒ all variables\n- we want: $P(Q | e_1,...,e_k)$\n    1. select entries consistent with evidence\n    2. sum out $H$ to get joint of query and evidence (marginalization)\n        \n        $P(Q, e_1,...,e_k) = \\sum_{h_1...h_r} P(Q, h_1 ... h_r, e_1 ... e_k)$\n        \n    3. totals may not add to 1 → normalize by dividing by $Z$\n\n**product rule**: $P(y)P(x|y) = P(x, y)$\n\n**chain rule:** can always write joint distribution as incremental product of conditional distributions\n\n- $P(x_1, x_2,...,x_n) = \\Pi_{i} P(x_i | x_1...x_{i - 1})$\n\n**bayes' rule:**\n\n- $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n    - $P(x|y) = \frac{P(y|x)}{P(y)} P(x)$\n\n### probabilistic inference and rules\n\ngoal: compute probability of sentence or sequence of words ⇒ $P(W) = P(w_1, w_2,...,w_n)$\n\n- computing the joint probability, chain rule\n    \n    $P(w_1w_2...w_n) = \\Pi_{i} P(w_i | w_1 w_2... w_{i - 1})$\n    \n    - $P(the)$, $P(underdog | the)$, $P(Philadelphia | \text{the underdog})$...\n- estimate these probabilities using MLE (maximum likelihood estimate)\n    - $P(won | \text{the underdog team} = \frac{count(\text{the underdog team won})}{count(\text{the underdog team})}$\n    - but this doesn't work for the whole sentence bc not enough data\n\nsimplifying assumption = *markov assumption*. probability of moving to next state only depends on current state (or previous $k$ words, k is # of context words that we take into account).\n\n- $P(w_1w_2...w_n) = \\Pi_{i}^{n} P(w_i | w_{i-k}... w_{i - 1})$\n- $k$ is amt of history we should use. if $k = 0$, unigram. $k = 1$ ⇒ bigram. $k = 2$ ⇒ trigram\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\n- **Bayesian network** - represent dependencies among variables. represent *any* full joint probability distribution concisely. directed graph:\n    - each node is a random variable (discrete or continuous)\n    - directed links / arrows connect pairs of nodes. it's a DAG.\n    - each node $X_i$ has associated pobability information\n- topology specifies conditional independence relationships\n- each node holds a *conditional probability table* (p. 783)\n    - The conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of all of the other variables (nodes) ⇒ FALSE\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n$$P(x_1,...,x_n) = \\Pi_{i=1}^n P(x_i | parents(X_i))$$\n\n- **locally structured, sparse** systems - each subcomponent interacts directly with a bounded number of other components. linear growth rather than exponential growth.\n- each variable is conditionally independent of its non-descendants, given its parents\n- a variable is conditionally independent of all other nodes in the network, given its parents, children, and children's parents (markov blanket)\n    - if 2 nodes X and Y don't share a path, they are conditionally independent\n- more than 1 bayesian network can represent the same joint distribution\n\n**d-separation**\n\n- ancestral subgraph: X, Y, Z, and ancestors\n- add links between any unlinked pair of nodes that share a common child (**moral graph**)\n- replace directed links with undirected links\n- if Z blocks all paths between X ad Y, then Z d-separates X and Y (X is conditionally independent of Y, given Z)\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- query can be answered using a bayes net by computing sums of products of conditional probabilities from the network\n- $O(2^n)$\n\n\n## Module 11 Lecture Notes\n\n### independence\n\n- X and Y are independent if:\n    - $\forall x, y P(x, y) = P(x)P(y)$\n- X and Y are conditionally independent given Z\n    - $\forall x, y, z P(x, y | z) = P(x | z) P(y | z)$\n    - alarm is conditionally independent of fire given smoke\n- conditional independence - most basic and robust form of knowledge about uncertain environments. unconditional (absolute) independence is very rare.\n- X is conditionally independent of Y given Z iff:\n    - $\forall x, y, z: P(x, y | z) = P(x | z) P(y | z)$\n    - OR $\forall x, y, z: P(x|z, y) = P(x|z)$\n\n### bayes net properties\n\nassumptions: terms in the chain rule are only dependent on parent.\n\n**D-separation** (dependents, algorithm to determine if things are independent of each other)\n\n- *causal chain* - low pressure system ⇒ rain ⇒ traffic\n    - $P(x, y, z) = P(x) P(y | x) P(z | y)$\n    - is x guaranteed to be independent of z? no. to show x is not independent of z: need to show low pressure causes rain which causes traffic; high pressure causes no rain which causes no traffice\n    - is x guarantted to be independent of z given y?\n        - $P(z | x, y) = \frac{P(x, y, z)}{P(x, y)}$\n- *common cause* - project is due so forms are busy and OH are full\n    - $P(x, y, z) = P(y)P(x | y)P(z | y)$\n- *common effect* - two things have a common effect — raining and ballgame result in traffic\n\n### reachability path\n\ngiven an entire bayes' net, are two variables independent?\n\n- attempt 1: shade evidence nodes, look for paths in resulting graph. if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent\n    - false ⇒ breaks with common effect\n\n**active path** if each triple is active. causal chain (a → b → c) where b is unobserved. common cause a ← b → c where b is unobserved. common effect a → b ← c where b or one of its descendants is observed.\n\n### d-separation algorithm\n\n- if all paths are inactive, then independence is guaranteed.\n- \"given T\" shades T\n- if middle node is not observed, then active (not shaded → not shaded → shaded is active)\n- a path is active if each triple is active (one inactive triple makes it inactive)\n\n![Screen Shot 2021-12-02 at 9.27.39 PM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/146b59eb-dce0-4abd-b0e2-201e7fafa6a5/Screen_Shot_2021-12-02_at_9.27.39_PM.png)\n\n### inference\n\n- inference: calculate some useful quantity from a joint probability distribution\n- posterior probability - what's the probability of PA given MI and NY...\n\ninference by enumeration\n\n- exponential table. can be slow.\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\n**naive bayes** = probabilistic classifier. class is sampled, $P(c)$ and then words are generated by sampling from $P(d|c)$, where $d$ is the document\n\n$$\\hat{c} = argmax_{c \\in C} P(d|c) P(c)$$\n\nsimplifying assumptions:\n\n1. bag of words: assume position doesn't matter\n2. **naive bayes assumption:** conditional independent assumption that probabilities are independent\n    \n    $P(f_1, f_2,...,f_n | c) = P(f_1 | c) P(f_2 | c) ... P(f_n | c)$\n    \n\n$$c_{NB} = argmax_{c \\in C}log(P(c)) + \\sum_{i \\in positions}log(P(w_i | c))$$\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n$$\\hat{P}(w_i | c) = \frac{count(w_i, c) + 1}{\\sum_{w \\in V}count(w, c) + |V|}$$\n\n- parametric models have a fixed size on number of parameters.\n\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\n\n## Module 12 Lecture Notes\n\n### classficiation tasks\n\nmodel-based classification with naive bayes and perceptrons\n\n**spam classification**\n\n- input: email (feature vector)\n    - words, text patterns, non-text (sender in contacts?)\n- output: spam / ham\n\n**digit recognition**\n\n- input: images / pixel grids\n- output: digit 0-9\n\n### naive bayes\n\nassume all features are independent effects of the label\n\n- $P(Y, F_1,...,F_n) = P(Y) \\Pi_i P(F_i | Y)$\n\n### basic ML concepts\n\n**data:**\n\n- training set\n- held out set\n- test set\n\n**features**: attribute-value pairs which characterize each x\n\n**experimentation cycle**: learn parameters on training set, tune hyperparameters, compute accuracy on test set.\n\n**evaluation:** accuracy\n\n**overfitting and generalization**\n\n- want to avoid giving unseen events 0 probability. need to *smooth* or *regularize* estimates.\n\n**parameter estimation**: to estimate the distribution of a random variable.\n\n- $L(x, \theta) = \\Pi_i P_{\theta}(x_i)$\n- use the estimate which maximizes the likelihood of the data\n\n**laplace smoothing**: pretend you saw every outcome once more than you actually did\n\n- $P_{LAP}(x) = \frac{c(x) + 1}{\\sum_x[c(x) + 1]} = \frac{c(x) + 1}{N + |X|}$\n\ntune hyperparameters on held-out data.\n\n### perceptron\n\n- inputs ⇒ weights ⇒ weighted sum ⇒ activation function ⇒ output\n- weighted inputs: dot product of weight and input vector\n- bias = -1 * threshold. measure of how \"easy\" it is to get perceptron to output 1.\n    - if a binary perceptron has a high bias value, it's easier for the perceptron to output a 1.\n\n**learning: binary perceptron**\n\n- start with weights = 0\n- for each training instance:\n    - classify with current weights: if dot product of w and f(x) ≥ threshold, then output 1 otherwise -1\n    - if correct, no change!\n    - if wrong, adjust weight vector by adding or subtracting feature vector. subtract if $y^*$ is -1.\n- linear functions: when using perceptron learning rule, weights are updated when actual output doesn't match hypothesis output.\n- may exist multiple boundaries that separate classes\n\n### improvements to perceptrons, and SVM\n\n- **separability**: true if some parameters get the training set perfectly correct.\n- **convergence:** if training is separable, perceptron will eventually converge.\n    - also decay the learning rate as training time increases to converge.\n- **mistake bound:** max number of mistakes (binary case) related to the degree of separability. $mistakes < \frac{k}{\\delta ^ 2}$\n\nproblems with perceptron\n\n- noise: if data isn't separable, weights thrash (change drastically). averaging weight vectors over time helps.\n- mediocre generalization: finds a \"barely\" separating solution. hyperplane may not be the best separator.\n- overtraining\n\nfixing the perceptron\n\n- MIRA = margin infused relaxed alg\n    - subtract $\tau f(x)$ instead of just $f(x)$\n\nmax step size\n\n- bad to make updates that are too large ⇒ cap max possible values of $\tau$ with some constant C\n\nnon-linear separators\n\n- can map data into a higher dimension to separate it...\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\nloss function to calculate how close the classifier output is to the correct output\n\n$$L_{CE}(\\hat{y}, y) = -[ylog\\sigma(w\\cdot x + b) + (1 - y)log(1 - \\sigma(w\\cdot x + b))]$$\n\n- minimize the negative log probability — goes from 0 (no loss) to infinity (infinite loss)\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n- find optimal weights and minimize loss function\n\n$$\\hat{\theta} = argmin_{\theta}\frac{1}{m}\\sum_{i=1}^m L_{CE}(f(x^i; \theta), y^i)$$\n\n- gradient descent - method to find minimum of a function by determining direction that slope rises most steeply.\n    - logistic regression - loss function is *convex*. has only one minimum.\n- amount to move in gradient descent is value of slope, weighted by **learning rate** $\\eta$. higher learning rate = move more on each step.\n\n\n## SLP Chapter 5.5 Regularization\n\n- **overfitting**: learns too specific to training model.\n- **L2 regularization**: quadratic function of weight values, ridge\n- L1 (lasso) regularization\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n\n- input = set of real-valued numbers\n- neural unit = weighted sum of inputs. adds a **bias term** to the sum.\n    \n    $z = w \\cdot x + b$\n    \n    $y = \\sigma(z) = \frac{1}{1 + e^{-z}}$\n    \n- **tanh** function is a variant of sigmoid and ranges from -1 to 1\n- **ReLU**: rectified linear unit activation function. same as $z$ when $z$ is positive and 0 otherwise. $y = max(z, 0)$\n  - result for negative numbers is same as linear function\n\n\n## SLP Chapter 7.2 The XOR problem\n\n- binary perceptron: outputs 0 if $w \\cdot x + b \\leq 0$ and outputs 1 if $w \\cdot x + b > 0$\n  - not a weighted average of perceptron inputs\n  - high bias = easier to output a 1\n  - if all weights are >= 0, will NOT always fire\n- **decision boundary**: output 0 assigned to all inputs on one side and output 1 if on the other side of the line.\n- XOR is not a **linearly separable** function\n    - 00, **01**, **10,** 11 (cannot linearly separate 01 and 10 from the rest)\n- (false): linear functions can only be used for classification, all sets of data points are linearly separable, learning rule must be applied to one example at a time.\n- true: When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output.\n- can be multiple decision boundaries to separate classes\n- converges to a min-error solution when learning rate decreases as training time increases\n**neural networks**: layed network of units. makes it possible to linearly separate.\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n- **feedforward network** - multilayer network where units are connected with no cycles. outputs from units in each layer are passed to units in the next higher layer.\n- output of hidden layer:\n    \n    $$h = \\sigma(Wx + b)$$\n    \n- output of output layer (actual output):\n    \n    $$softmax(z_i) = \frac{exp(z_i)}{\\sum_{j=1}^d exp(z_j)}, 1 \\leq i \\leq d$$\n    \n    - $z$ can't be the output. bc it's not a class!\n- hidden layer activation functions are typically different from the output layer\n- If we used a linear activation function, the resulting network would be equivalent to a single-layer network. (possible but becomes single-layer network basically)\n- perceptrons don't have non-linear activation functions\n\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\n- **error backpropagation (backward differentiation)** - partial out loss over all intermediate layers\n- enables us to correctly update all layers in neural network\n\n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n### logistic regression\n\n- **feature representation:** for each input observation, create a vector of features\n    - count of negative words. count of positive lexicon. pronouns. \"no\"? \"!\"?\n- **classification function** computes estimated class $\\hat{y}$ via $p(y | x)$\n    - $z = \\sum_i w_ix_i + b = w \\cdot x + b$\n    - $z$ ranges from -infinity to +infinity ⇒ squish it using **sigmoid function**\n        - $y = \frac{1}{1 + e^{-z}}$ bounds output range between 0 and 1\n        - decision boundary: $\\hat{y} = {1 \text{ if } P(y = 1 | x) > 0.5, 0 \text{ otherwise}}$\n- **objective function** for learning (loss function)\n- alg for **optimizing** the objective function (minimize loss function)\n\n### loss functions\n\n- how close is a classifier output to the correct output — $L(\\hat{y}, y)$\n    - e.g. mean squared error: $L_{mse}(\\hat{y}, y) = \frac{1}{2} (\\hat{y} - y)^2$\n- **cross entropy loss** - prefer correct class label of training example to be more likely. minimize the negative probability.\n\nfor one observation x, **maximize** probability of true label.\n\n$p(y | x) = y^y (1 - \\hat{y})^{1-y}$, y = 1 ($\\hat{y}$) or 0 (1 - $\\hat{y}$)\n\n- want to maximize probability of correct class, or $\\hat{y}$\n- change to logs:\n    \n    $$L_{CE}(\\hat{y}, y) = log(p (y | x)) = ylog(\\hat{y}) + (1 - y) log(1 - \\hat{y})$$\n    \n    - $\\hat{y} = \\sigma(w \\cdot x + b)$\n\nloss on all trianing examples:\n\n$log(p(\text{training labels})) = log \\Pi_{i = 1}^m p(y^i | x^i)$\n\n### stochastic gradient descent\n\nuse gradient descent to find good values for weights and bias by minimizing loss function:\n\n$\\hat{\theta} = argmin_{\theta} \frac{1}{m} \\sum_{i = 1}^m L_{CE}(y^i, x^i; \theta)$\n\n- loss vs. weight graph — trying to find weight value for which loss is minimizes. convex functions have just *one minimum,* no local minima to get stuck in. find minimum by continuously taking steps (learning rate, $\\eta$) and determining when the slope is 0.\n\n$$w^{t + 1} = w^t - \\eta \frac{d}{dw} f(x; w)$$\n\n![Screen Shot 2021-12-04 at 11.16.05 AM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7e6d5195-3511-4da2-baaf-1ef1563cadc2/Screen_Shot_2021-12-04_at_11.16.05_AM.png)\n\n![Screen Shot 2021-12-04 at 11.19.35 AM.png](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/98df085b-f1b9-4f7b-8de9-08c6d44659f2/Screen_Shot_2021-12-04_at_11.19.35_AM.png)\n\n**minimize avergage loss (uhh probably rewatch this, 13:00)**\n\n**mini-batch training**\n\n- stochastic gradient descent chooses a single random example and udpates weights. updates can fluctuate.\n- **batch training** computes gradient over entire dataset. better estimate for direction but longer time to compute. **mini-batch training** trained on a small batch size of 512-1024.\n\n**overfitting**\n\n**regularization** - penalize large weights, add regularization term to loss function. Lasso regression uses L1 regularization. Ridge regression uses L2 regularization.\n\n**multinomial logistic regression**\n\n- instead of binary classification - can have multiple class labels\n- generalization of sigmoid function is **softmax function**\n\n$$softmax(z_i) = \frac{e^{z_j}}{\\sum_{j=1}^k e^{z_j}}, 1 \\leq i \\leq k$$\n\n### neural networks\n\n- multiple hidden layers — *deep learning*\n- logistic regression transforms $z$ by the sigmoid.\n- different activation functions: sigmoid, ReLU, tanh\n\n**feed-forward neural network**\n\n- multi-layer network. units are fully-connected with no cycles. outputs from each layer are passed to units in the next higher layer, no outputs are passed back to lower layers.\n\nto train a neural net and learn the best parameters:\n\n- **loss function** - cross-entropy loss\n- **optimization alg** - gradient descent\n- **way of computing gradient of loss function** - multiple layers now, error propagation!\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\n- how to represent the meaning of a word?\n- **synonymy**: identical or nearly identical meaning words. substitutable for one another in any sentence (**propositional meaning**)\n- **word similarity**\n- **word relatedness**\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n- represent a word as a point in multi-dimensional space\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n**term-document matrix**: rows represent words, columns represent a document\n\n- if two documents have similar words, column vectors would be similar.\n- cells represent how often a word occurs in a document\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n- dot product of two vectors\n\n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n- $tf_{t, d} = count(t, d)$\n    - term frequency: frequency of word $t$ in document $d$\n- document frequency: number of documents a term occurs in\n    - inverse document frequency, idf = $N / df_t$, N is the total number of documents\n\n**word2vec skip-gram model**\n\n- how likely is word $w$ to show up near $apricot$?\n- \"the quick brown fox jumps over the lazy dog?\" positive training instances with window of +/- 2\n    - (lazy, the); (fox, over); (jumps, fox); NOT (the, fox)\n\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 14 Lecture Notes\n\n### neural language models\n\nneural language models have several advantages:\n\n1. don't need smoothing\n2. can handle much longer histories\n3. generalize over contexts of similar words\n4. neural LMs have higher predictive accuracy than n-gram LMs\n\ndisadv ⇒ slower to train\n\n- associate each word in vocab with vector-representation. create a notion of similarity between words.\n- express joint probability function of word sequence in terms of word vectors for words in that sequence.\n- simultaneously learn word vectors and parameters of the function.\n\nprobability function is the product of conditional probabilities of next word given previous word *using a multi-layer, feed-forward neural network.*\n\n**input**: k-gram of words $w_{1:k}$\n\n**output:** probability distribution over the next word\n\n### lexical semantic models\n\nN-gram LMs represent words as a string of letters. but ideally we want a meaning representation to encode:\n\n- synonyms, antonyms, connotations (positive/negative), semantic roles, entailment\n\n*word net* - all meanings and parts of speech for a word. manually enumerated.\n\n- **hypernym** - more general. **hyponym** - more specific.\n\n### vector semantic models\n\n- automatically extract language from a corpus. **corpus** = huge collection of text.\n- each word is represented as a point in vector space. points close to each other represent semantic similarity.\n- word similarity\n- **distributional hypothesis** - two words which occur in the same environment have similar meanings.\n\n**vector-spaced retrieval**\n\n- *document -* represented as a point in space\n- **term-document matrix:** column vector represents a document. row represents a term. cell represents how often that term occurred in the document. document vectors are quite sparse (most values are 0 since they don't use all the english vocab words)\n    - document similarity comparing two document vectors. words which occur in similar documents have similar meaning.\n- **vector L2 normalization** (normalize vectors by length). if x_A = 2 and y_A = 4, normalize so x_A = 2 / (4 + 16), sum for each term's freq squared\n- **cosine distance:** angle between two vectors. smaller angle = more similar.\n\n**term-term matrix**\n\n- rows and cols are # of terms. context windows— count how often it occurs to the left and right.\n- **dependency parsing** - plural descriptors etc.. the *pictures* of the old man *are* beautiful.\n    - using syntax to define a word's context\n- instead of raw counts (words like \"the\" or \"or\" occur a lot), transform vectors using TF-IDF or PPMI.\n    - term-frequency - inverse document frequency: how often a word occurred in a document * inverse document frequency.\n\n### word embeddings\n\n- co-occurrence matrix can be very very long and quite sparse.\n- learn vectors are short and dense (almost all elements are non-zero). choose dimensionality (200 - 1000).\n    - train a classifier\n        - treat corpus elements as positive examples. randomly sample words in lexicon to get negative samples. use weights as embeddings.\n- word2vec\n    - learn embeddings as part of the process of word prediction. train classifier to predict neighboring words. inspired by neural net language models.\n    - predict each neighboring word in a context window.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}