{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "“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": "a956c38c-3a48-4e49-be0f-0083422ec932"
      },
      "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": 439,
      "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": "e00b24fd-6fbc-4481-d502-2f0c99d6b178"
      },
      "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": 440,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 441,
      "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",
        "\n",
        "chapter16_1 = \"\"\" The transition model is given by $P(s'|s,a)$, the probability that action a in state s reaches state s'.\\\n",
        " The probability of reaching by s' doing a in the current state: \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\"Utility Functions\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"sequential decision problems: in which the agent’s utility depends on a sequence of decisions\"\"\"\n",
        "chapter17_2 =  \"\"\"In this section, we present four different algorithms for solving MDPs. The first three, value iteration,\\\n",
        " policy iteration, and linear programming, generate exact solutions offline.\\\n",
        " The fourth is a family of online approximate algorithms that includes Monte Carlo planning.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"A Markov decision process or MDP is a sequential decision problem for a fully observable environment\n",
        "with a stochastic transition model that has additive rewards. MDPs are non-deterministic search problems. One way of solving them\n",
        " is via expectimax search.\\n\n",
        " MDP:\n",
        " A set of states s ∈ S\n",
        "• A set of actions a ∈ A\n",
        "• A transition function T(s, a, s’)\n",
        "   Probability that executing action a in s will lead to s’ P(s’ | s, a)\n",
        "   The probability is called the model\n",
        "• A reward function R(s, a, s’)\n",
        "   Sometimes just R(s) or R(s’)\n",
        "• An initial state s0\n",
        "• Optionally, one or more terminal states\\n\n",
        "Comparison \n",
        "In value iteration:\n",
        "• Every iteration updates both the values and (implicitly) the policy\n",
        "• We don’t track the policy, but taking the max over actions implicitly recomputes it \\n\n",
        "In policy iteration:\n",
        "• We do several passes that update utilities with fixed policy (each pass is fast because we consider only one action, not all of them)\n",
        "• After the policy is evaluated, a new policy is chosen (slow like a value iteration pass)\n",
        "• The new policy will be better (or we’re done) Both are dynamic programs for solving MDPs\"\"\"\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 U(s)\" : \"The agent’s preferences are captured by a utility function, which assigns a single number to express the desirability of a state\",\n",
        "\"Th\": \"Theorem:any“rational”preferencescan be summarized as a utility function\",\n",
        "\"expected utility\" : r\"$EU(a) = \\sum_s P(resulr(a)=s)U(s)$\",\n",
        "\"maximum expected utility (MEU)\": \"$action=argmax_a EU(a)$\",\n",
        "\"lottery L\": \"each action as a ticket. $L=[p_1,S_1; ... ; p_,S_n]$\",\n",
        "\"ORDERABILITY\": \"exactly one of A>B, B>A, A~B holds\",\n",
        "\"TRANSITIVITY\": \"$A>B \\land B>C => A>C$\",\n",
        "\"continuity\": \"$A>B>C => \\exists p \\ [p,A;1-p,C]\\sim B$\",\n",
        "\"SUBSTITUTABILITY\": \"$A \\sim B => [p,A;1-p,C]\\sim [p,B;1-p,C]$\",\n",
        "\"MONOTONICITY\": \"$A>B =>(p>q\\ <=>  [p,A;1-p,B]>[q,A;1-q,B])$\",\n",
        "\"DECOMPOSABILITY\": \"\",\n",
        "\"EXISTENCE OF UTILITY FUNCTION\": \"U(A)>U(B) <=> A>B\",\n",
        "\"EXPECTED UTILITY OF A LOTTERY\": \"U([p1, S1; ...; n, Sn]) = $\\sum_i p_i U(S_i)$\",\n",
        "\"value function or ordinal utility function\": \"in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\",\n",
        "\"preference elicitation\": \"work out utility function--involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\",\n",
        "\"Normalized utilities\": \"(best possible prize at U(S)=$u_T$ and worst possible catastrophe at U(S)=$u_\\perp$) $u_\\perp=0,\\ u_T=1$\",\n",
        "\"standard lottery\": \"$[p,u_T; 1-p,u_\\perp]$\",\n",
        "\"QALY\": \"quality-adjusted life year\",\n",
        "\"micromort\": \"a one in a million chance of death\",\n",
        "\"expected monetary value (EMV)\": \"\",\n",
        "\"risk-averse\":\"they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\",\n",
        "\"risk-seeking\":\"antonyms of risk-averse\",\n",
        "\"certainty equivalent\":\"The value an agent will accept in lieu of a lottery\",\n",
        "\"insurance premium\":\"The difference between the EMV of a lottery and its certainty equivalent\",\n",
        "\"risk-neutral\":\"An agent that has a linear curve\",\n",
        "\"unbiased\":\"the expected value of the error, E($\\widehat{EU}(a)-EU(a))$, is zero\",\n",
        "\"order statistic\":\"the distribution of any particular ranked element of a sample\",\n",
        "\"normative theory\":\"it describes how a rational agent should act\",\n",
        "\"descriptive theory\":\"describes how actual agents—for example, humans— really do act\",\n",
        "\"Certainty effect\": \"people are strongly attracted to gains that are certain\",\n",
        "\"ambiguity aversion\": \" Most people elect the known probability rather than the unknown unknowns.\",\n",
        "\"framing effect\": \"the exact wording of a decision problem can have a big impact on the agent’s choices\",\n",
        "\"anchoring effect\": \"People feel more comfortable making relative utility judgments rather than absolute ones.\",\n",
        "\"transition model\": \"describes the outcome of each action in each state\",\n",
        "\"optimal policy\": \"a policy that yields the highest expected utility $\\pi^*$\",\n",
        "\"finite horizon\": \"there is a fixed time after which nothing matters—the game is over. $U_h([s_0,a_0,...,S_{N+k}]])=U_h(s_0,a_0,...,S_{N})$\",\n",
        "\"nonstationary\": \"A policy that depends on the time\",\n",
        "\"stationary policy\": \"With no fixed time limit, on the other hand, there is no reason to behave differently in the same state at different times. Hence, an optimal action depends only on the current state, and the optimal policy is stationary\",\n",
        "\"additive discounted rewards\": \"$U([s_0,a_0,...]) = R(s_0,a_0,s_1)+\\gamma R(s_1,a_1,s_2)$\",\n",
        "\"Q-function\": \"expected utility of taking a given action in a given state\",\n",
        "\"shaping theorem\": \"the following transformation leaves the optimal policy unchanged:$R'(s,a,s') = R(s,a,s')+\\gamma \\Phi(s')-\\Phi(s)$\",\n",
        "\"\": \"\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 442,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9dc68ac5-6296-4416-f43a-8e936c1459e5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": 443,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'stationary policy' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The transition model is given by $P(s'|s,a)$, the probability that action a in state s reaches state s'. The probability of reaching by s' doing a in the current state:  $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\nUtility Functions\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nsequential decision problems: in which the agent’s utility depends on a sequence of decisions\n\n## AIMA Chapter 17.2 Algorithms for MDPs\nIn this section, we present four different algorithms for solving MDPs. The first three, value iteration, policy iteration, and linear programming, generate exact solutions offline. The fourth is a family of online approximate algorithms that includes Monte Carlo planning.\n\n## Module 8 Lecture Notes\nA Markov decision process or MDP is a sequential decision problem for a fully observable environment\nwith a stochastic transition model that has additive rewards. MDPs are non-deterministic search problems. One way of solving them\n is via expectimax search.\n\n MDP:\n A set of states s ∈ S\n• A set of actions a ∈ A\n• A transition function T(s, a, s’)\n   Probability that executing action a in s will lead to s’ P(s’ | s, a)\n   The probability is called the model\n• A reward function R(s, a, s’)\n   Sometimes just R(s) or R(s’)\n• An initial state s0\n• Optionally, one or more terminal states\n\nComparison \nIn value iteration:\n• Every iteration updates both the values and (implicitly) the policy\n• We don’t track the policy, but taking the max over actions implicitly recomputes it \n\nIn policy iteration:\n• We do several passes that update utilities with fixed policy (each pass is fast because we consider only one action, not all of them)\n• After the policy is evaluated, a new policy is chosen (slow like a value iteration pass)\n• The new policy will be better (or we’re done) Both are dynamic programs for solving MDPs\n\n## Module 8 Definitions\n* **Utility function u(s)** - The agent’s preferences are captured by a utility function, which assigns a single number to express the desirability of a state\n* **Th** - Theorem:any“rational”preferencescan be summarized as a utility function\n* **Expected utility** - $EU(a) = \\sum_s P(resulr(a)=s)U(s)$\n* **Maximum expected utility (meu)** - $action=argmax_a EU(a)$\n* **Lottery l** - each action as a ticket. $L=[p_1,S_1; ... ; p_,S_n]$\n* **Orderability** - exactly one of A>B, B>A, A~B holds\n* **Transitivity** - $A>B \\land B>C => A>C$\n* **Continuity** - $A>B>C => \\exists p \\ [p,A;1-p,C]\\sim B$\n* **Substitutability** - $A \\sim B => [p,A;1-p,C]\\sim [p,B;1-p,C]$\n* **Monotonicity** - $A>B =>(p>q\\ <=>  [p,A;1-p,B]>[q,A;1-q,B])$\n* **Decomposability** - \n* **Existence of utility function** - U(A)>U(B) <=> A>B\n* **Expected utility of a lottery** - U([p1, S1; ...; n, Sn]) = $\\sum_i p_i U(S_i)$\n* **Value function or ordinal utility function** - in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\n* **Preference elicitation** - work out utility function--involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n* **Normalized utilities** - (best possible prize at U(S)=$u_T$ and worst possible catastrophe at U(S)=$u_\\perp$) $u_\\perp=0,\\ u_T=1$\n* **Standard lottery** - $[p,u_T; 1-p,u_\\perp]$\n* **Qaly** - quality-adjusted life year\n* **Micromort** - a one in a million chance of death\n* **Expected monetary value (emv)** - \n* **Risk-averse** - they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n* **Risk-seeking** - antonyms of risk-averse\n* **Certainty equivalent** - The value an agent will accept in lieu of a lottery\n* **Insurance premium** - The difference between the EMV of a lottery and its certainty equivalent\n* **Risk-neutral** - An agent that has a linear curve\n* **Unbiased** - the expected value of the error, E($\\widehat{EU}(a)-EU(a))$, is zero\n* **Order statistic** - the distribution of any particular ranked element of a sample\n* **Normative theory** - it describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents—for example, humans— really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** -  Most people elect the known probability rather than the unknown unknowns.\n* **Framing effect** - the exact wording of a decision problem can have a big impact on the agent’s choices\n* **Anchoring effect** - People feel more comfortable making relative utility judgments rather than absolute ones.\n* **Transition model** - describes the outcome of each action in each state\n* **Optimal policy** - a policy that yields the highest expected utility $\\pi^*$\n* **Finite horizon** - there is a fixed time after which nothing matters—the game is over. $U_h([s_0,a_0,...,S_{N+k}]])=U_h(s_0,a_0,...,S_{N})$\n* **Nonstationary** - A policy that depends on the time\n* **Stationary policy** - With no fixed time limit, on the other hand, there is no reason to behave differently in the same state at different times. Hence, an optimal action depends only on the current state, and the optimal policy is stationary\n* **Additive discounted rewards** - $U([s_0,a_0,...]) = R(s_0,a_0,s_1)+\\gamma R(s_1,a_1,s_2)$\n* **Q-function** - expected utility of taking a given action in a given state\n* **Shaping theorem** - the following transformation leaves the optimal policy unchanged:$R'(s,a,s') = R(s,a,s')+\\gamma \\Phi(s')-\\Phi(s)$\n* **** - \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 =  \"\"\"Bandit Problems: a one-armed bandit is a slot machine. A gambler can insert a coin, pull the lever, and collect the winnings (if any).\n",
        " An -armed bandit has levers.\\\n",
        " Behind each lever is a fixed but unknown probability distribution of winnings; each pull samples from that unknown distribution.\\n\n",
        " The gambler must choose which lever to play on each successive coin—the one that has paid off best, or maybe one that has not been \n",
        " tried yet? This is an example of the ubiquitous tradeoff between exploitation of the current best action to obtain rewards and exploration\n",
        "of previously unknown states and actions to gain information, which can in some cases be\n",
        "converted into a better policy and better long-term rewards.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"MODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither\n",
        "knows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave.\n",
        "ACTION-UTILITY LEARNING:The most common form of action-utility learning is Q-learning, where the agent learns a Q-function,\\\n",
        " or quality-function, denoting the sum of rewards from state onward if action is taken. Given a Q-function, the agent can\n",
        "  choose what to do in by finding the action with the highest Q-value.\"\"\"\n",
        "chapter22_2 =  \"\"\" The passive learning task is similar to the policy evaluation task, part of the policy iteration algorithm.\n",
        "The difference is passive learning agent does not know the transition modelP(s'|s,a), which specific the prob of reaching\n",
        "state s' from state after doing action a;nor does it know reward function, which specifies the reward for each transition. \"\"\"\n",
        "chapter22_3 =  \"\"\"Move from ADP to TD: Solving the underlying MDP is not the only way to use the Bellman equations more effectively. \\n\n",
        "While ADP adjusts a state to agree with all possible successors, TD adjusts a state to agree with the successor observed \n",
        "in the current trial. \\n\n",
        "a TD Q-learning agent does not need a transition model, P(s'|s,a), either for learning or for action selection\"\"\"\n",
        "chapter22_4 =  \"\"\"Generalization in Reinforcement Learning \"\"\"\n",
        "chapter22_5 =  \"\"\"Policy Search: keep twiddling the policy as long as its performance improves, then stop.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"Exploration: you have to try unknown actions to get information \\n\n",
        "Exploitation: eventually, you have to use what you know\\n\n",
        "Regret: even if you learn intelligently, you make mistakes\\n\n",
        "Sampling: because of chance, you have to try things repeatedly\\n\n",
        "Difficulty: learning can be much harder than solving a known MDP\\n\n",
        "Basic idea:\n",
        "Receive feedback in the form of rewards. \n",
        "Agent’s utility is defined by the reward function. \n",
        "Must (learn to) act so as to maximize expected rewards. All learning is based on observed samples of outcomes!\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Markov reward process\" : \"an MDP with only one possible action a_i.Each arm is a MRP\",\n",
        "\"Gittins index\":\"$\\lambda = $\",\n",
        "\"MODEL-BASED REINFORCEMENT LEARNING\":\"the agent uses a transition model of the environment to help interpret the reward signals and to make\\\n",
        " decisions about how to act. The model may be initially unknown, in which case the agent learns the model from observing the effects of its actions,\\\n",
        "  or it may already be known\",\n",
        "\"POLICY SEARCH\":\"The agent learns a policy that maps directly from states to actions\",\n",
        "\"passive reinforcement learning\":\"the agent’s policy is fixed and the task is to learn the utilities of states (or of state–action pairs); this could also involve learning a model of the environment.\",\n",
        "\"exploration\":\"an agent must experience as much as possible of its environment in order to learn how to behave in it\",\n",
        "\"apprenticeship learning\":\"training a learning agent using demonstrations rather than reward signals\",\n",
        "\"passive learning agent\":\"The agent is trying to learn $U^{\\pi}(s)$ —the expected total discounted reward\\\n",
        "                     if policy $\\pi$ is executed beginning in state s\",\n",
        "\"good about direct evaluation\":\"It’s easy to understand. It doesn’t require any knowledge of T, R. It eventually computes the correct average values, using just sample transitions\",\n",
        "\"bad about direct evaluation\":\"It wastes information about state connections. Each state must be learned separately. So, it takes a long time to learn\",\n",
        "\"diff between passive learning and policy evaluation\" : \"The passive learning agent doesn't necessarily know the transition probability P(s'∣s,a) or the reward function R\",\n",
        "\"direct utility estimation\":\"the utility of a state is defined as the expected total reward \\\n",
        "          from that state onward (called the expected reward-to-go), and that each trial provides a sample of this quantity for each state visited\",\n",
        "\"adaptive dynamic programming\":\"agent takes advantage of the constraints among the utilities of \\\n",
        "states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming\",\n",
        "\"temporal-difference (TD) equation\":\"$U^{\\pi}(s)<-U^{\\pi}(s)+\\alpha [R+\\gamma U(s')-U(s)]$\",\n",
        "\"problem of TD\": \"if we want to turn values into a (new) policy, we’re sunk -> learn Q-values, not values. Makes action selection model-free too!\",\n",
        "\"active learning agent\":\"A passive learning agent has a fixed policy that determines its behavior. An active learning agent gets to decide what actions to take\",\n",
        "\"rehgret\": \"Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality,\\\n",
        "  and optimal (expected) rewards. Minimizing regret goes beyond learning to be optimal – it requires optimally learning to be optimal\\\n",
        "  Example: random exploration and exploration functions both end up optimal, but random exploration has higher regret\",\n",
        "\"Bayesian reinforcement learning\": \"\",\n",
        "\"Reward-to-go\":\"the total reward from a particular state onwards given a policy\",\n",
        "\"off-policy\":\"Q-learning is an off-policy learning algorithm, because it learns Q-values that answer the question “What would this action be worth in this state,\\\n",
        " assuming that I stop using whatever policy I am using now, and start acting according to a policy that chooses the best action (according to my estimates)?\",\n",
        "\"on-policy\":\"SARSA is an on-policy algorithm: it learns Q-values that answer the question “What would this action be worth in this state, assuming I stick with my policy?\",\n",
        "\"Widrow–Hoff rule, or the delta rule\":\"$\\theta_i <- \\theta_i + \\alpha [u_j(s)-\\hat{U}_\\theta (s)]\\frac{\\partial \\hat{U}_\\theta (s)}{\\partial \\theta_i}$\",\n",
        "\"Approximating temporal-difference learning\":\"adjust the parameters to try to reduce the temporal difference between successive states.(apply delta rule)\",\n",
        "\"correlated sampling\":\"ex. A better solution for blackjack is to generate a certain number of hands in advance and have each program play the same set of hands. In this way, we eliminate the measurement error due to differences in the cards received. Only a few thousand hands are needed to determine which of the two blackjack policies is better.\",\n",
        "\"\":\"\",\n",
        "}"
      ],
      "execution_count": 444,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "fe70f57f-fe7b-4931-e49d-04aea0809ce0"
      },
      "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": 445,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'MODEL-BASED REINFORCEMENT LEARNING' is too long!\nWARNING: Your definition of 'passive reinforcement learning' is too long!\nWARNING: Your definition of 'passive learning agent' is too long!\nWARNING: Your definition of 'direct utility estimation' is too long!\nWARNING: Your definition of 'adaptive dynamic programming' is too long!\nWARNING: Your definition of 'rehgret' is too long!\nWARNING: Your definition of 'off-policy' is too long!\nWARNING: Your definition of 'on-policy' is too long!\nWARNING: Your definition of 'correlated sampling' is too long!\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nBandit Problems: a one-armed bandit is a slot machine. A gambler can insert a coin, pull the lever, and collect the winnings (if any).\n An -armed bandit has levers. Behind each lever is a fixed but unknown probability distribution of winnings; each pull samples from that unknown distribution.\n\n The gambler must choose which lever to play on each successive coin—the one that has paid off best, or maybe one that has not been \n tried yet? This is an example of the ubiquitous tradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information, which can in some cases be\nconverted into a better policy and better long-term rewards.\n\n## AIMA Chapter 22.1 Learning from Rewards\nMODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither\nknows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave.\nACTION-UTILITY LEARNING:The most common form of action-utility learning is Q-learning, where the agent learns a Q-function, or quality-function, denoting the sum of rewards from state onward if action is taken. Given a Q-function, the agent can\n  choose what to do in by finding the action with the highest Q-value.\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n The passive learning task is similar to the policy evaluation task, part of the policy iteration algorithm.\nThe difference is passive learning agent does not know the transition modelP(s'|s,a), which specific the prob of reaching\nstate s' from state after doing action a;nor does it know reward function, which specifies the reward for each transition. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nMove from ADP to TD: Solving the underlying MDP is not the only way to use the Bellman equations more effectively. \n\nWhile ADP adjusts a state to agree with all possible successors, TD adjusts a state to agree with the successor observed \nin the current trial. \n\na TD Q-learning agent does not need a transition model, P(s'|s,a), either for learning or for action selection\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nGeneralization in Reinforcement Learning \n\n## Module 9 Lecture Notes\nExploration: you have to try unknown actions to get information \n\nExploitation: eventually, you have to use what you know\n\nRegret: even if you learn intelligently, you make mistakes\n\nSampling: because of chance, you have to try things repeatedly\n\nDifficulty: learning can be much harder than solving a known MDP\n\nBasic idea:\nReceive feedback in the form of rewards. \nAgent’s utility is defined by the reward function. \nMust (learn to) act so as to maximize expected rewards. All learning is based on observed samples of outcomes!\n\n## Module 9 Definitions\n* **Markov reward process** - an MDP with only one possible action a_i.Each arm is a MRP\n* **Gittins index** - $\\lambda = $\n* **Model-based reinforcement learning** - the agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. The model may be initially unknown, in which case the agent learns the model from observing the effects of its actions,  or it may already be known\n* **Policy search** - The agent learns a policy that maps directly from states to actions\n* **Passive reinforcement learning** - the agent’s policy is fixed and the task is to learn the utilities of states (or of state–action pairs); this could also involve learning a model of the environment.\n* **Exploration** - an agent must experience as much as possible of its environment in order to learn how to behave in it\n* **Apprenticeship learning** - training a learning agent using demonstrations rather than reward signals\n* **Passive learning agent** - The agent is trying to learn $U^{\\pi}(s)$ —the expected total discounted reward                     if policy $\\pi$ is executed beginning in state s\n* **Good about direct evaluation** - It’s easy to understand. It doesn’t require any knowledge of T, R. It eventually computes the correct average values, using just sample transitions\n* **Bad about direct evaluation** - It wastes information about state connections. Each state must be learned separately. So, it takes a long time to learn\n* **Diff between passive learning and policy evaluation** - The passive learning agent doesn't necessarily know the transition probability P(s'∣s,a) or the reward function R\n* **Direct utility estimation** - the utility of a state is defined as the expected total reward           from that state onward (called the expected reward-to-go), and that each trial provides a sample of this quantity for each state visited\n* **Adaptive dynamic programming** - agent takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming\n* **Temporal-difference (td) equation** - $U^{\\pi}(s)<-U^{\\pi}(s)+\u0007lpha [R+\\gamma U(s')-U(s)]$\n* **Problem of td** - if we want to turn values into a (new) policy, we’re sunk -> learn Q-values, not values. Makes action selection model-free too!\n* **Active learning agent** - A passive learning agent has a fixed policy that determines its behavior. An active learning agent gets to decide what actions to take\n* **Rehgret** - Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality,  and optimal (expected) rewards. Minimizing regret goes beyond learning to be optimal – it requires optimally learning to be optimal  Example: random exploration and exploration functions both end up optimal, but random exploration has higher regret\n* **Bayesian reinforcement learning** - \n* **Reward-to-go** - the total reward from a particular state onwards given a policy\n* **Off-policy** - Q-learning is an off-policy learning algorithm, because it learns Q-values that answer the question “What would this action be worth in this state, assuming that I stop using whatever policy I am using now, and start acting according to a policy that chooses the best action (according to my estimates)?\n* **On-policy** - SARSA is an on-policy algorithm: it learns Q-values that answer the question “What would this action be worth in this state, assuming I stick with my policy?\n* **Widrow–hoff rule, or the delta rule** - $\theta_i <- \theta_i + \u0007lpha [u_j(s)-\\hat{U}_\theta (s)]\frac{\\partial \\hat{U}_\theta (s)}{\\partial \theta_i}$\n* **Approximating temporal-difference learning** - adjust the parameters to try to reduce the temporal difference between successive states.(apply delta rule)\n* **Correlated sampling** - ex. A better solution for blackjack is to generate a certain number of hands in advance and have each program play the same set of hands. In this way, we eliminate the measurement error due to differences in the cards received. Only a few thousand hands are needed to determine which of the two blackjack policies is better.\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gCVkOo33UeWM"
      },
      "source": [
        ""
      ],
      "execution_count": 445,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Naive Bayes Models \"\"\"\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-gram Language Models. \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\"Stupid backoff gives up the idea of trying to make the language model a true probability distribution.\\\n",
        " There is no discounting of the higher-order probabilities. If a higher-order n-gram has a zero count, we simply backoff to a lower\\\n",
        "  order n-gram, weighed by a fixed (context-independent) weight.\"\"\"\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",
        "\"belief state\" : \"a representation of the set of all possible world states that it might be in\",\n",
        "\"LAZINESS\":\" It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\",\n",
        "\"THEORETICAL IGNORANCE\":\"Medical science has no complete theory for the domain.\",\n",
        "\"PRACTICAL IGNORANCE\":\"Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\",\n",
        "\"decision theory\":\"decision theory=probability  theory + utility theory\",\n",
        "\"an agent is rational\":\"if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action.\",\n",
        "\"sample space\":\"the set of all possible worlds\",\n",
        "\"unconditional or prior probabilities\":\"degrees of belief in propositions in the absence of any other information\",\n",
        "\"product rule\":\"$P(a \\land b) = P(a|b)P(b)$\",\n",
        "\"probability density function\":\"the probability that a random variable takes on some value as a parameterized function of \",\n",
        "\"inclusion–exclusion principle\":\"$P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\",\n",
        "\"probabilistic inference\":\"the computation of posterior probabilities for query propositions given observed evidence\",\n",
        "\"independence\":\"also marginal independence and absolute independence\",\n",
        "\"language models or LMs\":\"Models that assign probabilities to sequences of words\",\n",
        "\"n-gram\":\"An n-gram is a sequence of n words\",\n",
        "\"Markov assumption\":\"the probability of a word depends only on the previous word\",\n",
        "\"extrinsic evaluation\":\"embed it in an application and measure how much the application improves. expensive\",\n",
        "\"intrinsic evaluation\":\"mea- sures the quality of a model independent of any application.\",\n",
        "\"perplexity\":\"perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words\",\n",
        "\"unknown words, or out of vocabulary (OOV) words\":\"words we haven’t seen before\",\n",
        "\"Laplace smoothing/add-one smoothing\":\"$P(w_i) = \\frac{c_i+1}{N+V}$.  V words in the vocabulary\",\n",
        "\"unsmoothed maximum likelihood estimate of the unigram probability\":\"MLE of the word wi is its count ci normalized by the total number of word tokens N:$P(w_i) = \\frac{c_i}{N}$\",\n",
        "\"add-k smoothing\":\"$P*(wn|wn−1) = \\frac{ C(w_{n−1}w_n) + k}{ C(w_{n−1}) + kV }$\",\n",
        "\"stupid backoff\":\"\",\n",
        "\"Problems for MLE\":\"Out of vocabulary items (OOV); <unk> to deal with OOVs; Fixed lexicon L of size V; Normalize training data by replacing any word not in L with <unk>\\\n",
        "  Avoid zeros with smoothing\",\n",
        "}"
      ],
      "execution_count": 446,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "04a0ffee-9756-4f9c-baf6-7efa2bb684f8"
      },
      "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": 447,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'LAZINESS' is too long!\nWARNING: Your definition of 'PRACTICAL IGNORANCE' is too long!\nWARNING: Your definition of 'Problems for MLE' is too long!\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Naive Bayes Models \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\nN-gram Language Models. \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nStupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. If a higher-order n-gram has a zero count, we simply backoff to a lower  order n-gram, weighed by a fixed (context-independent) weight.\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states that it might be in\n* **Laziness** -  It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n* **Theoretical ignorance** - Medical science has no complete theory for the domain.\n* **Practical ignorance** - Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n* **Decision theory** - decision theory=probability  theory + utility theory\n* **An agent is rational** - if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action.\n* **Sample space** - the set of all possible worlds\n* **Unconditional or prior probabilities** - degrees of belief in propositions in the absence of any other information\n* **Product rule** - $P(a \\land b) = P(a|b)P(b)$\n* **Probability density function** - the probability that a random variable takes on some value as a parameterized function of \n* **Inclusion–exclusion principle** - $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n* **Probabilistic inference** - the computation of posterior probabilities for query propositions given observed evidence\n* **Independence** - also marginal independence and absolute independence\n* **Language models or lms** - Models that assign probabilities to sequences of words\n* **N-gram** - An n-gram is a sequence of n words\n* **Markov assumption** - the probability of a word depends only on the previous word\n* **Extrinsic evaluation** - embed it in an application and measure how much the application improves. expensive\n* **Intrinsic evaluation** - mea- sures the quality of a model independent of any application.\n* **Perplexity** - perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words\n* **Unknown words, or out of vocabulary (oov) words** - words we haven’t seen before\n* **Laplace smoothing/add-one smoothing** - $P(w_i) = \frac{c_i+1}{N+V}$.  V words in the vocabulary\n* **Unsmoothed maximum likelihood estimate of the unigram probability** - MLE of the word wi is its count ci normalized by the total number of word tokens N:$P(w_i) = \frac{c_i}{N}$\n* **Add-k smoothing** - $P*(wn|wn−1) = \frac{ C(w_{n−1}w_n) + k}{ C(w_{n−1}) + kV }$\n* **Stupid backoff** - \n* **Problems for mle** - Out of vocabulary items (OOV); <unk> to deal with OOVs; Fixed lexicon L of size V; Normalize training data by replacing any word not in L with <unk>  Avoid zeros with smoothing\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Bayesian networks can represent essentially any full joint probability distribution,it's a directed graph.\"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"active--A path is active if each triple is active:\n",
        " Causal chain A -> B -> C where B is unobserved (either direction);\n",
        " Common cause A <- B -> C where B is unobserved;\n",
        " Common effect (aka v-structure) A -> B <- C where B or one of its descendents is observed\\n\n",
        "  Bayes nets compactly encode joint distributions.\n",
        "  Guaranteed independencies of distributions can be deduced from BN graph structure.\n",
        "  D-separation gives precise conditional independence guarantees from graph alone.\n",
        "  A Bayes’ Net’s joint distribution may have further (conditional) independence that is not detectable until you inspect its specific distribution.\\n \\n\n",
        "\n",
        " Models are always simplifications \\n\n",
        "Conditional Independence:\\n\n",
        "1. Unconditional (absolute) independence very rare, and it\n",
        "doesn’t help us make inferences about other variables.\\n\n",
        "2. Conditional independence is our most basic and robust form\n",
        "of knowledge about uncertain environments.\\n\n",
        "3. X is conditionally independent of Y given Z, iff, $forall x, y, z, P(x, y|z) = P(x|z)P(y|z) \\; or \\; P(x|z, y) = P(x|z)$ \\n\n",
        "Bayes Net Semantic: \\n\n",
        "1. A set of nodes, one per variable X \\n\n",
        "2. A directed, acyclic graph \\n\n",
        "3. A conditional distribution for each node; A collection of distributions over X, one for each\n",
        "combination of parents’ values $P(x|a1, a2..)$ where the a are the parents;  \\n\n",
        "Bayes’ nets implicitly encode joint distributions as a product of local conditional distributions, Not every BN can represent every joint distribution, The topology enforces certain conditional independencies \\n\n",
        "Why we guaranteed that setting $P(x_1, x_2..x_n) = \\prod_{i=1}^n P(x_i|parents(X_i))$: \\n\n",
        "1. Chain Rule: $P(x_1, x_2..x_n) = \\prod_{i=1}^n P(x_i|x_1..x_{i-1})$ \\n\n",
        "2. Assume conditional independences: $P(x_i | x_1 ... x_{i-1}) = P(x_i|parents(X_i))$\\n\n",
        "BNs need not actually be causal, Sometimes no causal net exists over the domain, correlation != causation \\n\n",
        "Topology may happen to encode causal structure\n",
        "Topology really encodes conditional independence\\n\n",
        "Common Cause: \\n\n",
        "1. Y: project due -> X: Piazza busy; Z: Office hour full \\n\n",
        "2. X not guaranteed independent of Z, but X, Z are independent given Y \\n\n",
        "3. Cause blocks the influence between effects \\n\n",
        "Common Effect: \\n\n",
        "1. X: raining, Y: Ballgame -> Z Traffic \\n\n",
        "2. X, Y independent, but X, Y not independent given Z because see traffic puts X and Y in competition as explanation \\n\n",
        "D-Separation: check all (undirected) paths between Xi and Xj, if one or more active, conditional independence not guaranteed, else if all paths are inactive, the independence is guaranteed \\n\n",
        "Given a Bayes net structure, can run dseparation algorithm to build a complete list of\n",
        "conditional independences that are necessarily\n",
        "true of the form \\n\n",
        "Bayes Net Summary: \\n\n",
        "1. Bayes nets compactly encode joint distributions \\n\n",
        "2. Guaranteed independencies of distributions can be\n",
        "deduced from BN graph structure \\n\n",
        "3. D-separation gives precise conditional independence\n",
        "guarantees from graph alone \\n\n",
        "4. A Bayes’ Net’s joint distribution may have further\n",
        "(conditional) independence that is not detectable until\n",
        "you inspect its specific distribution \\n\n",
        "Inference: $argmax_q P(Q=q|E_1 = e_1...)$ \\n\n",
        "Inference by enumeration is too slow to be practical, better use variable elimination \\n\n",
        "Variable Elimination: Interleave joining and marginalizing, Still NP-hard, but usually much faster than inference by enumeration \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"conditioning case\" : \"a possible combination of values for the parent nodes—a miniature possible world\",\n",
        "\"non-descendants property\":\"Each variable is conditionally independent of its non-descendants, given its parents.\",\n",
        "\"independence property\":\"a variable is conditionally independent of all other nodes in the network, given its parents, children,\\\n",
        "      and children’s parents—that is, given its Markov blanket.\",\n",
        "\"discretization\":\"dividing up the possible values into a fixed set of intervals\",\n",
        "\"absolute independence\":\"No interactions between variables\",\n",
        "\"D-separation\":\"Given a Bayes net structure, can run d- separation algorithm to build a complete list of conditional \\\n",
        "      independences that are necessarily true of the form $X_i \\prep X_j | {X_{k_1} ... X_{k_n} }$\",\n",
        "\"conditioning case\" : \"a possible combination of values for the parent nodes—a miniature possible world\",\n",
        "\"non-descendants property\":\"Each variable is conditionally independent of its non-descendants, given its parents.\",\n",
        "\"discretization\":\"dividing up the possible values into a fixed set of intervals\",\n",
        "\"Bayes' Net\" : \"a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\",    \n",
        "\"Active Path\": \"A path is active if each triple is active else inactive\",\n",
        "\"Inference\": \"calculating some useful quantity from a joint probability distribution\",\n",
        "\"Topological ordering\": \"in any order consistent with the directed graph structure\",\n",
        "\"Locally structured\": \"Sparse\",\n",
        "\"non-descendants property\": \"a variable is conditionally independent of all other nodes in the network given its Markov blanket\",\n",
        "\"Markov blanket\": \"its parents, children, and children’s parents\",\n",
        "\"Moral graph\":\"Add links between any unlinked pair of nodes that share a common child\",\n",
        "\"Deterministic nodes\":\"has its value specified exactly by the values of its parents, with no uncertainty\",\n",
        "\"Context-specific independence\": \"a variable is conditionally independent of some of its parents given certain values of others\",\n",
        "\"Discretization\": \"dividing up the possible values into a fixed set of intervals\",\n",
        "\"Nonparametric\": \"define the conditional distribution implicitly with a collection of instances\",\n",
        "\"Hybrid Bayesian network\": \"A network with both discrete and continuous variables\",\n",
        "\"hidden variables\": \"neither input nor output variables, but are essential for structuring the network\",\n",
        "\"singly connected networks or polytrees\": \"The time and space complexity of exact inference in polytrees is linear in the size of the network.\",\n",
        "}\n"
      ],
      "execution_count": 448,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e41c50b5-2599-4f20-8ef4-7cce692a6f07"
      },
      "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": 449,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'independence property' is too long!\nWARNING: Your definition of 'D-separation' is too long!\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian networks can represent essentially any full joint probability distribution,it's a directed graph.\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\nactive--A path is active if each triple is active:\n Causal chain A -> B -> C where B is unobserved (either direction);\n Common cause A <- B -> C where B is unobserved;\n Common effect (aka v-structure) A -> B <- C where B or one of its descendents is observed\n\n  Bayes nets compactly encode joint distributions.\n  Guaranteed independencies of distributions can be deduced from BN graph structure.\n  D-separation gives precise conditional independence guarantees from graph alone.\n  A Bayes’ Net’s joint distribution may have further (conditional) independence that is not detectable until you inspect its specific distribution.\n \n\n\n Models are always simplifications \n\nConditional Independence:\n\n1. Unconditional (absolute) independence very rare, and it\ndoesn’t help us make inferences about other variables.\n\n2. Conditional independence is our most basic and robust form\nof knowledge about uncertain environments.\n\n3. X is conditionally independent of Y given Z, iff, $forall x, y, z, P(x, y|z) = P(x|z)P(y|z) \\; or \\; P(x|z, y) = P(x|z)$ \n\nBayes Net Semantic: \n\n1. A set of nodes, one per variable X \n\n2. A directed, acyclic graph \n\n3. A conditional distribution for each node; A collection of distributions over X, one for each\ncombination of parents’ values $P(x|a1, a2..)$ where the a are the parents;  \n\nBayes’ nets implicitly encode joint distributions as a product of local conditional distributions, Not every BN can represent every joint distribution, The topology enforces certain conditional independencies \n\nWhy we guaranteed that setting $P(x_1, x_2..x_n) = \\prod_{i=1}^n P(x_i|parents(X_i))$: \n\n1. Chain Rule: $P(x_1, x_2..x_n) = \\prod_{i=1}^n P(x_i|x_1..x_{i-1})$ \n\n2. Assume conditional independences: $P(x_i | x_1 ... x_{i-1}) = P(x_i|parents(X_i))$\n\nBNs need not actually be causal, Sometimes no causal net exists over the domain, correlation != causation \n\nTopology may happen to encode causal structure\nTopology really encodes conditional independence\n\nCommon Cause: \n\n1. Y: project due -> X: Piazza busy; Z: Office hour full \n\n2. X not guaranteed independent of Z, but X, Z are independent given Y \n\n3. Cause blocks the influence between effects \n\nCommon Effect: \n\n1. X: raining, Y: Ballgame -> Z Traffic \n\n2. X, Y independent, but X, Y not independent given Z because see traffic puts X and Y in competition as explanation \n\nD-Separation: check all (undirected) paths between Xi and Xj, if one or more active, conditional independence not guaranteed, else if all paths are inactive, the independence is guaranteed \n\nGiven a Bayes net structure, can run dseparation algorithm to build a complete list of\nconditional independences that are necessarily\ntrue of the form \n\nBayes Net Summary: \n\n1. Bayes nets compactly encode joint distributions \n\n2. Guaranteed independencies of distributions can be\ndeduced from BN graph structure \n\n3. D-separation gives precise conditional independence\nguarantees from graph alone \n\n4. A Bayes’ Net’s joint distribution may have further\n(conditional) independence that is not detectable until\nyou inspect its specific distribution \n\nInference: $argmax_q P(Q=q|E_1 = e_1...)$ \n\nInference by enumeration is too slow to be practical, better use variable elimination \n\nVariable Elimination: Interleave joining and marginalizing, Still NP-hard, but usually much faster than inference by enumeration \n\n\n\n## Module 11 Definitions\n* **Conditioning case** - a possible combination of values for the parent nodes—a miniature possible world\n* **Non-descendants property** - a variable is conditionally independent of all other nodes in the network given its Markov blanket\n* **Independence property** - a variable is conditionally independent of all other nodes in the network, given its parents, children,      and children’s parents—that is, given its Markov blanket.\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Absolute independence** - No interactions between variables\n* **D-separation** - Given a Bayes net structure, can run d- separation algorithm to build a complete list of conditional       independences that are necessarily true of the form $X_i \\prep X_j | {X_{k_1} ... X_{k_n} }$\n* **Bayes' net** - a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n* **Active path** - A path is active if each triple is active else inactive\n* **Inference** - calculating some useful quantity from a joint probability distribution\n* **Topological ordering** - in any order consistent with the directed graph structure\n* **Locally structured** - Sparse\n* **Markov blanket** - its parents, children, and children’s parents\n* **Moral graph** - Add links between any unlinked pair of nodes that share a common child\n* **Deterministic nodes** - has its value specified exactly by the values of its parents, with no uncertainty\n* **Context-specific independence** - a variable is conditionally independent of some of its parents given certain values of others\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Nonparametric** - define the conditional distribution implicitly with a collection of instances\n* **Hybrid bayesian network** - A network with both discrete and continuous variables\n* **Hidden variables** - neither input nor output variables, but are essential for structuring the network\n* **Singly connected networks or polytrees** - The time and space complexity of exact inference in polytrees is linear in the size of the network.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"An agent is learning if it improves its performance after making observations about the world.\"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"Naïve Bayes\n",
        "• Builds a model training data\n",
        "• Gives prediction probabilities\n",
        "• Strong assumptions about feature independence • One pass through data (counting)\n",
        "Perceptrons / MIRA:\n",
        "• Makes less assumptions about data\n",
        "• Mistake-driven learning\n",
        "• Multiple passes through data (prediction) • Often more accurate\"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"Machine learning: how to acquire a model from data / experience\\n\n",
        "• Learning parameters (e.g. probabilities)\n",
        "• Learning structure (e.g. BN graphs)\n",
        "• Learning hidden concepts (e.g. clustering)\n",
        "Today: model-based classification with Naive Bayes and Perceptrons\\n\n",
        " Model-based approach:\\n\n",
        "1. Build a model where both the label and features are random variables \\n\n",
        "2. Instantiate any observed features \\n\n",
        "3. Query for the distribution of the\n",
        "label conditioned on the features \\n\n",
        "Inference for Naïve Bayes:\\n\n",
        "1. get joint probability of label and evidence for each label [$P(y1, f1...fn)$; $P(y2, f1...fn)$ ...] \\n\n",
        "2. sum to get probability of evidence $P(f1...fn)$ \\n\n",
        "3. normalize by dividing each label in Step 1 by Step 2 \\n\n",
        "General Naïve Bayes: \\n\n",
        "1. Method1: Inference for Naïve Bayes\\n\n",
        "2. Method2: Estimates of local conditional probability tables\\n\n",
        "To generalize better and avoid overfitting: we need to smooth or regularize the estimates \\n\n",
        "Estimating the distribution of a random variable: Elicitation: ask a human(hard); Empirically: use training data (learning!) \\n\n",
        "Relative frequency is the maximum likelihood, see before for that function \\n\n",
        "get a baseline; Baselines are very simple “straw man” procedures; Help determine how hard the task is; Help know what a “good” accuracy is; careful about weak baseline \\n\n",
        "The confidence of a probabilistic classifier: $confidence(x) = max_y P(y|x)$, Represents how sure the classifier is of\n",
        "the classification; No guarantee confidence is correct \\n\n",
        "Calibration: Weak calibration: higher confidences\n",
        "mean higher accuracy; Strong calibration: confidence predicts\n",
        "accuracy rate \\n\n",
        "Summary: \\n\n",
        "1. Bayes rule lets us do diagnostic queries with causal probabilities\\n\n",
        "2. The naïve Bayes assumption takes all features to be independent given\n",
        "the class label \\n\n",
        "3. We can build classifiers out of a naïve Bayes model using training data \\n\n",
        "4. Smoothing estimates is important in real systems \\n\n",
        "5. Classifier confidences are useful, when you can get them \\n\n",
        "Naïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are\n",
        "word occurrences)\\n\n",
        "Binary Decision Rule:\\n\n",
        "In the space of feature vectors; Examples are points;\n",
        "Any weight vector is a hyperplane;\n",
        "One side corresponds to Y=+1;\n",
        "Other corresponds to Y=-1; \\n\n",
        "Leaning(Binary): start with w = 0, classify examples, if wrong, update w = w + y^ * f, where y^ is the prediction and f is the feature vector\\n\n",
        "Multi-class decision rule: each class has a $w_y$, y^ = $argmax_y w_y * f(x)$, if wrong, update $w_y = w_y - f(x)$ and $w_{y^*} = w_{y^*} + f(x)$ $y^*$ is also y^\\n\n",
        "Properties of perceptron:\\n\n",
        "1. Separability: true if some parameters get the training\n",
        "set perfectly correct \\n\n",
        "2. Convergence: if the training is separable, perceptron\n",
        "will eventually converge (binary case) \\n\n",
        "3. Mistake Bound: the maximum number of mistakes\n",
        "(binary case) related to the margin or degree of\n",
        "separability \\n\n",
        "Problems with Perceptron:\\n\n",
        "1. Noise: if the data isn’t separable,\n",
        "weights might thrash; Averaging weight vectors over\n",
        "time can help (averaged\n",
        "perceptron) \\n\n",
        "2. Mediocre generalization: finds a\n",
        "“barely” separating solution\\n\n",
        "3. Overtraining: test / held-out\n",
        "accuracy usually rises, then falls; Overtraining is a kind of\n",
        "overfitting \\n\n",
        "Fixes:\\n\n",
        "1. MIRA: $min_w 1/2*||w-w'||^2$; choose an update size that fixes the current\n",
        "mistake but, minimizes the change to w; $w_y = w_y' - t*f(x)$ and $w_{y^*} = w_{y^*}' + t*f(x)$, where $t=((w_y' - w_{y^*}') * f + 1)/(2*f*f)$ \\n\n",
        "2. In practice, it’s also bad to make updates that are too large; so we  cap the maximum possible value of t with some\n",
        "constant C; $t = min(t, C)$, faster, and usually better, especially on noisy data \\n\n",
        "3. Support Vector Machine: finds the separator with max margin(best); $min_w 1/2* ||w||^2$; SVM is MIRA that optimize over all examples at once \\n\n",
        "Naive Bayes vs. Perceptron: \\n\n",
        "1. Builds a model training data; make less assumptions about data \\n\n",
        "2. Give prediction probabilities; Mistake-driven learning \\n\n",
        "3. One pass through data; Multiple passes through data \\n\n",
        "4. Strong assumptions about feature independence; Often more accurate \\n\n",
        "A complex network of perceptrons could make quite subtle\n",
        "decisions \\n\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"baseline\" : \" Baselines are very simple “straw man” procedures • Help determine how hard the task is. Help know what a “good” accuracy is\",  \n",
        "\"confidence\": \"Represents how sure the classifier is of the classification. Any probabilistic model will have confidences. No guarantee confidence is correct\",\n",
        "\"binary perceptron learning\": \"Start with weights = 0. For each training instance:\\n \\\n",
        "• Classify with current weights:y=+1 if w·f(x)>=0 \\\n",
        "• If correct (i.e., y=y*), no change! \\\n",
        "• If wrong: $w = w+y^* · f$\",\n",
        "\"Problems with the Perceptron\":\"Noise: if the data isn’t separable, weights might thrash->Averaging weight vectors over time can help (averaged perceptron)\",\n",
        "\"problem with proceptron\":\"Overtraining: test / held-out accuracy usually rises, then falls\",\n",
        "\"stochastic gradient descent\":\"function STOCHASTIC GRADIENT DESCENT(L(), f (), x, y) returns $ \\Theta$ # where: L is the loss function\\\n",
        "# f is a function parameterized by $\\Theta$\\\n",
        "# x is the set of training inputs x^(1), x^(2),..., x^(n)\\\n",
        "# y is the set of training outputs (labels) y^(1), y^(2),..., y^(n).\\n  $\\Theta <- 0$.\\n\\\n",
        "repeat T times\\n\\\n",
        "  For each training tuple (x^{(i)}, y^{(i)}); \\n \\\n",
        "  Compute $\\hat{y}^{(i)} = f(x^{(i)};\\Theta)$; \\n \\\n",
        "  Compute the loss $L(\\hat{y}^{(i)},y^{(i)})$; $g <— \\Delta_\\Theta L(f(x^{(i)};\\Theta),y^{(i)})$; \\n\\\n",
        "  $\\Theta <- \\Theta - \\eta g$; \\n \\\n",
        " return $\\Theta$\",\n",
        "\"Naïve Bayes\" : \"Assume all features are independent effects of the label\",\n",
        "\"General Naïve Bayes formula\": \"$P(Y, F_1 .. F_n) = P(Y) \\prod_i P(F_i|Y)$\", \n",
        " \"bag-of-words\": \"because model is insensitive to word order or reordering\",\n",
        " \"Data\": \"labeled instances: Training set, Held out set, Test set\",\n",
        " \"Features\": \"attribute-value pairs which characterize each x\",\n",
        " \"Experimentation cycle\": \"Learn parameters on training set, Tune hyperparameters on held-out set), Compute accuracy of test set\",\n",
        " \"Accuracy\": \"fraction of instances predicted correctly\",\n",
        " \"Overfitting\": \" fitting the training data very closely, but not generalizing well\",\n",
        " \"Laplace Smoothing\": \"Pretend you saw every outcome once more than you actually did\",\n",
        " \"linear interpolation\": \"$P(x|y) = a*P(x|y) + (1-a)P(x)$\",\n",
        " \"Tuning\": \"For each value of the hyperparameters, train and test on the held-out data\",\n",
        " \"Linear Classifier\" : \"Inputs are feature values Each feature has a weight Sum is the activation\",  \n",
        " \"Activation fucntions\": \"sigmoid; tanh;  rectified linear unit ReLU\",\n",
        " \"machine learning\": \"observes some data, builds a model, and uses the model as both a hypothesis about the world and a software that can solve problems\",\n",
        " \"transfer learning\": \"knowledge from one domain is transferred to a new domain, so that learning can proceed faster with less data\",\n",
        " \"classification\": \"output is one of a finite set of values\",\n",
        " \"regression\": \"output is a number\",\n",
        " \"supervised learning\": \"agent observes input-output pairs and learns a function that maps from input to output\",\n",
        " \"unsupervised learning\": \"agent learns patterns in the input without any explicit feedback\",\n",
        " \"reinforcement learning\": \"agent learns from a series of reinforcements: rewards and punishments\",\n",
        " \"hypothesis space\": \"set of possible functions. same as model class\",\n",
        " \"exploratory data analysis\": \"examining the data with statistical tests and visualizations, to get a feel for the data\",\n",
        " \"consistent hypothesis\": \"h such that each x in the training set has y\",\n",
        " \"best-fit function\": \"each h(xi) is close to yi\",\n",
        " \"underfitting\": \"fails to find a pattern in the data\",\n",
        " \"variance\": \"the amount of change in the hypothesis due to fluctuation in the training data\",\n",
        " \"bias–variance tradeoff\": \"a choice between hypotheses that fit the training data well and that may generalize better\",\n",
        " \"decision tree\": \"representation of a function that maps a vector of features to a single output value\",\n",
        " \"happy graphs\": \"as the training set size grows, the accuracy increases\",\n",
        " \"Entropy\": \"a measure of the uncertainty of a random variable; the more information, the less entropy\",\n",
        " \"decision tree pruning\": \"Pruning works by eliminating nodes that are not clearly relevant\",\n",
        " \"Early stopping\": \"have the decision tree algorithm stop generating nodes when there is no good attribute to split on\",\n",
        " \"regression tree\": \"A regression tree has at each leaf a linear function of some subset of numerical attributes\",\n",
        " \"unstable\": \"adding just one new example can change the test at the root\",\n",
        " \"stationarity\": \"assumption that the future examples will be like the past\",\n",
        " \"Hyperparameters\": \"parameters of the model class, not of the individual model\",\n",
        " \"validation set\": \"evaluate the candidate models and choose the best one\",\n",
        " \"Interpolated\": \"a model that exactly fits all the training data has interpolated the data.\",\n",
        " \"realizable\": \"hypothesis space actually contains the true function\",\n",
        " \"noisy\": \"it may return different values of f(x) for the same x\",\n",
        "\"regularization\": \"process of explicitly penalizing complex hypotheses\",\n",
        " \"grid search\": \"try all combinations of values and see which performs best on the validation data\",\n",
        " \"Bayesian optimization\": \"treats the task of choosing good hyperparameter values as a machine learning problem in itself\",\n",
        " \"computational learning theory\": \"any hypothesis that is seriously wrong will almost certainly be “found out” with high probability\",\n",
        " \"probably approximately correct\": \"hypothesis that is consistent with a sufficiently large set of training examples\",\n",
        " \"PAC learning\": \"Any learning algorithm that returns hypotheses that are probably approximately correct\",\n",
        " \"Sparse model\": \"it often sets many weights to zero\",\n",
        " \"text categorization\": \"the task of assigning a label to an entire text\",\n",
        " \"probabilistic classifier\": \" tell us the probability of the observation being in the class\",\n",
        " \"Generative classifiers\": \"like naive Bayes build a model of how a class could generate some input data\",\n",
        " \"Discriminative classifiers\": \"like logistic regression instead learn what features from input are most useful to discriminate\",\n",
        " \"stop word\": \" very frequent words like the , .\",\n",
        " \"sentiment lexicons\": \" lists of words that are preannotated with positive or negative sentiment\",\n",
        " \"Precision\": \"true positive/(true positive + false positive)\",\n",
        " \"Recall\": \"true positive/(true positive + false negative)\",\n",
        " \"macroaveraging\": \"compute the performance for each class, and then average over classes\",\n",
        " \"microaveraging\": \"we build into a single confusion matrix, and then compute precision and recall from that table\",\n",
        " \"bootstrap test\": \"create many virtual test sets from an observed test set by repeatedly sampling from it\",\n",
        " \"representational harms\": \", harms caused by a system that demeans a social group\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 450,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "39179255-2f34-4e25-a5fc-7397d47e60a4"
      },
      "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": 451,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'binary perceptron learning' is too long!\nWARNING: Your definition of 'stochastic gradient descent' is too long!\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nAn agent is learning if it improves its performance after making observations about the world.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\nNaïve Bayes\n• Builds a model training data\n• Gives prediction probabilities\n• Strong assumptions about feature independence • One pass through data (counting)\nPerceptrons / MIRA:\n• Makes less assumptions about data\n• Mistake-driven learning\n• Multiple passes through data (prediction) • Often more accurate\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\nMachine learning: how to acquire a model from data / experience\n\n• Learning parameters (e.g. probabilities)\n• Learning structure (e.g. BN graphs)\n• Learning hidden concepts (e.g. clustering)\nToday: model-based classification with Naive Bayes and Perceptrons\n\n Model-based approach:\n\n1. Build a model where both the label and features are random variables \n\n2. Instantiate any observed features \n\n3. Query for the distribution of the\nlabel conditioned on the features \n\nInference for Naïve Bayes:\n\n1. get joint probability of label and evidence for each label [$P(y1, f1...fn)$; $P(y2, f1...fn)$ ...] \n\n2. sum to get probability of evidence $P(f1...fn)$ \n\n3. normalize by dividing each label in Step 1 by Step 2 \n\nGeneral Naïve Bayes: \n\n1. Method1: Inference for Naïve Bayes\n\n2. Method2: Estimates of local conditional probability tables\n\nTo generalize better and avoid overfitting: we need to smooth or regularize the estimates \n\nEstimating the distribution of a random variable: Elicitation: ask a human(hard); Empirically: use training data (learning!) \n\nRelative frequency is the maximum likelihood, see before for that function \n\nget a baseline; Baselines are very simple “straw man” procedures; Help determine how hard the task is; Help know what a “good” accuracy is; careful about weak baseline \n\nThe confidence of a probabilistic classifier: $confidence(x) = max_y P(y|x)$, Represents how sure the classifier is of\nthe classification; No guarantee confidence is correct \n\nCalibration: Weak calibration: higher confidences\nmean higher accuracy; Strong calibration: confidence predicts\naccuracy rate \n\nSummary: \n\n1. Bayes rule lets us do diagnostic queries with causal probabilities\n\n2. The naïve Bayes assumption takes all features to be independent given\nthe class label \n\n3. We can build classifiers out of a naïve Bayes model using training data \n\n4. Smoothing estimates is important in real systems \n\n5. Classifier confidences are useful, when you can get them \n\nNaïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are\nword occurrences)\n\nBinary Decision Rule:\n\nIn the space of feature vectors; Examples are points;\nAny weight vector is a hyperplane;\nOne side corresponds to Y=+1;\nOther corresponds to Y=-1; \n\nLeaning(Binary): start with w = 0, classify examples, if wrong, update w = w + y^ * f, where y^ is the prediction and f is the feature vector\n\nMulti-class decision rule: each class has a $w_y$, y^ = $argmax_y w_y * f(x)$, if wrong, update $w_y = w_y - f(x)$ and $w_{y^*} = w_{y^*} + f(x)$ $y^*$ is also y^\n\nProperties of perceptron:\n\n1. Separability: true if some parameters get the training\nset perfectly correct \n\n2. Convergence: if the training is separable, perceptron\nwill eventually converge (binary case) \n\n3. Mistake Bound: the maximum number of mistakes\n(binary case) related to the margin or degree of\nseparability \n\nProblems with Perceptron:\n\n1. Noise: if the data isn’t separable,\nweights might thrash; Averaging weight vectors over\ntime can help (averaged\nperceptron) \n\n2. Mediocre generalization: finds a\n“barely” separating solution\n\n3. Overtraining: test / held-out\naccuracy usually rises, then falls; Overtraining is a kind of\noverfitting \n\nFixes:\n\n1. MIRA: $min_w 1/2*||w-w'||^2$; choose an update size that fixes the current\nmistake but, minimizes the change to w; $w_y = w_y' - t*f(x)$ and $w_{y^*} = w_{y^*}' + t*f(x)$, where $t=((w_y' - w_{y^*}') * f + 1)/(2*f*f)$ \n\n2. In practice, it’s also bad to make updates that are too large; so we  cap the maximum possible value of t with some\nconstant C; $t = min(t, C)$, faster, and usually better, especially on noisy data \n\n3. Support Vector Machine: finds the separator with max margin(best); $min_w 1/2* ||w||^2$; SVM is MIRA that optimize over all examples at once \n\nNaive Bayes vs. Perceptron: \n\n1. Builds a model training data; make less assumptions about data \n\n2. Give prediction probabilities; Mistake-driven learning \n\n3. One pass through data; Multiple passes through data \n\n4. Strong assumptions about feature independence; Often more accurate \n\nA complex network of perceptrons could make quite subtle\ndecisions \n\n\n## Module 12 Definitions\n* **Baseline** -  Baselines are very simple “straw man” procedures • Help determine how hard the task is. Help know what a “good” accuracy is\n* **Confidence** - Represents how sure the classifier is of the classification. Any probabilistic model will have confidences. No guarantee confidence is correct\n* **Binary perceptron learning** - Start with weights = 0. For each training instance:\n • Classify with current weights:y=+1 if w·f(x)>=0 • If correct (i.e., y=y*), no change! • If wrong: $w = w+y^* · f$\n* **Problems with the perceptron** - Noise: if the data isn’t separable, weights might thrash->Averaging weight vectors over time can help (averaged perceptron)\n* **Problem with proceptron** - Overtraining: test / held-out accuracy usually rises, then falls\n* **Stochastic gradient descent** - function STOCHASTIC GRADIENT DESCENT(L(), f (), x, y) returns $ \\Theta$ # where: L is the loss function# f is a function parameterized by $\\Theta$# x is the set of training inputs x^(1), x^(2),..., x^(n)# y is the set of training outputs (labels) y^(1), y^(2),..., y^(n).\n  $\\Theta <- 0$.\nrepeat T times\n  For each training tuple (x^{(i)}, y^{(i)}); \n   Compute $\\hat{y}^{(i)} = f(x^{(i)};\\Theta)$; \n   Compute the loss $L(\\hat{y}^{(i)},y^{(i)})$; $g <— \\Delta_\\Theta L(f(x^{(i)};\\Theta),y^{(i)})$; \n  $\\Theta <- \\Theta - \\eta g$; \n  return $\\Theta$\n* **Naïve bayes** - Assume all features are independent effects of the label\n* **General naïve bayes formula** - $P(Y, F_1 .. F_n) = P(Y) \\prod_i P(F_i|Y)$\n* **Bag-of-words** - because model is insensitive to word order or reordering\n* **Data** - labeled instances: Training set, Held out set, Test set\n* **Features** - attribute-value pairs which characterize each x\n* **Experimentation cycle** - Learn parameters on training set, Tune hyperparameters on held-out set), Compute accuracy of test set\n* **Accuracy** - fraction of instances predicted correctly\n* **Overfitting** -  fitting the training data very closely, but not generalizing well\n* **Laplace smoothing** - Pretend you saw every outcome once more than you actually did\n* **Linear interpolation** - $P(x|y) = a*P(x|y) + (1-a)P(x)$\n* **Tuning** - For each value of the hyperparameters, train and test on the held-out data\n* **Linear classifier** - Inputs are feature values Each feature has a weight Sum is the activation\n* **Activation fucntions** - sigmoid; tanh;  rectified linear unit ReLU\n* **Machine learning** - observes some data, builds a model, and uses the model as both a hypothesis about the world and a software that can solve problems\n* **Transfer learning** - knowledge from one domain is transferred to a new domain, so that learning can proceed faster with less data\n* **Classification** - output is one of a finite set of values\n* **Regression** - output is a number\n* **Supervised learning** - agent observes input-output pairs and learns a function that maps from input to output\n* **Unsupervised learning** - agent learns patterns in the input without any explicit feedback\n* **Reinforcement learning** - agent learns from a series of reinforcements: rewards and punishments\n* **Hypothesis space** - set of possible functions. same as model class\n* **Exploratory data analysis** - examining the data with statistical tests and visualizations, to get a feel for the data\n* **Consistent hypothesis** - h such that each x in the training set has y\n* **Best-fit function** - each h(xi) is close to yi\n* **Underfitting** - fails to find a pattern in the data\n* **Variance** - the amount of change in the hypothesis due to fluctuation in the training data\n* **Bias–variance tradeoff** - a choice between hypotheses that fit the training data well and that may generalize better\n* **Decision tree** - representation of a function that maps a vector of features to a single output value\n* **Happy graphs** - as the training set size grows, the accuracy increases\n* **Entropy** - a measure of the uncertainty of a random variable; the more information, the less entropy\n* **Decision tree pruning** - Pruning works by eliminating nodes that are not clearly relevant\n* **Early stopping** - have the decision tree algorithm stop generating nodes when there is no good attribute to split on\n* **Regression tree** - A regression tree has at each leaf a linear function of some subset of numerical attributes\n* **Unstable** - adding just one new example can change the test at the root\n* **Stationarity** - assumption that the future examples will be like the past\n* **Hyperparameters** - parameters of the model class, not of the individual model\n* **Validation set** - evaluate the candidate models and choose the best one\n* **Interpolated** - a model that exactly fits all the training data has interpolated the data.\n* **Realizable** - hypothesis space actually contains the true function\n* **Noisy** - it may return different values of f(x) for the same x\n* **Regularization** - process of explicitly penalizing complex hypotheses\n* **Grid search** - try all combinations of values and see which performs best on the validation data\n* **Bayesian optimization** - treats the task of choosing good hyperparameter values as a machine learning problem in itself\n* **Computational learning theory** - any hypothesis that is seriously wrong will almost certainly be “found out” with high probability\n* **Probably approximately correct** - hypothesis that is consistent with a sufficiently large set of training examples\n* **Pac learning** - Any learning algorithm that returns hypotheses that are probably approximately correct\n* **Sparse model** - it often sets many weights to zero\n* **Text categorization** - the task of assigning a label to an entire text\n* **Probabilistic classifier** -  tell us the probability of the observation being in the class\n* **Generative classifiers** - like naive Bayes build a model of how a class could generate some input data\n* **Discriminative classifiers** - like logistic regression instead learn what features from input are most useful to discriminate\n* **Stop word** -  very frequent words like the , .\n* **Sentiment lexicons** -  lists of words that are preannotated with positive or negative sentiment\n* **Precision** - true positive/(true positive + false positive)\n* **Recall** - true positive/(true positive + false negative)\n* **Macroaveraging** - compute the performance for each class, and then average over classes\n* **Microaveraging** - we build into a single confusion matrix, and then compute precision and recall from that table\n* **Bootstrap test** - create many virtual test sets from an observed test set by repeatedly sampling from it\n* **Representational harms** - , harms caused by a system that demeans a social group\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"Classifier Component: \\n\n",
        "1. A feature representation of the input. For each input observation\n",
        "x(i)\n",
        ", this will be a vector of features [x1,x2,...,xn]. \\n\n",
        "2. A classification function that computes the estimated class y^ via\n",
        "p(y|x). \\n\n",
        "3, An objective function for learning, usually involving minimizing\n",
        "error on training examples. \\n\n",
        "4. An algorithm for optimizing the objective function.\\n\n",
        "Learning in logistic regression: \\n\n",
        "1. An objective function or loss function that tells us distance between\n",
        "the system output and the gold output. We will use cross-entropy\n",
        "loss.\\n\n",
        "2. An algorithm for optimizing the objective function. We will use\n",
        "stochastic gradient descent to minimize the loss function. \\n\n",
        "Loss on all training examples: log(p(all training labels)) = $-\\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \\n\n",
        "Gradient descent: $theta = argmin_{theta} \\, 1/m \\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \\n\n",
        "update w: $w^{t + 1} = w'- n*(d/dw)f(x;w)$, where n is the learning rate; for muti-dimension change w to theta and f(x;w) to L(f(x;theta), y)\\n\n",
        "derivitive of cross entropy is $[sigmoid(wx +b) - y]*x_j$ for i in all features \\n\n",
        "Average loss is to sum all the $L_{CE}$ for each example and normalize it \\n\n",
        "The loss for a batch of data or an entire dataset is just the average loss over the m\n",
        "examples \\n\n",
        "The gradient for multiple data points is the sum of the individual gradients, which is $[sigmoid(wx +b) - y]*x_j$ \\n\n",
        "softmax(zi) = $e^{z_i}/(\\sum_{j=1}^k e^{z_j})$ \\n\n",
        "$L_{CE}(y^*, y)$ with softmax = -log ($e^{z_i}/(\\sum_{j=1}^k e^{z_j})$) \\n\n",
        "Computation Graphs: Although backpropagation was invented for neural nets, it is related to general\n",
        "procedure called backward differentiation, which depends on the notion of\n",
        "computation graphs.\n",
        "A computation graph represents the process of computing a mathematical expression.\n",
        "The computation is broken down into separate operations. Each operation is a node in\n",
        "a graph.\\n\n",
        "Backward difference uses chain rule \\n\n",
        "Summary:\\n\n",
        "1. Like with logistic regression, we learn the best parameters for the neural net to make\n",
        "its predictions y^ as close to possible as the gold standard labels in our training data y.\\n\n",
        "2. We use:\n",
        "A cross entropy loss function;\n",
        "Gradient descent to perform optimization;\n",
        "Error back propagation to compute the gradient of the loss function \\n\n",
        "3. Since Neural Networks combine many perceptron-like neural units, we have many\n",
        "more parameters in the models (weights and biases). This allows us to train systems to\n",
        "perform even more sophisticated tasks\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Linear Classifier\": \"Inputs are feature values Each feature has a weight Sum is the activation\",    \n",
        "\"Sigmoid function\": \"$y = 1/(1+e^{-z})$\", \n",
        "\"mean squared error\": \"$L_{MSE}(y^*, y) = 1/2 (y^* - y)^2$\",\n",
        "\"cross entropy loss\": \"$L_{CE}(y^*, y) = -[ylog(y^*) + (1-y)log(1-y^*)] = - \\sum_{i=1}^C y_i logy^*_i$\",\n",
        "\"Gradient descent\": \" a method that finds a minimum of a function by figuring out in which direction to move based on slope\",\n",
        "\"Stochastic gradient descent\": \"chooses a single random example at a time and updates its weights on that example. As a result the updates can fluctuate.\",\n",
        "\" batch training\": \"which computes the gradient over the entire dataset. a much better estimate of which direction to move the weights but takes a long time\",\n",
        "\"mini-batch training\": \"The loss is then accumulated.\",\n",
        "\"Regularization\": \"a way to penalize large weights. A regularization term is added to the loss function.\",\n",
        "\"softmax function\": \" generalization of the sigmoid function\",\n",
        "\"period disambiguation\": \"deciding if a period is the end of a sentence or part of a word\",\n",
        "\" cost/lost function\": \"distance between the system output and the gold output\",\n",
        "\"convex\": \"A convex function has just one minimum\",\n",
        "\"L2 regularization\": \"$\\sum_{j=1}^n (theta_j^2)$, aka lasso regression\",\n",
        "\"L1 regularization\": \"$\\sum_{j=1}^n (theta_j)$, aka ridge regression\",\n",
        "\"interpretable\": \"we should know why our algorithms reach the conclusions they do\",\n",
        "\"feedforward network\": \"the computation proceeds iteratively from one layer of units to the next\",\n",
        "\"saturated\": \"very high values of z result in values of y extremely close to 1\",\n",
        "\"XOR problem\": \"its decision boundry cannot be decided by a single perceptron, but a neural network helps\",\n",
        "\"pretraining\": \"the idea of relying on another algorithm to have already learned an embedding representation for our input words\",\n",
        "\"hard classification\": \"only one class is the correct one, and that there is one output unit in y for each class\",\n",
        "\"dropout\": \" randomly dropping some units and their connections from the network during training as regularization\",\n",
        "}\n"
      ],
      "execution_count": 452,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "cb333d4c-88f1-4b56-fd51-569d9f2b4181"
      },
      "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": 453,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\nClassifier Component: \n\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn]. \n\n2. A classification function that computes the estimated class y^ via\np(y|x). \n\n3, An objective function for learning, usually involving minimizing\nerror on training examples. \n\n4. An algorithm for optimizing the objective function.\n\nLearning in logistic regression: \n\n1. An objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nLoss on all training examples: log(p(all training labels)) = $-\\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nGradient descent: $theta = argmin_{theta} \\, 1/m \\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nupdate w: $w^{t + 1} = w'- n*(d/dw)f(x;w)$, where n is the learning rate; for muti-dimension change w to theta and f(x;w) to L(f(x;theta), y)\n\nderivitive of cross entropy is $[sigmoid(wx +b) - y]*x_j$ for i in all features \n\nAverage loss is to sum all the $L_{CE}$ for each example and normalize it \n\nThe loss for a batch of data or an entire dataset is just the average loss over the m\nexamples \n\nThe gradient for multiple data points is the sum of the individual gradients, which is $[sigmoid(wx +b) - y]*x_j$ \n\nsoftmax(zi) = $e^{z_i}/(\\sum_{j=1}^k e^{z_j})$ \n\n$L_{CE}(y^*, y)$ with softmax = -log ($e^{z_i}/(\\sum_{j=1}^k e^{z_j})$) \n\nComputation Graphs: Although backpropagation was invented for neural nets, it is related to general\nprocedure called backward differentiation, which depends on the notion of\ncomputation graphs.\nA computation graph represents the process of computing a mathematical expression.\nThe computation is broken down into separate operations. Each operation is a node in\na graph.\n\nBackward difference uses chain rule \n\nSummary:\n\n1. Like with logistic regression, we learn the best parameters for the neural net to make\nits predictions y^ as close to possible as the gold standard labels in our training data y.\n\n2. We use:\nA cross entropy loss function;\nGradient descent to perform optimization;\nError back propagation to compute the gradient of the loss function \n\n3. Since Neural Networks combine many perceptron-like neural units, we have many\nmore parameters in the models (weights and biases). This allows us to train systems to\nperform even more sophisticated tasks\n\n\n## Module 13 Definitions\n* **Linear classifier** - Inputs are feature values Each feature has a weight Sum is the activation\n* **Sigmoid function** - $y = 1/(1+e^{-z})$\n* **Mean squared error** - $L_{MSE}(y^*, y) = 1/2 (y^* - y)^2$\n* **Cross entropy loss** - $L_{CE}(y^*, y) = -[ylog(y^*) + (1-y)log(1-y^*)] = - \\sum_{i=1}^C y_i logy^*_i$\n* **Gradient descent** -  a method that finds a minimum of a function by figuring out in which direction to move based on slope\n* **Stochastic gradient descent** - chooses a single random example at a time and updates its weights on that example. As a result the updates can fluctuate.\n* ** batch training** - which computes the gradient over the entire dataset. a much better estimate of which direction to move the weights but takes a long time\n* **Mini-batch training** - The loss is then accumulated.\n* **Regularization** - a way to penalize large weights. A regularization term is added to the loss function.\n* **Softmax function** -  generalization of the sigmoid function\n* **Period disambiguation** - deciding if a period is the end of a sentence or part of a word\n* ** cost/lost function** - distance between the system output and the gold output\n* **Convex** - A convex function has just one minimum\n* **L2 regularization** - $\\sum_{j=1}^n (theta_j^2)$, aka lasso regression\n* **L1 regularization** - $\\sum_{j=1}^n (theta_j)$, aka ridge regression\n* **Interpretable** - we should know why our algorithms reach the conclusions they do\n* **Feedforward network** - the computation proceeds iteratively from one layer of units to the next\n* **Saturated** - very high values of z result in values of y extremely close to 1\n* **Xor problem** - its decision boundry cannot be decided by a single perceptron, but a neural network helps\n* **Pretraining** - the idea of relying on another algorithm to have already learned an embedding representation for our input words\n* **Hard classification** - only one class is the correct one, and that there is one output unit in y for each class\n* **Dropout** -  randomly dropping some units and their connections from the network during training as regularization\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"How do we get dense vectors: One recipe: train a classifier!\n",
        "1. Treat the target word and a neighboring context word as positive examples. 2. Randomly sample other words in the lexicon to get negative samples.\n",
        "3. Use logistic regression to train a classifier to distinguish those two cases.\n",
        "4. Use the weights as the embeddings.\\n\n",
        "Neural Language models have several advantages over n-gram LMs: \\n\n",
        "1. They don’t need smoothing \\n\n",
        "2. can handle much longer histories \\n\n",
        "3. can generalize over contexts of similar words \\n\n",
        "4. have much higher predictive accuracy \\n\n",
        "Disadv: slower to train than traditional n-gram LMs \\n\n",
        "Neural LMs: \\n\n",
        "input: k-gram of words \\n\n",
        "output: probability distribution over the next word \\n\n",
        "Term-Docu Matrix:\\n\n",
        "1. compare column by column we can see how two documents are similar \\n\n",
        "2. compare row by row can see how similar two words are \\n\n",
        "Better way to find similar words: L2 Normalization and cosine distance \\n\n",
        "context window: can be w +/- 2 for dependency pattern suj-v-obj \\n\n",
        "train a classifier to get dense vector: \\n\n",
        "1. Treat the target word and a neighboring context word as positive examples \\n\n",
        "2. Randomly sample other words in the lexicon to get negative samples \\n\n",
        "3. Use logistic regression to train a classifier to distinguish those two cases \\n\n",
        "4. Use the weights as the embeddings \\n\n",
        "Word2Vec: Learn embeddings as part of the process\n",
        "of word prediction; Train a classifier to predict neighboring\n",
        "words; Inspired by neural net language models; \n",
        "In so doing, learn dense embeddings for\n",
        "the words in the training corpus. \\n\n",
        "What does adaptive dynamic programming learn in addition to the utility function?\\n\n",
        "The transition model and reward function.\\n\n",
        "The value iteration algorithm alternates between what two steps until an equilibrium is reached?\\n\n",
        "Policy evaluation and policy improvement\\n\n",
        "Why does direct utility estimation converge slowly?\\n\n",
        "It ignores connections between states.\\n\n",
        "What passive reinforcement learning method builds on direct utility estimation to use the Bellman equations?\\n\n",
        "Adaptive Dynamic Programming\\n\n",
        "What is the advantage of reinforcement learning over supervised learning?\\n\n",
        "It is often easier to provide reward signals than labeled examples.\\n\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"Curse of dimensionality\": \" too many parameters to accurately estimate\",\n",
        "\"Antonyms\": \"words that have opposite meanings\",\n",
        "\"Connotations\": \"words that are positive or negative\",\n",
        "\"TF-IDF\": \"Term frequency - Inverse Document Frequency\",\n",
        "\"recurrent neural network\" : \" any network that contains a cycle within its network connections\", \n",
        "\"Backpropagation Through Time\": \"backpropagation algorithm for RNN, two passes\",\n",
        "\"teacher forcing\": \"always give the model the correct history sequence to predict the next word\",\n",
        "\"end-to-end training\": \" uses the loss from a downstream application to adjust the weights all the way through the network\",\n",
        "\"autoregressive generation\": \"using a language model to incrementally generate words by repeatedly sampling the next word conditioned on our previous choices\",\n",
        "\"vanishing gradients\": \" gradients are eventually driven to zero\",\n",
        "\"Long short-term memory\": \"removing information no longer needed and adding information likely to be needed for later decision making\",\n",
        "\" forget gate\": \"delete information from the context that is no longer needed\",\n",
        "\"add gate\": \"select the information to add to the current context\",\n",
        "\"output gate\": \"used to decide what information is required for the current hidden state\",\n",
        "\"transformers\": \"sequence processing that eliminates recurrent connections and returns to of the fully connected networks\",\n",
        "\"self-attention\": \"allows a network to directly extract and use information from arbitrarily large contexts\",\n",
        "\"positional embeddings\": \"start with randomly initialized embeddings corresponding to each possible input position up to some maximum length\",\n",
        "\"distributional hypothesis\": \"link between similarity in how words are distributed and similarity in what they mean\",\n",
        "\"embeddings\": \"representations of the meaning of words\",\n",
        "\"vector semantics\": \"instantiates distributional hypothesis by learning representations of the meaning of words\",\n",
        "\"polysemous\": \"have multiple senses\",\n",
        "\"principle of contrast\": \"a difference in linguistic form is always associated with some difference in meaning\",\n",
        "\"semantic field\": \" a set of words which cover a particular semantic domain and bear structured relations with each other\",\n",
        "\"semantic frame\": \"a set of words that denote perspectives or participants in a particular type of event\",\n",
        "\"contextual embeddings\": \"the vector for each word is different in different contexts\",\n",
        "\"static embeddings\": \"learns one fixed embedding for each word in the vocabulary\",\n",
        "\"skip-gram model\": \"uses stochastic gradient descent, learning embeddings that have a high dot product with nearby words, a low dot product with noise words\",\n",
        "\"first-order co-occurrence\": \"they are typically nearby each other\",\n",
        "\"second-order co-occurrence\": \"they have similar neighbors\",\n",
        "\"allocational harm\": \"a system allocates resources (jobs or credit) unfairly to different groups\",\n",
        "\"GloVe\": \" embedding algorithms based on ratios of word co-occurrence probabilities.\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": 454,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d0830dd9-d25e-4d35-bc2d-b214059d4ef1"
      },
      "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": 455,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\nClassifier Component: \n\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn]. \n\n2. A classification function that computes the estimated class y^ via\np(y|x). \n\n3, An objective function for learning, usually involving minimizing\nerror on training examples. \n\n4. An algorithm for optimizing the objective function.\n\nLearning in logistic regression: \n\n1. An objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nLoss on all training examples: log(p(all training labels)) = $-\\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nGradient descent: $theta = argmin_{theta} \\, 1/m \\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nupdate w: $w^{t + 1} = w'- n*(d/dw)f(x;w)$, where n is the learning rate; for muti-dimension change w to theta and f(x;w) to L(f(x;theta), y)\n\nderivitive of cross entropy is $[sigmoid(wx +b) - y]*x_j$ for i in all features \n\nAverage loss is to sum all the $L_{CE}$ for each example and normalize it \n\nThe loss for a batch of data or an entire dataset is just the average loss over the m\nexamples \n\nThe gradient for multiple data points is the sum of the individual gradients, which is $[sigmoid(wx +b) - y]*x_j$ \n\nsoftmax(zi) = $e^{z_i}/(\\sum_{j=1}^k e^{z_j})$ \n\n$L_{CE}(y^*, y)$ with softmax = -log ($e^{z_i}/(\\sum_{j=1}^k e^{z_j})$) \n\nComputation Graphs: Although backpropagation was invented for neural nets, it is related to general\nprocedure called backward differentiation, which depends on the notion of\ncomputation graphs.\nA computation graph represents the process of computing a mathematical expression.\nThe computation is broken down into separate operations. Each operation is a node in\na graph.\n\nBackward difference uses chain rule \n\nSummary:\n\n1. Like with logistic regression, we learn the best parameters for the neural net to make\nits predictions y^ as close to possible as the gold standard labels in our training data y.\n\n2. We use:\nA cross entropy loss function;\nGradient descent to perform optimization;\nError back propagation to compute the gradient of the loss function \n\n3. Since Neural Networks combine many perceptron-like neural units, we have many\nmore parameters in the models (weights and biases). This allows us to train systems to\nperform even more sophisticated tasks\n\n\n## Module 14 Definitions\n* **Curse of dimensionality** -  too many parameters to accurately estimate\n* **Antonyms** - words that have opposite meanings\n* **Connotations** - words that are positive or negative\n* **Tf-idf** - Term frequency - Inverse Document Frequency\n* **Recurrent neural network** -  any network that contains a cycle within its network connections\n* **Backpropagation through time** - backpropagation algorithm for RNN, two passes\n* **Teacher forcing** - always give the model the correct history sequence to predict the next word\n* **End-to-end training** -  uses the loss from a downstream application to adjust the weights all the way through the network\n* **Autoregressive generation** - using a language model to incrementally generate words by repeatedly sampling the next word conditioned on our previous choices\n* **Vanishing gradients** -  gradients are eventually driven to zero\n* **Long short-term memory** - removing information no longer needed and adding information likely to be needed for later decision making\n* ** forget gate** - delete information from the context that is no longer needed\n* **Add gate** - select the information to add to the current context\n* **Output gate** - used to decide what information is required for the current hidden state\n* **Transformers** - sequence processing that eliminates recurrent connections and returns to of the fully connected networks\n* **Self-attention** - allows a network to directly extract and use information from arbitrarily large contexts\n* **Positional embeddings** - start with randomly initialized embeddings corresponding to each possible input position up to some maximum length\n* **Distributional hypothesis** - link between similarity in how words are distributed and similarity in what they mean\n* **Embeddings** - representations of the meaning of words\n* **Vector semantics** - instantiates distributional hypothesis by learning representations of the meaning of words\n* **Polysemous** - have multiple senses\n* **Principle of contrast** - a difference in linguistic form is always associated with some difference in meaning\n* **Semantic field** -  a set of words which cover a particular semantic domain and bear structured relations with each other\n* **Semantic frame** - a set of words that denote perspectives or participants in a particular type of event\n* **Contextual embeddings** - the vector for each word is different in different contexts\n* **Static embeddings** - learns one fixed embedding for each word in the vocabulary\n* **Skip-gram model** - uses stochastic gradient descent, learning embeddings that have a high dot product with nearby words, a low dot product with noise words\n* **First-order co-occurrence** - they are typically nearby each other\n* **Second-order co-occurrence** - they have similar neighbors\n* **Allocational harm** - a system allocates resources (jobs or credit) unfairly to different groups\n* **Glove** -  embedding algorithms based on ratios of word co-occurrence probabilities.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "93d17a2f-bf8d-42e0-8593-d3e199148684"
      },
      "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": 456,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'stationary policy' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n The transition model is given by $P(s'|s,a)$, the probability that action a in state s reaches state s'. The probability of reaching by s' doing a in the current state:  $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\nUtility Functions\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nsequential decision problems: in which the agent’s utility depends on a sequence of decisions\n\n## AIMA Chapter 17.2 Algorithms for MDPs\nIn this section, we present four different algorithms for solving MDPs. The first three, value iteration, policy iteration, and linear programming, generate exact solutions offline. The fourth is a family of online approximate algorithms that includes Monte Carlo planning.\n\n## Module 8 Lecture Notes\nA Markov decision process or MDP is a sequential decision problem for a fully observable environment\nwith a stochastic transition model that has additive rewards. MDPs are non-deterministic search problems. One way of solving them\n is via expectimax search.\n\n MDP:\n A set of states s ∈ S\n• A set of actions a ∈ A\n• A transition function T(s, a, s’)\n   Probability that executing action a in s will lead to s’ P(s’ | s, a)\n   The probability is called the model\n• A reward function R(s, a, s’)\n   Sometimes just R(s) or R(s’)\n• An initial state s0\n• Optionally, one or more terminal states\n\nComparison \nIn value iteration:\n• Every iteration updates both the values and (implicitly) the policy\n• We don’t track the policy, but taking the max over actions implicitly recomputes it \n\nIn policy iteration:\n• We do several passes that update utilities with fixed policy (each pass is fast because we consider only one action, not all of them)\n• After the policy is evaluated, a new policy is chosen (slow like a value iteration pass)\n• The new policy will be better (or we’re done) Both are dynamic programs for solving MDPs\n\n## Module 8 Definitions\n* **Utility function u(s)** - The agent’s preferences are captured by a utility function, which assigns a single number to express the desirability of a state\n* **Th** - Theorem:any“rational”preferencescan be summarized as a utility function\n* **Expected utility** - $EU(a) = \\sum_s P(resulr(a)=s)U(s)$\n* **Maximum expected utility (meu)** - $action=argmax_a EU(a)$\n* **Lottery l** - each action as a ticket. $L=[p_1,S_1; ... ; p_,S_n]$\n* **Orderability** - exactly one of A>B, B>A, A~B holds\n* **Transitivity** - $A>B \\land B>C => A>C$\n* **Continuity** - $A>B>C => \\exists p \\ [p,A;1-p,C]\\sim B$\n* **Substitutability** - $A \\sim B => [p,A;1-p,C]\\sim [p,B;1-p,C]$\n* **Monotonicity** - $A>B =>(p>q\\ <=>  [p,A;1-p,B]>[q,A;1-q,B])$\n* **Decomposability** - \n* **Existence of utility function** - U(A)>U(B) <=> A>B\n* **Expected utility of a lottery** - U([p1, S1; ...; n, Sn]) = $\\sum_i p_i U(S_i)$\n* **Value function or ordinal utility function** - in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\n* **Preference elicitation** - work out utility function--involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n* **Normalized utilities** - (best possible prize at U(S)=$u_T$ and worst possible catastrophe at U(S)=$u_\\perp$) $u_\\perp=0,\\ u_T=1$\n* **Standard lottery** - $[p,u_T; 1-p,u_\\perp]$\n* **Qaly** - quality-adjusted life year\n* **Micromort** - a one in a million chance of death\n* **Expected monetary value (emv)** - \n* **Risk-averse** - they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n* **Risk-seeking** - antonyms of risk-averse\n* **Certainty equivalent** - The value an agent will accept in lieu of a lottery\n* **Insurance premium** - The difference between the EMV of a lottery and its certainty equivalent\n* **Risk-neutral** - An agent that has a linear curve\n* **Unbiased** - the expected value of the error, E($\\widehat{EU}(a)-EU(a))$, is zero\n* **Order statistic** - the distribution of any particular ranked element of a sample\n* **Normative theory** - it describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents—for example, humans— really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** -  Most people elect the known probability rather than the unknown unknowns.\n* **Framing effect** - the exact wording of a decision problem can have a big impact on the agent’s choices\n* **Anchoring effect** - People feel more comfortable making relative utility judgments rather than absolute ones.\n* **Transition model** - describes the outcome of each action in each state\n* **Optimal policy** - a policy that yields the highest expected utility $\\pi^*$\n* **Finite horizon** - there is a fixed time after which nothing matters—the game is over. $U_h([s_0,a_0,...,S_{N+k}]])=U_h(s_0,a_0,...,S_{N})$\n* **Nonstationary** - A policy that depends on the time\n* **Stationary policy** - With no fixed time limit, on the other hand, there is no reason to behave differently in the same state at different times. Hence, an optimal action depends only on the current state, and the optimal policy is stationary\n* **Additive discounted rewards** - $U([s_0,a_0,...]) = R(s_0,a_0,s_1)+\\gamma R(s_1,a_1,s_2)$\n* **Q-function** - expected utility of taking a given action in a given state\n* **Shaping theorem** - the following transformation leaves the optimal policy unchanged:$R'(s,a,s') = R(s,a,s')+\\gamma \\Phi(s')-\\Phi(s)$\n* **** - \n\n\n## WARNING: Your definition of 'MODEL-BASED REINFORCEMENT LEARNING' is too long!\nWARNING: Your definition of 'passive reinforcement learning' is too long!\nWARNING: Your definition of 'passive learning agent' is too long!\nWARNING: Your definition of 'direct utility estimation' is too long!\nWARNING: Your definition of 'adaptive dynamic programming' is too long!\nWARNING: Your definition of 'rehgret' is too long!\nWARNING: Your definition of 'off-policy' is too long!\nWARNING: Your definition of 'on-policy' is too long!\nWARNING: Your definition of 'correlated sampling' is too long!\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nBandit Problems: a one-armed bandit is a slot machine. A gambler can insert a coin, pull the lever, and collect the winnings (if any).\n An -armed bandit has levers. Behind each lever is a fixed but unknown probability distribution of winnings; each pull samples from that unknown distribution.\n\n The gambler must choose which lever to play on each successive coin—the one that has paid off best, or maybe one that has not been \n tried yet? This is an example of the ubiquitous tradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information, which can in some cases be\nconverted into a better policy and better long-term rewards.\n\n## AIMA Chapter 22.1 Learning from Rewards\nMODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither\nknows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave.\nACTION-UTILITY LEARNING:The most common form of action-utility learning is Q-learning, where the agent learns a Q-function, or quality-function, denoting the sum of rewards from state onward if action is taken. Given a Q-function, the agent can\n  choose what to do in by finding the action with the highest Q-value.\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n The passive learning task is similar to the policy evaluation task, part of the policy iteration algorithm.\nThe difference is passive learning agent does not know the transition modelP(s'|s,a), which specific the prob of reaching\nstate s' from state after doing action a;nor does it know reward function, which specifies the reward for each transition. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nMove from ADP to TD: Solving the underlying MDP is not the only way to use the Bellman equations more effectively. \n\nWhile ADP adjusts a state to agree with all possible successors, TD adjusts a state to agree with the successor observed \nin the current trial. \n\na TD Q-learning agent does not need a transition model, P(s'|s,a), either for learning or for action selection\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nGeneralization in Reinforcement Learning \n\n## Module 9 Lecture Notes\nExploration: you have to try unknown actions to get information \n\nExploitation: eventually, you have to use what you know\n\nRegret: even if you learn intelligently, you make mistakes\n\nSampling: because of chance, you have to try things repeatedly\n\nDifficulty: learning can be much harder than solving a known MDP\n\nBasic idea:\nReceive feedback in the form of rewards. \nAgent’s utility is defined by the reward function. \nMust (learn to) act so as to maximize expected rewards. All learning is based on observed samples of outcomes!\n\n## Module 9 Definitions\n* **Markov reward process** - an MDP with only one possible action a_i.Each arm is a MRP\n* **Gittins index** - $\\lambda = $\n* **Model-based reinforcement learning** - the agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. The model may be initially unknown, in which case the agent learns the model from observing the effects of its actions,  or it may already be known\n* **Policy search** - The agent learns a policy that maps directly from states to actions\n* **Passive reinforcement learning** - the agent’s policy is fixed and the task is to learn the utilities of states (or of state–action pairs); this could also involve learning a model of the environment.\n* **Exploration** - an agent must experience as much as possible of its environment in order to learn how to behave in it\n* **Apprenticeship learning** - training a learning agent using demonstrations rather than reward signals\n* **Passive learning agent** - The agent is trying to learn $U^{\\pi}(s)$ —the expected total discounted reward                     if policy $\\pi$ is executed beginning in state s\n* **Good about direct evaluation** - It’s easy to understand. It doesn’t require any knowledge of T, R. It eventually computes the correct average values, using just sample transitions\n* **Bad about direct evaluation** - It wastes information about state connections. Each state must be learned separately. So, it takes a long time to learn\n* **Diff between passive learning and policy evaluation** - The passive learning agent doesn't necessarily know the transition probability P(s'∣s,a) or the reward function R\n* **Direct utility estimation** - the utility of a state is defined as the expected total reward           from that state onward (called the expected reward-to-go), and that each trial provides a sample of this quantity for each state visited\n* **Adaptive dynamic programming** - agent takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming\n* **Temporal-difference (td) equation** - $U^{\\pi}(s)<-U^{\\pi}(s)+\u0007lpha [R+\\gamma U(s')-U(s)]$\n* **Problem of td** - if we want to turn values into a (new) policy, we’re sunk -> learn Q-values, not values. Makes action selection model-free too!\n* **Active learning agent** - A passive learning agent has a fixed policy that determines its behavior. An active learning agent gets to decide what actions to take\n* **Rehgret** - Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality,  and optimal (expected) rewards. Minimizing regret goes beyond learning to be optimal – it requires optimally learning to be optimal  Example: random exploration and exploration functions both end up optimal, but random exploration has higher regret\n* **Bayesian reinforcement learning** - \n* **Reward-to-go** - the total reward from a particular state onwards given a policy\n* **Off-policy** - Q-learning is an off-policy learning algorithm, because it learns Q-values that answer the question “What would this action be worth in this state, assuming that I stop using whatever policy I am using now, and start acting according to a policy that chooses the best action (according to my estimates)?\n* **On-policy** - SARSA is an on-policy algorithm: it learns Q-values that answer the question “What would this action be worth in this state, assuming I stick with my policy?\n* **Widrow–hoff rule, or the delta rule** - $\theta_i <- \theta_i + \u0007lpha [u_j(s)-\\hat{U}_\theta (s)]\frac{\\partial \\hat{U}_\theta (s)}{\\partial \theta_i}$\n* **Approximating temporal-difference learning** - adjust the parameters to try to reduce the temporal difference between successive states.(apply delta rule)\n* **Correlated sampling** - ex. A better solution for blackjack is to generate a certain number of hands in advance and have each program play the same set of hands. In this way, we eliminate the measurement error due to differences in the cards received. Only a few thousand hands are needed to determine which of the two blackjack policies is better.\n* **** - \n\n\n## WARNING: Your definition of 'LAZINESS' is too long!\nWARNING: Your definition of 'PRACTICAL IGNORANCE' is too long!\nWARNING: Your definition of 'Problems for MLE' is too long!\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Naive Bayes Models \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\nN-gram Language Models. \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nStupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. If a higher-order n-gram has a zero count, we simply backoff to a lower  order n-gram, weighed by a fixed (context-independent) weight.\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states that it might be in\n* **Laziness** -  It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n* **Theoretical ignorance** - Medical science has no complete theory for the domain.\n* **Practical ignorance** - Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n* **Decision theory** - decision theory=probability  theory + utility theory\n* **An agent is rational** - if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action.\n* **Sample space** - the set of all possible worlds\n* **Unconditional or prior probabilities** - degrees of belief in propositions in the absence of any other information\n* **Product rule** - $P(a \\land b) = P(a|b)P(b)$\n* **Probability density function** - the probability that a random variable takes on some value as a parameterized function of \n* **Inclusion–exclusion principle** - $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n* **Probabilistic inference** - the computation of posterior probabilities for query propositions given observed evidence\n* **Independence** - also marginal independence and absolute independence\n* **Language models or lms** - Models that assign probabilities to sequences of words\n* **N-gram** - An n-gram is a sequence of n words\n* **Markov assumption** - the probability of a word depends only on the previous word\n* **Extrinsic evaluation** - embed it in an application and measure how much the application improves. expensive\n* **Intrinsic evaluation** - mea- sures the quality of a model independent of any application.\n* **Perplexity** - perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words\n* **Unknown words, or out of vocabulary (oov) words** - words we haven’t seen before\n* **Laplace smoothing/add-one smoothing** - $P(w_i) = \frac{c_i+1}{N+V}$.  V words in the vocabulary\n* **Unsmoothed maximum likelihood estimate of the unigram probability** - MLE of the word wi is its count ci normalized by the total number of word tokens N:$P(w_i) = \frac{c_i}{N}$\n* **Add-k smoothing** - $P*(wn|wn−1) = \frac{ C(w_{n−1}w_n) + k}{ C(w_{n−1}) + kV }$\n* **Stupid backoff** - \n* **Problems for mle** - Out of vocabulary items (OOV); <unk> to deal with OOVs; Fixed lexicon L of size V; Normalize training data by replacing any word not in L with <unk>  Avoid zeros with smoothing\n\n\n## WARNING: Your definition of 'independence property' is too long!\nWARNING: Your definition of 'D-separation' is too long!\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian networks can represent essentially any full joint probability distribution,it's a directed graph.\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\nactive--A path is active if each triple is active:\n Causal chain A -> B -> C where B is unobserved (either direction);\n Common cause A <- B -> C where B is unobserved;\n Common effect (aka v-structure) A -> B <- C where B or one of its descendents is observed\n\n  Bayes nets compactly encode joint distributions.\n  Guaranteed independencies of distributions can be deduced from BN graph structure.\n  D-separation gives precise conditional independence guarantees from graph alone.\n  A Bayes’ Net’s joint distribution may have further (conditional) independence that is not detectable until you inspect its specific distribution.\n \n\n\n Models are always simplifications \n\nConditional Independence:\n\n1. Unconditional (absolute) independence very rare, and it\ndoesn’t help us make inferences about other variables.\n\n2. Conditional independence is our most basic and robust form\nof knowledge about uncertain environments.\n\n3. X is conditionally independent of Y given Z, iff, $forall x, y, z, P(x, y|z) = P(x|z)P(y|z) \\; or \\; P(x|z, y) = P(x|z)$ \n\nBayes Net Semantic: \n\n1. A set of nodes, one per variable X \n\n2. A directed, acyclic graph \n\n3. A conditional distribution for each node; A collection of distributions over X, one for each\ncombination of parents’ values $P(x|a1, a2..)$ where the a are the parents;  \n\nBayes’ nets implicitly encode joint distributions as a product of local conditional distributions, Not every BN can represent every joint distribution, The topology enforces certain conditional independencies \n\nWhy we guaranteed that setting $P(x_1, x_2..x_n) = \\prod_{i=1}^n P(x_i|parents(X_i))$: \n\n1. Chain Rule: $P(x_1, x_2..x_n) = \\prod_{i=1}^n P(x_i|x_1..x_{i-1})$ \n\n2. Assume conditional independences: $P(x_i | x_1 ... x_{i-1}) = P(x_i|parents(X_i))$\n\nBNs need not actually be causal, Sometimes no causal net exists over the domain, correlation != causation \n\nTopology may happen to encode causal structure\nTopology really encodes conditional independence\n\nCommon Cause: \n\n1. Y: project due -> X: Piazza busy; Z: Office hour full \n\n2. X not guaranteed independent of Z, but X, Z are independent given Y \n\n3. Cause blocks the influence between effects \n\nCommon Effect: \n\n1. X: raining, Y: Ballgame -> Z Traffic \n\n2. X, Y independent, but X, Y not independent given Z because see traffic puts X and Y in competition as explanation \n\nD-Separation: check all (undirected) paths between Xi and Xj, if one or more active, conditional independence not guaranteed, else if all paths are inactive, the independence is guaranteed \n\nGiven a Bayes net structure, can run dseparation algorithm to build a complete list of\nconditional independences that are necessarily\ntrue of the form \n\nBayes Net Summary: \n\n1. Bayes nets compactly encode joint distributions \n\n2. Guaranteed independencies of distributions can be\ndeduced from BN graph structure \n\n3. D-separation gives precise conditional independence\nguarantees from graph alone \n\n4. A Bayes’ Net’s joint distribution may have further\n(conditional) independence that is not detectable until\nyou inspect its specific distribution \n\nInference: $argmax_q P(Q=q|E_1 = e_1...)$ \n\nInference by enumeration is too slow to be practical, better use variable elimination \n\nVariable Elimination: Interleave joining and marginalizing, Still NP-hard, but usually much faster than inference by enumeration \n\n\n\n## Module 11 Definitions\n* **Conditioning case** - a possible combination of values for the parent nodes—a miniature possible world\n* **Non-descendants property** - a variable is conditionally independent of all other nodes in the network given its Markov blanket\n* **Independence property** - a variable is conditionally independent of all other nodes in the network, given its parents, children,      and children’s parents—that is, given its Markov blanket.\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Absolute independence** - No interactions between variables\n* **D-separation** - Given a Bayes net structure, can run d- separation algorithm to build a complete list of conditional       independences that are necessarily true of the form $X_i \\prep X_j | {X_{k_1} ... X_{k_n} }$\n* **Bayes' net** - a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n* **Active path** - A path is active if each triple is active else inactive\n* **Inference** - calculating some useful quantity from a joint probability distribution\n* **Topological ordering** - in any order consistent with the directed graph structure\n* **Locally structured** - Sparse\n* **Markov blanket** - its parents, children, and children’s parents\n* **Moral graph** - Add links between any unlinked pair of nodes that share a common child\n* **Deterministic nodes** - has its value specified exactly by the values of its parents, with no uncertainty\n* **Context-specific independence** - a variable is conditionally independent of some of its parents given certain values of others\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Nonparametric** - define the conditional distribution implicitly with a collection of instances\n* **Hybrid bayesian network** - A network with both discrete and continuous variables\n* **Hidden variables** - neither input nor output variables, but are essential for structuring the network\n* **Singly connected networks or polytrees** - The time and space complexity of exact inference in polytrees is linear in the size of the network.\n\n\n## WARNING: Your definition of 'binary perceptron learning' is too long!\nWARNING: Your definition of 'stochastic gradient descent' is too long!\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nAn agent is learning if it improves its performance after making observations about the world.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\nNaïve Bayes\n• Builds a model training data\n• Gives prediction probabilities\n• Strong assumptions about feature independence • One pass through data (counting)\nPerceptrons / MIRA:\n• Makes less assumptions about data\n• Mistake-driven learning\n• Multiple passes through data (prediction) • Often more accurate\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\nMachine learning: how to acquire a model from data / experience\n\n• Learning parameters (e.g. probabilities)\n• Learning structure (e.g. BN graphs)\n• Learning hidden concepts (e.g. clustering)\nToday: model-based classification with Naive Bayes and Perceptrons\n\n Model-based approach:\n\n1. Build a model where both the label and features are random variables \n\n2. Instantiate any observed features \n\n3. Query for the distribution of the\nlabel conditioned on the features \n\nInference for Naïve Bayes:\n\n1. get joint probability of label and evidence for each label [$P(y1, f1...fn)$; $P(y2, f1...fn)$ ...] \n\n2. sum to get probability of evidence $P(f1...fn)$ \n\n3. normalize by dividing each label in Step 1 by Step 2 \n\nGeneral Naïve Bayes: \n\n1. Method1: Inference for Naïve Bayes\n\n2. Method2: Estimates of local conditional probability tables\n\nTo generalize better and avoid overfitting: we need to smooth or regularize the estimates \n\nEstimating the distribution of a random variable: Elicitation: ask a human(hard); Empirically: use training data (learning!) \n\nRelative frequency is the maximum likelihood, see before for that function \n\nget a baseline; Baselines are very simple “straw man” procedures; Help determine how hard the task is; Help know what a “good” accuracy is; careful about weak baseline \n\nThe confidence of a probabilistic classifier: $confidence(x) = max_y P(y|x)$, Represents how sure the classifier is of\nthe classification; No guarantee confidence is correct \n\nCalibration: Weak calibration: higher confidences\nmean higher accuracy; Strong calibration: confidence predicts\naccuracy rate \n\nSummary: \n\n1. Bayes rule lets us do diagnostic queries with causal probabilities\n\n2. The naïve Bayes assumption takes all features to be independent given\nthe class label \n\n3. We can build classifiers out of a naïve Bayes model using training data \n\n4. Smoothing estimates is important in real systems \n\n5. Classifier confidences are useful, when you can get them \n\nNaïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are\nword occurrences)\n\nBinary Decision Rule:\n\nIn the space of feature vectors; Examples are points;\nAny weight vector is a hyperplane;\nOne side corresponds to Y=+1;\nOther corresponds to Y=-1; \n\nLeaning(Binary): start with w = 0, classify examples, if wrong, update w = w + y^ * f, where y^ is the prediction and f is the feature vector\n\nMulti-class decision rule: each class has a $w_y$, y^ = $argmax_y w_y * f(x)$, if wrong, update $w_y = w_y - f(x)$ and $w_{y^*} = w_{y^*} + f(x)$ $y^*$ is also y^\n\nProperties of perceptron:\n\n1. Separability: true if some parameters get the training\nset perfectly correct \n\n2. Convergence: if the training is separable, perceptron\nwill eventually converge (binary case) \n\n3. Mistake Bound: the maximum number of mistakes\n(binary case) related to the margin or degree of\nseparability \n\nProblems with Perceptron:\n\n1. Noise: if the data isn’t separable,\nweights might thrash; Averaging weight vectors over\ntime can help (averaged\nperceptron) \n\n2. Mediocre generalization: finds a\n“barely” separating solution\n\n3. Overtraining: test / held-out\naccuracy usually rises, then falls; Overtraining is a kind of\noverfitting \n\nFixes:\n\n1. MIRA: $min_w 1/2*||w-w'||^2$; choose an update size that fixes the current\nmistake but, minimizes the change to w; $w_y = w_y' - t*f(x)$ and $w_{y^*} = w_{y^*}' + t*f(x)$, where $t=((w_y' - w_{y^*}') * f + 1)/(2*f*f)$ \n\n2. In practice, it’s also bad to make updates that are too large; so we  cap the maximum possible value of t with some\nconstant C; $t = min(t, C)$, faster, and usually better, especially on noisy data \n\n3. Support Vector Machine: finds the separator with max margin(best); $min_w 1/2* ||w||^2$; SVM is MIRA that optimize over all examples at once \n\nNaive Bayes vs. Perceptron: \n\n1. Builds a model training data; make less assumptions about data \n\n2. Give prediction probabilities; Mistake-driven learning \n\n3. One pass through data; Multiple passes through data \n\n4. Strong assumptions about feature independence; Often more accurate \n\nA complex network of perceptrons could make quite subtle\ndecisions \n\n\n## Module 12 Definitions\n* **Baseline** -  Baselines are very simple “straw man” procedures • Help determine how hard the task is. Help know what a “good” accuracy is\n* **Confidence** - Represents how sure the classifier is of the classification. Any probabilistic model will have confidences. No guarantee confidence is correct\n* **Binary perceptron learning** - Start with weights = 0. For each training instance:\n • Classify with current weights:y=+1 if w·f(x)>=0 • If correct (i.e., y=y*), no change! • If wrong: $w = w+y^* · f$\n* **Problems with the perceptron** - Noise: if the data isn’t separable, weights might thrash->Averaging weight vectors over time can help (averaged perceptron)\n* **Problem with proceptron** - Overtraining: test / held-out accuracy usually rises, then falls\n* **Stochastic gradient descent** - function STOCHASTIC GRADIENT DESCENT(L(), f (), x, y) returns $ \\Theta$ # where: L is the loss function# f is a function parameterized by $\\Theta$# x is the set of training inputs x^(1), x^(2),..., x^(n)# y is the set of training outputs (labels) y^(1), y^(2),..., y^(n).\n  $\\Theta <- 0$.\nrepeat T times\n  For each training tuple (x^{(i)}, y^{(i)}); \n   Compute $\\hat{y}^{(i)} = f(x^{(i)};\\Theta)$; \n   Compute the loss $L(\\hat{y}^{(i)},y^{(i)})$; $g <— \\Delta_\\Theta L(f(x^{(i)};\\Theta),y^{(i)})$; \n  $\\Theta <- \\Theta - \\eta g$; \n  return $\\Theta$\n* **Naïve bayes** - Assume all features are independent effects of the label\n* **General naïve bayes formula** - $P(Y, F_1 .. F_n) = P(Y) \\prod_i P(F_i|Y)$\n* **Bag-of-words** - because model is insensitive to word order or reordering\n* **Data** - labeled instances: Training set, Held out set, Test set\n* **Features** - attribute-value pairs which characterize each x\n* **Experimentation cycle** - Learn parameters on training set, Tune hyperparameters on held-out set), Compute accuracy of test set\n* **Accuracy** - fraction of instances predicted correctly\n* **Overfitting** -  fitting the training data very closely, but not generalizing well\n* **Laplace smoothing** - Pretend you saw every outcome once more than you actually did\n* **Linear interpolation** - $P(x|y) = a*P(x|y) + (1-a)P(x)$\n* **Tuning** - For each value of the hyperparameters, train and test on the held-out data\n* **Linear classifier** - Inputs are feature values Each feature has a weight Sum is the activation\n* **Activation fucntions** - sigmoid; tanh;  rectified linear unit ReLU\n* **Machine learning** - observes some data, builds a model, and uses the model as both a hypothesis about the world and a software that can solve problems\n* **Transfer learning** - knowledge from one domain is transferred to a new domain, so that learning can proceed faster with less data\n* **Classification** - output is one of a finite set of values\n* **Regression** - output is a number\n* **Supervised learning** - agent observes input-output pairs and learns a function that maps from input to output\n* **Unsupervised learning** - agent learns patterns in the input without any explicit feedback\n* **Reinforcement learning** - agent learns from a series of reinforcements: rewards and punishments\n* **Hypothesis space** - set of possible functions. same as model class\n* **Exploratory data analysis** - examining the data with statistical tests and visualizations, to get a feel for the data\n* **Consistent hypothesis** - h such that each x in the training set has y\n* **Best-fit function** - each h(xi) is close to yi\n* **Underfitting** - fails to find a pattern in the data\n* **Variance** - the amount of change in the hypothesis due to fluctuation in the training data\n* **Bias–variance tradeoff** - a choice between hypotheses that fit the training data well and that may generalize better\n* **Decision tree** - representation of a function that maps a vector of features to a single output value\n* **Happy graphs** - as the training set size grows, the accuracy increases\n* **Entropy** - a measure of the uncertainty of a random variable; the more information, the less entropy\n* **Decision tree pruning** - Pruning works by eliminating nodes that are not clearly relevant\n* **Early stopping** - have the decision tree algorithm stop generating nodes when there is no good attribute to split on\n* **Regression tree** - A regression tree has at each leaf a linear function of some subset of numerical attributes\n* **Unstable** - adding just one new example can change the test at the root\n* **Stationarity** - assumption that the future examples will be like the past\n* **Hyperparameters** - parameters of the model class, not of the individual model\n* **Validation set** - evaluate the candidate models and choose the best one\n* **Interpolated** - a model that exactly fits all the training data has interpolated the data.\n* **Realizable** - hypothesis space actually contains the true function\n* **Noisy** - it may return different values of f(x) for the same x\n* **Regularization** - process of explicitly penalizing complex hypotheses\n* **Grid search** - try all combinations of values and see which performs best on the validation data\n* **Bayesian optimization** - treats the task of choosing good hyperparameter values as a machine learning problem in itself\n* **Computational learning theory** - any hypothesis that is seriously wrong will almost certainly be “found out” with high probability\n* **Probably approximately correct** - hypothesis that is consistent with a sufficiently large set of training examples\n* **Pac learning** - Any learning algorithm that returns hypotheses that are probably approximately correct\n* **Sparse model** - it often sets many weights to zero\n* **Text categorization** - the task of assigning a label to an entire text\n* **Probabilistic classifier** -  tell us the probability of the observation being in the class\n* **Generative classifiers** - like naive Bayes build a model of how a class could generate some input data\n* **Discriminative classifiers** - like logistic regression instead learn what features from input are most useful to discriminate\n* **Stop word** -  very frequent words like the , .\n* **Sentiment lexicons** -  lists of words that are preannotated with positive or negative sentiment\n* **Precision** - true positive/(true positive + false positive)\n* **Recall** - true positive/(true positive + false negative)\n* **Macroaveraging** - compute the performance for each class, and then average over classes\n* **Microaveraging** - we build into a single confusion matrix, and then compute precision and recall from that table\n* **Bootstrap test** - create many virtual test sets from an observed test set by repeatedly sampling from it\n* **Representational harms** - , harms caused by a system that demeans a social group\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\nClassifier Component: \n\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn]. \n\n2. A classification function that computes the estimated class y^ via\np(y|x). \n\n3, An objective function for learning, usually involving minimizing\nerror on training examples. \n\n4. An algorithm for optimizing the objective function.\n\nLearning in logistic regression: \n\n1. An objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nLoss on all training examples: log(p(all training labels)) = $-\\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nGradient descent: $theta = argmin_{theta} \\, 1/m \\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nupdate w: $w^{t + 1} = w'- n*(d/dw)f(x;w)$, where n is the learning rate; for muti-dimension change w to theta and f(x;w) to L(f(x;theta), y)\n\nderivitive of cross entropy is $[sigmoid(wx +b) - y]*x_j$ for i in all features \n\nAverage loss is to sum all the $L_{CE}$ for each example and normalize it \n\nThe loss for a batch of data or an entire dataset is just the average loss over the m\nexamples \n\nThe gradient for multiple data points is the sum of the individual gradients, which is $[sigmoid(wx +b) - y]*x_j$ \n\nsoftmax(zi) = $e^{z_i}/(\\sum_{j=1}^k e^{z_j})$ \n\n$L_{CE}(y^*, y)$ with softmax = -log ($e^{z_i}/(\\sum_{j=1}^k e^{z_j})$) \n\nComputation Graphs: Although backpropagation was invented for neural nets, it is related to general\nprocedure called backward differentiation, which depends on the notion of\ncomputation graphs.\nA computation graph represents the process of computing a mathematical expression.\nThe computation is broken down into separate operations. Each operation is a node in\na graph.\n\nBackward difference uses chain rule \n\nSummary:\n\n1. Like with logistic regression, we learn the best parameters for the neural net to make\nits predictions y^ as close to possible as the gold standard labels in our training data y.\n\n2. We use:\nA cross entropy loss function;\nGradient descent to perform optimization;\nError back propagation to compute the gradient of the loss function \n\n3. Since Neural Networks combine many perceptron-like neural units, we have many\nmore parameters in the models (weights and biases). This allows us to train systems to\nperform even more sophisticated tasks\n\n\n## Module 13 Definitions\n* **Linear classifier** - Inputs are feature values Each feature has a weight Sum is the activation\n* **Sigmoid function** - $y = 1/(1+e^{-z})$\n* **Mean squared error** - $L_{MSE}(y^*, y) = 1/2 (y^* - y)^2$\n* **Cross entropy loss** - $L_{CE}(y^*, y) = -[ylog(y^*) + (1-y)log(1-y^*)] = - \\sum_{i=1}^C y_i logy^*_i$\n* **Gradient descent** -  a method that finds a minimum of a function by figuring out in which direction to move based on slope\n* **Stochastic gradient descent** - chooses a single random example at a time and updates its weights on that example. As a result the updates can fluctuate.\n* ** batch training** - which computes the gradient over the entire dataset. a much better estimate of which direction to move the weights but takes a long time\n* **Mini-batch training** - The loss is then accumulated.\n* **Regularization** - a way to penalize large weights. A regularization term is added to the loss function.\n* **Softmax function** -  generalization of the sigmoid function\n* **Period disambiguation** - deciding if a period is the end of a sentence or part of a word\n* ** cost/lost function** - distance between the system output and the gold output\n* **Convex** - A convex function has just one minimum\n* **L2 regularization** - $\\sum_{j=1}^n (theta_j^2)$, aka lasso regression\n* **L1 regularization** - $\\sum_{j=1}^n (theta_j)$, aka ridge regression\n* **Interpretable** - we should know why our algorithms reach the conclusions they do\n* **Feedforward network** - the computation proceeds iteratively from one layer of units to the next\n* **Saturated** - very high values of z result in values of y extremely close to 1\n* **Xor problem** - its decision boundry cannot be decided by a single perceptron, but a neural network helps\n* **Pretraining** - the idea of relying on another algorithm to have already learned an embedding representation for our input words\n* **Hard classification** - only one class is the correct one, and that there is one output unit in y for each class\n* **Dropout** -  randomly dropping some units and their connections from the network during training as regularization\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\nClassifier Component: \n\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn]. \n\n2. A classification function that computes the estimated class y^ via\np(y|x). \n\n3, An objective function for learning, usually involving minimizing\nerror on training examples. \n\n4. An algorithm for optimizing the objective function.\n\nLearning in logistic regression: \n\n1. An objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nLoss on all training examples: log(p(all training labels)) = $-\\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nGradient descent: $theta = argmin_{theta} \\, 1/m \\sum_{i=1}^m L_{CE}(y^{* \\, (i)}|y^{(i)})$ \n\nupdate w: $w^{t + 1} = w'- n*(d/dw)f(x;w)$, where n is the learning rate; for muti-dimension change w to theta and f(x;w) to L(f(x;theta), y)\n\nderivitive of cross entropy is $[sigmoid(wx +b) - y]*x_j$ for i in all features \n\nAverage loss is to sum all the $L_{CE}$ for each example and normalize it \n\nThe loss for a batch of data or an entire dataset is just the average loss over the m\nexamples \n\nThe gradient for multiple data points is the sum of the individual gradients, which is $[sigmoid(wx +b) - y]*x_j$ \n\nsoftmax(zi) = $e^{z_i}/(\\sum_{j=1}^k e^{z_j})$ \n\n$L_{CE}(y^*, y)$ with softmax = -log ($e^{z_i}/(\\sum_{j=1}^k e^{z_j})$) \n\nComputation Graphs: Although backpropagation was invented for neural nets, it is related to general\nprocedure called backward differentiation, which depends on the notion of\ncomputation graphs.\nA computation graph represents the process of computing a mathematical expression.\nThe computation is broken down into separate operations. Each operation is a node in\na graph.\n\nBackward difference uses chain rule \n\nSummary:\n\n1. Like with logistic regression, we learn the best parameters for the neural net to make\nits predictions y^ as close to possible as the gold standard labels in our training data y.\n\n2. We use:\nA cross entropy loss function;\nGradient descent to perform optimization;\nError back propagation to compute the gradient of the loss function \n\n3. Since Neural Networks combine many perceptron-like neural units, we have many\nmore parameters in the models (weights and biases). This allows us to train systems to\nperform even more sophisticated tasks\n\n\n## Module 14 Definitions\n* **Curse of dimensionality** -  too many parameters to accurately estimate\n* **Antonyms** - words that have opposite meanings\n* **Connotations** - words that are positive or negative\n* **Tf-idf** - Term frequency - Inverse Document Frequency\n* **Recurrent neural network** -  any network that contains a cycle within its network connections\n* **Backpropagation through time** - backpropagation algorithm for RNN, two passes\n* **Teacher forcing** - always give the model the correct history sequence to predict the next word\n* **End-to-end training** -  uses the loss from a downstream application to adjust the weights all the way through the network\n* **Autoregressive generation** - using a language model to incrementally generate words by repeatedly sampling the next word conditioned on our previous choices\n* **Vanishing gradients** -  gradients are eventually driven to zero\n* **Long short-term memory** - removing information no longer needed and adding information likely to be needed for later decision making\n* ** forget gate** - delete information from the context that is no longer needed\n* **Add gate** - select the information to add to the current context\n* **Output gate** - used to decide what information is required for the current hidden state\n* **Transformers** - sequence processing that eliminates recurrent connections and returns to of the fully connected networks\n* **Self-attention** - allows a network to directly extract and use information from arbitrarily large contexts\n* **Positional embeddings** - start with randomly initialized embeddings corresponding to each possible input position up to some maximum length\n* **Distributional hypothesis** - link between similarity in how words are distributed and similarity in what they mean\n* **Embeddings** - representations of the meaning of words\n* **Vector semantics** - instantiates distributional hypothesis by learning representations of the meaning of words\n* **Polysemous** - have multiple senses\n* **Principle of contrast** - a difference in linguistic form is always associated with some difference in meaning\n* **Semantic field** -  a set of words which cover a particular semantic domain and bear structured relations with each other\n* **Semantic frame** - a set of words that denote perspectives or participants in a particular type of event\n* **Contextual embeddings** - the vector for each word is different in different contexts\n* **Static embeddings** - learns one fixed embedding for each word in the vocabulary\n* **Skip-gram model** - uses stochastic gradient descent, learning embeddings that have a high dot product with nearby words, a low dot product with noise words\n* **First-order co-occurrence** - they are typically nearby each other\n* **Second-order co-occurrence** - they have similar neighbors\n* **Allocational harm** - a system allocates resources (jobs or credit) unfairly to different groups\n* **Glove** -  embedding algorithms based on ratios of word co-occurrence probabilities.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}