{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "IK Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b2c47117-d273-43ee-88ef-a84ab4624f63"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4cacf84b-4f8c-42e8-eaeb-59cada16a279"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "**Markovian**: Prob of reach state depends only on previous state, not all earlier\n",
        "But decision problem is seq, so utlity will depndend on seq of states/actions\n",
        "\n",
        "MDP consistes of sets of: states, actions; transitino model, and reward func.\n",
        "\n",
        "Policy says what agent should do in any state. Measure polic by expected util. Optimal\n",
        "yields the highest expected util. Can be multiple optimal policies. \n",
        "\n",
        "**Nonstationary**: if time affects the policy (ex. exit early for N=3 steps).\n",
        "**Stationary**: if pol based only on current state. \n",
        "\n",
        "Discount, closer to 0 prefer rewards now over later. 1, ok to wait - additive. \n",
        "Ex $(1/\\gamma) - 1 $ is discount factor in monetary rewards\n",
        "\n",
        "\n",
        "Util for infinte sequnce is finite $\\\\frac{R_{max}}{1 - \\gamma}$\n",
        "\n",
        "**Proper policy** - guranteed to reach a terminal state. \n",
        "\n",
        "Discount util + infinte horizon means optimal pol is indepdnet of first state. \n",
        "\n",
        "$\\pi (s) = \\\\text{argmax}_{\\\\alpha \\\\in A(s) \\Sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s)]} $\n",
        "\n",
        "Choose action that max reward for the next step exp discounted utility of resulting state,\n",
        "assuming agent in s' chooses optimal action\n",
        "\n",
        "**Action-utility function/Q-function** - Expected utility of an action in given state. \n",
        "\n",
        "\n",
        "$P(S'|s,a)$ and $R(s,a,s')$ represented by 3d table $|S|^2|A|$. Might be sparse, and close to $|S||A|$\n",
        "if not every state can reach every other state. \n",
        "\n",
        "Dynamic decision networks (DDNs): factored representations.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "**Bellman update** The utility value for a state at a given iteration, which is updated. \n",
        "All states are updated for each iteration. \n",
        "\n",
        "Bellman equations converge. \n",
        "\n",
        "**Contraction** put in 2 inputs that return 2 outputs that are closer together. Ex: divide by 2\n",
        "Contractions have 1 fixed point (ex 0). Values must get closer to the fixed point. \n",
        "Smaller $\\gamma$  means faster convergence, but might miss longer effects.  Vs bigger $\\gamma$ \n",
        "N grows exponentnially. \n",
        "\n",
        "Policy becomes optimal long before utilities converge. \n",
        "\n",
        "**Policy iteration** has 2 parts:\n",
        "1. **Policy eval** given a policy cacluate the utility $U_i$ if $\\\\Pi_i$ was executed.\n",
        "2. **Policy improvement** try a new policy $\\\\Pi_{i+1}$ based on $U_i$\n",
        "Stop when no utility changes.\n",
        "\n",
        "Policy iteration removes the max, and instead have $n$ linear equations/unknowns for the $n$ states,\n",
        "So can be solved in $O(n^3)$. If sparse state space, even faster. \n",
        "**Modified Policy iteration** could also do value iteration for a few iterations \n",
        "go get approx utility and then do policy iteration. \n",
        "\n",
        "$$asynchornous policy iteration** updates only a subset of states\n",
        "\n",
        "Value/policy iterations are offline, compute then perform.\n",
        "\n",
        "\n",
        "For online learning, limit of tree where stop caring about rewards\n",
        "H = ceiling of $\\\\log_y\\\\epsilon(1-\\\\gamma) / R_{max})$ \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\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": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "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))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "fOFT8u14PuM1",
        "outputId": "d86a1a06-6318-4362-8e71-ee538fe18627"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n**Markovian**: Prob of reach state depends only on previous state, not all earlier\nBut decision problem is seq, so utlity will depndend on seq of states/actions\n\nMDP consistes of sets of: states, actions; transitino model, and reward func.\n\nPolicy says what agent should do in any state. Measure polic by expected util. Optimal\nyields the highest expected util. Can be multiple optimal policies. \n\n**Nonstationary**: if time affects the policy (ex. exit early for N=3 steps).\n**Stationary**: if pol based only on current state. \n\nDiscount, closer to 0 prefer rewards now over later. 1, ok to wait - additive. \nEx $(1/\\gamma) - 1 $ is discount factor in monetary rewards\n\n\nUtil for infinte sequnce is finite $\\frac{R_{max}}{1 - \\gamma}$\n\n**Proper policy** - guranteed to reach a terminal state. \n\nDiscount util + infinte horizon means optimal pol is indepdnet of first state. \n\n$\\pi (s) = \\text{argmax}_{\\alpha \\in A(s) \\Sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s)]} $\n\nChoose action that max reward for the next step exp discounted utility of resulting state,\nassuming agent in s' chooses optimal action\n\n**Action-utility function/Q-function** - Expected utility of an action in given state. \n\n\n$P(S'|s,a)$ and $R(s,a,s')$ represented by 3d table $|S|^2|A|$. Might be sparse, and close to $|S||A|$\nif not every state can reach every other state. \n\nDynamic decision networks (DDNs): factored representations.\n\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n**Bellman update** The utility value for a state at a given iteration, which is updated. \nAll states are updated for each iteration. \n\nBellman equations converge. \n\n**Contraction** put in 2 inputs that return 2 outputs that are closer together. Ex: divide by 2\nContractions have 1 fixed point (ex 0). Values must get closer to the fixed point. \nSmaller $\\gamma$  means faster convergence, but might miss longer effects.  Vs bigger $\\gamma$ \nN grows exponentnially. \n\nPolicy becomes optimal long before utilities converge. \n\n**Policy iteration** has 2 parts:\n1. **Policy eval** given a policy cacluate the utility $U_i$ if $\\Pi_i$ was executed.\n2. **Policy improvement** try a new policy $\\Pi_{i+1}$ based on $U_i$\nStop when no utility changes.\n\nPolicy iteration removes the max, and instead have $n$ linear equations/unknowns for the $n$ states,\nSo can be solved in $O(n^3)$. If sparse state space, even faster. \n**Modified Policy iteration** could also do value iteration for a few iterations \ngo get approx utility and then do policy iteration. \n\n$$asynchornous policy iteration** updates only a subset of states\n\nValue/policy iterations are offline, compute then perform.\n\n\nFor online learning, limit of tree where stop caring about rewards\nH = ceiling of $\\log_y\\epsilon(1-\\gamma) / R_{max})$ \n\n\n\n## Module 8 Lecture Notes\n Your summary here \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",
        "**expolitation** - use best current action\n",
        "**exploration** - try new state to gain information\n",
        "\n",
        "In **bandit problems**  arms are **Markove reward processes**, having one possible action.\n",
        "Bandit problem is an MDP.\n",
        "\n",
        "**Gittins index**\n",
        "\n",
        "$$ \\\\lambda = \\\\max_{T>0} \\\\frac{E(\\\\sum_{t=0}^{T-1}\\\\gamma^tR_t)}{E(\\\\sum_{t=0}^{T-1}\\\\gamma^t)} $$\n",
        "Lambda where indifferent b/t switching to $M_{\\\\lambda}$ immediatly or at T.\n",
        "\n",
        "Gittins index for an arm is equal to $1 - \\\\gamma *$  value of optimal policy for restarting the MDP.  \n",
        "\n",
        "**Upper confidence bound heuristic** use samples from each arm, create a confi interval for the value of it\n",
        "Choose arm w/ highest upper bound. Std dev is proportional to $\\\\sqrt{1/N_i}$ so index is approx\n",
        "$UCB(M_i) = \\\\hat{\\\\mu_i} + g(N)/\\\\sqrt{N_i}$ \n",
        "\n",
        "**regret** is the difference between expected rewards and optimal expected rewards\n",
        "\n",
        "**Thompson sampling** chose an arm randomly by probability based on current samples.\n",
        "\n",
        "**Selection problem** just need to choose the best option quickly, ex. chose employee to hire, or \n",
        "metalevel decison problem. No index for these.\n",
        "\n",
        "**Bandit superprocess** has each arm be a full MDP. Can't solve each on individually. \n",
        "Globablly optimal might be locally suboptimal. Changes the short/long term rewards.\n",
        "\n",
        "**Dominating policy** is an optimal policy unaffected by opportunity cost. Found by realxing MDP.\n",
        "Compute lower bound by solving each arm sepeartly. \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" \n",
        "**Supervised learning** give an agent example input/output pairs. \n",
        "**Reinfrocement learning** RL, agent interacts with the world and gets rewards.\n",
        "RL different from MDP b/c \"in\" in the MDP. Don't know the transition model/reward function.\n",
        "**Sparse** rewards  don't give rewards signal for most states. \n",
        "\n",
        "Approaches:\n",
        "1. Model Based reinforcement Learning: Agent use a transition model of the env to understand\n",
        "reward signals and make decisions. If partially observable, also use it for state estimation.\n",
        "\n",
        "2. Model free: agent doesn't know or learn transition model. Instead learns direct representation of behavior:\n",
        "2a. Action-utility learning: Q-learning, learn a q-function. Given a q-function choose what to by \n",
        "figuring out action with highest q-val\n",
        "2b. Policy search: agent learns pol that maps from state-to actions. i.e. reflex agent\n",
        "\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "**Passive RL**: Agent policy is fixed, try to learn the utility of states. \n",
        "like policy evaluation, but don't know the transition model ($P(s' | s,a)$) or the \n",
        "reward function $R(s,a,s')$. So instead setup a set of trials\n",
        "\n",
        "**direct utility estimation**: utility of a state is expected total reward from state forward.\n",
        "Each trail results in a sample of this. W/infite trials reach real expected value.\n",
        "\n",
        "Problem is that don't take into account utility of successor states. Slow convergence\n",
        "\n",
        "**adaptive dynamic progamming** ADP, learns the trasnition model and connects them.\n",
        "Env is fully observable so have $(s,a)$ and ouptu is $s'$. Estimate P(s' | s,a) from counts\n",
        "in of how often reach $s'$ by $a$ in $s$. \n",
        "\n",
        "**Temporal-difference learning** \n",
        "\n",
        "$$U^{\\\\pi}(s) \\\\leftarrow U^{\\\\pi}(s) + \\\\alpha[R(s,\\\\pi(s),s') + \\\\gamma U^{\\\\pi}(s') - U^{\\\\pi}(s)]$$\n",
        "If if transition from one state to another, and know estimate utilities, they should conform\n",
        "to $U(s+1) = r + U(s)$, so adjust it a bit. $\\\\alpha$ is the learning rate.\n",
        "\n",
        "Want to decrease $\\alpha$ more visit state. Causes $U^{\\\\pi}(s)$ to converge to right val. \n",
        "\n",
        "**Prioritized sweeping** a heuristc to adjust only states in ADP where it's succesors likely \n",
        "have a large adjustment. Can learn fast, and more efficient. \n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "**Active reinforcement learning** - decide what actions to take.\n",
        "Need to learn probability for all actions, and the utilities of the optimal policy. \n",
        "\n",
        "Problem is that the learned optimal policy in the learned model is not the true env.\n",
        "Tradeoff between **exploitation** of the best action know now, and **exploration** of uknown states. \n",
        "\n",
        "**GLIE** Greedy in the limit of infite exploration. Try all actions in all states\n",
        "a certain number of times. Good option is to try options that haven't tried a lot yet. \n",
        "More optimistic. Exploration function should be prefer higher utility, and low counts. \n",
        "\n",
        "Assumes safe exploration, in real world actions can be irreversible,\n",
        "may enter absorbing state.\n",
        "\n",
        "Bayesian reinforcement learning based on $P(h|e)$.  try to find the policy\n",
        "with max sum of expected probabilities given vidcne. \n",
        "\n",
        "Robust control theory, have a set of possible models. Optimal robust policy is the one w/best outcome in worst case. \n",
        "\n",
        "TD q-learning agent doesn't need a transition model. But can be long to figure out sparse rewards/\n",
        "needs long action sequnces. \n",
        "\n",
        "**SARSA** State, action, reward, state action. Updates with action taken. \n",
        "\n",
        "Q-learning is off policy, but SARSA is on-policy. SARSA stays with the policy.\n",
        "\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\n",
        "**function approximation** approximte true util/Q function. RL learn values\n",
        "for parameters (weights) in the linear combo of features. Use with look-ahead search\n",
        "to make better decisions and faster learning.\n",
        "\n",
        "RL use online learning, update parms after every trial. Use the delta rule/Widrow-Hoff rule\n",
        "\n",
        "$$\\\\theta_i \\\\leftarrow \\\\theta_i + \\\\alpha [u_j(s) -\\\\hat{U_{\\\\theta}}(s)] \\\\frac{\\\\partial \\\\hat{U_{\\\\theta}(S)}}{\\\\partial \\\\theta_{i}}$$\n",
        "\n",
        "**catastrophic forgetting** forget previously learned learning. \n",
        "**experience reply** is a solution, replay trajectory that caused negative rewards earlier. \n",
        "\n",
        "Sometimes can't come up with features for a linear function approximator. Deep learning has been effective\n",
        "Final layer might be linear, and can see what features the network is using to build it system.\n",
        "\n",
        "**credit assignment problem** hard to figure out which of the actions in a long string caused final reward.\n",
        "Solve w/**reward shaping** by giving agent more **pseudorewards** for progress. Ex: touching the ball.\n",
        "But can cause agent to max pseudoreward instead of goal. Can modify the reward function over time\n",
        "by a potential function. \n",
        "\n",
        "**hierarchial reinforcement learning**, another solution is break action sequences into small parts. \n",
        "\n",
        "**joint state space**, a physical and machine state for all states. \n",
        "\n",
        "**additive decompoition**, for each action, the utility dpends on a few variables, not all,\n",
        "and together they get summed up for the total utility. \n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "**Policy search** keep adjusting policy while prefromance improves. Adjust paramters in parmd Q-functions.\n",
        "\n",
        "Different from Q-learning b/c not trying to find the optimal Q, but just result in good perf.\n",
        "\n",
        "Discontinous function nature means slight change in paramter may cause action choice to switch,\n",
        "and policy to switch. Use **Stochastic policy** representation, the probability of selecting an action in a state.\n",
        "\n",
        "\n",
        "**correlated sampling** gives same input to two policies and sees which does better. \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6393dabd-8ee5-4a9a-9d3a-cd63ad71b68a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \n**expolitation** - use best current action\n**exploration** - try new state to gain information\n\nIn **bandit problems**  arms are **Markove reward processes**, having one possible action.\nBandit problem is an MDP.\n\n**Gittins index**\n\n$$ \\lambda = \\max_{T>0} \\frac{E(\\sum_{t=0}^{T-1}\\gamma^tR_t)}{E(\\sum_{t=0}^{T-1}\\gamma^t)} $$\nLambda where indifferent b/t switching to $M_{\\lambda}$ immediatly or at T.\n\nGittins index for an arm is equal to $1 - \\gamma *$  value of optimal policy for restarting the MDP.  \n\n**Upper confidence bound heuristic** use samples from each arm, create a confi interval for the value of it\nChoose arm w/ highest upper bound. Std dev is proportional to $\\sqrt{1/N_i}$ so index is approx\n$UCB(M_i) = \\hat{\\mu_i} + g(N)/\\sqrt{N_i}$ \n\n**regret** is the difference between expected rewards and optimal expected rewards\n\n**Thompson sampling** chose an arm randomly by probability based on current samples.\n\n**Selection problem** just need to choose the best option quickly, ex. chose employee to hire, or \nmetalevel decison problem. No index for these.\n\n**Bandit superprocess** has each arm be a full MDP. Can't solve each on individually. \nGlobablly optimal might be locally suboptimal. Changes the short/long term rewards.\n\n**Dominating policy** is an optimal policy unaffected by opportunity cost. Found by realxing MDP.\nCompute lower bound by solving each arm sepeartly. \n\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n \n**Supervised learning** give an agent example input/output pairs. \n**Reinfrocement learning** RL, agent interacts with the world and gets rewards.\nRL different from MDP b/c \"in\" in the MDP. Don't know the transition model/reward function.\n**Sparse** rewards  don't give rewards signal for most states. \n\nApproaches:\n1. Model Based reinforcement Learning: Agent use a transition model of the env to understand\nreward signals and make decisions. If partially observable, also use it for state estimation.\n\n2. Model free: agent doesn't know or learn transition model. Instead learns direct representation of behavior:\n2a. Action-utility learning: Q-learning, learn a q-function. Given a q-function choose what to by \nfiguring out action with highest q-val\n2b. Policy search: agent learns pol that maps from state-to actions. i.e. reflex agent\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n**Passive RL**: Agent policy is fixed, try to learn the utility of states. \nlike policy evaluation, but don't know the transition model ($P(s' | s,a)$) or the \nreward function $R(s,a,s')$. So instead setup a set of trials\n\n**direct utility estimation**: utility of a state is expected total reward from state forward.\nEach trail results in a sample of this. W/infite trials reach real expected value.\n\nProblem is that don't take into account utility of successor states. Slow convergence\n\n**adaptive dynamic progamming** ADP, learns the trasnition model and connects them.\nEnv is fully observable so have $(s,a)$ and ouptu is $s'$. Estimate P(s' | s,a) from counts\nin of how often reach $s'$ by $a$ in $s$. \n\n**Temporal-difference learning** \n\n$$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s,\\pi(s),s') + \\gamma U^{\\pi}(s') - U^{\\pi}(s)]$$\nIf if transition from one state to another, and know estimate utilities, they should conform\nto $U(s+1) = r + U(s)$, so adjust it a bit. $\\alpha$ is the learning rate.\n\nWant to decrease $\u0007lpha$ more visit state. Causes $U^{\\pi}(s)$ to converge to right val. \n\n**Prioritized sweeping** a heuristc to adjust only states in ADP where it's succesors likely \nhave a large adjustment. Can learn fast, and more efficient. \n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n**Active reinforcement learning** - decide what actions to take.\nNeed to learn probability for all actions, and the utilities of the optimal policy. \n\nProblem is that the learned optimal policy in the learned model is not the true env.\nTradeoff between **exploitation** of the best action know now, and **exploration** of uknown states. \n\n**GLIE** Greedy in the limit of infite exploration. Try all actions in all states\na certain number of times. Good option is to try options that haven't tried a lot yet. \nMore optimistic. Exploration function should be prefer higher utility, and low counts. \n\nAssumes safe exploration, in real world actions can be irreversible,\nmay enter absorbing state.\n\nBayesian reinforcement learning based on $P(h|e)$.  try to find the policy\nwith max sum of expected probabilities given vidcne. \n\nRobust control theory, have a set of possible models. Optimal robust policy is the one w/best outcome in worst case. \n\nTD q-learning agent doesn't need a transition model. But can be long to figure out sparse rewards/\nneeds long action sequnces. \n\n**SARSA** State, action, reward, state action. Updates with action taken. \n\nQ-learning is off policy, but SARSA is on-policy. SARSA stays with the policy.\n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n**function approximation** approximte true util/Q function. RL learn values\nfor parameters (weights) in the linear combo of features. Use with look-ahead search\nto make better decisions and faster learning.\n\nRL use online learning, update parms after every trial. Use the delta rule/Widrow-Hoff rule\n\n$$\\theta_i \\leftarrow \\theta_i + \\alpha [u_j(s) -\\hat{U_{\\theta}}(s)] \\frac{\\partial \\hat{U_{\\theta}(S)}}{\\partial \\theta_{i}}$$\n\n**catastrophic forgetting** forget previously learned learning. \n**experience reply** is a solution, replay trajectory that caused negative rewards earlier. \n\nSometimes can't come up with features for a linear function approximator. Deep learning has been effective\nFinal layer might be linear, and can see what features the network is using to build it system.\n\n**credit assignment problem** hard to figure out which of the actions in a long string caused final reward.\nSolve w/**reward shaping** by giving agent more **pseudorewards** for progress. Ex: touching the ball.\nBut can cause agent to max pseudoreward instead of goal. Can modify the reward function over time\nby a potential function. \n\n**hierarchial reinforcement learning**, another solution is break action sequences into small parts. \n\n**joint state space**, a physical and machine state for all states. \n\n**additive decompoition**, for each action, the utility dpends on a few variables, not all,\nand together they get summed up for the total utility. \n\n\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" \n",
        "$P(effct | cause)$ is causal, while P(cause | effect) is disagnostic$. Doctors\n",
        "knows causal probabilities, and wants to figure out diagnosis for patient. \n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "**Naive Bayes** assume that effects are independent given a cause. \n",
        "$P(cause |e) = \\\\alpha P(Cause) \\\\Pi_j P(ej | Cause)$\n",
        "The probability of the cause given the cause is the prob of cause, times\n",
        "the product of the conditional probabilities of the effects given the cause.\n",
        "This is then normalized. Unobserved effects sum to 1 so can be ignored. runtime is O(e)\n",
        "\n",
        "Can use NB for txt classificaiton. Decide which class a text belongs to.\n",
        "Category is the cause, and effect is which words are present.\n",
        "\n",
        "Assume words occur independently. In reality not so. Model is overconfident. But ranking of cateogries is still accurate.\n",
        "\n",
        "NB works well for language determ, document retrive, spam.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" \n",
        "Language models assign a probability to series of words. \n",
        "**n-gram** is a combo of _n_ words. So 2-gram is 2 word sequence. \n",
        "n-gram models try to estm probability of the final word given the first n-1 words.\n",
        "\n",
        "can try to use counts of history to calculate P(w|h), but doesn't account for novelty.\n",
        "\n",
        "Chain rule: $P(x_1..x_n) = P(x_1)P(x_2 | x1)P(x_3|x_{1:2}...P(x_n | x_{1:n-1})$\n",
        "\n",
        "instead of getting probability using whole industry, use just some of the past words. \n",
        "ex. in bigram conditional probability of past word.\n",
        "\n",
        "**Markov assumption** is that the probability of a word conditional only on prvious word.\n",
        "\n",
        "Estimate n-gram probabilities using **maximum likelihood estimation**, \n",
        "normalize counts from a corpus so they are between 0 an 1. \n",
        "\n",
        "For bigram $P(w_n | w_{n-1} = \\\\frac{C(w_{n-1}w_n)}{C(w_{n-1})})$\n",
        "Ratio is the **relative frequency**\n",
        "\n",
        "Use log probabilities because the probabilities are < 1 and as multiply can have underflow. \n",
        "Add log probabilities instead of multiplying.\n",
        "so $p_1 * p_2 * p_3 * p_4 = exp(\\\\log{p1} + log{p2} + log{p3} + log{p4})$\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "Extrinsic evaluation is trying a model in an application. \n",
        "Intrinsic evaluation is sepearte from any application. Use a **test set** instead. \n",
        "Eval on a test set that was unseen. \n",
        "\n",
        "Might separate out a part of the test set for inital testing, called the devset. \n",
        "Typically do 80% of data for train, 10% dev, 10% test.\n",
        "\n",
        "Preplexity is inverse probability of tet set, normalized by the number of words\n",
        "$PP(W) = P(w_1w_2...w_n)^{-1/n}$ and via chain rule\n",
        "$PP(W) = \\\\sqrt[n]{\\\\prod_{i=1}^N \\\\frac{1}{P(w_i | w1 ...w_{i-1})}}$\n",
        "\n",
        "Higher probability the lower the perplexity. Want lower perplexity to max the LM.\n",
        "\n",
        "Perplexity is also the **weighted average branching factor** i.e. how many words can follow a word\n",
        "Ex: if all 10 digits equally likely then $P(w_1w_2...w_N)^{-1/N} = ((1/10)^N)^(-1/N) = (1/10)^-1 = 10$\n",
        "but if a digit is way more likely, then perplexity is lower, the branching factor is 10, but weighted branching factor is smaller.\n",
        "\n",
        "Bigger n-gram lower perplexity\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Can generate words by their probability distribution interval.\n",
        "Choose a random number then choose first word w/in interval of that number then next via bigram \"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "Grammar depends a lot on the training set. Genre needs to match b/t training corpus and test/task.\n",
        "Also need to match the dialect/variety.\n",
        "\n",
        "Problem of sparsity. Can have good word have 0 probability. Problem because underestimate the probability of the word.\n",
        "Also a problem because the entire probability becomes 0. Perplexity can't be computed b/c denom is 0 \n",
        "\n",
        "Might have unknown words in the test set. Out of vocabulary rate. use psuedo-word <UNK>.\n",
        "If have closed vocab can treate all <UNK> as one. Similarly replace all words in open vocab with count < n with <UNK>\n",
        "Can create low peplexity by choosing a small vocab, so then UNK has high prob. Should only compare \n",
        "LMs with same vocab.\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\" \n",
        "Word in vocab but have unseen context need to be accounted for with smoothing.\n",
        "**Smoothing**/**discounting** moves some probability from seen to unseen events.\n",
        "\n",
        "**Laplace smoothing** adds 1 to all 1 n-gram counts. Need to add V to numerator\n",
        "since every vocab word was counted once more so $P_{Laplace}(w_i) = \\\\frac{c_i +1}{N + V}$\n",
        "\n",
        "**Add-k smoothing** adds only a fractional count to the counts\n",
        "$P_{add-k}(w_n| w_{n-1}) = \\\\frac{C(w_{n-1}w_n) + k}{C(w_{n-1}) + kV}$\n",
        "\n",
        "doesn't work that well though.\n",
        "\n",
        "**Backoff** use the n-gram if there is evidence, else go to n-2 -gram if exits, \n",
        "else to n-3 -gram ...to unigram.\n",
        "\n",
        "**Interpolation** mix the probability estimates from al the n-grams.\n",
        "Can do linear interpolation, weight each one by $\\\\lambda_i$$, such that the \n",
        "sum of the $\\\\lambda$s is 1.\n",
        "\n",
        "Learn the $\\\\lambda$ weights from the held-out corpus.\n",
        "\n",
        "$$Katz backoff$$ redistribute some of weight of the higher-order n-grams so probability adds to 1.\n",
        "use some alpha function to distribute it to the lower-order n-grams. \n",
        "Combine with **Good-Turing** smoothing.\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "Efficiency when storing words. The words are stored in member as 64bit has numbers,\n",
        "actual words on disc. Probabilities use only 4-8 bits. Use reverse tries for n-grams.\n",
        "\n",
        "**Stupid backoff** doesn't use discounting of high order probabilities. \n",
        "Just use a weight $\\lambda$ when switching to lower order n-gram.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "34aa1955-b3db-4038-a2c1-7cb1e6d485ce"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n$P(effct | cause)$ is causal, while P(cause | effect) is disagnostic$. Doctors\nknows causal probabilities, and wants to figure out diagnosis for patient. \n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n**Naive Bayes** assume that effects are independent given a cause. \n$P(cause |e) = \\alpha P(Cause) \\Pi_j P(ej | Cause)$\nThe probability of the cause given the cause is the prob of cause, times\nthe product of the conditional probabilities of the effects given the cause.\nThis is then normalized. Unobserved effects sum to 1 so can be ignored. runtime is O(e)\n\nCan use NB for txt classificaiton. Decide which class a text belongs to.\nCategory is the cause, and effect is which words are present.\n\nAssume words occur independently. In reality not so. Model is overconfident. But ranking of cateogries is still accurate.\n\nNB works well for language determ, document retrive, spam.\n\n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n \nLanguage models assign a probability to series of words. \n**n-gram** is a combo of _n_ words. So 2-gram is 2 word sequence. \nn-gram models try to estm probability of the final word given the first n-1 words.\n\ncan try to use counts of history to calculate P(w|h), but doesn't account for novelty.\n\nChain rule: $P(x_1..x_n) = P(x_1)P(x_2 | x1)P(x_3|x_{1:2}...P(x_n | x_{1:n-1})$\n\ninstead of getting probability using whole industry, use just some of the past words. \nex. in bigram conditional probability of past word.\n\n**Markov assumption** is that the probability of a word conditional only on prvious word.\n\nEstimate n-gram probabilities using **maximum likelihood estimation**, \nnormalize counts from a corpus so they are between 0 an 1. \n\nFor bigram $P(w_n | w_{n-1} = \\frac{C(w_{n-1}w_n)}{C(w_{n-1})})$\nRatio is the **relative frequency**\n\nUse log probabilities because the probabilities are < 1 and as multiply can have underflow. \nAdd log probabilities instead of multiplying.\nso $p_1 * p_2 * p_3 * p_4 = exp(\\log{p1} + log{p2} + log{p3} + log{p4})$\n\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nExtrinsic evaluation is trying a model in an application. \nIntrinsic evaluation is sepearte from any application. Use a **test set** instead. \nEval on a test set that was unseen. \n\nMight separate out a part of the test set for inital testing, called the devset. \nTypically do 80% of data for train, 10% dev, 10% test.\n\nPreplexity is inverse probability of tet set, normalized by the number of words\n$PP(W) = P(w_1w_2...w_n)^{-1/n}$ and via chain rule\n$PP(W) = \\sqrt[n]{\\prod_{i=1}^N \\frac{1}{P(w_i | w1 ...w_{i-1})}}$\n\nHigher probability the lower the perplexity. Want lower perplexity to max the LM.\n\nPerplexity is also the **weighted average branching factor** i.e. how many words can follow a word\nEx: if all 10 digits equally likely then $P(w_1w_2...w_N)^{-1/N} = ((1/10)^N)^(-1/N) = (1/10)^-1 = 10$\nbut if a digit is way more likely, then perplexity is lower, the branching factor is 10, but weighted branching factor is smaller.\n\nBigger n-gram lower perplexity\n\n\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Can generate words by their probability distribution interval.\nChoose a random number then choose first word w/in interval of that number then next via bigram \n\n## SLP Chapter 3.4 Generalization and Zeros\n\nGrammar depends a lot on the training set. Genre needs to match b/t training corpus and test/task.\nAlso need to match the dialect/variety.\n\nProblem of sparsity. Can have good word have 0 probability. Problem because underestimate the probability of the word.\nAlso a problem because the entire probability becomes 0. Perplexity can't be computed b/c denom is 0 \n\nMight have unknown words in the test set. Out of vocabulary rate. use psuedo-word <UNK>.\nIf have closed vocab can treate all <UNK> as one. Similarly replace all words in open vocab with count < n with <UNK>\nCan create low peplexity by choosing a small vocab, so then UNK has high prob. Should only compare \nLMs with same vocab.\n\n\n\n## SLP Chapter 3.5 Smoothing\n \nWord in vocab but have unseen context need to be accounted for with smoothing.\n**Smoothing**/**discounting** moves some probability from seen to unseen events.\n\n**Laplace smoothing** adds 1 to all 1 n-gram counts. Need to add V to numerator\nsince every vocab word was counted once more so $P_{Laplace}(w_i) = \\frac{c_i +1}{N + V}$\n\n**Add-k smoothing** adds only a fractional count to the counts\n$P_{add-k}(w_n| w_{n-1}) = \\frac{C(w_{n-1}w_n) + k}{C(w_{n-1}) + kV}$\n\ndoesn't work that well though.\n\n**Backoff** use the n-gram if there is evidence, else go to n-2 -gram if exits, \nelse to n-3 -gram ...to unigram.\n\n**Interpolation** mix the probability estimates from al the n-grams.\nCan do linear interpolation, weight each one by $\\lambda_i$$, such that the \nsum of the $\\lambda$s is 1.\n\nLearn the $\\lambda$ weights from the held-out corpus.\n\n$$Katz backoff$$ redistribute some of weight of the higher-order n-grams so probability adds to 1.\nuse some alpha function to distribute it to the lower-order n-grams. \nCombine with **Good-Turing** smoothing.\n\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\nEfficiency when storing words. The words are stored in member as 64bit has numbers,\nactual words on disc. Probabilities use only 4-8 bits. Use reverse tries for n-grams.\n\n**Stupid backoff** doesn't use discounting of high order probabilities. \nJust use a weight $\\lambda$ when switching to lower order n-gram.\n\n\n\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4ec55d5e-80cb-4109-8db2-e5c8fc0b3995"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "**Bayesian network** a directed graph with:\n",
        "1. Nodes that are random variables\n",
        "2. Directed edges b/t pairs of nodes. Source is parent of destination. Is a DAG\n",
        "3. Every node has probability infor on effect of parents \n",
        "\n",
        "Node with boolean variable w/ k parents, has $2^k$ probabilities. \n",
        "\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "Syntax of BN is a DAG w/ nodes w/ probabilities.\n",
        "Semantics is how syntax relates to joint probability distribution of the vars.\n",
        "\n",
        "probability of joint distribution entry is\n",
        "$P(x_1, ..., x_n) = \\\\Pi_{i=1}^n \\\\theta (x_i | parents(x_i)$\n",
        "\n",
        "**chain rule** $P(x_1,...,x_n) = P(x_n | x_{n-1}, ..., x_1)P(x_{n-1}|x_{n-2}...,x_1)...P(x_2|x_1)P(x_1)$\n",
        "\n",
        "Same as parents being causaul. Depends on toplogical ordering of the nodes. \n",
        "\n",
        "A BN is correct representation if every node is conidtitinally indepent of all other predecessors, given it's parents.\n",
        "\n",
        "Achived by\n",
        "1. Nodes, ordered by cause to effects \n",
        "2. Links with min set for parents for $X_i$, and a conditional probability table for $x_i$ given its parents\n",
        "\n",
        "BN more compact than  full joint distribution. \n",
        "BN is a **locally strctured** system, in which every subcomponent is directly interacting with some $n$ number\n",
        "of other components < N total components. \n",
        "Ex: if a RV in a BN is influnced by k others, then conditional probability tables will have $2^k$ numbers,\n",
        "so toatl will be $2^k *n $ while the joint distribution will contain $2^n$ numbers. \n",
        "\n",
        "Better to leave out some links b/c otherwise as big as a table of the joint distribution. \n",
        "Tradeoff between accuracy and complexity. \n",
        "\n",
        "Given a vars parents, the var is conditionally independent of non-decendants.\n",
        "\n",
        "BN can be through of as set of of conditional independences. \n",
        "\n",
        "Markov blanket - a node is independent of all other nodes, given parents, childeren,\n",
        "and co-parents\n",
        "\n",
        "**D-sepeartion**\n",
        "1. Take an ancestral subgraph of 3 vars\n",
        "2. Link between any non-lined nodes that have a child -> **moral graph**\n",
        "3. Make all directed edges undirected\n",
        "4. Z-despeartes two vars if it blocks all paths between them. And $X \\\\perp Y | Z$ \n",
        "\n",
        "**Canonical distributions**\n",
        "1. **Deterministic nodes** value is determined by value of parents.\n",
        "Value can be min, max, or some other function.\n",
        "2.**Context-specific independence** if node is independent of parents w/ certain values. \n",
        "ex: damage is indep of rugedness given not accident\n",
        "\n",
        "For continious vars might use **discretization** dividing values in some num of intervals\n",
        "or might assign a distribution. \n",
        "\n",
        "**hybrid Bayesian network** has both discrete and continous vars. \n",
        "\n",
        "BN can contain **hidden variables** that are not input/output vars but important to make more sparse network\n",
        "\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "print(f\"chapter 13_2: word length:{len(chapter13_2.split(' '))} charchters: {len(chapter13_2)}\")\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "chapter 13_2: word length:339 charchters: 2311\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "93c76e74-de6f-49c4-e384-3bb49b47aa98"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n**Bayesian network** a directed graph with:\n1. Nodes that are random variables\n2. Directed edges b/t pairs of nodes. Source is parent of destination. Is a DAG\n3. Every node has probability infor on effect of parents \n\nNode with boolean variable w/ k parents, has $2^k$ probabilities. \n\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nSyntax of BN is a DAG w/ nodes w/ probabilities.\nSemantics is how syntax relates to joint probability distribution of the vars.\n\nprobability of joint distribution entry is\n$P(x_1, ..., x_n) = \\Pi_{i=1}^n \\theta (x_i | parents(x_i)$\n\n**chain rule** $P(x_1,...,x_n) = P(x_n | x_{n-1}, ..., x_1)P(x_{n-1}|x_{n-2}...,x_1)...P(x_2|x_1)P(x_1)$\n\nSame as parents being causaul. Depends on toplogical ordering of the nodes. \n\nA BN is correct representation if every node is conidtitinally indepent of all other predecessors, given it's parents.\n\nAchived by\n1. Nodes, ordered by cause to effects \n2. Links with min set for parents for $X_i$, and a conditional probability table for $x_i$ given its parents\n\nBN more compact than  full joint distribution. \nBN is a **locally strctured** system, in which every subcomponent is directly interacting with some $n$ number\nof other components < N total components. \nEx: if a RV in a BN is influnced by k others, then conditional probability tables will have $2^k$ numbers,\nso toatl will be $2^k *n $ while the joint distribution will contain $2^n$ numbers. \n\nBetter to leave out some links b/c otherwise as big as a table of the joint distribution. \nTradeoff between accuracy and complexity. \n\nGiven a vars parents, the var is conditionally independent of non-decendants.\n\nBN can be through of as set of of conditional independences. \n\nMarkov blanket - a node is independent of all other nodes, given parents, childeren,\nand co-parents\n\n**D-sepeartion**\n1. Take an ancestral subgraph of 3 vars\n2. Link between any non-lined nodes that have a child -> **moral graph**\n3. Make all directed edges undirected\n4. Z-despeartes two vars if it blocks all paths between them. And $X \\perp Y | Z$ \n\n**Canonical distributions**\n1. **Deterministic nodes** value is determined by value of parents.\nValue can be min, max, or some other function.\n2.**Context-specific independence** if node is independent of parents w/ certain values. \nex: damage is indep of rugedness given not accident\n\nFor continious vars might use **discretization** dividing values in some num of intervals\nor might assign a distribution. \n\n**hybrid Bayesian network** has both discrete and continous vars. \n\nBN can contain **hidden variables** that are not input/output vars but important to make more sparse network\n\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6083c17e-7bc9-4c1b-f434-cbdaeaad3516"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "**induction** is observation to rule. Might be wrong.\n",
        "**deduction** rule to case. Guranteed to be correct.\n",
        "\n",
        "**classification** are problems where output of ML algo is a finite set of vals.\n",
        "**regression** when ouput is a number\n",
        "\n",
        "**supervised learning* give agent input and ouput, agent learns map from i to o.\n",
        "Output that categorizes inputs is a **label**, agent is predicting a label.\n",
        "\n",
        "**unsupervised learning** agent needs to learn without direct feedback.\n",
        "Common task is **clustering**, finding a cluster of inputs.\n",
        "\n",
        "**reinforcement learning** agent learns from reinforcements, pos rewards or neg punishments.\n",
        "Needs to figure out what actions caused the reinfforcement.\n",
        "\"\"\"\n",
        "\n",
        "chapter19_2 = \"\"\"\n",
        "Supervised learning, has a training set of $(x_i, y_i)$ pairs, trying to find $h(x)$\n",
        "that approximates the real function $f(x)$ that creates the pairs.\n",
        "\n",
        "$h$ is the **hypothesis**, taken from **hypothesis space** $H$. \n",
        "$h$ can be called the **model** of the data, from **model class** $H$\n",
        "\n",
        "**ground truth** is the actual output $y_i$\n",
        "\n",
        "Hypothesis space based on knowledge or exploring data, or just experimenting\n",
        "\n",
        "**consistent hypothesis** $h$ where every $x_i$ in train set has corresponding $h(x_i) = y_i$.\n",
        "If continous values for $y_i$ use a **best-fit function** that produces $h(x_i)$ approx $y_i$.\n",
        "**generalizes** meas $h$ predicts the outputs in test set accurately. \n",
        "\n",
        "consistent hypothesis != good hypothesis\n",
        "\n",
        "Eval hypothesis space by bias and variance\n",
        "\n",
        "**bias** is how much $h$ deviates from expected val when averaged of different train sets.\n",
        "linear functions have strong bias. If data has non-linear pattern, linear func can't represent it.\n",
        "**underfitting** is not being able to find pattern in data. contrast piecewise function has low bias.\n",
        "\n",
        "**variance** amount of change in $h$ wrt fluctuation in train set. \n",
        "Ex lin func would have low variance, polynomial would have high variance\n",
        "**overfitting** too much weight on train set, perform poorly on new sets.\n",
        "\n",
        "Trade off between bias and variance. \n",
        "Low-bias hypothesis fit data well, more complicated vs. low-variance, simple, and generalize better.\n",
        "\n",
        "Can choose hypothesis most likely based on data\n",
        "$h^* = \\\\argmax P(h|data)$ == $h^* = \\\\argmax P(data|h)P(h)$\n",
        "\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\"\n",
        "**Decision tree** func w/input vector utliple attribute values to output 1 value the decision\n",
        "\n",
        "**Boolean classification** only true or false outputs.\n",
        "\n",
        "Try to get a small consistent tree. Choose the attributes that are most discerning first (biggest impact)\n",
        "Leads to more shallow tree.\n",
        "\n",
        "Eval a learning algo using **learning curve** - % correct on test vs training set size.\n",
        "\n",
        "**Entropy** measure of uncertainty for a RV. Info amount inverse with entropy.\n",
        "$$-\\sum_kP(v_k)\\\\log_2P(v_k)$$\n",
        "for fair coin entropy = $-(0.5\\\\log_2 0.5 + .5\\\\log_2 0.5) = 1$ bits\n",
        "Loaded coin entropy = $-(0.99\\\\log_2 0.99 + 0.01\\\\log_2 0.01) = 0.08$ bits\n",
        "\n",
        "For boolean rv entropy: $B(q) = - (qlog_2(q) + (1-q)log_2(1-q))$, where q is prob of true.\n",
        "\n",
        "An attribute divides a training set by number of values, and each subset has pos and neg examples\n",
        "So entropy remaining after testing for A is\n",
        "Reaminder(A) = $\\sum_k=1^d \\\\frac{p_k + n_k}{p+n}B(\\\\frac{p_k}{p_k + n_k})\n",
        "\n",
        "informatin gain is the reduction in entropy\n",
        "Gain(A) = $B(\\\\frac{p}{p+N})$ - Remainder(A)\n",
        "Want to max gain. \n",
        "\n",
        "Overfitting liklihood increases w/number of attributes, decreases w/more training examples.\n",
        "Bigger hypothesis space more likely to fit/overfit.\n",
        "\n",
        "**decision tree pruning** elimnates nodes that aren't relevant to reduce overfitting. \n",
        "If a node w/ only leaf nodes only detects noise, its eliminated. Measure by information gain.\n",
        "\n",
        "Use significane test test to measure if enough info gain. Null hypohtesis that attribute not signficant.\n",
        "Use chi-squared test\n",
        "\n",
        "Pruned trees do better than unpruned when a lot of noise in the data. Also more efficient and clear.\n",
        "\n",
        "Can't do early stopping because might have attributes that are informative in comboination. \n",
        "\n",
        "Dealing with continous data, may want to use a **split point test** where test value of attribute\n",
        "can do **equality test** for non continous non ordered data.\n",
        "\n",
        "Decision trees can be suboptimially acurate, and can take too long to run. Also unstable b/c new example can change whole tree.\n",
        "Random forest can address some problems\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\"\n",
        "**Stationary** is the assumption that time doesn't affect examples' probability distributin\n",
        "Also assume they are independent. *iid* independent and identically distrbiuted\n",
        "\n",
        "**error rate** is % of time when hypothesis function isn't matching actual y\n",
        "\n",
        "**Hyperparameters** are parms for the model class, not just for an individual model.\n",
        "Ex $\\\\chi^2$ threshold or degree.\n",
        "\n",
        "Use 3 data sets\n",
        "1. Training set \n",
        "2. Validation/development set to eval possible models, and pick one\n",
        "3. Test set for final test\n",
        "\n",
        "Use k-fold cross-validation to get more out of data. split into k subsets and perfrom k round of learning.\n",
        "but use 1/k of data as validation set. Average scross across the round is the estimate.\n",
        "If $k=n$ this is leave-one-out cross validation LOOCV\n",
        "\n",
        "**Model selection** is finding right hypohtesis space, \n",
        "while **optimatization/training** is finding best hypothesis.\n",
        "\n",
        "Model interpolates data if it fits all of the training set. Point at which it beings to overfit.\n",
        "\n",
        "In ML try to minimize loss function instead of maxmize util.\n",
        "**Loss function** is the amount of util lost if guess is wrong\n",
        "$L(x, y, \\\\hat{y})=Utility(f(x)=y) - Utility(h(x)=\\\\hat{y})$\n",
        "or just $L(y, \\\\hat{y})$\n",
        "\n",
        "$L_1(y, \\\\hat{y}) = \\\\abs(y-\\\\hat{y})$\n",
        "$L_2(y, \\\\hat{y}) = (y-\\\\hat{y})^2$\n",
        "$L_{0/1}(y, \\\\hat{y}) =$ 0 only when $y = \\\\hat{y}$, 1 otherwise\n",
        "\n",
        "\n",
        "Want to do this over all inputs, would do over epxected generalized loss, \n",
        "but don't know probabilities generally so estimate iwth **empirical loss*\n",
        "\n",
        "EmpericalLoss = $\\\\sum_{(x,y) \\\\in E}L(y, h(x)) \\\\frac{1}{N}$, where N is the size of example set\n",
        "\n",
        "want to choose $h$ with lowert empirical loss\n",
        "\n",
        "reasons optiaml $h$ might be different:\n",
        "1. **Unrealizability** - if hypo space doesn't actually contain the true function $f$\n",
        "2. **Variance** - alog hypothesis varies with sets of examples. Vraince decrease w/# trainings if realizable\n",
        "3. **Noise** - $f$ might return different values for same input $x$\n",
        "4. If large hypospace, can't compute the best one for sure\n",
        "\n",
        "\n",
        "in large-scale learning loss affected mostly by limits of computation. \n",
        "\n",
        "Cost(h) = EmpLoss(h) + $\\\\labmda$ Complexity(h)\n",
        "\n",
        "**Regularization** is process for punishing complexity. Complexity is measured by **regularization function**\n",
        "**feature selection** discards features that are irrelavent, kind of like in prunning\n",
        "\n",
        "**minimum descriptin length** is the hypohteis that minimizes the bits required to encode data\n",
        "\n",
        "**hand-tuning** approach to hyperparameters is setting hyperparameters based on past and figuing out new ones.\n",
        "**grid search** is more mechanical way to tune them. \n",
        "\n",
        "if a lot of values for hyperparams use random search.\n",
        "\n",
        "**Bayesian optimization** make hyperparameter choice as an ML problem\n",
        "\n",
        "**Population-based training (PBT)** trains models with different hyperparams in parallel, via random search\n",
        "2nd generation then chooses values based on 1st generation + mutation.\n",
        "\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\"\n",
        "if $h$ is really wrong, will figure that out after a few examples. \n",
        "If consistent with many examples, unlikely to be way off so its *probably approximately correct*\n",
        "\n",
        "**approximately corre**ct if error of $h \\\\leq \\\\epsilon$ , w/$\\\\epsilon$ being small constant.\n",
        "Can find an $n$ where with with $n$ examples consistent hypothesis is appox correct. \n",
        "Inside the $\\\\epsilion$-ball of $f$. If outside, $H_{bad}$\n",
        "\n",
        "**sample complexity** is the number of examples needed for approx correct $h$\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter19_6 = \"\"\"\n",
        "linear regression used to minimze loss  of  $h_w$ in linear functions\n",
        "Loss($h_w$) = $\\sum_{j=1}^N(y_j - (w_1x_j +w_0))^2$\n",
        "\n",
        "Do that when partial derivatives wrt $w_0$ and $w_1$ are 0.\n",
        "so\n",
        "$$w_1 = N(\\\\sum x_jy_j) - (\\\\sum x_j)(\\\\sum y_j) / [N(\\\\sum x_j^2) - (\\\\sum x_j)^2]$$\n",
        "$$w_0 = (\\\\sum y_j - w1(\\\\sum x_j)) / N $$\n",
        "\n",
        "**Gradient descent**, start at some point in weight space, get an estimate of gardient, and move twoards downhill.\n",
        "adjustment is $w_i \\\\leftarrow w_i - \\\\alpha \\\\frac{\\\\partial}{\\\\partial w_i} Loss(w)$\n",
        "$\\\\alpha is the learning rate or learning step$\n",
        "\n",
        "Need to do for all examples. But can be very slow\n",
        "\n",
        "**epoch** is a step for all training examples\n",
        "\n",
        "**stochastic gradient descent** randomly selects some training examples. OK to do b/c\n",
        "std error of mean gradient based on sqrt of N. So ok trade off for speed and error.\n",
        "\n",
        "**SGD** also usefule for online, called **online gradient descent**\n",
        "\n",
        "$Complexity(h_w) = \\\\sum_i \\\\abs(w_i)^q$\n",
        "\n",
        "L2 regulariztion mins the sum of squares. L1 makes sparse model\n",
        "\n",
        "**decision boundry** b/t 2 classes. In linear dimension it's a **linear separator**\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "NB is generative b/c a class is sampled first from $P(c)$ and then word are generated from $P(d|c)$\n",
        "Most probable $c-hat$ given $d$ based on argmax $P(d|c) * P(c)$ where $P(c)$ is the prior probability of class $c$\n",
        "Naive Bayes Assumptions:\n",
        "Position doesn’t matter\n",
        "Probabilities are independent given class $c$\n",
        "Naive Bayes and LM use log space b/c of underflow\n",
        "Linear classifiers use linear combination of inputs for classification. Ex: Naive Bayes, logistic regression\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\" \n",
        "Maximum Likelihood Estimate (MLE) - consider what % of docs in train set are of class $c$.\n",
        "$P(f_i | c) = P(w_i | c)$ is count(w_i) in docs w/class $c$\n",
        "$P(w_i | c) = \\frac{count(w_i, c}{Sum_{w \\in V} count(w,c}\n",
        "Problem is that NB multiliplies all features liklihoods together, \n",
        "so if have a 0 probability for any term, probably of class drops to 0, even if have other evidence.\n",
        "Can do Laplace smoothing, adding 1 to the counts\n",
        "Ignore unknown words\n",
        "Might also ignore stop words, and frequent words (the, a)\n",
        "\"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" \n",
        "Binary multinomial naive Bayes, remove all duplicate words. Ie. word occurs or not per doc. \n",
        "Use negation on every word after a logical negation. (ex. After didn’t, NOT_like, NOT_this.\n",
        "\"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" \n",
        "Confusion matrix - table compare how algo does compared to gold labl. \n",
        "False negative, are system id as negative, but is positive (ex. Is spam)\n",
        "Accuracy is measure % of all observations labelled correctly. (tp + tn) / (tp + fp + tn + fn). \n",
        "Don’t use it for text classification, b/c if classes are not balanced, doesn’t work well. \n",
        "Ex if mostly negatives, can do all negative, and get high accuracy because false negatives would just be a low%.\n",
        "**precision** tp/(tp+fp). % items detected that are tp over all labeled so. Which ones did it label correctly\n",
        "**recall** tp/(tp+fn) % items correctly id’d. Which ones did it miss \n",
        "**F-measure** $F_\\beta = (\\beta^2 +1) PR / (\\beta^2P + R)$. \n",
        "B is a weighting of recall and precision, if B >1 more weight on recall, = 1, equal weight, < 1 precision.\n",
        "$F1 = 2PR/(P+R)$.\n",
        "For multi-class evaluation, can use *macroaveraging*, where computer perf for each class, then average, \n",
        "Or *microaverageing* collect all decisions into a single matrix, and ocompute it for that.\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\"\n",
        "**Cross-validation** choose a number $k$ partition set into k “folds”. \n",
        "Use 1 for a test set, train on k-1 folds. Repeat k times with different ks as test sets.  \"\"\"\n",
        "\n",
        "slp_chapter4_9 = \"\"\"\n",
        "How well M(A) does over M(B) is \\delta(x), called effect size. \n",
        "Is statistically significant measured by non-parametric test.\n",
        "Use approximate randomization and bootstrap test.\n",
        "Paired test are tests where compare two sets of observations that can be aligned together. \n",
        "I.e pair performance of systems A and b on same x \n",
        "Boostrap test - draw large # of small samples\n",
        "\"\"\"\n",
        "slp_chapter4_10 = \"\"\" \n",
        "Representations harms - demean a social group. Ex. sentiment that is weighed by race. \n",
        "Toxcity classifiers can cause harm, b/c flag incorrectly mentions of minority identities. \n",
        "Base false positives. \n",
        "Release a **model card** on the training algorithms, training data sources, \n",
        "motivations and preprocessing, evaluation source, intended use, and model performance across different demographic groups.\n",
        " \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(f\"chapter 19_3: word length:{len(chapter19_3.split(' '))} charchters: {len(chapter19_3)}\")\n",
        "print(f\"chapter 19_4: word length:{len(chapter19_4.split(' '))} charchters: {len(chapter19_4)}\")\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "chapter 19_3: word length:289 charchters: 2022\n",
            "chapter 19_4: word length:389 charchters: 2853\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "caf4fd7f-d7c5-465f-839f-f8efcc0e0eff"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n**induction** is observation to rule. Might be wrong.\n**deduction** rule to case. Guranteed to be correct.\n\n**classification** are problems where output of ML algo is a finite set of vals.\n**regression** when ouput is a number\n\n**supervised learning* give agent input and ouput, agent learns map from i to o.\nOutput that categorizes inputs is a **label**, agent is predicting a label.\n\n**unsupervised learning** agent needs to learn without direct feedback.\nCommon task is **clustering**, finding a cluster of inputs.\n\n**reinforcement learning** agent learns from reinforcements, pos rewards or neg punishments.\nNeeds to figure out what actions caused the reinfforcement.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nSupervised learning, has a training set of $(x_i, y_i)$ pairs, trying to find $h(x)$\nthat approximates the real function $f(x)$ that creates the pairs.\n\n$h$ is the **hypothesis**, taken from **hypothesis space** $H$. \n$h$ can be called the **model** of the data, from **model class** $H$\n\n**ground truth** is the actual output $y_i$\n\nHypothesis space based on knowledge or exploring data, or just experimenting\n\n**consistent hypothesis** $h$ where every $x_i$ in train set has corresponding $h(x_i) = y_i$.\nIf continous values for $y_i$ use a **best-fit function** that produces $h(x_i)$ approx $y_i$.\n**generalizes** meas $h$ predicts the outputs in test set accurately. \n\nconsistent hypothesis != good hypothesis\n\nEval hypothesis space by bias and variance\n\n**bias** is how much $h$ deviates from expected val when averaged of different train sets.\nlinear functions have strong bias. If data has non-linear pattern, linear func can't represent it.\n**underfitting** is not being able to find pattern in data. contrast piecewise function has low bias.\n\n**variance** amount of change in $h$ wrt fluctuation in train set. \nEx lin func would have low variance, polynomial would have high variance\n**overfitting** too much weight on train set, perform poorly on new sets.\n\nTrade off between bias and variance. \nLow-bias hypothesis fit data well, more complicated vs. low-variance, simple, and generalize better.\n\nCan choose hypothesis most likely based on data\n$h^* = \\argmax P(h|data)$ == $h^* = \\argmax P(data|h)P(h)$\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n**Decision tree** func w/input vector utliple attribute values to output 1 value the decision\n\n**Boolean classification** only true or false outputs.\n\nTry to get a small consistent tree. Choose the attributes that are most discerning first (biggest impact)\nLeads to more shallow tree.\n\nEval a learning algo using **learning curve** - % correct on test vs training set size.\n\n**Entropy** measure of uncertainty for a RV. Info amount inverse with entropy.\n$$-\\sum_kP(v_k)\\log_2P(v_k)$$\nfor fair coin entropy = $-(0.5\\log_2 0.5 + .5\\log_2 0.5) = 1$ bits\nLoaded coin entropy = $-(0.99\\log_2 0.99 + 0.01\\log_2 0.01) = 0.08$ bits\n\nFor boolean rv entropy: $B(q) = - (qlog_2(q) + (1-q)log_2(1-q))$, where q is prob of true.\n\nAn attribute divides a training set by number of values, and each subset has pos and neg examples\nSo entropy remaining after testing for A is\nReaminder(A) = $\\sum_k=1^d \\frac{p_k + n_k}{p+n}B(\\frac{p_k}{p_k + n_k})\n\ninformatin gain is the reduction in entropy\nGain(A) = $B(\\frac{p}{p+N})$ - Remainder(A)\nWant to max gain. \n\nOverfitting liklihood increases w/number of attributes, decreases w/more training examples.\nBigger hypothesis space more likely to fit/overfit.\n\n**decision tree pruning** elimnates nodes that aren't relevant to reduce overfitting. \nIf a node w/ only leaf nodes only detects noise, its eliminated. Measure by information gain.\n\nUse significane test test to measure if enough info gain. Null hypohtesis that attribute not signficant.\nUse chi-squared test\n\nPruned trees do better than unpruned when a lot of noise in the data. Also more efficient and clear.\n\nCan't do early stopping because might have attributes that are informative in comboination. \n\nDealing with continous data, may want to use a **split point test** where test value of attribute\ncan do **equality test** for non continous non ordered data.\n\nDecision trees can be suboptimially acurate, and can take too long to run. Also unstable b/c new example can change whole tree.\nRandom forest can address some problems\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n**Stationary** is the assumption that time doesn't affect examples' probability distributin\nAlso assume they are independent. *iid* independent and identically distrbiuted\n\n**error rate** is % of time when hypothesis function isn't matching actual y\n\n**Hyperparameters** are parms for the model class, not just for an individual model.\nEx $\\chi^2$ threshold or degree.\n\nUse 3 data sets\n1. Training set \n2. Validation/development set to eval possible models, and pick one\n3. Test set for final test\n\nUse k-fold cross-validation to get more out of data. split into k subsets and perfrom k round of learning.\nbut use 1/k of data as validation set. Average scross across the round is the estimate.\nIf $k=n$ this is leave-one-out cross validation LOOCV\n\n**Model selection** is finding right hypohtesis space, \nwhile **optimatization/training** is finding best hypothesis.\n\nModel interpolates data if it fits all of the training set. Point at which it beings to overfit.\n\nIn ML try to minimize loss function instead of maxmize util.\n**Loss function** is the amount of util lost if guess is wrong\n$L(x, y, \\hat{y})=Utility(f(x)=y) - Utility(h(x)=\\hat{y})$\nor just $L(y, \\hat{y})$\n\n$L_1(y, \\hat{y}) = \\abs(y-\\hat{y})$\n$L_2(y, \\hat{y}) = (y-\\hat{y})^2$\n$L_{0/1}(y, \\hat{y}) =$ 0 only when $y = \\hat{y}$, 1 otherwise\n\n\nWant to do this over all inputs, would do over epxected generalized loss, \nbut don't know probabilities generally so estimate iwth **empirical loss*\n\nEmpericalLoss = $\\sum_{(x,y) \\in E}L(y, h(x)) \\frac{1}{N}$, where N is the size of example set\n\nwant to choose $h$ with lowert empirical loss\n\nreasons optiaml $h$ might be different:\n1. **Unrealizability** - if hypo space doesn't actually contain the true function $f$\n2. **Variance** - alog hypothesis varies with sets of examples. Vraince decrease w/# trainings if realizable\n3. **Noise** - $f$ might return different values for same input $x$\n4. If large hypospace, can't compute the best one for sure\n\n\nin large-scale learning loss affected mostly by limits of computation. \n\nCost(h) = EmpLoss(h) + $\\labmda$ Complexity(h)\n\n**Regularization** is process for punishing complexity. Complexity is measured by **regularization function**\n**feature selection** discards features that are irrelavent, kind of like in prunning\n\n**minimum descriptin length** is the hypohteis that minimizes the bits required to encode data\n\n**hand-tuning** approach to hyperparameters is setting hyperparameters based on past and figuing out new ones.\n**grid search** is more mechanical way to tune them. \n\nif a lot of values for hyperparams use random search.\n\n**Bayesian optimization** make hyperparameter choice as an ML problem\n\n**Population-based training (PBT)** trains models with different hyperparams in parallel, via random search\n2nd generation then chooses values based on 1st generation + mutation.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nif $h$ is really wrong, will figure that out after a few examples. \nIf consistent with many examples, unlikely to be way off so its *probably approximately correct*\n\n**approximately corre**ct if error of $h \\leq \\epsilon$ , w/$\\epsilon$ being small constant.\nCan find an $n$ where with with $n$ examples consistent hypothesis is appox correct. \nInside the $\\epsilion$-ball of $f$. If outside, $H_{bad}$\n\n**sample complexity** is the number of examples needed for approx correct $h$\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nlinear regression used to minimze loss  of  $h_w$ in linear functions\nLoss($h_w$) = $\\sum_{j=1}^N(y_j - (w_1x_j +w_0))^2$\n\nDo that when partial derivatives wrt $w_0$ and $w_1$ are 0.\nso\n$$w_1 = N(\\sum x_jy_j) - (\\sum x_j)(\\sum y_j) / [N(\\sum x_j^2) - (\\sum x_j)^2]$$\n$$w_0 = (\\sum y_j - w1(\\sum x_j)) / N $$\n\n**Gradient descent**, start at some point in weight space, get an estimate of gardient, and move twoards downhill.\nadjustment is $w_i \\leftarrow w_i - \\alpha \\frac{\\partial}{\\partial w_i} Loss(w)$\n$\\alpha is the learning rate or learning step$\n\nNeed to do for all examples. But can be very slow\n\n**epoch** is a step for all training examples\n\n**stochastic gradient descent** randomly selects some training examples. OK to do b/c\nstd error of mean gradient based on sqrt of N. So ok trade off for speed and error.\n\n**SGD** also usefule for online, called **online gradient descent**\n\n$Complexity(h_w) = \\sum_i \\abs(w_i)^q$\n\nL2 regulariztion mins the sum of squares. L1 makes sparse model\n\n**decision boundry** b/t 2 classes. In linear dimension it's a **linear separator**\n\n\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\nNB is generative b/c a class is sampled first from $P(c)$ and then word are generated from $P(d|c)$\nMost probable $c-hat$ given $d$ based on argmax $P(d|c) * P(c)$ where $P(c)$ is the prior probability of class $c$\nNaive Bayes Assumptions:\nPosition doesn’t matter\nProbabilities are independent given class $c$\nNaive Bayes and LM use log space b/c of underflow\nLinear classifiers use linear combination of inputs for classification. Ex: Naive Bayes, logistic regression\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \nMaximum Likelihood Estimate (MLE) - consider what % of docs in train set are of class $c$.\n$P(f_i | c) = P(w_i | c)$ is count(w_i) in docs w/class $c$\n$P(w_i | c) = \frac{count(w_i, c}{Sum_{w \\in V} count(w,c}\nProblem is that NB multiliplies all features liklihoods together, \nso if have a 0 probability for any term, probably of class drops to 0, even if have other evidence.\nCan do Laplace smoothing, adding 1 to the counts\nIgnore unknown words\nMight also ignore stop words, and frequent words (the, a)\n\n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \nBinary multinomial naive Bayes, remove all duplicate words. Ie. word occurs or not per doc. \nUse negation on every word after a logical negation. (ex. After didn’t, NOT_like, NOT_this.\n\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 \nConfusion matrix - table compare how algo does compared to gold labl. \nFalse negative, are system id as negative, but is positive (ex. Is spam)\nAccuracy is measure % of all observations labelled correctly. (tp + tn) / (tp + fp + tn + fn). \nDon’t use it for text classification, b/c if classes are not balanced, doesn’t work well. \nEx if mostly negatives, can do all negative, and get high accuracy because false negatives would just be a low%.\n**precision** tp/(tp+fp). % items detected that are tp over all labeled so. Which ones did it label correctly\n**recall** tp/(tp+fn) % items correctly id’d. Which ones did it miss \n**F-measure** $F_\beta = (\beta^2 +1) PR / (\beta^2P + R)$. \nB is a weighting of recall and precision, if B >1 more weight on recall, = 1, equal weight, < 1 precision.\n$F1 = 2PR/(P+R)$.\nFor multi-class evaluation, can use *macroaveraging*, where computer perf for each class, then average, \nOr *microaverageing* collect all decisions into a single matrix, and ocompute it for that.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n**Cross-validation** choose a number $k$ partition set into k “folds”. \nUse 1 for a test set, train on k-1 folds. Repeat k times with different ks as test sets.  \n\n## SLP Chapter 4.9 Statistical Significance Testing\n\nHow well M(A) does over M(B) is \\delta(x), called effect size. \nIs statistically significant measured by non-parametric test.\nUse approximate randomization and bootstrap test.\nPaired test are tests where compare two sets of observations that can be aligned together. \nI.e pair performance of systems A and b on same x \nBoostrap test - draw large # of small samples\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n \nRepresentations harms - demean a social group. Ex. sentiment that is weighed by race. \nToxcity classifiers can cause harm, b/c flag incorrectly mentions of minority identities. \nBase false positives. \nRelease a **model card** on the training algorithms, training data sources, \nmotivations and preprocessing, evaluation source, intended use, and model performance across different demographic groups.\n \n\n\n## Module 12 Lecture Notes\n Your summary here \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 = \"\"\" \n",
        "Naive Bayes is generative while logistic regression is discriminative\n",
        "Generative model give an input tests which of its models better first the input \n",
        "chooses that label.\n",
        "Discriminative model tries to just differntiate between the classes. Can be satisified by 1 feature.\n",
        "\n",
        "Generative model uses *likelihood* $P(d|c)$ and prior $P(c)$ to find\n",
        "$\\\\hat{c} = \\\\argmax_{c \\in C} P(d|c)P(c)$\n",
        "\n",
        "Discrimintive model tries to find P(c|d)\n",
        "\n",
        "Logistic regression solves classification task by learning a vector of \n",
        "**weights**, one for each feature, and a **bias term**. Weight is how important the feature is. \n",
        "Weight is pos if feature adds to likelihood input is in class or neg if reduces likelihood\n",
        "\n",
        "For decision, classifier uses the sum of the products of each $x_i * w_i$ plus the bias\n",
        "$z = (\\\\sum_{i=1}^n w_ix_i) + b$\n",
        "\n",
        "Since z can be any real number, it's not a probability. Use the **sigmoid** function to turn into one\n",
        "called **logistic function**\n",
        "\n",
        "$$\\\\sigma(Z) = \\\\frac{1}{1+ e^{-z}} = \\\\frac{1}{1+exp(-z)}$$\n",
        "\n",
        "$$P(y =1 ) = \\\\frac{1}{1 + exp(-(w \\\\cdot x + b))}$$\n",
        "\n",
        "**Decision boundry** is the min probability at which we classify if input belongs to a class or not.\n",
        "\n",
        "**period disambiguation** figure out if \".\" is end of sentence or part of word.\n",
        "\n",
        "**feature templates** are abstract specs creates automatically by going through train set.\n",
        "**representation learning** uses unsupervised learning for auto feature learning. \n",
        "\n",
        "Naive Bayes strong assumption of conditional indepdence. Logistic regression more sensitive\n",
        "to correlated features, distributes weights amont them. \n",
        "\n",
        "NB works well/better on small datasets. NB is faster to train. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" \n",
        "Logistic regression produces a $\\\\hat{y}$ that is an estimate of the real $y$.\n",
        "distance $\\\\hat(y)-y$ is called the **loss (or cost) function**\n",
        "\n",
        "use **gradient descent** algo to optimally update weights to minimize loss function.\n",
        " \"\"\"\n",
        "slp_chapter5_3 = \"\"\"\n",
        "**conditional maximum likelihood estimate** choose the weigtht vector and intcerpet that \n",
        "max the log probability of the gold label in the train data for an input. \n",
        "\n",
        "**cross-entropy loss** is the negative log likihood loss\n",
        "\n",
        "try to maximize $p(y | x) = \\\\hat{y}^y (1- \\\\hat{y})^(1-y)$\n",
        "\n",
        "which in log form is\n",
        "\n",
        "$\\\\log p(y|x) = log[\\\\hat{y}^y (1- \\\\hat{y})^(1-y)]$\n",
        "\n",
        "$\\\\log p(y|x) = ylog\\\\hat{y} + (1-y)log(1-\\\\hat{y})$\n",
        "\n",
        "loss function is the negative of that \n",
        "$L_{CE}(\\\\hat{y}, y) = -[ylog\\\\hat{y} + (1-y)log(1-\\\\hat{y})]$\n",
        "\n",
        "w/ sigmoid function:\n",
        "\n",
        "$L_{CE}(\\\\hat{y}, y) = -[ylog\\\\sigma(w \\\\cdot x + b) + (1-y)log(1-\\\\sigma(w \\\\cdot x + b))]$\n",
        "\n",
        "Simplifies to 1 side of the equation or the other for binary classificaiton, since y is either 1 or 0\n",
        "Want to minimize loss\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "Gradient descent tries to find where in $\\\\theta$ function is rising most and \n",
        "going in the opposite way.\n",
        "\n",
        "trying to find:\n",
        "$$\\\\hat{\\\\theta} = \\\\argmin_{\\\\theta} \\\\frac{1}{m} \\\\sum_{i=1}^m L_{CE}(f(x_i;w), y_i)$$\n",
        "\n",
        "loss function is convex in logistic regresison so always guranteed to find min.\n",
        "Not true in non-convex function.\n",
        "\n",
        "Find the gradient of the loss function at some value for $w$. If slope is negative\n",
        "want to make $w$ bigger. If slope is positive, want to make $w$ smaller. \n",
        "\n",
        "Amount to move $w$ is the slope $\\\\frac{d}{dw}L(f(x;w), y)$ times the learning rate $\\\\eta$\n",
        "\n",
        "For actual weight vectors, would have a partial for each feature. \n",
        "From graident get a vector of partials for each, how much change in a given weight would influnce total loss\n",
        "\n",
        "Derivative for an observaiton x is = $[\\\\sigma(w \\\\cdot x + b) -y]x_j$\n",
        "\n",
        "Updating $\\\\theta$ is then\n",
        "$$\\\\theta_{t+1} = \\\\theta_{t} - \\\\eta \\\\Delta L(f(x;\\\\theta),y)$$\n",
        "\n",
        "$\\\\eta$ is a hyperparmeter. If too big will miss the minimum. Too small takes too long\n",
        "Common to decrease $\\\\eta$ with iterations.\n",
        "\n",
        "Stochastic gradient descent moves weights per example, can be choppy.\n",
        "\n",
        "**batch training* gradient is calculated based on whole dataset. Good estimate, but takes longer\n",
        "\n",
        "**mini-batch** uses a subset of examples < whole. is happy medium.\n",
        "Loss function is the average loss for each example, and gradient is \n",
        "the average of the per-example gradients ==\n",
        "the sum of the loss derivatives for m examples divided by m.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "**overfitting* happens when weights match too perfectly with train set.\n",
        "Could be a problem if specious correlation. \n",
        "\n",
        "Use **regularization* to avoid ovefitting, which penalizes large weights\n",
        "$$\\\\hat{\\\\theta} = \\\\argmax_{\\\\theta} \\\\sum_{i=1}^m \\\\log P(y_i|x_i) - \\\\alpha R(\\\\theta)$$\n",
        "\n",
        "**L2 regularization** is quadratic. The L2 norm is the euclidean distance of $\\\\theta$ from the origin.\n",
        "So R(\\\\theta) = \\\\sum_{j=1}^n \\\\theta_j^2\n",
        "\n",
        "L1 regulaizaiton uses L1 norm like Manhattan distance, which is based on the sum aboslute values\n",
        "\n",
        "L2 perfes small weights, lots of them. L1 Perfers sparce vectos, but ok with larger weights.\n",
        "L1 -> Lapalace, L2->Gaussian. \n",
        "\n",
        "\"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "if have more than 2 classes, **multinomial logistic regression* or **softmax regression**\n",
        "Softmax function is a gneralization of sigmoid, used to calculate $p(y = c |x)$\n",
        "\n",
        "softmax = $\\\\frac{exp(z_i)}{\\\\sum_{j=1}^k exp(z_j)}$\n",
        "\n",
        "Have a separate weight for each feature for each class\n",
        "\n",
        "Loss function is sum of logs of the classes so loss is\n",
        "$$ - \\\\sum_{k=1}^K \\{y ==k\\} \\\\log \\\\frac{exp(w_k \\cdot x + b_k)}{\\\\sum_{j=1}^K w_k \\cdot x + b_k} $$\n",
        "\n",
        "One-hot vector is a vector with one value \"1\" and the rest 0.\n",
        "\n",
        "since the formula above is only true when y==k, can just take out of the sum\n",
        " \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" \n",
        "**Feedfoward network** - computation goes from one layer to the next\n",
        "**deep learning** because have many layers\n",
        "\n",
        "Neural networks strong than logistic regression. Doesn't used hand made features.\n",
        "\n",
        "**computation unit** is the building block in a NN. Function that takes in real and outputs osmething\n",
        "$z = w \\cdot x + b$\n",
        "\n",
        "a unit applies some non-linear function $f$ to that $z$. \n",
        "**Activation** is the output of $f$. \n",
        "\n",
        "$f$ might be sigmoid, tanh, or rectified linear (ReLU). \n",
        "\n",
        "Tanh use more often than sigmoid. Range is [-1, 1]\n",
        "$y = \\\\frac{\\\\exp^z - \\\\exp^{-z}}{\\\\exp^z + \\\\exp^{-z}}$\n",
        "\n",
        "\n",
        "ReLU is simplest activation function\n",
        "$y = \\\\max(z, 0)$\n",
        "\n",
        "Tanh is easy to differentaite, and outputs outliers close to the mean\n",
        "ReLU is close to linear.\n",
        "\n",
        "high $z$ results in y that are saturated (close to1) in Tanh and sigmoid .\n",
        "Derivs of high value in tanh and sigmoid are close to 0 which can cause problems in learning.\n",
        "**vanishing graident problem** 0ish values cause problems b/c \n",
        "multiply derivatives/gradients b/t layers and small gradients cause small error signals.\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_2 = \"\"\" \n",
        "**perceptron** does not have linear activation function.\n",
        "Can't build a XOR with perceptron.\n",
        "\n",
        "**decision boundry** in 2d space is a line. Everyone one side is 0, other side is 1.\n",
        "XOR is an example of problem that is not **linearly separable**\n",
        "\n",
        "The hidden layer of a newrok creates a representation. NN can auto form userful representations. \n",
        "\n",
        "Network formed of layers of linear units can reduce to single layer of linear units.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_3 = \"\"\"\n",
        "**Feedforward network** is multilayer, units connects w/o cycles. Never pass back outputs\n",
        "Called feedforward called multi-layer perceptrons but not perceptrons b/c perceptrons are linear\n",
        "\n",
        "3 types of units:\n",
        "1. input\n",
        "2. hiddent\n",
        "3. output\n",
        "\n",
        "Hidden layers has hidden units that do the dot product+activation function\n",
        "Typically every layer is **fully-connected** so that inputs to a layer are all of \n",
        "outputs from the previous layer\n",
        "\n",
        "Combine weights for all units in a hidden layer into one matrix **W** and vector **b**\n",
        "where W_{ji} is the weight from $i$ input to $j$ unit.\n",
        "\n",
        "Then need to multiply input vectors times **W** add bias vector and apply activation func\n",
        "so output of hidden layer is vector h where:\n",
        "$h = \\\\sigma(Wx + b)\n",
        "\n",
        "activation function is applied element wise to the elements in the vector \n",
        "\n",
        "The hidden layer creates a representation of the input. Output layer calcuates final output\n",
        "can be real or class. Output node might be one value, or vector of probabilities for all the classes.\n",
        "\n",
        "Hidden layer acts as input to output layer. Output layer has weight matrix **U**\n",
        "where $U_{ij}$ is the weight of the input from hidden unit $j$ into unit $i$ in the output layer\n",
        "$z = Uh$ which then needs to be normalized using softmax\n",
        "so $y = softmax(z)$\n",
        "\n",
        "2 layer network - count hidden and output, but not input. \n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_4 = \"\"\" \n",
        "Neural networks don't use hand chose features. Instead use embeddings as inputs.\n",
        "*pretraining* is using another algorithm to learn an embededed representation of the input.\n",
        "\"\"\"\n",
        "slp_chapter7_5 = \"\"\"\n",
        "Neural language models can have longer histories, generalize better, more accurate. \n",
        "But also complex, slower to train, harder to interpret. \n",
        "\n",
        "**Forward inference/decoding** is forward pass in NN to get probability of possible outputs.\n",
        "\n",
        "Represent each of N context words as 1-hot vecto. \n",
        "\n",
        "1. Mutliply the 1hvs by weights in embedding matrix E. E has col per word. column has d dimensions, so dimenison is d x |V|.\n",
        "The mutlplication select the relevant column, so resulting embedding layer is d x 1\n",
        "embeddings grouped as embedding layer \n",
        "2. Then e multiply by W and pass to activaiton function to get layer $h$\n",
        "3. then mutiply $h$ by $U$\n",
        "4. Then apply softmax, so the output is probabilities.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_6 = \"\"\"\n",
        "to train feedforward neural net need to use a loss function like cross-entropy loss\n",
        "and can use gradient descent to minimize loss function\n",
        "\n",
        "Hard to determine gradient b/c partial deriv of a weight in early layer since loss \n",
        "comes much later. Use **error backpropagation/backward differentiation**\n",
        "\n",
        "If binary loss function is:\n",
        "$$L_{CE}(\\\\hat{y}, y) = -y [y \\\\log \\\\hat{y} + (1- y) \\\\log(1-\\\\hat(y)]$$\n",
        "\n",
        "if multinomial it's\n",
        "$$L_{CE}(\\\\hat{y}, y) = - \\\\sum_{i=1}^C y_i \\\\log \\\\hat{y_i}$$\n",
        "\n",
        "if hard classfication where only 1 class is right\n",
        "$$L_{CE}(\\\\hat{y}, y) = - \\\\log \\\\hat{y_i} = -\\\\log \\\\frac{\\\\exp(z_i)}{\\\\sum_{j=1}^K \\\\exp(z_j)}$$ i is correct class\n",
        "\n",
        "\n",
        "To figure out derivative:\n",
        "\n",
        "**Computation graphs** represent process of computing by breaking down into different operations,\n",
        "every operation is an node in the graph\n",
        "\n",
        "**Backward pass** uses **chain rule**, for f(x) = u(v(x)):\n",
        "$$\\\\frac{df}{dx} = \\\\frac{du}{dv} * \\\\frac{dv}{dx}$$\n",
        "\n",
        "So nodes pass gradients back from the final node to all nodes\n",
        "\n",
        "Compute partials from right to left, and apply chain rule. Start downstream and go up.\n",
        "When go up, derivative is gradient of output (later layer) wrt input (earlier layer)\n",
        "\n",
        "Neural networks have non-convex optimizations. Need to use small random numbers for all the weights.\n",
        "Also use a mean of 0 and 1 variance.\n",
        "\n",
        "**dropout** is used to prevent overfitting, it drops some units during training, randomly.\n",
        "\n",
        "Need to tune hyperparamenters, like the learning rate, batch size, and architecture.\n",
        "Weights and bias are the parms.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_7 = \"\"\" \n",
        "Neural language model has parms $\\\\theta = E, W, U, b$.\n",
        "\n",
        "Can **freeze** embedding layer, holding it constant if use pretraining. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0a759e50-3e92-4bf7-edfa-6f2b8b946a4e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nNaive Bayes is generative while logistic regression is discriminative\nGenerative model give an input tests which of its models better first the input \nchooses that label.\nDiscriminative model tries to just differntiate between the classes. Can be satisified by 1 feature.\n\nGenerative model uses *likelihood* $P(d|c)$ and prior $P(c)$ to find\n$\\hat{c} = \\argmax_{c \\in C} P(d|c)P(c)$\n\nDiscrimintive model tries to find P(c|d)\n\nLogistic regression solves classification task by learning a vector of \n**weights**, one for each feature, and a **bias term**. Weight is how important the feature is. \nWeight is pos if feature adds to likelihood input is in class or neg if reduces likelihood\n\nFor decision, classifier uses the sum of the products of each $x_i * w_i$ plus the bias\n$z = (\\sum_{i=1}^n w_ix_i) + b$\n\nSince z can be any real number, it's not a probability. Use the **sigmoid** function to turn into one\ncalled **logistic function**\n\n$$\\sigma(Z) = \\frac{1}{1+ e^{-z}} = \\frac{1}{1+exp(-z)}$$\n\n$$P(y =1 ) = \\frac{1}{1 + exp(-(w \\cdot x + b))}$$\n\n**Decision boundry** is the min probability at which we classify if input belongs to a class or not.\n\n**period disambiguation** figure out if \".\" is end of sentence or part of word.\n\n**feature templates** are abstract specs creates automatically by going through train set.\n**representation learning** uses unsupervised learning for auto feature learning. \n\nNaive Bayes strong assumption of conditional indepdence. Logistic regression more sensitive\nto correlated features, distributes weights amont them. \n\nNB works well/better on small datasets. NB is faster to train. \n\n\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nLogistic regression produces a $\\hat{y}$ that is an estimate of the real $y$.\ndistance $\\hat(y)-y$ is called the **loss (or cost) function**\n\nuse **gradient descent** algo to optimally update weights to minimize loss function.\n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n**conditional maximum likelihood estimate** choose the weigtht vector and intcerpet that \nmax the log probability of the gold label in the train data for an input. \n\n**cross-entropy loss** is the negative log likihood loss\n\ntry to maximize $p(y | x) = \\hat{y}^y (1- \\hat{y})^(1-y)$\n\nwhich in log form is\n\n$\\log p(y|x) = log[\\hat{y}^y (1- \\hat{y})^(1-y)]$\n\n$\\log p(y|x) = ylog\\hat{y} + (1-y)log(1-\\hat{y})$\n\nloss function is the negative of that \n$L_{CE}(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n\nw/ sigmoid function:\n\n$L_{CE}(\\hat{y}, y) = -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n\nSimplifies to 1 side of the equation or the other for binary classificaiton, since y is either 1 or 0\nWant to minimize loss\n\n\n\n## SLP Chapter 5.4 Gradient Descent\n\nGradient descent tries to find where in $\\theta$ function is rising most and \ngoing in the opposite way.\n\ntrying to find:\n$$\\hat{\\theta} = \\argmin_{\\theta} \\frac{1}{m} \\sum_{i=1}^m L_{CE}(f(x_i;w), y_i)$$\n\nloss function is convex in logistic regresison so always guranteed to find min.\nNot true in non-convex function.\n\nFind the gradient of the loss function at some value for $w$. If slope is negative\nwant to make $w$ bigger. If slope is positive, want to make $w$ smaller. \n\nAmount to move $w$ is the slope $\\frac{d}{dw}L(f(x;w), y)$ times the learning rate $\\eta$\n\nFor actual weight vectors, would have a partial for each feature. \nFrom graident get a vector of partials for each, how much change in a given weight would influnce total loss\n\nDerivative for an observaiton x is = $[\\sigma(w \\cdot x + b) -y]x_j$\n\nUpdating $\\theta$ is then\n$$\\theta_{t+1} = \\theta_{t} - \\eta \\Delta L(f(x;\\theta),y)$$\n\n$\\eta$ is a hyperparmeter. If too big will miss the minimum. Too small takes too long\nCommon to decrease $\\eta$ with iterations.\n\nStochastic gradient descent moves weights per example, can be choppy.\n\n**batch training* gradient is calculated based on whole dataset. Good estimate, but takes longer\n\n**mini-batch** uses a subset of examples < whole. is happy medium.\nLoss function is the average loss for each example, and gradient is \nthe average of the per-example gradients ==\nthe sum of the loss derivatives for m examples divided by m.\n\n\n\n## SLP Chapter 5.5 Regularization\n\n**overfitting* happens when weights match too perfectly with train set.\nCould be a problem if specious correlation. \n\nUse **regularization* to avoid ovefitting, which penalizes large weights\n$$\\hat{\\theta} = \\argmax_{\\theta} \\sum_{i=1}^m \\log P(y_i|x_i) - \\alpha R(\\theta)$$\n\n**L2 regularization** is quadratic. The L2 norm is the euclidean distance of $\\theta$ from the origin.\nSo R(\\theta) = \\sum_{j=1}^n \\theta_j^2\n\nL1 regulaizaiton uses L1 norm like Manhattan distance, which is based on the sum aboslute values\n\nL2 perfes small weights, lots of them. L1 Perfers sparce vectos, but ok with larger weights.\nL1 -> Lapalace, L2->Gaussian. \n\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\nif have more than 2 classes, **multinomial logistic regression* or **softmax regression**\nSoftmax function is a gneralization of sigmoid, used to calculate $p(y = c |x)$\n\nsoftmax = $\\frac{exp(z_i)}{\\sum_{j=1}^k exp(z_j)}$\n\nHave a separate weight for each feature for each class\n\nLoss function is sum of logs of the classes so loss is\n$$ - \\sum_{k=1}^K \\{y ==k\\} \\log \\frac{exp(w_k \\cdot x + b_k)}{\\sum_{j=1}^K w_k \\cdot x + b_k} $$\n\nOne-hot vector is a vector with one value \"1\" and the rest 0.\n\nsince the formula above is only true when y==k, can just take out of the sum\n \n\n## SLP Chapter 7.1 Units\n \n**Feedfoward network** - computation goes from one layer to the next\n**deep learning** because have many layers\n\nNeural networks strong than logistic regression. Doesn't used hand made features.\n\n**computation unit** is the building block in a NN. Function that takes in real and outputs osmething\n$z = w \\cdot x + b$\n\na unit applies some non-linear function $f$ to that $z$. \n**Activation** is the output of $f$. \n\n$f$ might be sigmoid, tanh, or rectified linear (ReLU). \n\nTanh use more often than sigmoid. Range is [-1, 1]\n$y = \\frac{\\exp^z - \\exp^{-z}}{\\exp^z + \\exp^{-z}}$\n\n\nReLU is simplest activation function\n$y = \\max(z, 0)$\n\nTanh is easy to differentaite, and outputs outliers close to the mean\nReLU is close to linear.\n\nhigh $z$ results in y that are saturated (close to1) in Tanh and sigmoid .\nDerivs of high value in tanh and sigmoid are close to 0 which can cause problems in learning.\n**vanishing graident problem** 0ish values cause problems b/c \nmultiply derivatives/gradients b/t layers and small gradients cause small error signals.\n\n\n## SLP Chapter 7.2 The XOR problem\n \n**perceptron** does not have linear activation function.\nCan't build a XOR with perceptron.\n\n**decision boundry** in 2d space is a line. Everyone one side is 0, other side is 1.\nXOR is an example of problem that is not **linearly separable**\n\nThe hidden layer of a newrok creates a representation. NN can auto form userful representations. \n\nNetwork formed of layers of linear units can reduce to single layer of linear units.\n\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n**Feedforward network** is multilayer, units connects w/o cycles. Never pass back outputs\nCalled feedforward called multi-layer perceptrons but not perceptrons b/c perceptrons are linear\n\n3 types of units:\n1. input\n2. hiddent\n3. output\n\nHidden layers has hidden units that do the dot product+activation function\nTypically every layer is **fully-connected** so that inputs to a layer are all of \noutputs from the previous layer\n\nCombine weights for all units in a hidden layer into one matrix **W** and vector **b**\nwhere W_{ji} is the weight from $i$ input to $j$ unit.\n\nThen need to multiply input vectors times **W** add bias vector and apply activation func\nso output of hidden layer is vector h where:\n$h = \\sigma(Wx + b)\n\nactivation function is applied element wise to the elements in the vector \n\nThe hidden layer creates a representation of the input. Output layer calcuates final output\ncan be real or class. Output node might be one value, or vector of probabilities for all the classes.\n\nHidden layer acts as input to output layer. Output layer has weight matrix **U**\nwhere $U_{ij}$ is the weight of the input from hidden unit $j$ into unit $i$ in the output layer\n$z = Uh$ which then needs to be normalized using softmax\nso $y = softmax(z)$\n\n2 layer network - count hidden and output, but not input. \n\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n \nNeural networks don't use hand chose features. Instead use embeddings as inputs.\n*pretraining* is using another algorithm to learn an embededed representation of the input.\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\nNeural language models can have longer histories, generalize better, more accurate. \nBut also complex, slower to train, harder to interpret. \n\n**Forward inference/decoding** is forward pass in NN to get probability of possible outputs.\n\nRepresent each of N context words as 1-hot vecto. \n\n1. Mutliply the 1hvs by weights in embedding matrix E. E has col per word. column has d dimensions, so dimenison is d x |V|.\nThe mutlplication select the relevant column, so resulting embedding layer is d x 1\nembeddings grouped as embedding layer \n2. Then e multiply by W and pass to activaiton function to get layer $h$\n3. then mutiply $h$ by $U$\n4. Then apply softmax, so the output is probabilities.\n\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\nto train feedforward neural net need to use a loss function like cross-entropy loss\nand can use gradient descent to minimize loss function\n\nHard to determine gradient b/c partial deriv of a weight in early layer since loss \ncomes much later. Use **error backpropagation/backward differentiation**\n\nIf binary loss function is:\n$$L_{CE}(\\hat{y}, y) = -y [y \\log \\hat{y} + (1- y) \\log(1-\\hat(y)]$$\n\nif multinomial it's\n$$L_{CE}(\\hat{y}, y) = - \\sum_{i=1}^C y_i \\log \\hat{y_i}$$\n\nif hard classfication where only 1 class is right\n$$L_{CE}(\\hat{y}, y) = - \\log \\hat{y_i} = -\\log \\frac{\\exp(z_i)}{\\sum_{j=1}^K \\exp(z_j)}$$ i is correct class\n\n\nTo figure out derivative:\n\n**Computation graphs** represent process of computing by breaking down into different operations,\nevery operation is an node in the graph\n\n**Backward pass** uses **chain rule**, for f(x) = u(v(x)):\n$$\\frac{df}{dx} = \\frac{du}{dv} * \\frac{dv}{dx}$$\n\nSo nodes pass gradients back from the final node to all nodes\n\nCompute partials from right to left, and apply chain rule. Start downstream and go up.\nWhen go up, derivative is gradient of output (later layer) wrt input (earlier layer)\n\nNeural networks have non-convex optimizations. Need to use small random numbers for all the weights.\nAlso use a mean of 0 and 1 variance.\n\n**dropout** is used to prevent overfitting, it drops some units during training, randomly.\n\nNeed to tune hyperparamenters, like the learning rate, batch size, and architecture.\nWeights and bias are the parms.\n\n\n\n## SLP Chapter 7.7 Training the neural language model\n \nNeural language model has parms $\\theta = E, W, U, b$.\n\nCan **freeze** embedding layer, holding it constant if use pretraining. \n\n\n## Module 13 Lecture Notes\n Your summary here \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 = \"\"\"\n",
        "Feedforward networks still have limited context. \n",
        "\n",
        "Language modesl assin conditional probability to all possible words,\n",
        "and can use the chain rule to get probability to a sequnce by using the conditional proba.\n",
        "\n",
        "Perplexity is inverse of probability for a test word. Can chain together again with product\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter9_2 = \"\"\" \n",
        "Recurrent neural network has a cycle within the network. A unit may have it's own output as an input\n",
        "**Elman netowrks** are simple RNN. \n",
        "\n",
        "Start with an input at certain time **x_t** \n",
        "Link output of hidden layer to itself at next time step. \n",
        "\n",
        "So need to get $h_t$, mutiply $x_$ by $W$, and $h_{t-1} with $U$$, \n",
        "add these together and apply activation function $g$. \n",
        "Then apply weights $V$ to get value to feed into $f$, the activation function for ouptut y\n",
        "$$h_t = g(Uh_{t-1} + Wx_t)$$\n",
        "$$y_t = f(Vh_t)$$\n",
        "\n",
        "$W$ is $d_h x d_in$, U is $d_h x d_h$, and V is $d_out x d_h$\n",
        "\n",
        "Need to use backpropagation through time b/c hidden layer affects loss of current layer and next layer\n",
        "or instead can unrol the RNN into a feedforward computation graph.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter9_3 = \"\"\"\n",
        "RNN Language Models don't have limited context problem, b/c hidden layer can represent infor about all words\n",
        "\n",
        "**teacher forcing** ignore prediction and use actual next word an input for the next-next word\n",
        "\n",
        "**Weight tying** use $E=V$, same embeddings for input and softmax. so final hidden layer is $d_h$.\n",
        "Improves perplexity, and number of parameters needed in model.\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\"\n",
        "**Distributional hypothesis** words with similar meanings appear in same env.\n",
        "\n",
        "**representation learning** - is ML auto learn of good reprsentation of text. \n",
        "Is **self-supervised**\n",
        "\n",
        "For a set of related words like **mouse** and **mice**, one form serves as the **lemma* or **citation form**\n",
        "The other versions of the word are **wordforms**\n",
        "\n",
        "**word sense** is different meanings of the word\n",
        "**polysemous** have multiple meanings\n",
        "**word sense disambiguation** is figuring out which meaning of a word is being used\n",
        "\n",
        "**propositional meaning** words are synonyms if can sub them in any sentence w/o changing truth of the sentence\n",
        "**principle of contrast** different forms always have some different meaning\n",
        "\n",
        "**similarity** delas with relations b/t words instead of meanings.\n",
        "**relatedness/association** - relation b/t words beyond similarity. Ex. Coffee and cup.\n",
        "**semantic field** - words in  set that are in teh same domain ex. hospital, restaruants\n",
        "\n",
        "**semantic frame** - set of words that indicate the perspectives/participants. Ex. Buyer, seller, goods.\n",
        "\n",
        "**connotation** is the affective/emotional meaning of a word.\n",
        "**sentiment** is the pos/neg determination of language. \n",
        "\n",
        "Affect rated on:\n",
        "1. **valence** how pleasent something is\n",
        "2. **arousal** how intense the emoition is\n",
        "3. **dominance** how much control the cause has\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\" \n",
        "words that have similar neghborhing word are similar.\n",
        "\n",
        "**embeddings** are vector representation of words in multi-dimensional space\n",
        "\n",
        "Advantage of vector semantics is that don't have to have exact wod as in n-grams,\n",
        "b/c can use similar meanings. \n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_3 = \"\"\" \n",
        "**term-document** matix each row represent a word in vocab, while column is a document\n",
        "a cell is number of times a word occurs in a doc\n",
        "\n",
        "In term-document matrix, vectors (columns) are of dimensionsality $|V|$, size of vocab\n",
        "\n",
        "Two docs are similar if their column vectors are similar\n",
        "\n",
        "**information retrieval** is trying to find document *d* from all of the *D* docs based on query\n",
        "query can be a vector of length *|V*|\n",
        "\n",
        "can use **row vector**, grouping the dimensions to find meaning of words\n",
        "similar words have similar vectors, occur in similar documents\n",
        "\n",
        "**term-term** or **word-word** or **term-context** matrix is word by word matrix.\n",
        "Dimensionality is $|V| * |V|$. How often a target row word, co-occurs with a context colum nword in a corpus.\n",
        "Context can be a doc or a word window (+/-).\n",
        "\n",
        "Most of the co-occurance numbers are 0s, so the vectors are sparse. \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_4 = \"\"\"\n",
        "**cosine** of angle between vectors is most often used to determine the similarity\n",
        "Uses  the dot product of the two vectors. High when have large values in the same dimensions\n",
        "If have 0s in differnt dimensions will have lower docut product.\n",
        "But dot product is biased toward longer vectors. \n",
        "Vector length: $$|v| = \\\\sqrt{\\\\sum_{i=1}^N v_i^2}$$\n",
        "More frequent words occur more often, so have denser -> longer vectors\n",
        "Use the normalized dot product instead to account for that.\n",
        "$$a \\cdot b = |a||b|\\\\cos \\\\theta$$\n",
        "$$\\\\frac {a \\cdot b}{|a||b|} = \\\\cos \\\\theta$$\n",
        "$$= \\\\frac{\\\\sum_{i=1}^N v_iw_i}{\\\\sqrt{\\\\sum_{i=1}^N v_i^2} \\\\sqrt{\\\\sum_{i=1}^N w_i^2}}$$\n",
        "\n",
        "can also pre-normalize, by dividing the vector by it's length, and then dot product is the cosine.\n",
        "\n",
        "cosine range is [-1, 1], but since counts are $\\geq 0$, cosine range is [0,1]\n",
        "\n",
        "**tf-idf** term frequency - document frequency. Document frequency is number of document a term apperas in.\n",
        "Different rom collection frequency, totatl number of times it appears across all D.\n",
        "\n",
        "inverse document frequence $N/df_t$. Total document / number of docs that have $t$.\n",
        "So fewer docs with $t$ higher weight. \n",
        "so then $idf_t = \\\\log_{10} (\\\\frac{N}{df_t})$\n",
        "and tf-idf is: $$\\\\log_{10}((count(t,d) + 1) * \\\\log_{10} (\\\\frac{N}{df_t}) $$\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_8 = \"\"\" \n",
        "**embeddings** are short and desne vectors. dimensions ranges from 50-1000 instead of vocab size or documents count\n",
        "They are dense in that most are real numbers. Not clear interpretation of the dimensions.\n",
        "\n",
        "Word2vec have static embeddings that are fixed for every word.\n",
        "Uses a binary classifier to decide if a word likely to show up near another word\n",
        "and using the weights as embeddings. \n",
        "\n",
        "Self-supervision, use text as the supervised training data. \n",
        "\n",
        "**skip-gram with negative sampling (SGNS)**:\n",
        "1. Target word and context word are positive samples\n",
        "2. Other random words are negative samples\n",
        "3. Logistic regression to train classifier\n",
        "4. Weights are now the embeddings\n",
        "\n",
        "Trying to determine if given a $(w,c)$ of target word and context, the probability\n",
        "that $c$ is actually context for the target $w$. So $P(+ | w,c)$\n",
        "\n",
        "To determine the probability, compare the embedding vectors of context and target\n",
        "by taking the dot prouct of the two vectors, and then apply the sigmoid function\n",
        "$$P(+ | w,c ) = \\\\sigma (c \\\\cdot w) = \\\\frac{1}{1 + \\\\exp(-c \\\\cdot w)}$$\n",
        "for negative case can just find $\\\\sigma(-c \\\\cdot w)$\n",
        "\n",
        "This is for one word, for the full context, assume that context words are indepenednt, and so \n",
        "take the product of their probabilities (via sigmoid). Take the log to avoid underflow. \n",
        "\n",
        "Learning embeddings\n",
        "Need to create negative examples for each positive example. # negs is determined by paramater $k$\n",
        "Noise words are chose by weighted probability with $\\\\alpha=.75$ often as the weight.\n",
        "\n",
        "$P_{\\\\alpha}(w) = \\\\frac{count(w)^{\\\\alpha}}{\\\\sum_{w'}count(w')^{\\\\alpha}}$\n",
        "\n",
        "Use stocahstic gradient descent to minimize loss, which is assign high prob to actaul context, and low to all neg examples\n",
        "\n",
        "word2vec has problems with unknwon words. Fasttext deals with by using subwords\n",
        "where it takes an n-gram of the word via chars, and learns embeddings using the n-grams\n",
        "and summing the embeddings of the constitutents\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_10 = \"\"\" \n",
        "Size of context windwow affects representaiton. Shorter = mo syntatctic.\n",
        "Longer context, words are topical but not similar. Ex: 2 window lead to similar schoo lnames\n",
        "5 window led to word from the same series. \n",
        "\n",
        "**first-order co-occurence** if words are near one another\n",
        "**second-order co-occurence* if have similar neighbors\n",
        "\n",
        "Can use parallelograms to solve some analogies. With a, b, a* can find x by\n",
        "$x = a^* -a + b$ with x that results in the smallest distance between a* and x\n",
        "\"\"\"\n",
        "slp_chapter6_11 = \"\"\" \n",
        "**allocational harm** is allocating resources unfairly to different groups.\n",
        "Could be a potential negative consequnce of embeddings.\n",
        "\n",
        "They tend to amplify bias.\n",
        "\n",
        "Can also cause **representation harm** - harm of demeaning/ignoring socail groups\n",
        " \"\"\"\n",
        "slp_chapter6_12 = \"\"\" \n",
        "Eval performance of vector models. Metric of similarity, \n",
        "comparing similartiy determined by algo and by human lables.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8d21ecdc-8843-45e0-a093-92b5c8042bbd"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\nFeedforward networks still have limited context. \n\nLanguage modesl assin conditional probability to all possible words,\nand can use the chain rule to get probability to a sequnce by using the conditional proba.\n\nPerplexity is inverse of probability for a test word. Can chain together again with product\n\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n \nRecurrent neural network has a cycle within the network. A unit may have it's own output as an input\n**Elman netowrks** are simple RNN. \n\nStart with an input at certain time **x_t** \nLink output of hidden layer to itself at next time step. \n\nSo need to get $h_t$, mutiply $x_$ by $W$, and $h_{t-1} with $U$$, \nadd these together and apply activation function $g$. \nThen apply weights $V$ to get value to feed into $f$, the activation function for ouptut y\n$$h_t = g(Uh_{t-1} + Wx_t)$$\n$$y_t = f(Vh_t)$$\n\n$W$ is $d_h x d_in$, U is $d_h x d_h$, and V is $d_out x d_h$\n\nNeed to use backpropagation through time b/c hidden layer affects loss of current layer and next layer\nor instead can unrol the RNN into a feedforward computation graph.\n\n\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\nRNN Language Models don't have limited context problem, b/c hidden layer can represent infor about all words\n\n**teacher forcing** ignore prediction and use actual next word an input for the next-next word\n\n**Weight tying** use $E=V$, same embeddings for input and softmax. so final hidden layer is $d_h$.\nImproves perplexity, and number of parameters needed in model.\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n**Distributional hypothesis** words with similar meanings appear in same env.\n\n**representation learning** - is ML auto learn of good reprsentation of text. \nIs **self-supervised**\n\nFor a set of related words like **mouse** and **mice**, one form serves as the **lemma* or **citation form**\nThe other versions of the word are **wordforms**\n\n**word sense** is different meanings of the word\n**polysemous** have multiple meanings\n**word sense disambiguation** is figuring out which meaning of a word is being used\n\n**propositional meaning** words are synonyms if can sub them in any sentence w/o changing truth of the sentence\n**principle of contrast** different forms always have some different meaning\n\n**similarity** delas with relations b/t words instead of meanings.\n**relatedness/association** - relation b/t words beyond similarity. Ex. Coffee and cup.\n**semantic field** - words in  set that are in teh same domain ex. hospital, restaruants\n\n**semantic frame** - set of words that indicate the perspectives/participants. Ex. Buyer, seller, goods.\n\n**connotation** is the affective/emotional meaning of a word.\n**sentiment** is the pos/neg determination of language. \n\nAffect rated on:\n1. **valence** how pleasent something is\n2. **arousal** how intense the emoition is\n3. **dominance** how much control the cause has\n\n\n\n\n## SLP Chapter 6.2 Vector Semantics\n \nwords that have similar neghborhing word are similar.\n\n**embeddings** are vector representation of words in multi-dimensional space\n\nAdvantage of vector semantics is that don't have to have exact wod as in n-grams,\nb/c can use similar meanings. \n\n\n\n## SLP Chapter 6.3 Words and Vectors\n \n**term-document** matix each row represent a word in vocab, while column is a document\na cell is number of times a word occurs in a doc\n\nIn term-document matrix, vectors (columns) are of dimensionsality $|V|$, size of vocab\n\nTwo docs are similar if their column vectors are similar\n\n**information retrieval** is trying to find document *d* from all of the *D* docs based on query\nquery can be a vector of length *|V*|\n\ncan use **row vector**, grouping the dimensions to find meaning of words\nsimilar words have similar vectors, occur in similar documents\n\n**term-term** or **word-word** or **term-context** matrix is word by word matrix.\nDimensionality is $|V| * |V|$. How often a target row word, co-occurs with a context colum nword in a corpus.\nContext can be a doc or a word window (+/-).\n\nMost of the co-occurance numbers are 0s, so the vectors are sparse. \n\n\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n**cosine** of angle between vectors is most often used to determine the similarity\nUses  the dot product of the two vectors. High when have large values in the same dimensions\nIf have 0s in differnt dimensions will have lower docut product.\nBut dot product is biased toward longer vectors. \nVector length: $$|v| = \\sqrt{\\sum_{i=1}^N v_i^2}$$\nMore frequent words occur more often, so have denser -> longer vectors\nUse the normalized dot product instead to account for that.\n$$a \\cdot b = |a||b|\\cos \\theta$$\n$$\\frac {a \\cdot b}{|a||b|} = \\cos \\theta$$\n$$= \\frac{\\sum_{i=1}^N v_iw_i}{\\sqrt{\\sum_{i=1}^N v_i^2} \\sqrt{\\sum_{i=1}^N w_i^2}}$$\n\ncan also pre-normalize, by dividing the vector by it's length, and then dot product is the cosine.\n\ncosine range is [-1, 1], but since counts are $\\geq 0$, cosine range is [0,1]\n\n**tf-idf** term frequency - document frequency. Document frequency is number of document a term apperas in.\nDifferent rom collection frequency, totatl number of times it appears across all D.\n\ninverse document frequence $N/df_t$. Total document / number of docs that have $t$.\nSo fewer docs with $t$ higher weight. \nso then $idf_t = \\log_{10} (\\frac{N}{df_t})$\nand tf-idf is: $$\\log_{10}((count(t,d) + 1) * \\log_{10} (\\frac{N}{df_t}) $$\n\n\n\n\n## SLP Chapter 6.8 Word2vec\n \n**embeddings** are short and desne vectors. dimensions ranges from 50-1000 instead of vocab size or documents count\nThey are dense in that most are real numbers. Not clear interpretation of the dimensions.\n\nWord2vec have static embeddings that are fixed for every word.\nUses a binary classifier to decide if a word likely to show up near another word\nand using the weights as embeddings. \n\nSelf-supervision, use text as the supervised training data. \n\n**skip-gram with negative sampling (SGNS)**:\n1. Target word and context word are positive samples\n2. Other random words are negative samples\n3. Logistic regression to train classifier\n4. Weights are now the embeddings\n\nTrying to determine if given a $(w,c)$ of target word and context, the probability\nthat $c$ is actually context for the target $w$. So $P(+ | w,c)$\n\nTo determine the probability, compare the embedding vectors of context and target\nby taking the dot prouct of the two vectors, and then apply the sigmoid function\n$$P(+ | w,c ) = \\sigma (c \\cdot w) = \\frac{1}{1 + \\exp(-c \\cdot w)}$$\nfor negative case can just find $\\sigma(-c \\cdot w)$\n\nThis is for one word, for the full context, assume that context words are indepenednt, and so \ntake the product of their probabilities (via sigmoid). Take the log to avoid underflow. \n\nLearning embeddings\nNeed to create negative examples for each positive example. # negs is determined by paramater $k$\nNoise words are chose by weighted probability with $\\alpha=.75$ often as the weight.\n\n$P_{\\alpha}(w) = \\frac{count(w)^{\\alpha}}{\\sum_{w'}count(w')^{\\alpha}}$\n\nUse stocahstic gradient descent to minimize loss, which is assign high prob to actaul context, and low to all neg examples\n\nword2vec has problems with unknwon words. Fasttext deals with by using subwords\nwhere it takes an n-gram of the word via chars, and learns embeddings using the n-grams\nand summing the embeddings of the constitutents\n\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \nSize of context windwow affects representaiton. Shorter = mo syntatctic.\nLonger context, words are topical but not similar. Ex: 2 window lead to similar schoo lnames\n5 window led to word from the same series. \n\n**first-order co-occurence** if words are near one another\n**second-order co-occurence* if have similar neighbors\n\nCan use parallelograms to solve some analogies. With a, b, a* can find x by\n$x = a^* -a + b$ with x that results in the smallest distance between a* and x\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n \n**allocational harm** is allocating resources unfairly to different groups.\nCould be a potential negative consequnce of embeddings.\n\nThey tend to amplify bias.\n\nCan also cause **representation harm** - harm of demeaning/ignoring socail groups\n \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \nEval performance of vector models. Metric of similarity, \ncomparing similartiy determined by algo and by human lables.\n\n\n## Module 13 Lecture Notes\n Your summary here \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": 16540
        },
        "id": "T3cm1WV542_a",
        "outputId": "7846b9e7-1bec-47c5-a075-d70c1b247961"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n**Markovian**: Prob of reach state depends only on previous state, not all earlier\nBut decision problem is seq, so utlity will depndend on seq of states/actions\n\nMDP consistes of sets of: states, actions; transitino model, and reward func.\n\nPolicy says what agent should do in any state. Measure polic by expected util. Optimal\nyields the highest expected util. Can be multiple optimal policies. \n\n**Nonstationary**: if time affects the policy (ex. exit early for N=3 steps).\n**Stationary**: if pol based only on current state. \n\nDiscount, closer to 0 prefer rewards now over later. 1, ok to wait - additive. \nEx $(1/\\gamma) - 1 $ is discount factor in monetary rewards\n\n\nUtil for infinte sequnce is finite $\\frac{R_{max}}{1 - \\gamma}$\n\n**Proper policy** - guranteed to reach a terminal state. \n\nDiscount util + infinte horizon means optimal pol is indepdnet of first state. \n\n$\\pi (s) = \\text{argmax}_{\\alpha \\in A(s) \\Sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s)]} $\n\nChoose action that max reward for the next step exp discounted utility of resulting state,\nassuming agent in s' chooses optimal action\n\n**Action-utility function/Q-function** - Expected utility of an action in given state. \n\n\n$P(S'|s,a)$ and $R(s,a,s')$ represented by 3d table $|S|^2|A|$. Might be sparse, and close to $|S||A|$\nif not every state can reach every other state. \n\nDynamic decision networks (DDNs): factored representations.\n\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n**Bellman update** The utility value for a state at a given iteration, which is updated. \nAll states are updated for each iteration. \n\nBellman equations converge. \n\n**Contraction** put in 2 inputs that return 2 outputs that are closer together. Ex: divide by 2\nContractions have 1 fixed point (ex 0). Values must get closer to the fixed point. \nSmaller $\\gamma$  means faster convergence, but might miss longer effects.  Vs bigger $\\gamma$ \nN grows exponentnially. \n\nPolicy becomes optimal long before utilities converge. \n\n**Policy iteration** has 2 parts:\n1. **Policy eval** given a policy cacluate the utility $U_i$ if $\\Pi_i$ was executed.\n2. **Policy improvement** try a new policy $\\Pi_{i+1}$ based on $U_i$\nStop when no utility changes.\n\nPolicy iteration removes the max, and instead have $n$ linear equations/unknowns for the $n$ states,\nSo can be solved in $O(n^3)$. If sparse state space, even faster. \n**Modified Policy iteration** could also do value iteration for a few iterations \ngo get approx utility and then do policy iteration. \n\n$$asynchornous policy iteration** updates only a subset of states\n\nValue/policy iterations are offline, compute then perform.\n\n\nFor online learning, limit of tree where stop caring about rewards\nH = ceiling of $\\log_y\\epsilon(1-\\gamma) / R_{max})$ \n\n\n\n## Module 8 Lecture Notes\n Your summary here \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**expolitation** - use best current action\n**exploration** - try new state to gain information\n\nIn **bandit problems**  arms are **Markove reward processes**, having one possible action.\nBandit problem is an MDP.\n\n**Gittins index**\n\n$$ \\lambda = \\max_{T>0} \\frac{E(\\sum_{t=0}^{T-1}\\gamma^tR_t)}{E(\\sum_{t=0}^{T-1}\\gamma^t)} $$\nLambda where indifferent b/t switching to $M_{\\lambda}$ immediatly or at T.\n\nGittins index for an arm is equal to $1 - \\gamma *$  value of optimal policy for restarting the MDP.  \n\n**Upper confidence bound heuristic** use samples from each arm, create a confi interval for the value of it\nChoose arm w/ highest upper bound. Std dev is proportional to $\\sqrt{1/N_i}$ so index is approx\n$UCB(M_i) = \\hat{\\mu_i} + g(N)/\\sqrt{N_i}$ \n\n**regret** is the difference between expected rewards and optimal expected rewards\n\n**Thompson sampling** chose an arm randomly by probability based on current samples.\n\n**Selection problem** just need to choose the best option quickly, ex. chose employee to hire, or \nmetalevel decison problem. No index for these.\n\n**Bandit superprocess** has each arm be a full MDP. Can't solve each on individually. \nGlobablly optimal might be locally suboptimal. Changes the short/long term rewards.\n\n**Dominating policy** is an optimal policy unaffected by opportunity cost. Found by realxing MDP.\nCompute lower bound by solving each arm sepeartly. \n\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n \n**Supervised learning** give an agent example input/output pairs. \n**Reinfrocement learning** RL, agent interacts with the world and gets rewards.\nRL different from MDP b/c \"in\" in the MDP. Don't know the transition model/reward function.\n**Sparse** rewards  don't give rewards signal for most states. \n\nApproaches:\n1. Model Based reinforcement Learning: Agent use a transition model of the env to understand\nreward signals and make decisions. If partially observable, also use it for state estimation.\n\n2. Model free: agent doesn't know or learn transition model. Instead learns direct representation of behavior:\n2a. Action-utility learning: Q-learning, learn a q-function. Given a q-function choose what to by \nfiguring out action with highest q-val\n2b. Policy search: agent learns pol that maps from state-to actions. i.e. reflex agent\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n**Passive RL**: Agent policy is fixed, try to learn the utility of states. \nlike policy evaluation, but don't know the transition model ($P(s' | s,a)$) or the \nreward function $R(s,a,s')$. So instead setup a set of trials\n\n**direct utility estimation**: utility of a state is expected total reward from state forward.\nEach trail results in a sample of this. W/infite trials reach real expected value.\n\nProblem is that don't take into account utility of successor states. Slow convergence\n\n**adaptive dynamic progamming** ADP, learns the trasnition model and connects them.\nEnv is fully observable so have $(s,a)$ and ouptu is $s'$. Estimate P(s' | s,a) from counts\nin of how often reach $s'$ by $a$ in $s$. \n\n**Temporal-difference learning** \n\n$$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s,\\pi(s),s') + \\gamma U^{\\pi}(s') - U^{\\pi}(s)]$$\nIf if transition from one state to another, and know estimate utilities, they should conform\nto $U(s+1) = r + U(s)$, so adjust it a bit. $\\alpha$ is the learning rate.\n\nWant to decrease $\u0007lpha$ more visit state. Causes $U^{\\pi}(s)$ to converge to right val. \n\n**Prioritized sweeping** a heuristc to adjust only states in ADP where it's succesors likely \nhave a large adjustment. Can learn fast, and more efficient. \n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n**Active reinforcement learning** - decide what actions to take.\nNeed to learn probability for all actions, and the utilities of the optimal policy. \n\nProblem is that the learned optimal policy in the learned model is not the true env.\nTradeoff between **exploitation** of the best action know now, and **exploration** of uknown states. \n\n**GLIE** Greedy in the limit of infite exploration. Try all actions in all states\na certain number of times. Good option is to try options that haven't tried a lot yet. \nMore optimistic. Exploration function should be prefer higher utility, and low counts. \n\nAssumes safe exploration, in real world actions can be irreversible,\nmay enter absorbing state.\n\nBayesian reinforcement learning based on $P(h|e)$.  try to find the policy\nwith max sum of expected probabilities given vidcne. \n\nRobust control theory, have a set of possible models. Optimal robust policy is the one w/best outcome in worst case. \n\nTD q-learning agent doesn't need a transition model. But can be long to figure out sparse rewards/\nneeds long action sequnces. \n\n**SARSA** State, action, reward, state action. Updates with action taken. \n\nQ-learning is off policy, but SARSA is on-policy. SARSA stays with the policy.\n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n**function approximation** approximte true util/Q function. RL learn values\nfor parameters (weights) in the linear combo of features. Use with look-ahead search\nto make better decisions and faster learning.\n\nRL use online learning, update parms after every trial. Use the delta rule/Widrow-Hoff rule\n\n$$\\theta_i \\leftarrow \\theta_i + \\alpha [u_j(s) -\\hat{U_{\\theta}}(s)] \\frac{\\partial \\hat{U_{\\theta}(S)}}{\\partial \\theta_{i}}$$\n\n**catastrophic forgetting** forget previously learned learning. \n**experience reply** is a solution, replay trajectory that caused negative rewards earlier. \n\nSometimes can't come up with features for a linear function approximator. Deep learning has been effective\nFinal layer might be linear, and can see what features the network is using to build it system.\n\n**credit assignment problem** hard to figure out which of the actions in a long string caused final reward.\nSolve w/**reward shaping** by giving agent more **pseudorewards** for progress. Ex: touching the ball.\nBut can cause agent to max pseudoreward instead of goal. Can modify the reward function over time\nby a potential function. \n\n**hierarchial reinforcement learning**, another solution is break action sequences into small parts. \n\n**joint state space**, a physical and machine state for all states. \n\n**additive decompoition**, for each action, the utility dpends on a few variables, not all,\nand together they get summed up for the total utility. \n\n\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n$P(effct | cause)$ is causal, while P(cause | effect) is disagnostic$. Doctors\nknows causal probabilities, and wants to figure out diagnosis for patient. \n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n**Naive Bayes** assume that effects are independent given a cause. \n$P(cause |e) = \\alpha P(Cause) \\Pi_j P(ej | Cause)$\nThe probability of the cause given the cause is the prob of cause, times\nthe product of the conditional probabilities of the effects given the cause.\nThis is then normalized. Unobserved effects sum to 1 so can be ignored. runtime is O(e)\n\nCan use NB for txt classificaiton. Decide which class a text belongs to.\nCategory is the cause, and effect is which words are present.\n\nAssume words occur independently. In reality not so. Model is overconfident. But ranking of cateogries is still accurate.\n\nNB works well for language determ, document retrive, spam.\n\n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n \nLanguage models assign a probability to series of words. \n**n-gram** is a combo of _n_ words. So 2-gram is 2 word sequence. \nn-gram models try to estm probability of the final word given the first n-1 words.\n\ncan try to use counts of history to calculate P(w|h), but doesn't account for novelty.\n\nChain rule: $P(x_1..x_n) = P(x_1)P(x_2 | x1)P(x_3|x_{1:2}...P(x_n | x_{1:n-1})$\n\ninstead of getting probability using whole industry, use just some of the past words. \nex. in bigram conditional probability of past word.\n\n**Markov assumption** is that the probability of a word conditional only on prvious word.\n\nEstimate n-gram probabilities using **maximum likelihood estimation**, \nnormalize counts from a corpus so they are between 0 an 1. \n\nFor bigram $P(w_n | w_{n-1} = \\frac{C(w_{n-1}w_n)}{C(w_{n-1})})$\nRatio is the **relative frequency**\n\nUse log probabilities because the probabilities are < 1 and as multiply can have underflow. \nAdd log probabilities instead of multiplying.\nso $p_1 * p_2 * p_3 * p_4 = exp(\\log{p1} + log{p2} + log{p3} + log{p4})$\n\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nExtrinsic evaluation is trying a model in an application. \nIntrinsic evaluation is sepearte from any application. Use a **test set** instead. \nEval on a test set that was unseen. \n\nMight separate out a part of the test set for inital testing, called the devset. \nTypically do 80% of data for train, 10% dev, 10% test.\n\nPreplexity is inverse probability of tet set, normalized by the number of words\n$PP(W) = P(w_1w_2...w_n)^{-1/n}$ and via chain rule\n$PP(W) = \\sqrt[n]{\\prod_{i=1}^N \\frac{1}{P(w_i | w1 ...w_{i-1})}}$\n\nHigher probability the lower the perplexity. Want lower perplexity to max the LM.\n\nPerplexity is also the **weighted average branching factor** i.e. how many words can follow a word\nEx: if all 10 digits equally likely then $P(w_1w_2...w_N)^{-1/N} = ((1/10)^N)^(-1/N) = (1/10)^-1 = 10$\nbut if a digit is way more likely, then perplexity is lower, the branching factor is 10, but weighted branching factor is smaller.\n\nBigger n-gram lower perplexity\n\n\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Can generate words by their probability distribution interval.\nChoose a random number then choose first word w/in interval of that number then next via bigram \n\n## SLP Chapter 3.4 Generalization and Zeros\n\nGrammar depends a lot on the training set. Genre needs to match b/t training corpus and test/task.\nAlso need to match the dialect/variety.\n\nProblem of sparsity. Can have good word have 0 probability. Problem because underestimate the probability of the word.\nAlso a problem because the entire probability becomes 0. Perplexity can't be computed b/c denom is 0 \n\nMight have unknown words in the test set. Out of vocabulary rate. use psuedo-word <UNK>.\nIf have closed vocab can treate all <UNK> as one. Similarly replace all words in open vocab with count < n with <UNK>\nCan create low peplexity by choosing a small vocab, so then UNK has high prob. Should only compare \nLMs with same vocab.\n\n\n\n## SLP Chapter 3.5 Smoothing\n \nWord in vocab but have unseen context need to be accounted for with smoothing.\n**Smoothing**/**discounting** moves some probability from seen to unseen events.\n\n**Laplace smoothing** adds 1 to all 1 n-gram counts. Need to add V to numerator\nsince every vocab word was counted once more so $P_{Laplace}(w_i) = \\frac{c_i +1}{N + V}$\n\n**Add-k smoothing** adds only a fractional count to the counts\n$P_{add-k}(w_n| w_{n-1}) = \\frac{C(w_{n-1}w_n) + k}{C(w_{n-1}) + kV}$\n\ndoesn't work that well though.\n\n**Backoff** use the n-gram if there is evidence, else go to n-2 -gram if exits, \nelse to n-3 -gram ...to unigram.\n\n**Interpolation** mix the probability estimates from al the n-grams.\nCan do linear interpolation, weight each one by $\\lambda_i$$, such that the \nsum of the $\\lambda$s is 1.\n\nLearn the $\\lambda$ weights from the held-out corpus.\n\n$$Katz backoff$$ redistribute some of weight of the higher-order n-grams so probability adds to 1.\nuse some alpha function to distribute it to the lower-order n-grams. \nCombine with **Good-Turing** smoothing.\n\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\nEfficiency when storing words. The words are stored in member as 64bit has numbers,\nactual words on disc. Probabilities use only 4-8 bits. Use reverse tries for n-grams.\n\n**Stupid backoff** doesn't use discounting of high order probabilities. \nJust use a weight $\\lambda$ when switching to lower order n-gram.\n\n\n\n\n## Module 10 Lecture Notes\n Your summary here \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** a directed graph with:\n1. Nodes that are random variables\n2. Directed edges b/t pairs of nodes. Source is parent of destination. Is a DAG\n3. Every node has probability infor on effect of parents \n\nNode with boolean variable w/ k parents, has $2^k$ probabilities. \n\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nSyntax of BN is a DAG w/ nodes w/ probabilities.\nSemantics is how syntax relates to joint probability distribution of the vars.\n\nprobability of joint distribution entry is\n$P(x_1, ..., x_n) = \\Pi_{i=1}^n \\theta (x_i | parents(x_i)$\n\n**chain rule** $P(x_1,...,x_n) = P(x_n | x_{n-1}, ..., x_1)P(x_{n-1}|x_{n-2}...,x_1)...P(x_2|x_1)P(x_1)$\n\nSame as parents being causaul. Depends on toplogical ordering of the nodes. \n\nA BN is correct representation if every node is conidtitinally indepent of all other predecessors, given it's parents.\n\nAchived by\n1. Nodes, ordered by cause to effects \n2. Links with min set for parents for $X_i$, and a conditional probability table for $x_i$ given its parents\n\nBN more compact than  full joint distribution. \nBN is a **locally strctured** system, in which every subcomponent is directly interacting with some $n$ number\nof other components < N total components. \nEx: if a RV in a BN is influnced by k others, then conditional probability tables will have $2^k$ numbers,\nso toatl will be $2^k *n $ while the joint distribution will contain $2^n$ numbers. \n\nBetter to leave out some links b/c otherwise as big as a table of the joint distribution. \nTradeoff between accuracy and complexity. \n\nGiven a vars parents, the var is conditionally independent of non-decendants.\n\nBN can be through of as set of of conditional independences. \n\nMarkov blanket - a node is independent of all other nodes, given parents, childeren,\nand co-parents\n\n**D-sepeartion**\n1. Take an ancestral subgraph of 3 vars\n2. Link between any non-lined nodes that have a child -> **moral graph**\n3. Make all directed edges undirected\n4. Z-despeartes two vars if it blocks all paths between them. And $X \\perp Y | Z$ \n\n**Canonical distributions**\n1. **Deterministic nodes** value is determined by value of parents.\nValue can be min, max, or some other function.\n2.**Context-specific independence** if node is independent of parents w/ certain values. \nex: damage is indep of rugedness given not accident\n\nFor continious vars might use **discretization** dividing values in some num of intervals\nor might assign a distribution. \n\n**hybrid Bayesian network** has both discrete and continous vars. \n\nBN can contain **hidden variables** that are not input/output vars but important to make more sparse network\n\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \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\n**induction** is observation to rule. Might be wrong.\n**deduction** rule to case. Guranteed to be correct.\n\n**classification** are problems where output of ML algo is a finite set of vals.\n**regression** when ouput is a number\n\n**supervised learning* give agent input and ouput, agent learns map from i to o.\nOutput that categorizes inputs is a **label**, agent is predicting a label.\n\n**unsupervised learning** agent needs to learn without direct feedback.\nCommon task is **clustering**, finding a cluster of inputs.\n\n**reinforcement learning** agent learns from reinforcements, pos rewards or neg punishments.\nNeeds to figure out what actions caused the reinfforcement.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nSupervised learning, has a training set of $(x_i, y_i)$ pairs, trying to find $h(x)$\nthat approximates the real function $f(x)$ that creates the pairs.\n\n$h$ is the **hypothesis**, taken from **hypothesis space** $H$. \n$h$ can be called the **model** of the data, from **model class** $H$\n\n**ground truth** is the actual output $y_i$\n\nHypothesis space based on knowledge or exploring data, or just experimenting\n\n**consistent hypothesis** $h$ where every $x_i$ in train set has corresponding $h(x_i) = y_i$.\nIf continous values for $y_i$ use a **best-fit function** that produces $h(x_i)$ approx $y_i$.\n**generalizes** meas $h$ predicts the outputs in test set accurately. \n\nconsistent hypothesis != good hypothesis\n\nEval hypothesis space by bias and variance\n\n**bias** is how much $h$ deviates from expected val when averaged of different train sets.\nlinear functions have strong bias. If data has non-linear pattern, linear func can't represent it.\n**underfitting** is not being able to find pattern in data. contrast piecewise function has low bias.\n\n**variance** amount of change in $h$ wrt fluctuation in train set. \nEx lin func would have low variance, polynomial would have high variance\n**overfitting** too much weight on train set, perform poorly on new sets.\n\nTrade off between bias and variance. \nLow-bias hypothesis fit data well, more complicated vs. low-variance, simple, and generalize better.\n\nCan choose hypothesis most likely based on data\n$h^* = \\argmax P(h|data)$ == $h^* = \\argmax P(data|h)P(h)$\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n**Decision tree** func w/input vector utliple attribute values to output 1 value the decision\n\n**Boolean classification** only true or false outputs.\n\nTry to get a small consistent tree. Choose the attributes that are most discerning first (biggest impact)\nLeads to more shallow tree.\n\nEval a learning algo using **learning curve** - % correct on test vs training set size.\n\n**Entropy** measure of uncertainty for a RV. Info amount inverse with entropy.\n$$-\\sum_kP(v_k)\\log_2P(v_k)$$\nfor fair coin entropy = $-(0.5\\log_2 0.5 + .5\\log_2 0.5) = 1$ bits\nLoaded coin entropy = $-(0.99\\log_2 0.99 + 0.01\\log_2 0.01) = 0.08$ bits\n\nFor boolean rv entropy: $B(q) = - (qlog_2(q) + (1-q)log_2(1-q))$, where q is prob of true.\n\nAn attribute divides a training set by number of values, and each subset has pos and neg examples\nSo entropy remaining after testing for A is\nReaminder(A) = $\\sum_k=1^d \\frac{p_k + n_k}{p+n}B(\\frac{p_k}{p_k + n_k})\n\ninformatin gain is the reduction in entropy\nGain(A) = $B(\\frac{p}{p+N})$ - Remainder(A)\nWant to max gain. \n\nOverfitting liklihood increases w/number of attributes, decreases w/more training examples.\nBigger hypothesis space more likely to fit/overfit.\n\n**decision tree pruning** elimnates nodes that aren't relevant to reduce overfitting. \nIf a node w/ only leaf nodes only detects noise, its eliminated. Measure by information gain.\n\nUse significane test test to measure if enough info gain. Null hypohtesis that attribute not signficant.\nUse chi-squared test\n\nPruned trees do better than unpruned when a lot of noise in the data. Also more efficient and clear.\n\nCan't do early stopping because might have attributes that are informative in comboination. \n\nDealing with continous data, may want to use a **split point test** where test value of attribute\ncan do **equality test** for non continous non ordered data.\n\nDecision trees can be suboptimially acurate, and can take too long to run. Also unstable b/c new example can change whole tree.\nRandom forest can address some problems\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n**Stationary** is the assumption that time doesn't affect examples' probability distributin\nAlso assume they are independent. *iid* independent and identically distrbiuted\n\n**error rate** is % of time when hypothesis function isn't matching actual y\n\n**Hyperparameters** are parms for the model class, not just for an individual model.\nEx $\\chi^2$ threshold or degree.\n\nUse 3 data sets\n1. Training set \n2. Validation/development set to eval possible models, and pick one\n3. Test set for final test\n\nUse k-fold cross-validation to get more out of data. split into k subsets and perfrom k round of learning.\nbut use 1/k of data as validation set. Average scross across the round is the estimate.\nIf $k=n$ this is leave-one-out cross validation LOOCV\n\n**Model selection** is finding right hypohtesis space, \nwhile **optimatization/training** is finding best hypothesis.\n\nModel interpolates data if it fits all of the training set. Point at which it beings to overfit.\n\nIn ML try to minimize loss function instead of maxmize util.\n**Loss function** is the amount of util lost if guess is wrong\n$L(x, y, \\hat{y})=Utility(f(x)=y) - Utility(h(x)=\\hat{y})$\nor just $L(y, \\hat{y})$\n\n$L_1(y, \\hat{y}) = \\abs(y-\\hat{y})$\n$L_2(y, \\hat{y}) = (y-\\hat{y})^2$\n$L_{0/1}(y, \\hat{y}) =$ 0 only when $y = \\hat{y}$, 1 otherwise\n\n\nWant to do this over all inputs, would do over epxected generalized loss, \nbut don't know probabilities generally so estimate iwth **empirical loss*\n\nEmpericalLoss = $\\sum_{(x,y) \\in E}L(y, h(x)) \\frac{1}{N}$, where N is the size of example set\n\nwant to choose $h$ with lowert empirical loss\n\nreasons optiaml $h$ might be different:\n1. **Unrealizability** - if hypo space doesn't actually contain the true function $f$\n2. **Variance** - alog hypothesis varies with sets of examples. Vraince decrease w/# trainings if realizable\n3. **Noise** - $f$ might return different values for same input $x$\n4. If large hypospace, can't compute the best one for sure\n\n\nin large-scale learning loss affected mostly by limits of computation. \n\nCost(h) = EmpLoss(h) + $\\labmda$ Complexity(h)\n\n**Regularization** is process for punishing complexity. Complexity is measured by **regularization function**\n**feature selection** discards features that are irrelavent, kind of like in prunning\n\n**minimum descriptin length** is the hypohteis that minimizes the bits required to encode data\n\n**hand-tuning** approach to hyperparameters is setting hyperparameters based on past and figuing out new ones.\n**grid search** is more mechanical way to tune them. \n\nif a lot of values for hyperparams use random search.\n\n**Bayesian optimization** make hyperparameter choice as an ML problem\n\n**Population-based training (PBT)** trains models with different hyperparams in parallel, via random search\n2nd generation then chooses values based on 1st generation + mutation.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nif $h$ is really wrong, will figure that out after a few examples. \nIf consistent with many examples, unlikely to be way off so its *probably approximately correct*\n\n**approximately corre**ct if error of $h \\leq \\epsilon$ , w/$\\epsilon$ being small constant.\nCan find an $n$ where with with $n$ examples consistent hypothesis is appox correct. \nInside the $\\epsilion$-ball of $f$. If outside, $H_{bad}$\n\n**sample complexity** is the number of examples needed for approx correct $h$\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nlinear regression used to minimze loss  of  $h_w$ in linear functions\nLoss($h_w$) = $\\sum_{j=1}^N(y_j - (w_1x_j +w_0))^2$\n\nDo that when partial derivatives wrt $w_0$ and $w_1$ are 0.\nso\n$$w_1 = N(\\sum x_jy_j) - (\\sum x_j)(\\sum y_j) / [N(\\sum x_j^2) - (\\sum x_j)^2]$$\n$$w_0 = (\\sum y_j - w1(\\sum x_j)) / N $$\n\n**Gradient descent**, start at some point in weight space, get an estimate of gardient, and move twoards downhill.\nadjustment is $w_i \\leftarrow w_i - \\alpha \\frac{\\partial}{\\partial w_i} Loss(w)$\n$\\alpha is the learning rate or learning step$\n\nNeed to do for all examples. But can be very slow\n\n**epoch** is a step for all training examples\n\n**stochastic gradient descent** randomly selects some training examples. OK to do b/c\nstd error of mean gradient based on sqrt of N. So ok trade off for speed and error.\n\n**SGD** also usefule for online, called **online gradient descent**\n\n$Complexity(h_w) = \\sum_i \\abs(w_i)^q$\n\nL2 regulariztion mins the sum of squares. L1 makes sparse model\n\n**decision boundry** b/t 2 classes. In linear dimension it's a **linear separator**\n\n\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\nNB is generative b/c a class is sampled first from $P(c)$ and then word are generated from $P(d|c)$\nMost probable $c-hat$ given $d$ based on argmax $P(d|c) * P(c)$ where $P(c)$ is the prior probability of class $c$\nNaive Bayes Assumptions:\nPosition doesn’t matter\nProbabilities are independent given class $c$\nNaive Bayes and LM use log space b/c of underflow\nLinear classifiers use linear combination of inputs for classification. Ex: Naive Bayes, logistic regression\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \nMaximum Likelihood Estimate (MLE) - consider what % of docs in train set are of class $c$.\n$P(f_i | c) = P(w_i | c)$ is count(w_i) in docs w/class $c$\n$P(w_i | c) = \frac{count(w_i, c}{Sum_{w \\in V} count(w,c}\nProblem is that NB multiliplies all features liklihoods together, \nso if have a 0 probability for any term, probably of class drops to 0, even if have other evidence.\nCan do Laplace smoothing, adding 1 to the counts\nIgnore unknown words\nMight also ignore stop words, and frequent words (the, a)\n\n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \nBinary multinomial naive Bayes, remove all duplicate words. Ie. word occurs or not per doc. \nUse negation on every word after a logical negation. (ex. After didn’t, NOT_like, NOT_this.\n\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 \nConfusion matrix - table compare how algo does compared to gold labl. \nFalse negative, are system id as negative, but is positive (ex. Is spam)\nAccuracy is measure % of all observations labelled correctly. (tp + tn) / (tp + fp + tn + fn). \nDon’t use it for text classification, b/c if classes are not balanced, doesn’t work well. \nEx if mostly negatives, can do all negative, and get high accuracy because false negatives would just be a low%.\n**precision** tp/(tp+fp). % items detected that are tp over all labeled so. Which ones did it label correctly\n**recall** tp/(tp+fn) % items correctly id’d. Which ones did it miss \n**F-measure** $F_\beta = (\beta^2 +1) PR / (\beta^2P + R)$. \nB is a weighting of recall and precision, if B >1 more weight on recall, = 1, equal weight, < 1 precision.\n$F1 = 2PR/(P+R)$.\nFor multi-class evaluation, can use *macroaveraging*, where computer perf for each class, then average, \nOr *microaverageing* collect all decisions into a single matrix, and ocompute it for that.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n**Cross-validation** choose a number $k$ partition set into k “folds”. \nUse 1 for a test set, train on k-1 folds. Repeat k times with different ks as test sets.  \n\n## SLP Chapter 4.9 Statistical Significance Testing\n\nHow well M(A) does over M(B) is \\delta(x), called effect size. \nIs statistically significant measured by non-parametric test.\nUse approximate randomization and bootstrap test.\nPaired test are tests where compare two sets of observations that can be aligned together. \nI.e pair performance of systems A and b on same x \nBoostrap test - draw large # of small samples\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n \nRepresentations harms - demean a social group. Ex. sentiment that is weighed by race. \nToxcity classifiers can cause harm, b/c flag incorrectly mentions of minority identities. \nBase false positives. \nRelease a **model card** on the training algorithms, training data sources, \nmotivations and preprocessing, evaluation source, intended use, and model performance across different demographic groups.\n \n\n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nNaive Bayes is generative while logistic regression is discriminative\nGenerative model give an input tests which of its models better first the input \nchooses that label.\nDiscriminative model tries to just differntiate between the classes. Can be satisified by 1 feature.\n\nGenerative model uses *likelihood* $P(d|c)$ and prior $P(c)$ to find\n$\\hat{c} = \\argmax_{c \\in C} P(d|c)P(c)$\n\nDiscrimintive model tries to find P(c|d)\n\nLogistic regression solves classification task by learning a vector of \n**weights**, one for each feature, and a **bias term**. Weight is how important the feature is. \nWeight is pos if feature adds to likelihood input is in class or neg if reduces likelihood\n\nFor decision, classifier uses the sum of the products of each $x_i * w_i$ plus the bias\n$z = (\\sum_{i=1}^n w_ix_i) + b$\n\nSince z can be any real number, it's not a probability. Use the **sigmoid** function to turn into one\ncalled **logistic function**\n\n$$\\sigma(Z) = \\frac{1}{1+ e^{-z}} = \\frac{1}{1+exp(-z)}$$\n\n$$P(y =1 ) = \\frac{1}{1 + exp(-(w \\cdot x + b))}$$\n\n**Decision boundry** is the min probability at which we classify if input belongs to a class or not.\n\n**period disambiguation** figure out if \".\" is end of sentence or part of word.\n\n**feature templates** are abstract specs creates automatically by going through train set.\n**representation learning** uses unsupervised learning for auto feature learning. \n\nNaive Bayes strong assumption of conditional indepdence. Logistic regression more sensitive\nto correlated features, distributes weights amont them. \n\nNB works well/better on small datasets. NB is faster to train. \n\n\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nLogistic regression produces a $\\hat{y}$ that is an estimate of the real $y$.\ndistance $\\hat(y)-y$ is called the **loss (or cost) function**\n\nuse **gradient descent** algo to optimally update weights to minimize loss function.\n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n**conditional maximum likelihood estimate** choose the weigtht vector and intcerpet that \nmax the log probability of the gold label in the train data for an input. \n\n**cross-entropy loss** is the negative log likihood loss\n\ntry to maximize $p(y | x) = \\hat{y}^y (1- \\hat{y})^(1-y)$\n\nwhich in log form is\n\n$\\log p(y|x) = log[\\hat{y}^y (1- \\hat{y})^(1-y)]$\n\n$\\log p(y|x) = ylog\\hat{y} + (1-y)log(1-\\hat{y})$\n\nloss function is the negative of that \n$L_{CE}(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n\nw/ sigmoid function:\n\n$L_{CE}(\\hat{y}, y) = -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n\nSimplifies to 1 side of the equation or the other for binary classificaiton, since y is either 1 or 0\nWant to minimize loss\n\n\n\n## SLP Chapter 5.4 Gradient Descent\n\nGradient descent tries to find where in $\\theta$ function is rising most and \ngoing in the opposite way.\n\ntrying to find:\n$$\\hat{\\theta} = \\argmin_{\\theta} \\frac{1}{m} \\sum_{i=1}^m L_{CE}(f(x_i;w), y_i)$$\n\nloss function is convex in logistic regresison so always guranteed to find min.\nNot true in non-convex function.\n\nFind the gradient of the loss function at some value for $w$. If slope is negative\nwant to make $w$ bigger. If slope is positive, want to make $w$ smaller. \n\nAmount to move $w$ is the slope $\\frac{d}{dw}L(f(x;w), y)$ times the learning rate $\\eta$\n\nFor actual weight vectors, would have a partial for each feature. \nFrom graident get a vector of partials for each, how much change in a given weight would influnce total loss\n\nDerivative for an observaiton x is = $[\\sigma(w \\cdot x + b) -y]x_j$\n\nUpdating $\\theta$ is then\n$$\\theta_{t+1} = \\theta_{t} - \\eta \\Delta L(f(x;\\theta),y)$$\n\n$\\eta$ is a hyperparmeter. If too big will miss the minimum. Too small takes too long\nCommon to decrease $\\eta$ with iterations.\n\nStochastic gradient descent moves weights per example, can be choppy.\n\n**batch training* gradient is calculated based on whole dataset. Good estimate, but takes longer\n\n**mini-batch** uses a subset of examples < whole. is happy medium.\nLoss function is the average loss for each example, and gradient is \nthe average of the per-example gradients ==\nthe sum of the loss derivatives for m examples divided by m.\n\n\n\n## SLP Chapter 5.5 Regularization\n\n**overfitting* happens when weights match too perfectly with train set.\nCould be a problem if specious correlation. \n\nUse **regularization* to avoid ovefitting, which penalizes large weights\n$$\\hat{\\theta} = \\argmax_{\\theta} \\sum_{i=1}^m \\log P(y_i|x_i) - \\alpha R(\\theta)$$\n\n**L2 regularization** is quadratic. The L2 norm is the euclidean distance of $\\theta$ from the origin.\nSo R(\\theta) = \\sum_{j=1}^n \\theta_j^2\n\nL1 regulaizaiton uses L1 norm like Manhattan distance, which is based on the sum aboslute values\n\nL2 perfes small weights, lots of them. L1 Perfers sparce vectos, but ok with larger weights.\nL1 -> Lapalace, L2->Gaussian. \n\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\nif have more than 2 classes, **multinomial logistic regression* or **softmax regression**\nSoftmax function is a gneralization of sigmoid, used to calculate $p(y = c |x)$\n\nsoftmax = $\\frac{exp(z_i)}{\\sum_{j=1}^k exp(z_j)}$\n\nHave a separate weight for each feature for each class\n\nLoss function is sum of logs of the classes so loss is\n$$ - \\sum_{k=1}^K \\{y ==k\\} \\log \\frac{exp(w_k \\cdot x + b_k)}{\\sum_{j=1}^K w_k \\cdot x + b_k} $$\n\nOne-hot vector is a vector with one value \"1\" and the rest 0.\n\nsince the formula above is only true when y==k, can just take out of the sum\n \n\n## SLP Chapter 7.1 Units\n \n**Feedfoward network** - computation goes from one layer to the next\n**deep learning** because have many layers\n\nNeural networks strong than logistic regression. Doesn't used hand made features.\n\n**computation unit** is the building block in a NN. Function that takes in real and outputs osmething\n$z = w \\cdot x + b$\n\na unit applies some non-linear function $f$ to that $z$. \n**Activation** is the output of $f$. \n\n$f$ might be sigmoid, tanh, or rectified linear (ReLU). \n\nTanh use more often than sigmoid. Range is [-1, 1]\n$y = \\frac{\\exp^z - \\exp^{-z}}{\\exp^z + \\exp^{-z}}$\n\n\nReLU is simplest activation function\n$y = \\max(z, 0)$\n\nTanh is easy to differentaite, and outputs outliers close to the mean\nReLU is close to linear.\n\nhigh $z$ results in y that are saturated (close to1) in Tanh and sigmoid .\nDerivs of high value in tanh and sigmoid are close to 0 which can cause problems in learning.\n**vanishing graident problem** 0ish values cause problems b/c \nmultiply derivatives/gradients b/t layers and small gradients cause small error signals.\n\n\n## SLP Chapter 7.2 The XOR problem\n \n**perceptron** does not have linear activation function.\nCan't build a XOR with perceptron.\n\n**decision boundry** in 2d space is a line. Everyone one side is 0, other side is 1.\nXOR is an example of problem that is not **linearly separable**\n\nThe hidden layer of a newrok creates a representation. NN can auto form userful representations. \n\nNetwork formed of layers of linear units can reduce to single layer of linear units.\n\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n**Feedforward network** is multilayer, units connects w/o cycles. Never pass back outputs\nCalled feedforward called multi-layer perceptrons but not perceptrons b/c perceptrons are linear\n\n3 types of units:\n1. input\n2. hiddent\n3. output\n\nHidden layers has hidden units that do the dot product+activation function\nTypically every layer is **fully-connected** so that inputs to a layer are all of \noutputs from the previous layer\n\nCombine weights for all units in a hidden layer into one matrix **W** and vector **b**\nwhere W_{ji} is the weight from $i$ input to $j$ unit.\n\nThen need to multiply input vectors times **W** add bias vector and apply activation func\nso output of hidden layer is vector h where:\n$h = \\sigma(Wx + b)\n\nactivation function is applied element wise to the elements in the vector \n\nThe hidden layer creates a representation of the input. Output layer calcuates final output\ncan be real or class. Output node might be one value, or vector of probabilities for all the classes.\n\nHidden layer acts as input to output layer. Output layer has weight matrix **U**\nwhere $U_{ij}$ is the weight of the input from hidden unit $j$ into unit $i$ in the output layer\n$z = Uh$ which then needs to be normalized using softmax\nso $y = softmax(z)$\n\n2 layer network - count hidden and output, but not input. \n\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n \nNeural networks don't use hand chose features. Instead use embeddings as inputs.\n*pretraining* is using another algorithm to learn an embededed representation of the input.\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\nNeural language models can have longer histories, generalize better, more accurate. \nBut also complex, slower to train, harder to interpret. \n\n**Forward inference/decoding** is forward pass in NN to get probability of possible outputs.\n\nRepresent each of N context words as 1-hot vecto. \n\n1. Mutliply the 1hvs by weights in embedding matrix E. E has col per word. column has d dimensions, so dimenison is d x |V|.\nThe mutlplication select the relevant column, so resulting embedding layer is d x 1\nembeddings grouped as embedding layer \n2. Then e multiply by W and pass to activaiton function to get layer $h$\n3. then mutiply $h$ by $U$\n4. Then apply softmax, so the output is probabilities.\n\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\nto train feedforward neural net need to use a loss function like cross-entropy loss\nand can use gradient descent to minimize loss function\n\nHard to determine gradient b/c partial deriv of a weight in early layer since loss \ncomes much later. Use **error backpropagation/backward differentiation**\n\nIf binary loss function is:\n$$L_{CE}(\\hat{y}, y) = -y [y \\log \\hat{y} + (1- y) \\log(1-\\hat(y)]$$\n\nif multinomial it's\n$$L_{CE}(\\hat{y}, y) = - \\sum_{i=1}^C y_i \\log \\hat{y_i}$$\n\nif hard classfication where only 1 class is right\n$$L_{CE}(\\hat{y}, y) = - \\log \\hat{y_i} = -\\log \\frac{\\exp(z_i)}{\\sum_{j=1}^K \\exp(z_j)}$$ i is correct class\n\n\nTo figure out derivative:\n\n**Computation graphs** represent process of computing by breaking down into different operations,\nevery operation is an node in the graph\n\n**Backward pass** uses **chain rule**, for f(x) = u(v(x)):\n$$\\frac{df}{dx} = \\frac{du}{dv} * \\frac{dv}{dx}$$\n\nSo nodes pass gradients back from the final node to all nodes\n\nCompute partials from right to left, and apply chain rule. Start downstream and go up.\nWhen go up, derivative is gradient of output (later layer) wrt input (earlier layer)\n\nNeural networks have non-convex optimizations. Need to use small random numbers for all the weights.\nAlso use a mean of 0 and 1 variance.\n\n**dropout** is used to prevent overfitting, it drops some units during training, randomly.\n\nNeed to tune hyperparamenters, like the learning rate, batch size, and architecture.\nWeights and bias are the parms.\n\n\n\n## SLP Chapter 7.7 Training the neural language model\n \nNeural language model has parms $\\theta = E, W, U, b$.\n\nCan **freeze** embedding layer, holding it constant if use pretraining. \n\n\n## Module 13 Lecture Notes\n Your summary here \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\nFeedforward networks still have limited context. \n\nLanguage modesl assin conditional probability to all possible words,\nand can use the chain rule to get probability to a sequnce by using the conditional proba.\n\nPerplexity is inverse of probability for a test word. Can chain together again with product\n\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n \nRecurrent neural network has a cycle within the network. A unit may have it's own output as an input\n**Elman netowrks** are simple RNN. \n\nStart with an input at certain time **x_t** \nLink output of hidden layer to itself at next time step. \n\nSo need to get $h_t$, mutiply $x_$ by $W$, and $h_{t-1} with $U$$, \nadd these together and apply activation function $g$. \nThen apply weights $V$ to get value to feed into $f$, the activation function for ouptut y\n$$h_t = g(Uh_{t-1} + Wx_t)$$\n$$y_t = f(Vh_t)$$\n\n$W$ is $d_h x d_in$, U is $d_h x d_h$, and V is $d_out x d_h$\n\nNeed to use backpropagation through time b/c hidden layer affects loss of current layer and next layer\nor instead can unrol the RNN into a feedforward computation graph.\n\n\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\nRNN Language Models don't have limited context problem, b/c hidden layer can represent infor about all words\n\n**teacher forcing** ignore prediction and use actual next word an input for the next-next word\n\n**Weight tying** use $E=V$, same embeddings for input and softmax. so final hidden layer is $d_h$.\nImproves perplexity, and number of parameters needed in model.\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n**Distributional hypothesis** words with similar meanings appear in same env.\n\n**representation learning** - is ML auto learn of good reprsentation of text. \nIs **self-supervised**\n\nFor a set of related words like **mouse** and **mice**, one form serves as the **lemma* or **citation form**\nThe other versions of the word are **wordforms**\n\n**word sense** is different meanings of the word\n**polysemous** have multiple meanings\n**word sense disambiguation** is figuring out which meaning of a word is being used\n\n**propositional meaning** words are synonyms if can sub them in any sentence w/o changing truth of the sentence\n**principle of contrast** different forms always have some different meaning\n\n**similarity** delas with relations b/t words instead of meanings.\n**relatedness/association** - relation b/t words beyond similarity. Ex. Coffee and cup.\n**semantic field** - words in  set that are in teh same domain ex. hospital, restaruants\n\n**semantic frame** - set of words that indicate the perspectives/participants. Ex. Buyer, seller, goods.\n\n**connotation** is the affective/emotional meaning of a word.\n**sentiment** is the pos/neg determination of language. \n\nAffect rated on:\n1. **valence** how pleasent something is\n2. **arousal** how intense the emoition is\n3. **dominance** how much control the cause has\n\n\n\n\n## SLP Chapter 6.2 Vector Semantics\n \nwords that have similar neghborhing word are similar.\n\n**embeddings** are vector representation of words in multi-dimensional space\n\nAdvantage of vector semantics is that don't have to have exact wod as in n-grams,\nb/c can use similar meanings. \n\n\n\n## SLP Chapter 6.3 Words and Vectors\n \n**term-document** matix each row represent a word in vocab, while column is a document\na cell is number of times a word occurs in a doc\n\nIn term-document matrix, vectors (columns) are of dimensionsality $|V|$, size of vocab\n\nTwo docs are similar if their column vectors are similar\n\n**information retrieval** is trying to find document *d* from all of the *D* docs based on query\nquery can be a vector of length *|V*|\n\ncan use **row vector**, grouping the dimensions to find meaning of words\nsimilar words have similar vectors, occur in similar documents\n\n**term-term** or **word-word** or **term-context** matrix is word by word matrix.\nDimensionality is $|V| * |V|$. How often a target row word, co-occurs with a context colum nword in a corpus.\nContext can be a doc or a word window (+/-).\n\nMost of the co-occurance numbers are 0s, so the vectors are sparse. \n\n\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n**cosine** of angle between vectors is most often used to determine the similarity\nUses  the dot product of the two vectors. High when have large values in the same dimensions\nIf have 0s in differnt dimensions will have lower docut product.\nBut dot product is biased toward longer vectors. \nVector length: $$|v| = \\sqrt{\\sum_{i=1}^N v_i^2}$$\nMore frequent words occur more often, so have denser -> longer vectors\nUse the normalized dot product instead to account for that.\n$$a \\cdot b = |a||b|\\cos \\theta$$\n$$\\frac {a \\cdot b}{|a||b|} = \\cos \\theta$$\n$$= \\frac{\\sum_{i=1}^N v_iw_i}{\\sqrt{\\sum_{i=1}^N v_i^2} \\sqrt{\\sum_{i=1}^N w_i^2}}$$\n\ncan also pre-normalize, by dividing the vector by it's length, and then dot product is the cosine.\n\ncosine range is [-1, 1], but since counts are $\\geq 0$, cosine range is [0,1]\n\n**tf-idf** term frequency - document frequency. Document frequency is number of document a term apperas in.\nDifferent rom collection frequency, totatl number of times it appears across all D.\n\ninverse document frequence $N/df_t$. Total document / number of docs that have $t$.\nSo fewer docs with $t$ higher weight. \nso then $idf_t = \\log_{10} (\\frac{N}{df_t})$\nand tf-idf is: $$\\log_{10}((count(t,d) + 1) * \\log_{10} (\\frac{N}{df_t}) $$\n\n\n\n\n## SLP Chapter 6.8 Word2vec\n \n**embeddings** are short and desne vectors. dimensions ranges from 50-1000 instead of vocab size or documents count\nThey are dense in that most are real numbers. Not clear interpretation of the dimensions.\n\nWord2vec have static embeddings that are fixed for every word.\nUses a binary classifier to decide if a word likely to show up near another word\nand using the weights as embeddings. \n\nSelf-supervision, use text as the supervised training data. \n\n**skip-gram with negative sampling (SGNS)**:\n1. Target word and context word are positive samples\n2. Other random words are negative samples\n3. Logistic regression to train classifier\n4. Weights are now the embeddings\n\nTrying to determine if given a $(w,c)$ of target word and context, the probability\nthat $c$ is actually context for the target $w$. So $P(+ | w,c)$\n\nTo determine the probability, compare the embedding vectors of context and target\nby taking the dot prouct of the two vectors, and then apply the sigmoid function\n$$P(+ | w,c ) = \\sigma (c \\cdot w) = \\frac{1}{1 + \\exp(-c \\cdot w)}$$\nfor negative case can just find $\\sigma(-c \\cdot w)$\n\nThis is for one word, for the full context, assume that context words are indepenednt, and so \ntake the product of their probabilities (via sigmoid). Take the log to avoid underflow. \n\nLearning embeddings\nNeed to create negative examples for each positive example. # negs is determined by paramater $k$\nNoise words are chose by weighted probability with $\\alpha=.75$ often as the weight.\n\n$P_{\\alpha}(w) = \\frac{count(w)^{\\alpha}}{\\sum_{w'}count(w')^{\\alpha}}$\n\nUse stocahstic gradient descent to minimize loss, which is assign high prob to actaul context, and low to all neg examples\n\nword2vec has problems with unknwon words. Fasttext deals with by using subwords\nwhere it takes an n-gram of the word via chars, and learns embeddings using the n-grams\nand summing the embeddings of the constitutents\n\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \nSize of context windwow affects representaiton. Shorter = mo syntatctic.\nLonger context, words are topical but not similar. Ex: 2 window lead to similar schoo lnames\n5 window led to word from the same series. \n\n**first-order co-occurence** if words are near one another\n**second-order co-occurence* if have similar neighbors\n\nCan use parallelograms to solve some analogies. With a, b, a* can find x by\n$x = a^* -a + b$ with x that results in the smallest distance between a* and x\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n \n**allocational harm** is allocating resources unfairly to different groups.\nCould be a potential negative consequnce of embeddings.\n\nThey tend to amplify bias.\n\nCan also cause **representation harm** - harm of demeaning/ignoring socail groups\n \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \nEval performance of vector models. Metric of similarity, \ncomparing similartiy determined by algo and by human lables.\n\n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}