{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "brNDGX-kvzds"
   },
   "source": [
    "# Template for Notes for CIS 521 Midterm 2\n",
    "\n",
    "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
    "\n",
    "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
    "\n",
    "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "aPtM8g7R0Pds"
   },
   "source": [
    "# Instructions\n",
    "\n",
    "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
    "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
    "3. Read the notes below about how you can format your summaries.\n",
    "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
    "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
    "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
    "* Run the last cell of this notebook\n",
    "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n",
    "\n",
    "## Formatting Notes\n",
    "\n",
    "1. The max length for each section's summary is 500 words / 3000 characters.\n",
    "2. You can also write a 2000 word summary of the lectures for each module.\n",
    "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
    "2. You can use Markdown formatting for your summaries. \n",
    "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
    "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
    "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
    "```\n",
    "def function():\n",
    "      print('hello world')\n",
    "```\n",
    "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "cw5IpDLCZa4W"
   },
   "source": [
    "## Example summary\n",
    "\n",
    "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lzaavW96tcxM",
    "outputId": "7dbd0b37-5287-4c1e-933a-0ed3930179ea"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 116 words long, so you could write an additional 384 words.\n"
     ]
    }
   ],
   "source": [
    "chapter_2_1_example = \"\"\"\n",
    "Regular expressions are an algebraic notation for characterizing \\\n",
    "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
    "Only the first matching result will be shown. The search string is case sensitive, \\\n",
    "but it can consist of a single character or a sequence of characters. \\\n",
    "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
    "for characters over a range. The caret specifies the non-existence of a character. \\\n",
    "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
    "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
    "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
    "...\n",
    "\"\"\"\n",
    "\n",
    "length = len(chapter_2_1_example.split(\" \"))\n",
    "print(\"The example summary is {len} words long, so you could write an additional \\\n",
    "{remaining} words.\".format(len=length, remaining=(500-length)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "s3Uk9gQTevcj"
   },
   "source": [
    "## Example summary length\n",
    "\n",
    "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "600a08c5-ab07-4dd0-ed77-29f2512da385"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n"
     ]
    }
   ],
   "source": [
    "# This is an example of a 500 word placeholder\n",
    "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
    " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
    " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
    " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
    " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
    " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
    " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
    " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
    " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
    " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
    " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
    " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
    " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
    " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
    " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
    " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
    " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
    " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
    " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
    " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
    " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
    " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
    " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
    " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
    " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
    " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
    " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
    " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
    " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
    " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
    " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
    " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
    " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
    " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
    " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
    " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
    " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
    " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
    "\n",
    "print(\"The length in words is\", len(placeholder.split(' ')))\n",
    "print(\"The length in characters is\", len(placeholder))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5yG3-YncJfTB"
   },
   "source": [
    "# Permissions to use your summaries\n",
    "\n",
    "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
    "\n",
    "1. Please enter your name.  \n",
    "\n",
    "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
    "\n",
    "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 8 - Markov Decision Process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
    "\n",
    "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
    "\n",
    "chapter16_1 = \"\"\"\"\"\"  + sample_equation\n",
    "chapter16_2 =  \"\"\"\"\"\"\n",
    "chapter16_3 =  \"\"\"\"\"\"\n",
    "\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
    "chapter17_1 = \"\"\"\"\"\"\n",
    "chapter17_2 =  \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 8.\n",
    "# You can define any term in the textbook or lecture, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 25 words long.\n",
    "\n",
    "module8_definitions = {\n",
    "\"utility function\" : \"Your definition here\",\n",
    "\"expected utility\" : \"your definition here\",\n",
    "\"etc.\": \"your definition here\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "elCCgY64spuq"
   },
   "source": [
    "## Preview of your notes for Module 8\n",
    "\n",
    "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 489
    },
    "id": "gYYeNcdM_maE",
    "outputId": "43f57264-1bd8-4f40-e3ea-674816931ad9"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " $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",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       "\n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       "\n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Utility function** - Your definition here\n",
       "* **Expected utility** - your definition here\n",
       "* **Etc.** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "from IPython.display import display, Markdown, Latex\n",
    "\n",
    "module8_sections = [\n",
    "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
    "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
    "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
    "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
    "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
    "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
    "]\n",
    "\n",
    "\n",
    "def length_check(sections):\n",
    "  warnings = \"\"\n",
    "  for section, summary in sections:\n",
    "    max_word_length = 500\n",
    "    max_character_length = 3000\n",
    "    if \"lecture\" in section.lower():\n",
    "      # It's OK to do longer summaries of the lectures\n",
    "      max_word_length = 2000\n",
    "      max_character_length = 12000  \n",
    "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
    "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
    "  return warnings\n",
    "\n",
    "def length_check_definitions(definitions):\n",
    "  warnings = \"\"\n",
    "  for concept, definition in definitions.items():\n",
    "    if(len(definition.split(' ')) > 25):\n",
    "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
    "  return warnings\n",
    "\n",
    "\n",
    "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
    "  markdown = \"\"\n",
    "\n",
    "  # Check summary lengths\n",
    "  warnings = length_check(sections)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  # Check definition lengths\n",
    "  warnings = length_check_definitions(definitions)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
    "\n",
    "\n",
    "  for section, summary in sections:\n",
    "    if show_placeholder and summary == \" Your summary here \":\n",
    "      summary = placeholder\n",
    "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
    "  \n",
    "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
    "  for concept, definition in definitions.items():\n",
    "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
    "  return markdown\n",
    "\n",
    "\n",
    "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
    "display(Markdown(module8_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 9 - Reinforcement Learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
    "chapter17_3 =  \"\"\"\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
    "chapter22_1 =  \"\"\"MODEL-BASED REINFORCEMENT LEARNING: In these approaches the \\\n",
    "agent uses a transition model of the environment to help interpret the reward \\\n",
    "signals and to make decisions about how to act. MODEL-FREE REINFORCEMENT LEARNING: \\\n",
    "In these approaches the agent neither knows nor learns a transition model for \\\n",
    "the environment. Instead, it learns a more direct representation of how to behave. \\\n",
    "\"\"\"\n",
    "chapter22_2 =  \"\"\"Temporal-difference (TD) equation: $U^{\\pi }(s) \\leftarrow U^{\\pi }(s)+a[R(s, \\pi (s),s')+\\gamma U^{\\pi }(s')-U^{\\pi }(s)]$. \\\n",
    "The TD term $R(s, \\pi (s),s')+\\gamma U^{\\pi }(s')-U^{\\pi }(s)$ is effectively an error signal, and the \\\n",
    "update is intended to reduce the error. \"\"\"\n",
    "chapter22_3 =  \"\"\"A passive learning agent has a fixed policy that determines its \\\n",
    "behavior. An active learning agent gets to decide what actions to take. an agent \\\n",
    "must make a tradeoff between exploitation of the current best action to maximize \\\n",
    "its short-term reward and exploration of previously unknown states to gain \\\n",
    "information that can lead to a change in policy (and to greater rewards in the \\\n",
    "future). A GLIE (greedy in the limit of infinite exploration) scheme must try \\\n",
    "each action in each state an unbounded number of times to avoid having a finite \\\n",
    "probability that an optimal action is missed. one of the simplest GLIE scheme is \\\n",
    "to have the agent choose a random action at time step t with probability 1/t and \\\n",
    "to follow the greedy policy otherwise. A better approach would give some weight \\\n",
    "to actions that the agent has not tried very often, while tending to avoid actions \\\n",
    "that are believed to be of low utility. f is the exploration function. The function \\\n",
    "f(u,n) determines how greed (preference for high values of the utility u) \\\n",
    "is traded off against curiosity (preference for actions that have not been tried \\\n",
    "often and have a low count n). Many actions are irreversible: no subsequent \\\n",
    "sequence of actions can restore the state to what it was before the irreversible \\\n",
    "action was taken. In the worst case, the agent enters an absorbing state where \\\n",
    "no actions have any effect and no rewards are received. We can end up in a bad \\\n",
    "state either because our model is unknown, and we actively choose to explore in \\\n",
    "a direction that turns out to be bad, or because our model is incorrect and we \\\n",
    "don’t know that a given action can have a disastrous result. The Q-learning method \\\n",
    "avoids the need for a model by learning an action-utility function Q(s,a) \\\n",
    "instead of a utility function U(s). A TD Q-learning agent does not need a transition \\\n",
    "model, P(s'|s,a), either for learning or for action selection. Model-free methods \\\n",
    "can be applied even in very complex domains because no model need be provided or \\\n",
    "learned. The Q-learning agent has no means of looking into the future, so it may \\\n",
    "have difficulty when rewards are sparse and long action sequences must be \\\n",
    "constructed to reach them. \"\"\"\n",
    "chapter22_4 =  \"\"\"\"\"\"\n",
    "chapter22_5 =  \"\"\"The idea of policy search is to keep twiddling the policy as \\\n",
    "long as its performance improves, then stop. Policy search methods often use a \\\n",
    "stochastic policy representation $\\pi_{\\theta } (s,a)$, which specifies the \\\n",
    "probability of selecting action a in state s. One popular representation is the \\\n",
    "softmax function. \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module9_lecture_notes = \"\"\"\"\"\"\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module9_definitions = {\n",
    "\"term\" : \"your definition here\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 754
    },
    "id": "ydOK__lwWgdp",
    "outputId": "780e3c46-9d8b-4515-aa25-7032f158bffc"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       "\n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       "MODEL-BASED REINFORCEMENT LEARNING: In these approaches the agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. MODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither knows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave. \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       "Temporal-difference (TD) equation: $U^{\\pi }(s) \\leftarrow U^{\\pi }(s)+a[R(s, \\pi (s),s')+\\gamma U^{\\pi }(s')-U^{\\pi }(s)]$. The TD term $R(s, \\pi (s),s')+\\gamma U^{\\pi }(s')-U^{\\pi }(s)$ is effectively an error signal, and the update is intended to reduce the error. \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       "A passive learning agent has a fixed policy that determines its behavior. An active learning agent gets to decide what actions to take. an agent must make a tradeoff between exploitation of the current best action to maximize its short-term reward and exploration of previously unknown states to gain information that can lead to a change in policy (and to greater rewards in the future). A GLIE (greedy in the limit of infinite exploration) scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed. one of the simplest GLIE scheme is to have the agent choose a random action at time step t with probability 1/t and to follow the greedy policy otherwise. A better approach would give some weight to actions that the agent has not tried very often, while tending to avoid actions that are believed to be of low utility. f is the exploration function. The function f(u,n) determines how greed (preference for high values of the utility u) is traded off against curiosity (preference for actions that have not been tried often and have a low count n). Many actions are irreversible: no subsequent sequence of actions can restore the state to what it was before the irreversible action was taken. In the worst case, the agent enters an absorbing state where no actions have any effect and no rewards are received. We can end up in a bad state either because our model is unknown, and we actively choose to explore in a direction that turns out to be bad, or because our model is incorrect and we don’t know that a given action can have a disastrous result. The Q-learning method avoids the need for a model by learning an action-utility function Q(s,a) instead of a utility function U(s). A TD Q-learning agent does not need a transition model, P(s'|s,a), either for learning or for action selection. Model-free methods can be applied even in very complex domains because no model need be provided or learned. The Q-learning agent has no means of looking into the future, so it may have difficulty when rewards are sparse and long action sequences must be constructed to reach them. \n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       "\n",
       "\n",
       "## Module 9 Lecture Notes\n",
       "\n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Term** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "\n",
    "module9_sections = [\n",
    "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
    "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
    "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
    "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
    "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
    "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
    "]\n",
    "\n",
    "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
    "display(Markdown(module9_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 10 - Probabilities and Language Models"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "BN0b1eVYx-nd",
    "outputId": "07037a6e-bbfe-469c-8a82-466b70607fec"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 353\n",
      "The length in characters is 2367\n"
     ]
    }
   ],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
    "chapter12_1 = \"\"\"\"\"\"\n",
    "chapter12_2 = \"\"\"\"\"\"\n",
    "chapter12_3 = \"\"\"General marginalization rule: $P(Y)=\\sum_{Z} P(Y,Z=z)$. \\\n",
    "Conditioning: $P(Y)=\\sum_{Z} P(Y|Z)P(Z)$. \"\"\"\n",
    "chapter12_4 = \"\"\"\"\"\"\n",
    "chapter12_5 = \"\"\"\"\"\"\n",
    "chapter12_6 = \"\"\"\"\"\"\n",
    "chapter12_7 = \"\"\"\"\"\"\n",
    "\n",
    "\n",
    "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
    "SLP_chapter3_1 = \"\"\"Chain rule of probability: $P(X_1...X_n)=P(X_1)P(X_2|X_1)...P(X_n|X_{1:n-1})= \\prod_{k = 1}^{n} P(X_k|X_{1:k-1})$. \\\n",
    "The assumption that the probability of a word depends only on the previous word \\\n",
    "is called a Markov assumption. N-gram: looks n-1 words into the past $P(w_n|w_{1:n-1})\\approx P(w_n|w_{n-N+1:n-1})$. \\\n",
    "The maximum likelihood estimation (MLE) for the parameters of an n-gram model is \\\n",
    "got counts from a corpus, and normalizing the counts so that they lie between 0 and 1. \\\n",
    "Relative frequency: estimates the n-gram probability by dividing the observed \\\n",
    "frequency of a particular sequence by the observed frequency of a prefix. \\\n",
    "\"\"\"\n",
    "SLP_chapter3_2 = \"\"\"Extrinsic evaluation: an end-to-end evaluation that \\\n",
    "embedding the performance of a language model in an application and measure \\\n",
    "how much the application improves. Intrinsic evaluation:  measures the quality \\\n",
    "of a model independent of any application. Perplexity (PP): the inverse probability \\\n",
    "of the test set, normalized by the number of words. $PP(W)= \\sqrt[N]{\\prod_{i=1}^{N} 1/P(w_i|w_1...w_{i-1})}$. \\\n",
    "There is another way to think about perplexity: as the weighted average branching \\\n",
    "factor of a language. The branching factor of a language is the number of \\\n",
    "possible next words that can follow any word. \"\"\"\n",
    "SLP_chapter3_3 = \"\"\"Sampling from a distribution means to choose random points \\\n",
    "according to their likelihood. \"\"\"\n",
    "SLP_chapter3_4 = \"\"\"Why are things that don’t ever occur in the training set but \\\n",
    "do occur in the test set a problem? First, their presence means we are underestimating \\\n",
    "the probability of all sorts of words that might occur, which will hurt the \\\n",
    "performance of any application we want to run on this data. Second, if the probability \\\n",
    "of any word in the test set is 0, the entire probability of the test set is 0. \\\n",
    "By definition, perplexity is based on the inverse probability of the test set. \\\n",
    "Thus if some words have zero probability, we can’t compute perplexity at all, \\\n",
    "since we can’t divide by 0! \"\"\"\n",
    "SLP_chapter3_5 = \"\"\"Laplace smoothing: add one to all the n-gram counts, before \\\n",
    "we normalize them into probabilities. Add-k smoothing: instead of adding 1 to each \\\n",
    "count, we add a fractional count k (.5? .05? .01?). \"\"\"\n",
    "SLP_chapter3_7 = \"\"\"\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module10_lecture_notes = \"\"\"3 general situations of Uncertainty: 1. Observed variables \\\n",
    "(evidence): Agent knows certain things about the state of the world (e.g., sensor \\\n",
    "readings or symptoms). 2. Unobserved variables (states): Agent needs to reason \\\n",
    "about other aspects (e.g. where an object is or what disease is present). 3. Model: \\\n",
    "Agent knows something about how the known variables relate to the unknown variables. \\\n",
    "In probability theory, the possible worlds are called the sample space, and they \\\n",
    "mutually exclusive (P(A∩B)=0) and exhaustive (events that contains all of the outcomes \\\n",
    "in the sample space, P(A∪B)=1). A joint distribution over a set of random variables: \\\n",
    "X1, X2,..., Xn specifies a real number for each assignment (or outcome) P(x1,x2,...,xn). \\\n",
    "A probabilistic model is a joint distribution over a set of random variables. \\\n",
    "An event is a set E of outcomes $$P(E) = \\sum_(x_1...x_n\\inE) P(x_1...x_n)$$. \\\n",
    "Conditional Probabilities: P(a|b)=P(a,b)/P(b). Probabilistic Inference: compute \\\n",
    "a desired probability from other known probabilities (e.g. conditional from joint). \\\n",
    "Inference by Enumeration: Evidence variables: things have observed. Query variables: \\\n",
    "things we care about and want to reason about how likely their outcomes are. Hidden \\\n",
    "variables: things occur and big joint probability distribution but aren't things taht \\\n",
    "we've either observed or reasoning about. We care about P(Q|e1...ek). Step 1: \\\n",
    "Select the entries consistent with the evidence. Step 2: Sum out H to get joint \\\n",
    "of Query and evidence. Step 3: Normalize. Product Rule: P(y)P(x|y) = P(x,y). \\\n",
    "The Chain Rule: P(x1,x2,...,xn) = ΠiP(xi|x1,...,xi-1). Bayes’ Rule: P(x,y) = P(x|y)P(y) \\\n",
    "= P(y|x)P(x). P(x|y) = (P(y|x)/P(y))P(x). Why Bayes' rule useful? Lets us build \\\n",
    "one conditional from its reverse; Often one conditional is tricky but the other \\\n",
    "one is simple. Probabilistic Language Modeling's Goal: compute the probability \\\n",
    "of a sentence or sequence of words. Related task: probability of an upcoming word. \\\n",
    "A model that computes either of these is called a language model or LM. Joint \\\n",
    "probability of words in sentence: P(w1w2...wn) = ΠiP(wi|w1...wi-1). Just count \\\n",
    "and divide doesn't work because some sentences may never appear in the corpus. \\\n",
    "Markov Assumption: only depends on the previous k words, not the whole context. \\\n",
    "The Maximum Likelihood Estimate of bigram probabilities: P(wi|wi-1) = count(wi-1,wi)/ \\\n",
    "count(wi-1). \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module10_definitions = {\n",
    "\"term\" : \"your definition here\",\n",
    "}\n",
    "\n",
    "print(\"The length in words is\", len(module10_lecture_notes.split(' ')))\n",
    "print(\"The length in characters is\", len(module10_lecture_notes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "a75beda6-02d0-4d47-ac74-3b8fcdb2abeb"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       "General marginalization rule: $P(Y)=\\sum_{Z} P(Y,Z=z)$. Conditioning: $P(Y)=\\sum_{Z} P(Y|Z)P(Z)$. \n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       "\n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       "Chain rule of probability: $P(X_1...X_n)=P(X_1)P(X_2|X_1)...P(X_n|X_{1:n-1})= \\prod_{k = 1}^{n} P(X_k|X_{1:k-1})$. The assumption that the probability of a word depends only on the previous word is called a Markov assumption. N-gram: looks n-1 words into the past $P(w_n|w_{1:n-1})\u0007pprox P(w_n|w_{n-N+1:n-1})$. The maximum likelihood estimation (MLE) for the parameters of an n-gram model is got counts from a corpus, and normalizing the counts so that they lie between 0 and 1. Relative frequency: estimates the n-gram probability by dividing the observed frequency of a particular sequence by the observed frequency of a prefix. \n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       "Extrinsic evaluation: an end-to-end evaluation that embedding the performance of a language model in an application and measure how much the application improves. Intrinsic evaluation:  measures the quality of a model independent of any application. Perplexity (PP): the inverse probability of the test set, normalized by the number of words. $PP(W)= \\sqrt[N]{\\prod_{i=1}^{N} 1/P(w_i|w_1...w_{i-1})}$. There is another way to think about perplexity: as the weighted average branching factor of a language. The branching factor of a language is the number of possible next words that can follow any word. \n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       "Sampling from a distribution means to choose random points according to their likelihood. \n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       "Why are things that don’t ever occur in the training set but do occur in the test set a problem? First, their presence means we are underestimating the probability of all sorts of words that might occur, which will hurt the performance of any application we want to run on this data. Second, if the probability of any word in the test set is 0, the entire probability of the test set is 0. By definition, perplexity is based on the inverse probability of the test set. Thus if some words have zero probability, we can’t compute perplexity at all, since we can’t divide by 0! \n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       "Laplace smoothing: add one to all the n-gram counts, before we normalize them into probabilities. Add-k smoothing: instead of adding 1 to each count, we add a fractional count k (.5? .05? .01?). \n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       "\n",
       "\n",
       "## Module 10 Lecture Notes\n",
       "3 general situations of Uncertainty: 1. Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms). 2. Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present). 3. Model: Agent knows something about how the known variables relate to the unknown variables. In probability theory, the possible worlds are called the sample space, and they mutually exclusive (P(A∩B)=0) and exhaustive (events that contains all of the outcomes in the sample space, P(A∪B)=1). A joint distribution over a set of random variables: X1, X2,..., Xn specifies a real number for each assignment (or outcome) P(x1,x2,...,xn). A probabilistic model is a joint distribution over a set of random variables. An event is a set E of outcomes $$P(E) = \\sum_(x_1...x_n\\inE) P(x_1...x_n)$$. Conditional Probabilities: P(a|b)=P(a,b)/P(b). Probabilistic Inference: compute a desired probability from other known probabilities (e.g. conditional from joint). Inference by Enumeration: Evidence variables: things have observed. Query variables: things we care about and want to reason about how likely their outcomes are. Hidden variables: things occur and big joint probability distribution but aren't things taht we've either observed or reasoning about. We care about P(Q|e1...ek). Step 1: Select the entries consistent with the evidence. Step 2: Sum out H to get joint of Query and evidence. Step 3: Normalize. Product Rule: P(y)P(x|y) = P(x,y). The Chain Rule: P(x1,x2,...,xn) = ΠiP(xi|x1,...,xi-1). Bayes’ Rule: P(x,y) = P(x|y)P(y) = P(y|x)P(x). P(x|y) = (P(y|x)/P(y))P(x). Why Bayes' rule useful? Lets us build one conditional from its reverse; Often one conditional is tricky but the other one is simple. Probabilistic Language Modeling's Goal: compute the probability of a sentence or sequence of words. Related task: probability of an upcoming word. A model that computes either of these is called a language model or LM. Joint probability of words in sentence: P(w1w2...wn) = ΠiP(wi|w1...wi-1). Just count and divide doesn't work because some sentences may never appear in the corpus. Markov Assumption: only depends on the previous k words, not the whole context. The Maximum Likelihood Estimate of bigram probabilities: P(wi|wi-1) = count(wi-1,wi)/ count(wi-1). \n",
       "\n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Term** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module10_sections = [\n",
    "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
    "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
    "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
    "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
    "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
    "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
    "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
    "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
    "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
    "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
    "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
    "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
    "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
    "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
    "]\n",
    "\n",
    "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
    "display(Markdown(module10_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
    "chapter13_1 = \"\"\"Full joint probability distribution can answer any question about \\\n",
    "the domain, but can become intractably large as the number of variables grows. \\\n",
    "Furthermore, specifying probabilities for possible worlds one by one is unnatural \\\n",
    "and tedious. Bayesian networks can represent essentially any full joint probability \\\n",
    "distribution and in many cases can do so very concisely. A Bayesian network is a \\\n",
    "directed graph in which each node is annotated with quantitative probability information. \\\n",
    "The intuitive meaning of an arrow is typically that X has a direct influence on Y, \\\n",
    "which suggests that causes should be parents of effects. \"\"\"\n",
    "chapter13_2 = \"\"\"The syntax of a Bayes net consists of a directed acyclic graph \\\n",
    "with some local probability information attached to each node. The semantics \\\n",
    "defines how the syntax corresponds to a joint distribution over the variables \\\n",
    "of the network. As well as being a complete and nonredundant representation of \\\n",
    "the domain, a Bayes net can often be far more compact than the full joint distribution. \\\n",
    "This property is what makes it feasible to handle domains with many variables. \\\n",
    "The compactness of Bayesian networks is an example of a general property of locally \\\n",
    "structured (also called sparse) systems. In a locally structured system, each \\\n",
    "subcomponent interacts directly with only a bounded number of other components, \\\n",
    "regardless of the total number of components. Local structure is usually associated \\\n",
    "with linear rather than exponential growth in complexity. The most general conditional \\\n",
    "independence question one might ask in a Bayes net is whether a set of nodes X \\\n",
    "is conditionally independent of another set Y, given a third set Z. This can be \\\n",
    "determined efficiently by examining the Bayes net to see whether Z d-separates X \\\n",
    "and Y. In brief, then, d-separation means separation in the undirected, moralized, \\\n",
    "ancestral subgraph. Even if the maximum number of parents k is smallish, filling \\\n",
    "in the CPT for a node requires up to $O(2^k)$ numbers and perhaps a great deal \\\n",
    "of experience with all the possible conditioning cases. A deterministic node has \\\n",
    "its value specified exactly by the values of its parents, with no uncertainty. \\\n",
    "A conditional distribution exhibits CSI (context-specific independence) if a \\\n",
    "variable is conditionally independent of some of its parents given certain values \\\n",
    "of others. Uncertain relationships can often be characterized by so-called noisy \\\n",
    "logical relationships. The standard example is the noisy-OR relation, which is a \\\n",
    "generalization of the logical OR. One way to handle continuous variables is with \\\n",
    "discretization: dividing up the possible values into a fixed set of intervals. \\\n",
    "A nonparametric representation: define the conditional distribution implicitly \\\n",
    "with a collection of instances, each containing specific values of the parent and \\\n",
    "child variables. A network with both discrete and continuous variables is called \\\n",
    "a hybrid Bayesian network. \"\"\"\n",
    "chapter13_3 = \"\"\"The basic task for any probabilistic inference system is to compute \\\n",
    "the posterior probability distribution for a set of query variables, given some \\\n",
    "observed event—usually, some assignment of values to a set of evidence variables. \\\n",
    "The time and space complexity of exact inference in polytrees is linear in the \\\n",
    "size of the network. \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module11_lecture_notes = \"\"\"Models describe how (a portion of) the world works. \\\n",
    "Models are always simplifications: May not account for every variable; May not \\\n",
    "account for all interactions between variables. X and Y are independent if p(x,y) \\\n",
    "= p(x)p(y). Knowing p(x) providing no information about p(y). X and Y are conditionally \\\n",
    "independent given Z: p(x,y|z) = p(x|z)p(y|z). (Conditional) independence is a \\\n",
    "property of a distribution. Conditional independence is our most basic and robust form \\\n",
    "of knowledge about uncertain environments. Causal chain: P(x,y,z) = P(x)P(y|x)P(z|y). \\\n",
    "Guaranteed X independent of Z? No! One example set of CPTs for which X is not \\\n",
    "independent of Z is sufficient to show this independence is not guaranteed. \\\n",
    "Guaranteed X independent of Z given Y? Yes! Common cause: P(x,y,z) = P(y)P(x|y)P(z|y). \\\n",
    "Common effect: two causes of onee effect (v-structures). \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module11_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 797
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "a5d41f2b-28c2-4e73-b60e-412817ad3958"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       "Full joint probability distribution can answer any question about the domain, but can become intractably large as the number of variables grows. Furthermore, specifying probabilities for possible worlds one by one is unnatural and tedious. Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely. A Bayesian network is a directed graph in which each node is annotated with quantitative probability information. The intuitive meaning of an arrow is typically that X has a direct influence on Y, which suggests that causes should be parents of effects. \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       "The syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. The semantics defines how the syntax corresponds to a joint distribution over the variables of the network. As well as being a complete and nonredundant representation of the domain, a Bayes net can often be far more compact than the full joint distribution. This property is what makes it feasible to handle domains with many variables. The compactness of Bayesian networks is an example of a general property of locally structured (also called sparse) systems. In a locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity. The most general conditional independence question one might ask in a Bayes net is whether a set of nodes X is conditionally independent of another set Y, given a third set Z. This can be determined efficiently by examining the Bayes net to see whether Z d-separates X and Y. In brief, then, d-separation means separation in the undirected, moralized, ancestral subgraph. Even if the maximum number of parents k is smallish, filling in the CPT for a node requires up to $O(2^k)$ numbers and perhaps a great deal of experience with all the possible conditioning cases. A deterministic node has its value specified exactly by the values of its parents, with no uncertainty. A conditional distribution exhibits CSI (context-specific independence) if a variable is conditionally independent of some of its parents given certain values of others. Uncertain relationships can often be characterized by so-called noisy logical relationships. The standard example is the noisy-OR relation, which is a generalization of the logical OR. One way to handle continuous variables is with discretization: dividing up the possible values into a fixed set of intervals. A nonparametric representation: define the conditional distribution implicitly with a collection of instances, each containing specific values of the parent and child variables. A network with both discrete and continuous variables is called a hybrid Bayesian network. \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       "The basic task for any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event—usually, some assignment of values to a set of evidence variables. The time and space complexity of exact inference in polytrees is linear in the size of the network. \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       "Models describe how (a portion of) the world works. Models are always simplifications: May not account for every variable; May not account for all interactions between variables. X and Y are independent if p(x,y) = p(x)p(y). Knowing p(x) providing no information about p(y). X and Y are conditionally independent given Z: p(x,y|z) = p(x|z)p(y|z). (Conditional) independence is a property of a distribution. Conditional independence is our most basic and robust form of knowledge about uncertain environments. Causal chain: P(x,y,z) = P(x)P(y|x)P(z|y). Guaranteed X independent of Z? No! One example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed. Guaranteed X independent of Z given Y? Yes! Common cause: P(x,y,z) = P(y)P(x|y)P(z|y). Common effect: two causes of onee effect (v-structures). \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module11_sections = [\n",
    "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
    "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
    "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
    "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
    "]\n",
    "\n",
    "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
    "                         module11_sections, \n",
    "                         module11_definitions)\n",
    "display(Markdown(module11_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 12 - Naive Bayes and Perceptrons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
    "\n",
    "chapter19_1 = \"\"\"When the output is one of a finite set of values (such as sunny/cloudy/rainy or true/false), \\\n",
    "the learning problem is called classification. When it is a number (such as tomorrow’s \\\n",
    "temperature, measured either as an integer or a real number), the learning problem \\\n",
    "has the (admittedly obscure) name regression. There are three types of feedback \\\n",
    "that can accompany the inputs, and that determine the three main types of learning: \\\n",
    "Supervised learning; unsupervised learning; reinforcement learning. \"\"\"\n",
    "chapter19_2 = \"\"\"Exploratory data analysis: examining the data with statistical \\\n",
    "tests and visualizations—histograms, scatter plots, box plots—to get a feel for \\\n",
    "the data, and some insight into what hypothesis space might be appropriate. How \\\n",
    "do we choose a good hypothesis from within the hypothesis space? We could hope \\\n",
    "for a consistent hypothesis: an h such that each xi in the training set has \\\n",
    "$h(x_i)=y_i$. With continuous-valued outputs we can’t expect an exact match to the \\\n",
    "ground truth; instead we look for a best-fit function. We say that h generalizes \\\n",
    "well if it accurately predicts the outputs of the test set. By bias we mean (loosely) \\\n",
    "the tendency of a predictive hypothesis to deviate from the expected value when \\\n",
    "averaged over different training sets. Bias often results from restrictions \\\n",
    "imposed by the hypothesis space. We say that a hypothesis is underfitting when it \\\n",
    "fails to find a pattern in the data. On the other hand, the piecewise linear function \\\n",
    "has low bias; the shape of the function is driven by the data. By variance we mean \\\n",
    "the amount of change in the hypothesis due to fluctuation in the training data. \\\n",
    "We say a function is overfitting the data when it pays too much attention to the \\\n",
    "particular data set it is trained on, causing it to perform poorly on unseen data. \\\n",
    "Bias–variance tradeoff: a choice between more complex, low-bias hypotheses that \\\n",
    "fit the training data well and simpler, low-variance hypotheses that may generalize \\\n",
    "better. \"\"\"\n",
    "chapter19_3 = \"\"\"A decision tree is a representation of a function that maps a \\\n",
    "vector of attribute values to a single output value—a “decision.” A decision tree \\\n",
    "reaches its decision by performing a sequence of tests, starting at the root and \\\n",
    "following the appropriate branch until a leaf is reached. In general, the input \\\n",
    "and output values can be discrete or continuous. Boolean classification: inputs \\\n",
    "only consisting of discrete values and outputs that are either true (a positive \\\n",
    "example) or false (a negative example). We can evaluate the performance of a \\\n",
    "learning algorithm with a learning curve. Entropy is a measure of the uncertainty \\\n",
    "of a random variable; the more information, the less entropy. The information gain \\\n",
    "from the attribute test on is the expected reduction in entropy: $Gain(A)=B(p/p+n)-Remainder(A)$. \\\n",
    "For decision trees, a technique called decision tree pruning combats overfitting. \\\n",
    "Pruning works by eliminating nodes that are not clearly relevant. \"\"\"\n",
    "chapter19_4 = \"\"\"Stationarity assumption: the future examples will be like the past. \\\n",
    "Error rate: the proportion of times that $h(x)!=y$ for an (x,y) example. \\\n",
    "A process of feature selection can be performed to discard attributes that appear \\\n",
    "to be irrelevant. The simplest approach to hyperparameter tuning is hand-tuning: \\\n",
    "guess some parameter values based on past experience, train a model, measure its \\\n",
    "performance on the validation data, analyze the results, and use your intuition to \\\n",
    "suggest new parameter values. Repeat until you have satisfactory performance (or \\\n",
    "you run out of time, computing budget, or patience). If there are only a few hyperparameters, \\\n",
    "each with a small number of possible values, then a more systematic approach called \\\n",
    "grid search is appropriate: try all combinations of values and see which performs \\\n",
    "best on the validation data. Different combinations can be run in parallel on \\\n",
    "different machines, so if you have sufficient computing resources, this need not \\\n",
    "be slow, although in some cases model selection has been known to suck up resources \\\n",
    "on thousand-computer clusters for days at a time. If there are too many combinations \\\n",
    "of possible values, then random search samples uniformly from the set of all \\\n",
    "possible hyperparameter settings, repeating for as long as you are willing to \\\n",
    "spend the time and computational resources. Random sampling is also a good way \\\n",
    "to handle continuous values. When each training run takes a long time, it can be \\\n",
    "helpful to get useful information out of each one. Bayesian optimization treats \\\n",
    "the task of choosing good hyperparameter values as a machine learning problem in itself. \\\n",
    "\"\"\"\n",
    "chapter19_5 = \"\"\"PAC(probably approximately correct)-learning theorems, like all \\\n",
    "theorems, are logical consequences of axioms. \"\"\"\n",
    "chapter19_6 = \"\"\"Weights in linear regression: the value of y is changed by \\\n",
    "changing the relative weight of one term or another.\"\"\"\n",
    "\n",
    "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
    "slp_chapter4_1 = \"\"\"Bag-of-words: an unordered set of words with their position \\\n",
    "ignored, keeping only their frequency in the document. we compute the most probable \\\n",
    "class $\\hat{c} $ given some document d by choosing the class which has the highest product \\\n",
    "of two probabilities: the prior probability of the class P(c) and the likelihood \\\n",
    "of the document P(d|c). Naive Bayes classifiers make two simplifying assumptions. \\\n",
    "The first is the bag of words assumption: we assume position doesn’t matter. \\\n",
    "The second is commonly called the naive Bayes assumption: this is the conditional \\\n",
    "independence assumption that the probabilities P(fi|c) are independent given \\\n",
    "the class c and hence can be ‘naively’ multiplied. Classifiers that use a linear \\\n",
    "combination of the inputs to make a classification decision —like naive Bayes and \\\n",
    "also logistic regression— are called linear classifiers.\"\"\"\n",
    "slp_chapter4_2 = \"\"\"\"\"\"\n",
    "slp_chapter4_3 = \"\"\"\"\"\"\n",
    "slp_chapter4_4 = \"\"\"\"\"\"\n",
    "slp_chapter4_5 = \"\"\"\"\"\"\n",
    "slp_chapter4_6 = \"\"\"\"\"\"\n",
    "slp_chapter4_7 = \"\"\"Gold label: the human-defined labels for each document that \\\n",
    "we are trying to match. Confusion matrix: a table for visualizing how an algorithm \\\n",
    "performs with respect to the human gold labels, using two dimensions (system output \\\n",
    "and gold labels), and each cell labeling a set of possible outcomes. Precision \\\n",
    "measures the percentage of the items that the system detected (i.e., the system \\\n",
    "labeled as positive) that are in fact positive (i.e., are positive according to \\\n",
    "the human gold labels). Precision is defined as: Presision = true positive/true positive + false positive. \\\n",
    "Recall measures the percentage of items actually present in the input that were \\\n",
    "correctly identified by the system. Recall is defined as: Recall = true positive/true positive + false negative. \\\n",
    "There are many ways to define a single metric that incorporates aspects of both \\\n",
    "precision and recall. The simplest of these combinations is the F-measure: $F_b=(b^2+1)PR/b^2P+R$. \\\n",
    "The b parameter differentially weights the importance of recall and precision, \\\n",
    "based perhaps on the needs of an application. Values of b > 1 favor recall, while \\\n",
    "values of b < 1 favor precision. When b = 1, precision and recall are equally \\\n",
    "balanced; this is the most frequently used metric, and is called $F_{b-1}$ or just $F_1$: \\\n",
    "$F_1=2PR/P+R$. \"\"\"\n",
    "slp_chapter4_8 = \"\"\"In cross-validation, we choose a number k, and partition our \\\n",
    "data into k disjointsubsets called folds.  If we choose k = 10, we would train 10 \\\n",
    "different models (each on 90% of our data), test the model 10 times, and average \\\n",
    "these 10 values. This is called 10-fold cross-validation. \"\"\"\n",
    "slp_chapter4_9 = \"\"\"\"\"\"\n",
    "slp_chapter4_10 = \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module12_lecture_notes = \"\"\"Naïve Bayes: Assume all features are independent \\\n",
    "effects of the label. A general Naive Bayes model: $P(Y,F_1...F_n)=P(Y) \\prod_{i} P(F_i|Y)$. \\\n",
    "We only have to specify how each feature depends on the class. Total number of \\\n",
    "parameters is linear in number of features. Downside: model is very simplistic. \\\n",
    "Bag-of-words Naïve Bayes: Features: $W_i$ is the word at positon i; As before: \\\n",
    "predict label conditioned on feature variables (spam vs. ham); As before: assume \\\n",
    "features are conditionally independent given label; New: each $W_i$ is identically \\\n",
    "distributed. Generative model: $P(Y,W_1...W_n)=P(Y) \\prod_{i} P(W_i|Y)$. \\\n",
    "In a bag-of-words model all positions share the same conditional probs P(W|Y). \\\n",
    "Called “bag-of-words” because model is insensitive to word order or reordering. \\\n",
    "Maximum likelihood: $P_{ML}(x)=count(x)/totalSamples$. Laplace smoothing for \\\n",
    "conditionals: $P_{LAP,k}(x|y)=(c(x,y)+k)/(c(y)+k|X|)$. In proctice, Laplace \\\n",
    "often performs poorly for P(x|y) when |X| or |Y| is very large. Linear interpolation: \\\n",
    "$P_{LIN}(x|y)=a\\hat{P} (x|y)+(1.0-a)\\hat{P} (x)$. Bayes rule lets us do diagnostic \\\n",
    "queries with causal probabilities. The naïve Bayes assumption takes all features \\\n",
    "to be independent given the class label. We can build classifiers out of a naïve \\\n",
    "Bayes model using training data. Smoothing estimates is important in real systems. \\\n",
    "Classifier confidences are useful, when you can get them. Linear Classifiers: \\\n",
    "inputs are feature values, each feature has a weight. Sum is the activation. \\\n",
    "Learning: Binary Perceptron. Start with weights = 0. For each training instance: \\\n",
    "Classify with current weights; If correct (i.e., y=y*), no change! If wrong: \\\n",
    "adjust the weight vector by adding or subtracting the feature vector. Subtract \\\n",
    "if y* is -1. Multiclass Decision Rule. If we have multiple classes: a weight \\\n",
    "vector for each class $w_y$; score (activation) of a class y $w_y \\cdot f(x)$; \\\n",
    "prediction highest score wins $y=argmax_yw_y\\cdot f(x)$. If wrong: lower score \\\n",
    "of wrong answer, raise score of right answer. Properties of Perceptrons: \\\n",
    "Separability: true if some parameters get the training set perfectly correct; \\\n",
    "Convergence: if the training is separable, perceptron will eventually converge \\\n",
    "(binary case); Mistake Bound: the maximum number of mistakes (binary case) related \\\n",
    "to the margin or degree of separability. Problems with the Perceptron: \\\n",
    "Noise: if the data isn’t separable, weights might thrash, Averaging weight \\\n",
    "vectors over time can help (averaged perceptron); Mediocre generalization: finds a \\\n",
    "“barely” separating solution; Overtraining: test / held-out accuracy usually \\\n",
    "rises, then falls. Classification comparison: Naïve Bayes: Builds a model training data; \\\n",
    "Gives prediction probabilities; Strong assumptions about feature independence; \\\n",
    "One pass through data (counting). Perceptrons / MIRA: Makes less assumptions about \\\n",
    "data; Mistake-driven learning; Multiple passes through data (prediction); Often more accurate.\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module12_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "e64ec963-e9e7-47cd-d723-6a0a94742684"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 19.1 Forms of Learning\n",
       "When the output is one of a finite set of values (such as sunny/cloudy/rainy or true/false), the learning problem is called classification. When it is a number (such as tomorrow’s temperature, measured either as an integer or a real number), the learning problem has the (admittedly obscure) name regression. There are three types of feedback that can accompany the inputs, and that determine the three main types of learning: Supervised learning; unsupervised learning; reinforcement learning. \n",
       "\n",
       "## AIMA Chapter 19.2 Supervised Learning\n",
       "Exploratory data analysis: examining the data with statistical tests and visualizations—histograms, scatter plots, box plots—to get a feel for the data, and some insight into what hypothesis space might be appropriate. How do we choose a good hypothesis from within the hypothesis space? We could hope for a consistent hypothesis: an h such that each xi in the training set has $h(x_i)=y_i$. With continuous-valued outputs we can’t expect an exact match to the ground truth; instead we look for a best-fit function. We say that h generalizes well if it accurately predicts the outputs of the test set. By bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space. We say that a hypothesis is underfitting when it fails to find a pattern in the data. On the other hand, the piecewise linear function has low bias; the shape of the function is driven by the data. By variance we mean the amount of change in the hypothesis due to fluctuation in the training data. We say a function is overfitting the data when it pays too much attention to the particular data set it is trained on, causing it to perform poorly on unseen data. Bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may generalize better. \n",
       "\n",
       "## AIMA Chapter 19.3 Learning Decision Trees\n",
       "A decision tree is a representation of a function that maps a vector of attribute values to a single output value—a “decision.” A decision tree reaches its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached. In general, the input and output values can be discrete or continuous. Boolean classification: inputs only consisting of discrete values and outputs that are either true (a positive example) or false (a negative example). We can evaluate the performance of a learning algorithm with a learning curve. Entropy is a measure of the uncertainty of a random variable; the more information, the less entropy. The information gain from the attribute test on is the expected reduction in entropy: $Gain(A)=B(p/p+n)-Remainder(A)$. For decision trees, a technique called decision tree pruning combats overfitting. Pruning works by eliminating nodes that are not clearly relevant. \n",
       "\n",
       "## AIMA Chapter 19.4 Model Selection and Optimization\n",
       "Stationarity assumption: the future examples will be like the past. Error rate: the proportion of times that $h(x)!=y$ for an (x,y) example. A process of feature selection can be performed to discard attributes that appear to be irrelevant. The simplest approach to hyperparameter tuning is hand-tuning: guess some parameter values based on past experience, train a model, measure its performance on the validation data, analyze the results, and use your intuition to suggest new parameter values. Repeat until you have satisfactory performance (or you run out of time, computing budget, or patience). If there are only a few hyperparameters, each with a small number of possible values, then a more systematic approach called grid search is appropriate: try all combinations of values and see which performs best on the validation data. Different combinations can be run in parallel on different machines, so if you have sufficient computing resources, this need not be slow, although in some cases model selection has been known to suck up resources on thousand-computer clusters for days at a time. If there are too many combinations of possible values, then random search samples uniformly from the set of all possible hyperparameter settings, repeating for as long as you are willing to spend the time and computational resources. Random sampling is also a good way to handle continuous values. When each training run takes a long time, it can be helpful to get useful information out of each one. Bayesian optimization treats the task of choosing good hyperparameter values as a machine learning problem in itself. \n",
       "\n",
       "## AIMA Chapter 19.5 The Theory of Learning\n",
       "PAC(probably approximately correct)-learning theorems, like all theorems, are logical consequences of axioms. \n",
       "\n",
       "## AIMA Chapter 19.6 Linear Regression and Classification\n",
       "Weights in linear regression: the value of y is changed by changing the relative weight of one term or another.\n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       "Bag-of-words: an unordered set of words with their position ignored, keeping only their frequency in the document. we compute the most probable class $\\hat{c} $ given some document d by choosing the class which has the highest product of two probabilities: the prior probability of the class P(c) and the likelihood of the document P(d|c). Naive Bayes classifiers make two simplifying assumptions. The first is the bag of words assumption: we assume position doesn’t matter. The second is commonly called the naive Bayes assumption: this is the conditional independence assumption that the probabilities P(fi|c) are independent given the class c and hence can be ‘naively’ multiplied. Classifiers that use a linear combination of the inputs to make a classification decision —like naive Bayes and also logistic regression— are called linear classifiers.\n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       "\n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       "\n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       "\n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       "\n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       "\n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       "Gold label: the human-defined labels for each document that we are trying to match. Confusion matrix: a table for visualizing how an algorithm performs with respect to the human gold labels, using two dimensions (system output and gold labels), and each cell labeling a set of possible outcomes. Precision measures the percentage of the items that the system detected (i.e., the system labeled as positive) that are in fact positive (i.e., are positive according to the human gold labels). Precision is defined as: Presision = true positive/true positive + false positive. Recall measures the percentage of items actually present in the input that were correctly identified by the system. Recall is defined as: Recall = true positive/true positive + false negative. There are many ways to define a single metric that incorporates aspects of both precision and recall. The simplest of these combinations is the F-measure: $F_b=(b^2+1)PR/b^2P+R$. The b parameter differentially weights the importance of recall and precision, based perhaps on the needs of an application. Values of b > 1 favor recall, while values of b < 1 favor precision. When b = 1, precision and recall are equally balanced; this is the most frequently used metric, and is called $F_{b-1}$ or just $F_1$: $F_1=2PR/P+R$. \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       "In cross-validation, we choose a number k, and partition our data into k disjointsubsets called folds.  If we choose k = 10, we would train 10 different models (each on 90% of our data), test the model 10 times, and average these 10 values. This is called 10-fold cross-validation. \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       "\n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       "\n",
       "\n",
       "## Module 12 Lecture Notes\n",
       "Naïve Bayes: Assume all features are independent effects of the label. A general Naive Bayes model: $P(Y,F_1...F_n)=P(Y) \\prod_{i} P(F_i|Y)$. We only have to specify how each feature depends on the class. Total number of parameters is linear in number of features. Downside: model is very simplistic. Bag-of-words Naïve Bayes: Features: $W_i$ is the word at positon i; As before: predict label conditioned on feature variables (spam vs. ham); As before: assume features are conditionally independent given label; New: each $W_i$ is identically distributed. Generative model: $P(Y,W_1...W_n)=P(Y) \\prod_{i} P(W_i|Y)$. In a bag-of-words model all positions share the same conditional probs P(W|Y). Called “bag-of-words” because model is insensitive to word order or reordering. Maximum likelihood: $P_{ML}(x)=count(x)/totalSamples$. Laplace smoothing for conditionals: $P_{LAP,k}(x|y)=(c(x,y)+k)/(c(y)+k|X|)$. In proctice, Laplace often performs poorly for P(x|y) when |X| or |Y| is very large. Linear interpolation: $P_{LIN}(x|y)=a\\hat{P} (x|y)+(1.0-a)\\hat{P} (x)$. Bayes rule lets us do diagnostic queries with causal probabilities. The naïve Bayes assumption takes all features to be independent given the class label. We can build classifiers out of a naïve Bayes model using training data. Smoothing estimates is important in real systems. Classifier confidences are useful, when you can get them. Linear Classifiers: inputs are feature values, each feature has a weight. Sum is the activation. Learning: Binary Perceptron. Start with weights = 0. For each training instance: Classify with current weights; If correct (i.e., y=y*), no change! If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1. Multiclass Decision Rule. If we have multiple classes: a weight vector for each class $w_y$; score (activation) of a class y $w_y \\cdot f(x)$; prediction highest score wins $y=argmax_yw_y\\cdot f(x)$. If wrong: lower score of wrong answer, raise score of right answer. Properties of Perceptrons: Separability: true if some parameters get the training set perfectly correct; Convergence: if the training is separable, perceptron will eventually converge (binary case); Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability. Problems with the Perceptron: Noise: if the data isn’t separable, weights might thrash, Averaging weight vectors over time can help (averaged perceptron); Mediocre generalization: finds a “barely” separating solution; Overtraining: test / held-out accuracy usually rises, then falls. Classification comparison: Naïve Bayes: Builds a model training data; Gives prediction probabilities; Strong assumptions about feature independence; One pass through data (counting). Perceptrons / MIRA: Makes less assumptions about data; Mistake-driven learning; Multiple passes through data (prediction); Often more accurate.\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module12_sections = [\n",
    "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
    "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
    "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
    "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
    "  (\"AIMA Chapter 19.5 The Theory of Learning\", chapter19_5),\n",
    "  (\"AIMA Chapter 19.6 Linear Regression and Classification\", chapter19_6),\n",
    "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
    "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
    "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
    "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
    "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
    "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
    "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
    "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
    "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
    "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
    "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
    "]\n",
    "\n",
    "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
    "                         module12_sections, \n",
    "                         module12_definitions)\n",
    "display(Markdown(module12_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "# Module 13 - Neural Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
    "\n",
    "slp_chapter5_1 = \"\"\"Logistic regression has a number of advantages over naive Bayes. \\\n",
    "Naive Bayes has overly strong conditional independence assumptions. Consider two \\\n",
    "features which are strongly correlated; in fact, imagine that we just add the \\ \n",
    "same feature f1 twice. Naive Bayes will treat both copies of f1 as if they were \\\n",
    "separate, multiplying them both in, overestimating the evidence. By contrast, logistic \\\n",
    "regression is much more robust to correlated features; if two features f1 and f2 are \\\n",
    "perfectly correlated, regression will simply assign part of the weight to w1 and part \\\n",
    "to w2. Thus when there are many correlated features, logistic regression will assign \\\n",
    "a more accurate probability than naive Bayes. So logistic regression generally works \\\n",
    "better on larger documents or datasets and is a common default. Despite the less \\\n",
    "accurate probabilities, naive Bayes still often makes the correct classification \\\n",
    "decision. Furthermore, naive Bayes can work extremely well (sometimes even better \\\n",
    "than logistic regression) on very small datasets or short documents. Furthermore, \\\n",
    "naive Bayes is easy to implement and very fast to train (there’s no optimization \\\n",
    "step). So it’s still a reasonable approach to use in some situations.\"\"\"\n",
    "slp_chapter5_2 = \"\"\"\"\"\"\n",
    "slp_chapter5_3 = \"\"\"\"\"\"\n",
    "slp_chapter5_4 = \"\"\"\"\"\"\n",
    "slp_chapter5_5 = \"\"\"\"\"\"\n",
    "slp_chapter5_6 = \"\"\"\"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
    "\n",
    "slp_chapter7_1 = \"\"\"A neural unit is taking a weighted sum of its inputs, with \\\n",
    "one additional term in the sum called a bias term $z=b+\\sum_{i} w_ix_i$. \\\n",
    "\"\"\"\n",
    "slp_chapter7_2 = \"\"\"Perceptron is a very simple neural unit that has a binary \\\n",
    "output and does not have a non-linear activation function. XOR is not a linearly \\\n",
    "separable function. While the XOR function cannot be calculated by a single \\\n",
    "perceptron, it can be calculated by a layered network of units. \"\"\"\n",
    "slp_chapter7_3 = \"\"\" A feedforward network is a multilayer network in which the \\\n",
    "units are connected with no cycles; the outputs from units in each layer are \\\n",
    "passed to units in the next higher layer, and no outputs are passed back to lower \\\n",
    "layers. Simple feedforward networks have three kinds of nodes: input units, \\\n",
    "hidden units, and output units. The core of the neural network is the hidden layer \\\n",
    "h formed of hidden units hi, each of which is a neural unit. In the standard \\\n",
    "architecture, each layer is fully-connected, meaning that each unit in each \\\n",
    "layer takes as input the outputs from all the units in the previous layer, and \\\n",
    "there is a link between every pair of units from two adjacent layers. Thus each \\\n",
    "hidden unit sums over all the input units. One of the reasons we use non-linear \\\n",
    "activation functions for each layer in a neural network is that if we did not, the \\\n",
    "resulting network is exactly equivalent to a single-layer network. \"\"\"\n",
    "slp_chapter7_4 = \"\"\"\"\"\"\n",
    "slp_chapter7_5 = \"\"\"Neural language models represent words in this prior context \\\n",
    "by their embeddings, rather than just by their word identity as used in n-gram \\\n",
    "language models. Using embeddings allows neural language models to generalize \\\n",
    "better to unseen data. Forward inference is the task, given an input, of running \\\n",
    "a forward pass on the network to produce a probability distribution over possible \\\n",
    "outputs, in this case next words. A one-hot vector is a vector that has one \\\n",
    "element equal to 1 — in the dimension corresponding to that word’s index in the \\\n",
    "vocabulary — while all the other elements are set to zero. \"\"\"\n",
    "slp_chapter7_6 = \"\"\"First, we’ll need a loss function that models the distance \\\n",
    "between the system output and the gold output, and it’s common to use the loss \\\n",
    "function used for logistic regression, the cross-entropy loss. Second, to find \\\n",
    "the parameters that minimize this loss function, we’ll use the gradient descent \\\n",
    "optimization algorithm. Third, gradient descent requires knowing the gradient of \\\n",
    "the loss function, the vector that contains the partial derivative of the loss \\\n",
    "function with respect to each of the parameters. How do we partial out the loss \\\n",
    "over all those intermediate layers? The answer is the algorithm called error \\\n",
    "backpropagation or backward differentiation. Hard classification task: only one \\\n",
    "class is the correct one, and that there is one output unit in y for each class. \\\n",
    "Hence the cross-entropy loss is simply the log of the output probability corresponding \\\n",
    "to the correct class, and we therefore also call this the negative log likelihood \\\n",
    "loss. Backwards differentiation makes use of the chain rule in calculus, so let’s \\\n",
    "remind ourselves of that. Suppose we are computing the derivative of a composite \\\n",
    "function f(x) = u(v(x)). The derivative of f(x) is the derivative of u(x) with \\\n",
    "respect to v(x) times the derivative of v(x) with respect to x: $df/dx = du/dv\\cdot dv/dx$. \\\n",
    "Various forms of regularization are used to prevent overfitting. One of the most\\\n",
    "important is dropout: randomly dropping some units and their connections from \\\n",
    "the network during training. Tuning of hyperparameters is also important. The \\\n",
    "parameters of a neural network are the weights W and biases b; those are learned by \\\n",
    "gradient descent. The hyperparameters are things that are chosen by the algorithm \\\n",
    "designer; optimal values are tuned on a devset rather than by gradient descent \\\n",
    "learning on the training set. Hyperparameters include the learning rate η, the \\\n",
    "mini-batch size, the model architecture (the number of layers, the number of \\\n",
    "hidden nodes per layer, the choice of activation functions), how to regularize, and so on. \"\"\"\n",
    "slp_chapter7_7 = \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module13_lecture_notes = \"\"\"Logistic regression solves sentiment classifier task by learning, \\\n",
    "from a training set, a vector of weights and a bias term. $z=\\sum_iw_ix_i+b$ \\\n",
    "Can also be written as a dot product: $z=w \\cdot x+b$. Sigmoid function: \\\n",
    "$y=1/(1+e^{-z})$. Probability: $P(y=1)= \\sigma (w \\cdot x+b)=1/1+e^{-(w \\cdot x+b)}$. \\\n",
    "Decision boundary: $ \\hat{y} =1 $ if P(y=1|x) > 0.5 or 0 otherwise. How do we get \\\n",
    "the weights of the model? We learn the parameters (weights + bias) via learning. \\\n",
    "This requires 2 components: 1. An objective function or loss function that tells \\\n",
    "us distance between the system output and the gold output. We will use cross-entropy \\\n",
    "loss; 2. An algorithm for optimizing the objective function. We will use stochastic \\\n",
    "gradient descent to minimize the loss function. Mean squared error is non convex. \\\n",
    "Conditional maximum likelihood estimation: Choose parameters w, b that maximize \\\n",
    "the (log) probabilities of the true labels in the training data. The resulting \\\n",
    "loss function is the negative log likelihood loss, more commonly called the cross \\\n",
    "entropy loss. For one observation x, let’s maximize the probability of the correct label \\\n",
    "$P(y|x)= \\hat{y}^y(1- \\hat{y} )^{1-y}$. If y = 1, then P(y|x) = $\\hat{y}$ (as high as possible). \\\n",
    "if y = 0, then P(y|x) = 1 - $\\hat{y}$. Changes to logs: $\\log P(y|x)= \\log [\\hat{y}^y(1- \\hat{y} )^{1-y}]\\\n",
    "=y \\log \\hat{y} +(1-y)\\log (1-\\hat{y} )$. This tells us what log likelihood should be \\\n",
    "maximized. But for loss functions, we want to minimize things, so we’ll flip the sign. \\ \n",
    "The result is cross-entropy loss: $L_{CE}(\\hat{y} ,y)=-\\log P(y|x)=-[y\\log \\hat{y} +(1-y)\\log (1-\\hat{y} )]$. \\\n",
    "Finally, plug in the definition for $\\hat{y} =\\sigma (w\\cdot x)+b$: \\\n",
    "$L_{CE}(\\hat{y} ,y)=-[y\\log \\sigma (w\\cdot x+b) +(1-y)\\log (1-\\sigma (w\\cdot x+b) )]$. \\\n",
    "Why does minimizing this negative log probability do what we want? We want the \\\n",
    "loss to be smaller if the model’s estimate is close to correct, and we want the \\\n",
    "loss to be bigger if it is confused. For logistic regression, this loss function \\\n",
    "is conveniently convex. A convex function has just one minimum, so there are no \\\n",
    "local minima to get stuck in. So gradient descent starting from any point is \\\n",
    "guaranteed to find the minimum. The magnitude of the amount to move in gradient \\\n",
    "descent is the value of the slope weighted by a learning rate $\\eta$. \\\n",
    "The derivative of the cross-entropy loss function of logistic regression for one \\\n",
    "observation vector x for a single weight $w_j$ is $\\partial {L_{CE}(w,b)} / \\partial {w_j}\\\n",
    "=[\\sigma (w \\cdot x+b)-y]x_j$. Average loss $Cost(w,b)=1/m \\sum_{i=1}^{m} L_{CE}(\\hat{y} ^{(i)},y^{(i)})\\\n",
    "=-1/m \\sum_{i=1}^{m} y^{(i)}\\log \\sigma (w \\cdot x^{(i)}+b)+(1-y^{(i)}) \\log (1-\\sigma (w \\cdot x^{(i)}+b))$. \\\n",
    "This is what we want to minimize. Stochastic gradient descent chooses a single \\\n",
    "random example at a time and updates its weights on that example. As a result \\\n",
    "the updates can fluctuate. An alternate is batch training, which computes the \\\n",
    "gradient over the entire dataset. This gives a much better estimate of which \\\n",
    "direction to move the weights but takes a long time to compute. A commonly used \\\n",
    "compromise is mini-batch training, where we train on a small batch. The batch \\\n",
    "size can be 512 or 1024, often selected based on computational resources, so that \\\n",
    "all examples in the mini-batch can be processed in parallel. The loss is then accumulated. \\\n",
    "Lasso regression uses L1 regularization. Ridge regression uses L2 regularization. \\\n",
    "Softmax function will be used for multinomial logistic regression. Multilayer \\\n",
    "network, all units are usually fully-connected, and no cycles. What do we need \\\n",
    "to train NN? A loss function – cross-entropy loss. An optimization algorithm – \\\n",
    "gradient descent. A way of computing the gradient of the loss function – error propagation. \\\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module13_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "4ec1b67c-9b9f-49cc-f12e-dbfdeed99e92"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       "Logistic regression has a number of advantages over naive Bayes. Naive Bayes has overly strong conditional independence assumptions. Consider two features which are strongly correlated; in fact, imagine that we just add the \\ \n",
       "same feature f1 twice. Naive Bayes will treat both copies of f1 as if they were separate, multiplying them both in, overestimating the evidence. By contrast, logistic regression is much more robust to correlated features; if two features f1 and f2 are perfectly correlated, regression will simply assign part of the weight to w1 and part to w2. Thus when there are many correlated features, logistic regression will assign a more accurate probability than naive Bayes. So logistic regression generally works better on larger documents or datasets and is a common default. Despite the less accurate probabilities, naive Bayes still often makes the correct classification decision. Furthermore, naive Bayes can work extremely well (sometimes even better than logistic regression) on very small datasets or short documents. Furthermore, naive Bayes is easy to implement and very fast to train (there’s no optimization step). So it’s still a reasonable approach to use in some situations.\n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       "\n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       "\n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       "\n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       "\n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       "\n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       "A neural unit is taking a weighted sum of its inputs, with one additional term in the sum called a bias term $z=b+\\sum_{i} w_ix_i$. \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       "Perceptron is a very simple neural unit that has a binary output and does not have a non-linear activation function. XOR is not a linearly separable function. While the XOR function cannot be calculated by a single perceptron, it can be calculated by a layered network of units. \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " A feedforward network is a multilayer network in which the units are connected with no cycles; the outputs from units in each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers. Simple feedforward networks have three kinds of nodes: input units, hidden units, and output units. The core of the neural network is the hidden layer h formed of hidden units hi, each of which is a neural unit. In the standard architecture, each layer is fully-connected, meaning that each unit in each layer takes as input the outputs from all the units in the previous layer, and there is a link between every pair of units from two adjacent layers. Thus each hidden unit sums over all the input units. One of the reasons we use non-linear activation functions for each layer in a neural network is that if we did not, the resulting network is exactly equivalent to a single-layer network. \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       "\n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       "Neural language models represent words in this prior context by their embeddings, rather than just by their word identity as used in n-gram language models. Using embeddings allows neural language models to generalize better to unseen data. Forward inference is the task, given an input, of running a forward pass on the network to produce a probability distribution over possible outputs, in this case next words. A one-hot vector is a vector that has one element equal to 1 — in the dimension corresponding to that word’s index in the vocabulary — while all the other elements are set to zero. \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       "First, we’ll need a loss function that models the distance between the system output and the gold output, and it’s common to use the loss function used for logistic regression, the cross-entropy loss. Second, to find the parameters that minimize this loss function, we’ll use the gradient descent optimization algorithm. Third, gradient descent requires knowing the gradient of the loss function, the vector that contains the partial derivative of the loss function with respect to each of the parameters. How do we partial out the loss over all those intermediate layers? The answer is the algorithm called error backpropagation or backward differentiation. Hard classification task: only one class is the correct one, and that there is one output unit in y for each class. Hence the cross-entropy loss is simply the log of the output probability corresponding to the correct class, and we therefore also call this the negative log likelihood loss. Backwards differentiation makes use of the chain rule in calculus, so let’s remind ourselves of that. Suppose we are computing the derivative of a composite function f(x) = u(v(x)). The derivative of f(x) is the derivative of u(x) with respect to v(x) times the derivative of v(x) with respect to x: $df/dx = du/dv\\cdot dv/dx$. Various forms of regularization are used to prevent overfitting. One of the mostimportant is dropout: randomly dropping some units and their connections from the network during training. Tuning of hyperparameters is also important. The parameters of a neural network are the weights W and biases b; those are learned by gradient descent. The hyperparameters are things that are chosen by the algorithm designer; optimal values are tuned on a devset rather than by gradient descent learning on the training set. Hyperparameters include the learning rate η, the mini-batch size, the model architecture (the number of layers, the number of hidden nodes per layer, the choice of activation functions), how to regularize, and so on. \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       "\n",
       "\n",
       "## Module 13 Lecture Notes\n",
       "Logistic regression solves sentiment classifier task by learning, from a training set, a vector of weights and a bias term. $z=\\sum_iw_ix_i+b$ Can also be written as a dot product: $z=w \\cdot x+b$. Sigmoid function: $y=1/(1+e^{-z})$. Probability: $P(y=1)= \\sigma (w \\cdot x+b)=1/1+e^{-(w \\cdot x+b)}$. Decision boundary: $ \\hat{y} =1 $ if P(y=1|x) > 0.5 or 0 otherwise. How do we get the weights of the model? We learn the parameters (weights + bias) via learning. This requires 2 components: 1. An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss; 2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function. Mean squared error is non convex. Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss. For one observation x, let’s maximize the probability of the correct label $P(y|x)= \\hat{y}^y(1- \\hat{y} )^{1-y}$. If y = 1, then P(y|x) = $\\hat{y}$ (as high as possible). if y = 0, then P(y|x) = 1 - $\\hat{y}$. Changes to logs: $\\log P(y|x)= \\log [\\hat{y}^y(1- \\hat{y} )^{1-y}]=y \\log \\hat{y} +(1-y)\\log (1-\\hat{y} )$. This tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we’ll flip the sign. \\ \n",
       "The result is cross-entropy loss: $L_{CE}(\\hat{y} ,y)=-\\log P(y|x)=-[y\\log \\hat{y} +(1-y)\\log (1-\\hat{y} )]$. Finally, plug in the definition for $\\hat{y} =\\sigma (w\\cdot x)+b$: $L_{CE}(\\hat{y} ,y)=-[y\\log \\sigma (w\\cdot x+b) +(1-y)\\log (1-\\sigma (w\\cdot x+b) )]$. Why does minimizing this negative log probability do what we want? We want the loss to be smaller if the model’s estimate is close to correct, and we want the loss to be bigger if it is confused. For logistic regression, this loss function is conveniently convex. A convex function has just one minimum, so there are no local minima to get stuck in. So gradient descent starting from any point is guaranteed to find the minimum. The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate $\\eta$. The derivative of the cross-entropy loss function of logistic regression for one observation vector x for a single weight $w_j$ is $\\partial {L_{CE}(w,b)} / \\partial {w_j}=[\\sigma (w \\cdot x+b)-y]x_j$. Average loss $Cost(w,b)=1/m \\sum_{i=1}^{m} L_{CE}(\\hat{y} ^{(i)},y^{(i)})=-1/m \\sum_{i=1}^{m} y^{(i)}\\log \\sigma (w \\cdot x^{(i)}+b)+(1-y^{(i)}) \\log (1-\\sigma (w \\cdot x^{(i)}+b))$. This is what we want to minimize. 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. An alternate is batch training, which computes the gradient over the entire dataset. This gives a much better estimate of which direction to move the weights but takes a long time to compute. A commonly used compromise is mini-batch training, where we train on a small batch. The batch size can be 512 or 1024, often selected based on computational resources, so that all examples in the mini-batch can be processed in parallel. The loss is then accumulated. Lasso regression uses L1 regularization. Ridge regression uses L2 regularization. Softmax function will be used for multinomial logistic regression. Multilayer network, all units are usually fully-connected, and no cycles. What do we need to train NN? A loss function – cross-entropy loss. An optimization algorithm – gradient descent. A way of computing the gradient of the loss function – error propagation. \n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module13_sections = [\n",
    "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
    "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
    "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
    "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
    "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
    "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
    "\n",
    "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
    "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
    "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
    "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
    "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
    "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
    "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
    "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
    "]\n",
    "\n",
    "module13_markdown = format_module(13, \"Neural Networks\", \n",
    "                         module13_sections, \n",
    "                         module13_definitions)\n",
    "display(Markdown(module13_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "# Module 14 - Natural Language Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
    "\n",
    "slp_chapter9_1 = \"\"\"\"\"\"\n",
    "slp_chapter9_2 = \"\"\"RNN: recurrent neural network. To compute an output yt for \\\n",
    "an input xt, we need the activation value for the hidden layer ht. To calculate \\\n",
    "this, we multiply the input xt with the weight matrix W, and the hidden layer \\\n",
    "from the previous time step ht−1 with the weight matrix U. We add these values \\\n",
    "together and pass them through a suitable activation function, g, to arrive at \\\n",
    "the activation value for the current hidden layer, ht. $h_t=g(Uh_{t-1}+Wx_t)$, \\\n",
    "$y_t=f(Vh_t)$. W = dh x din, U = dh x dh, and V = dout x dh. 3 sets of weights \\\n",
    "to update: W, the weights from the input layer to the hidden layer, U, the weights \\\n",
    "from the previous hidden layer to the current hidden layer, and finally V, the \\\n",
    "weights from the hidden layer to the output layer. Tailoring the backpropagation \\\n",
    "algorithm to this situation leads to a two-pass algorithm for training the weights \\\n",
    "in RNNs. In the first pass, we perform forward inference, computing ht, yt, \\\n",
    "accumulating the loss at each step in time, saving the value of the hidden layer \\\n",
    "at each step for use at the next time step. In the second phase, we process the \\\n",
    "sequence in reverse, computing the required gradients as we go, computing and \\\n",
    "saving the error term for use in the hidden layer for each step backward in time. \\\n",
    "This general approach is commonly referred to as Backpropagation Through Time. \"\"\"\n",
    "slp_chapter9_3 = \"\"\"The input sequence X = [x1;...;xt;...;xN] consists of a series \\\n",
    "of word embeddings each represented as a one-hot vector of size |V|×1, and the output \\\n",
    "prediction, y, is a vector representing a probability distribution over the vocabulary. \\\n",
    "To train an RNN as a language model, we use a corpus of text as training material, \\\n",
    "having the model predict the next word at each time step t. We train the model to \\\n",
    "minimize the error in predicting the true next word in the training sequence, using \\\n",
    "cross-entropy as the loss function. In the case of language modeling, the correct \\\n",
    "distribution yt comes from knowing the next word. This is represented as a one-hot \\\n",
    "vector corresponding to the vocabulary where the entry for the actual next word \\\n",
    "is 1, and all the other entries are 0. Thus, the cross-entropy loss for language \\\n",
    "modeling is determined by the probability the model assigns to the correct next \\\n",
    "word. Teacher forcing: always give the model the correct history sequence to \\\n",
    "predict the next word.\"\"\"\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 = \"\"\"Semantic field: a set of words which cover a particular semantic \\\n",
    "domain and bear structured relations with each other. Semantic frame: a set of \\\n",
    "words that denote perspectives or participants in a particular type of event. \\\n",
    "\"\"\"\n",
    "slp_chapter6_2 = \"\"\"The idea of vector semantics is to represent a word as a point \\\n",
    "in a multidimensional semantic space that is derived (in ways we’ll see) from the \\\n",
    "distributions of word neighbors. \"\"\"\n",
    "slp_chapter6_3 = \"\"\"Vector or distributional models of meaning are generally based \\\n",
    "on a co-occurrence matrix. Information retrieval (IR) is the task of finding the \\\n",
    "document d from the D documents in some collection that best matches a query q. \\\n",
    "For documents, we saw that similar documents had similar vectors, because similar \\\n",
    "documents tend to have similar words. This same principle applies to words: \\\n",
    "similar words have similar vectors because they tend to occur in similar documents.\\\n",
    "\"\"\"\n",
    "slp_chapter6_4 = \"\"\"The cosine is based on the dot product operator from linear \\\n",
    "algebra, also called the inner product. This raw dot product, however, has a problem \\\n",
    "as a similarity metric: it favors long vectors. We modify the dot product to \\\n",
    "normalize for the vector length by dividing the dot product by the lengths of \\\n",
    "each of the two vectors. This normalized dot product turns out to be the same as \\\n",
    "the cosine of the angle between the two vectors, following from the definition \\\n",
    "of the dot product between two vectors a and b. \"\"\"\n",
    "slp_chapter6_8 = \"\"\"Unlike the vectors, embeddings are short, with number of \\\n",
    "dimensions d ranging from 50-1000, rather than the much larger vocabulary size \\\n",
    "|V| or number of documents D we’ve seen. The vectors are dense: instead of vector \\\n",
    "entries being sparse, mostly-zero counts or functions of counts, the values will \\\n",
    "be real-valued numbers that can be negative. It turns out that dense vectors work \\\n",
    "better in every NLP task than sparse vectors. Dense vectors may also do a better \\\n",
    "job of capturing synonymy. Skip-gram with negative sampling (SGNS) loosely \\\n",
    "referred to as word2vec. The intuition of word2vec is that instead of counting \\\n",
    "how often each word w occurs near, say, apricot, we’ll instead train a classifier \\\n",
    "on a binary prediction task: “Is word w likely to show up near apricot?” We don’t \\\n",
    "actually care about this prediction task; instead we’ll take the learned \\\n",
    "classifier weights as the word embeddings. word2vec is a much simpler model than \\\n",
    "the neural network language model, in two ways. First, word2vec simplifies the \\\n",
    "task (making it binary classification instead of word prediction). Second, \\\n",
    "word2vec simplifies the architecture (training a logistic regression classifier \\\n",
    "instead of a multi-layer neural network with hidden layers that demand more \\\n",
    "sophisticated training algorithms). The intuition of the skipgram model is to \\\n",
    "base this probability on embedding similarity: a word is likely to occur near \\\n",
    "the target if its embedding vector is similar to the target embedding.\"\"\"\n",
    "slp_chapter6_10 = \"\"\"Different types of similarity or association: One parameter \\\n",
    "of vector semantic models that is relevant to both sparse tf-idf vectors and \\\n",
    "dense word2vec vectors is the size of the context window used to collect counts. \\\n",
    "This is generally between 1 and 10 words on each side of the target word (for a \\\n",
    "total context of 2-20 words). Analogy/Relational Similarity: Another semantic \\\n",
    "property of embeddings is their ability to capture relational meanings.\"\"\"\n",
    "slp_chapter6_11 = \"\"\"In addition to their ability to learn word meaning from text, \\\n",
    "embeddings, alas, also reproduce the implicit biases and stereotypes that were \\\n",
    "latent in the text. It turns out that embeddings don’t just reflect the statistics \\\n",
    "of their input, but also amplify bias. \"\"\"\n",
    "slp_chapter6_12 = \"\"\"\"\"\"\n",
    "\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module14_lecture_notes = \"\"\"Documents creatd by term-by-document or term-context \\\n",
    "matrices are long and sparse. Alternative: short and dense vactors. Why? Short \\\n",
    "vectors may be easier to use as features. Dense vectors may generalize better \\\n",
    "than storing explicit counts. Do better at capturing synonymy. Word2vec: Skip-Gram Task. \\\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module14_definitions = {\n",
    "\"Embeddings\" : \"vectors for representing words\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "2b6b6e01-be09-469b-bc1d-e4e7d367f788"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       "\n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       "RNN: recurrent neural network. To compute an output yt for an input xt, we need the activation value for the hidden layer ht. To calculate this, we multiply the input xt with the weight matrix W, and the hidden layer from the previous time step ht−1 with the weight matrix U. We add these values together and pass them through a suitable activation function, g, to arrive at the activation value for the current hidden layer, ht. $h_t=g(Uh_{t-1}+Wx_t)$, $y_t=f(Vh_t)$. W = dh x din, U = dh x dh, and V = dout x dh. 3 sets of weights to update: W, the weights from the input layer to the hidden layer, U, the weights from the previous hidden layer to the current hidden layer, and finally V, the weights from the hidden layer to the output layer. Tailoring the backpropagation algorithm to this situation leads to a two-pass algorithm for training the weights in RNNs. In the first pass, we perform forward inference, computing ht, yt, accumulating the loss at each step in time, saving the value of the hidden layer at each step for use at the next time step. In the second phase, we process the sequence in reverse, computing the required gradients as we go, computing and saving the error term for use in the hidden layer for each step backward in time. This general approach is commonly referred to as Backpropagation Through Time. \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       "The input sequence X = [x1;...;xt;...;xN] consists of a series of word embeddings each represented as a one-hot vector of size |V|×1, and the output prediction, y, is a vector representing a probability distribution over the vocabulary. To train an RNN as a language model, we use a corpus of text as training material, having the model predict the next word at each time step t. We train the model to minimize the error in predicting the true next word in the training sequence, using cross-entropy as the loss function. In the case of language modeling, the correct distribution yt comes from knowing the next word. This is represented as a one-hot vector corresponding to the vocabulary where the entry for the actual next word is 1, and all the other entries are 0. Thus, the cross-entropy loss for language modeling is determined by the probability the model assigns to the correct next word. Teacher forcing: always give the model the correct history sequence to predict the next word.\n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       "Semantic field: a set of words which cover a particular semantic domain and bear structured relations with each other. Semantic frame: a set of words that denote perspectives or participants in a particular type of event. \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       "The idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived (in ways we’ll see) from the distributions of word neighbors. \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       "Vector or distributional models of meaning are generally based on a co-occurrence matrix. Information retrieval (IR) is the task of finding the document d from the D documents in some collection that best matches a query q. For documents, we saw that similar documents had similar vectors, because similar documents tend to have similar words. This same principle applies to words: similar words have similar vectors because they tend to occur in similar documents.\n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       "The cosine is based on the dot product operator from linear algebra, also called the inner product. This raw dot product, however, has a problem as a similarity metric: it favors long vectors. We modify the dot product to normalize for the vector length by dividing the dot product by the lengths of each of the two vectors. This normalized dot product turns out to be the same as the cosine of the angle between the two vectors, following from the definition of the dot product between two vectors a and b. \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       "Unlike the vectors, embeddings are short, with number of dimensions d ranging from 50-1000, rather than the much larger vocabulary size |V| or number of documents D we’ve seen. The vectors are dense: instead of vector entries being sparse, mostly-zero counts or functions of counts, the values will be real-valued numbers that can be negative. It turns out that dense vectors work better in every NLP task than sparse vectors. Dense vectors may also do a better job of capturing synonymy. Skip-gram with negative sampling (SGNS) loosely referred to as word2vec. The intuition of word2vec is that instead of counting how often each word w occurs near, say, apricot, we’ll instead train a classifier on a binary prediction task: “Is word w likely to show up near apricot?” We don’t actually care about this prediction task; instead we’ll take the learned classifier weights as the word embeddings. word2vec is a much simpler model than the neural network language model, in two ways. First, word2vec simplifies the task (making it binary classification instead of word prediction). Second, word2vec simplifies the architecture (training a logistic regression classifier instead of a multi-layer neural network with hidden layers that demand more sophisticated training algorithms). The intuition of the skipgram model is to base this probability on embedding similarity: a word is likely to occur near the target if its embedding vector is similar to the target embedding.\n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       "Different types of similarity or association: One parameter of vector semantic models that is relevant to both sparse tf-idf vectors and dense word2vec vectors is the size of the context window used to collect counts. This is generally between 1 and 10 words on each side of the target word (for a total context of 2-20 words). Analogy/Relational Similarity: Another semantic property of embeddings is their ability to capture relational meanings.\n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       "In addition to their ability to learn word meaning from text, embeddings, alas, also reproduce the implicit biases and stereotypes that were latent in the text. It turns out that embeddings don’t just reflect the statistics of their input, but also amplify bias. \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       "\n",
       "\n",
       "## Module 14 Lecture Notes\n",
       "Documents creatd by term-by-document or term-context matrices are long and sparse. Alternative: short and dense vactors. Why? Short vectors may be easier to use as features. Dense vectors may generalize better than storing explicit counts. Do better at capturing synonymy. Word2vec: Skip-Gram Task. \n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Embeddings** - vectors for representing words\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module14_sections = [\n",
    "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
    "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
    "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
    "\n",
    "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
    "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
    "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
    "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
    "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
    "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
    "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
    "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
    "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
    "]\n",
    "\n",
    "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
    "                         module14_sections, \n",
    "                         module14_definitions)\n",
    "display(Markdown(module14_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vX7lbnJd4sT5"
   },
   "source": [
    "# Your Exam Notes\n",
    "\n",
    "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
    "\n",
    "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
    "* Run the cell below. \n",
    "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "T3cm1WV542_a",
    "outputId": "97f3b442-cf6d-48af-9a21-bd390b8a14a3"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " $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",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       "\n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       "\n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Utility function** - Your definition here\n",
       "* **Expected utility** - your definition here\n",
       "* **Etc.** - your definition here\n",
       "\n",
       "\n",
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       "\n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       "MODEL-BASED REINFORCEMENT LEARNING: In these approaches the agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. MODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither knows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave. \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       "Temporal-difference (TD) equation: $U^{\\pi }(s) \\leftarrow U^{\\pi }(s)+a[R(s, \\pi (s),s')+\\gamma U^{\\pi }(s')-U^{\\pi }(s)]$. The TD term $R(s, \\pi (s),s')+\\gamma U^{\\pi }(s')-U^{\\pi }(s)$ is effectively an error signal, and the update is intended to reduce the error. \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       "A passive learning agent has a fixed policy that determines its behavior. An active learning agent gets to decide what actions to take. an agent must make a tradeoff between exploitation of the current best action to maximize its short-term reward and exploration of previously unknown states to gain information that can lead to a change in policy (and to greater rewards in the future). A GLIE (greedy in the limit of infinite exploration) scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed. one of the simplest GLIE scheme is to have the agent choose a random action at time step t with probability 1/t and to follow the greedy policy otherwise. A better approach would give some weight to actions that the agent has not tried very often, while tending to avoid actions that are believed to be of low utility. f is the exploration function. The function f(u,n) determines how greed (preference for high values of the utility u) is traded off against curiosity (preference for actions that have not been tried often and have a low count n). Many actions are irreversible: no subsequent sequence of actions can restore the state to what it was before the irreversible action was taken. In the worst case, the agent enters an absorbing state where no actions have any effect and no rewards are received. We can end up in a bad state either because our model is unknown, and we actively choose to explore in a direction that turns out to be bad, or because our model is incorrect and we don’t know that a given action can have a disastrous result. The Q-learning method avoids the need for a model by learning an action-utility function Q(s,a) instead of a utility function U(s). A TD Q-learning agent does not need a transition model, P(s'|s,a), either for learning or for action selection. Model-free methods can be applied even in very complex domains because no model need be provided or learned. The Q-learning agent has no means of looking into the future, so it may have difficulty when rewards are sparse and long action sequences must be constructed to reach them. \n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       "\n",
       "\n",
       "## Module 9 Lecture Notes\n",
       "\n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Term** - your definition here\n",
       "\n",
       "\n",
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       "General marginalization rule: $P(Y)=\\sum_{Z} P(Y,Z=z)$. Conditioning: $P(Y)=\\sum_{Z} P(Y|Z)P(Z)$. \n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       "\n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       "Chain rule of probability: $P(X_1...X_n)=P(X_1)P(X_2|X_1)...P(X_n|X_{1:n-1})= \\prod_{k = 1}^{n} P(X_k|X_{1:k-1})$. The assumption that the probability of a word depends only on the previous word is called a Markov assumption. N-gram: looks n-1 words into the past $P(w_n|w_{1:n-1})\u0007pprox P(w_n|w_{n-N+1:n-1})$. The maximum likelihood estimation (MLE) for the parameters of an n-gram model is got counts from a corpus, and normalizing the counts so that they lie between 0 and 1. Relative frequency: estimates the n-gram probability by dividing the observed frequency of a particular sequence by the observed frequency of a prefix. \n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       "Extrinsic evaluation: an end-to-end evaluation that embedding the performance of a language model in an application and measure how much the application improves. Intrinsic evaluation:  measures the quality of a model independent of any application. Perplexity (PP): the inverse probability of the test set, normalized by the number of words. $PP(W)= \\sqrt[N]{\\prod_{i=1}^{N} 1/P(w_i|w_1...w_{i-1})}$. There is another way to think about perplexity: as the weighted average branching factor of a language. The branching factor of a language is the number of possible next words that can follow any word. \n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       "Sampling from a distribution means to choose random points according to their likelihood. \n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       "Why are things that don’t ever occur in the training set but do occur in the test set a problem? First, their presence means we are underestimating the probability of all sorts of words that might occur, which will hurt the performance of any application we want to run on this data. Second, if the probability of any word in the test set is 0, the entire probability of the test set is 0. By definition, perplexity is based on the inverse probability of the test set. Thus if some words have zero probability, we can’t compute perplexity at all, since we can’t divide by 0! \n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       "Laplace smoothing: add one to all the n-gram counts, before we normalize them into probabilities. Add-k smoothing: instead of adding 1 to each count, we add a fractional count k (.5? .05? .01?). \n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       "\n",
       "\n",
       "## Module 10 Lecture Notes\n",
       "3 general situations of Uncertainty: 1. Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms). 2. Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present). 3. Model: Agent knows something about how the known variables relate to the unknown variables. In probability theory, the possible worlds are called the sample space, and they mutually exclusive (P(A∩B)=0) and exhaustive (events that contains all of the outcomes in the sample space, P(A∪B)=1). A joint distribution over a set of random variables: X1, X2,..., Xn specifies a real number for each assignment (or outcome) P(x1,x2,...,xn). A probabilistic model is a joint distribution over a set of random variables. An event is a set E of outcomes $$P(E) = \\sum_(x_1...x_n\\inE) P(x_1...x_n)$$. Conditional Probabilities: P(a|b)=P(a,b)/P(b). Probabilistic Inference: compute a desired probability from other known probabilities (e.g. conditional from joint). Inference by Enumeration: Evidence variables: things have observed. Query variables: things we care about and want to reason about how likely their outcomes are. Hidden variables: things occur and big joint probability distribution but aren't things taht we've either observed or reasoning about. We care about P(Q|e1...ek). Step 1: Select the entries consistent with the evidence. Step 2: Sum out H to get joint of Query and evidence. Step 3: Normalize. Product Rule: P(y)P(x|y) = P(x,y). The Chain Rule: P(x1,x2,...,xn) = ΠiP(xi|x1,...,xi-1). Bayes’ Rule: P(x,y) = P(x|y)P(y) = P(y|x)P(x). P(x|y) = (P(y|x)/P(y))P(x). Why Bayes' rule useful? Lets us build one conditional from its reverse; Often one conditional is tricky but the other one is simple. Probabilistic Language Modeling's Goal: compute the probability of a sentence or sequence of words. Related task: probability of an upcoming word. A model that computes either of these is called a language model or LM. Joint probability of words in sentence: P(w1w2...wn) = ΠiP(wi|w1...wi-1). Just count and divide doesn't work because some sentences may never appear in the corpus. Markov Assumption: only depends on the previous k words, not the whole context. The Maximum Likelihood Estimate of bigram probabilities: P(wi|wi-1) = count(wi-1,wi)/ count(wi-1). \n",
       "\n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Term** - your definition here\n",
       "\n",
       "\n",
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       "Full joint probability distribution can answer any question about the domain, but can become intractably large as the number of variables grows. Furthermore, specifying probabilities for possible worlds one by one is unnatural and tedious. Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely. A Bayesian network is a directed graph in which each node is annotated with quantitative probability information. The intuitive meaning of an arrow is typically that X has a direct influence on Y, which suggests that causes should be parents of effects. \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       "The syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. The semantics defines how the syntax corresponds to a joint distribution over the variables of the network. As well as being a complete and nonredundant representation of the domain, a Bayes net can often be far more compact than the full joint distribution. This property is what makes it feasible to handle domains with many variables. The compactness of Bayesian networks is an example of a general property of locally structured (also called sparse) systems. In a locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity. The most general conditional independence question one might ask in a Bayes net is whether a set of nodes X is conditionally independent of another set Y, given a third set Z. This can be determined efficiently by examining the Bayes net to see whether Z d-separates X and Y. In brief, then, d-separation means separation in the undirected, moralized, ancestral subgraph. Even if the maximum number of parents k is smallish, filling in the CPT for a node requires up to $O(2^k)$ numbers and perhaps a great deal of experience with all the possible conditioning cases. A deterministic node has its value specified exactly by the values of its parents, with no uncertainty. A conditional distribution exhibits CSI (context-specific independence) if a variable is conditionally independent of some of its parents given certain values of others. Uncertain relationships can often be characterized by so-called noisy logical relationships. The standard example is the noisy-OR relation, which is a generalization of the logical OR. One way to handle continuous variables is with discretization: dividing up the possible values into a fixed set of intervals. A nonparametric representation: define the conditional distribution implicitly with a collection of instances, each containing specific values of the parent and child variables. A network with both discrete and continuous variables is called a hybrid Bayesian network. \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       "The basic task for any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event—usually, some assignment of values to a set of evidence variables. The time and space complexity of exact inference in polytrees is linear in the size of the network. \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       "Models describe how (a portion of) the world works. Models are always simplifications: May not account for every variable; May not account for all interactions between variables. X and Y are independent if p(x,y) = p(x)p(y). Knowing p(x) providing no information about p(y). X and Y are conditionally independent given Z: p(x,y|z) = p(x|z)p(y|z). (Conditional) independence is a property of a distribution. Conditional independence is our most basic and robust form of knowledge about uncertain environments. Causal chain: P(x,y,z) = P(x)P(y|x)P(z|y). Guaranteed X independent of Z? No! One example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed. Guaranteed X independent of Z given Y? Yes! Common cause: P(x,y,z) = P(y)P(x|y)P(z|y). Common effect: two causes of onee effect (v-structures). \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 19.1 Forms of Learning\n",
       "When the output is one of a finite set of values (such as sunny/cloudy/rainy or true/false), the learning problem is called classification. When it is a number (such as tomorrow’s temperature, measured either as an integer or a real number), the learning problem has the (admittedly obscure) name regression. There are three types of feedback that can accompany the inputs, and that determine the three main types of learning: Supervised learning; unsupervised learning; reinforcement learning. \n",
       "\n",
       "## AIMA Chapter 19.2 Supervised Learning\n",
       "Exploratory data analysis: examining the data with statistical tests and visualizations—histograms, scatter plots, box plots—to get a feel for the data, and some insight into what hypothesis space might be appropriate. How do we choose a good hypothesis from within the hypothesis space? We could hope for a consistent hypothesis: an h such that each xi in the training set has $h(x_i)=y_i$. With continuous-valued outputs we can’t expect an exact match to the ground truth; instead we look for a best-fit function. We say that h generalizes well if it accurately predicts the outputs of the test set. By bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space. We say that a hypothesis is underfitting when it fails to find a pattern in the data. On the other hand, the piecewise linear function has low bias; the shape of the function is driven by the data. By variance we mean the amount of change in the hypothesis due to fluctuation in the training data. We say a function is overfitting the data when it pays too much attention to the particular data set it is trained on, causing it to perform poorly on unseen data. Bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may generalize better. \n",
       "\n",
       "## AIMA Chapter 19.3 Learning Decision Trees\n",
       "A decision tree is a representation of a function that maps a vector of attribute values to a single output value—a “decision.” A decision tree reaches its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached. In general, the input and output values can be discrete or continuous. Boolean classification: inputs only consisting of discrete values and outputs that are either true (a positive example) or false (a negative example). We can evaluate the performance of a learning algorithm with a learning curve. Entropy is a measure of the uncertainty of a random variable; the more information, the less entropy. The information gain from the attribute test on is the expected reduction in entropy: $Gain(A)=B(p/p+n)-Remainder(A)$. For decision trees, a technique called decision tree pruning combats overfitting. Pruning works by eliminating nodes that are not clearly relevant. \n",
       "\n",
       "## AIMA Chapter 19.4 Model Selection and Optimization\n",
       "Stationarity assumption: the future examples will be like the past. Error rate: the proportion of times that $h(x)!=y$ for an (x,y) example. A process of feature selection can be performed to discard attributes that appear to be irrelevant. The simplest approach to hyperparameter tuning is hand-tuning: guess some parameter values based on past experience, train a model, measure its performance on the validation data, analyze the results, and use your intuition to suggest new parameter values. Repeat until you have satisfactory performance (or you run out of time, computing budget, or patience). If there are only a few hyperparameters, each with a small number of possible values, then a more systematic approach called grid search is appropriate: try all combinations of values and see which performs best on the validation data. Different combinations can be run in parallel on different machines, so if you have sufficient computing resources, this need not be slow, although in some cases model selection has been known to suck up resources on thousand-computer clusters for days at a time. If there are too many combinations of possible values, then random search samples uniformly from the set of all possible hyperparameter settings, repeating for as long as you are willing to spend the time and computational resources. Random sampling is also a good way to handle continuous values. When each training run takes a long time, it can be helpful to get useful information out of each one. Bayesian optimization treats the task of choosing good hyperparameter values as a machine learning problem in itself. \n",
       "\n",
       "## AIMA Chapter 19.5 The Theory of Learning\n",
       "PAC(probably approximately correct)-learning theorems, like all theorems, are logical consequences of axioms. \n",
       "\n",
       "## AIMA Chapter 19.6 Linear Regression and Classification\n",
       "Weights in linear regression: the value of y is changed by changing the relative weight of one term or another.\n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       "Bag-of-words: an unordered set of words with their position ignored, keeping only their frequency in the document. we compute the most probable class $\\hat{c} $ given some document d by choosing the class which has the highest product of two probabilities: the prior probability of the class P(c) and the likelihood of the document P(d|c). Naive Bayes classifiers make two simplifying assumptions. The first is the bag of words assumption: we assume position doesn’t matter. The second is commonly called the naive Bayes assumption: this is the conditional independence assumption that the probabilities P(fi|c) are independent given the class c and hence can be ‘naively’ multiplied. Classifiers that use a linear combination of the inputs to make a classification decision —like naive Bayes and also logistic regression— are called linear classifiers.\n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       "\n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       "\n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       "\n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       "\n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       "\n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       "Gold label: the human-defined labels for each document that we are trying to match. Confusion matrix: a table for visualizing how an algorithm performs with respect to the human gold labels, using two dimensions (system output and gold labels), and each cell labeling a set of possible outcomes. Precision measures the percentage of the items that the system detected (i.e., the system labeled as positive) that are in fact positive (i.e., are positive according to the human gold labels). Precision is defined as: Presision = true positive/true positive + false positive. Recall measures the percentage of items actually present in the input that were correctly identified by the system. Recall is defined as: Recall = true positive/true positive + false negative. There are many ways to define a single metric that incorporates aspects of both precision and recall. The simplest of these combinations is the F-measure: $F_b=(b^2+1)PR/b^2P+R$. The b parameter differentially weights the importance of recall and precision, based perhaps on the needs of an application. Values of b > 1 favor recall, while values of b < 1 favor precision. When b = 1, precision and recall are equally balanced; this is the most frequently used metric, and is called $F_{b-1}$ or just $F_1$: $F_1=2PR/P+R$. \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       "In cross-validation, we choose a number k, and partition our data into k disjointsubsets called folds.  If we choose k = 10, we would train 10 different models (each on 90% of our data), test the model 10 times, and average these 10 values. This is called 10-fold cross-validation. \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       "\n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       "\n",
       "\n",
       "## Module 12 Lecture Notes\n",
       "Naïve Bayes: Assume all features are independent effects of the label. A general Naive Bayes model: $P(Y,F_1...F_n)=P(Y) \\prod_{i} P(F_i|Y)$. We only have to specify how each feature depends on the class. Total number of parameters is linear in number of features. Downside: model is very simplistic. Bag-of-words Naïve Bayes: Features: $W_i$ is the word at positon i; As before: predict label conditioned on feature variables (spam vs. ham); As before: assume features are conditionally independent given label; New: each $W_i$ is identically distributed. Generative model: $P(Y,W_1...W_n)=P(Y) \\prod_{i} P(W_i|Y)$. In a bag-of-words model all positions share the same conditional probs P(W|Y). Called “bag-of-words” because model is insensitive to word order or reordering. Maximum likelihood: $P_{ML}(x)=count(x)/totalSamples$. Laplace smoothing for conditionals: $P_{LAP,k}(x|y)=(c(x,y)+k)/(c(y)+k|X|)$. In proctice, Laplace often performs poorly for P(x|y) when |X| or |Y| is very large. Linear interpolation: $P_{LIN}(x|y)=a\\hat{P} (x|y)+(1.0-a)\\hat{P} (x)$. Bayes rule lets us do diagnostic queries with causal probabilities. The naïve Bayes assumption takes all features to be independent given the class label. We can build classifiers out of a naïve Bayes model using training data. Smoothing estimates is important in real systems. Classifier confidences are useful, when you can get them. Linear Classifiers: inputs are feature values, each feature has a weight. Sum is the activation. Learning: Binary Perceptron. Start with weights = 0. For each training instance: Classify with current weights; If correct (i.e., y=y*), no change! If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1. Multiclass Decision Rule. If we have multiple classes: a weight vector for each class $w_y$; score (activation) of a class y $w_y \\cdot f(x)$; prediction highest score wins $y=argmax_yw_y\\cdot f(x)$. If wrong: lower score of wrong answer, raise score of right answer. Properties of Perceptrons: Separability: true if some parameters get the training set perfectly correct; Convergence: if the training is separable, perceptron will eventually converge (binary case); Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability. Problems with the Perceptron: Noise: if the data isn’t separable, weights might thrash, Averaging weight vectors over time can help (averaged perceptron); Mediocre generalization: finds a “barely” separating solution; Overtraining: test / held-out accuracy usually rises, then falls. Classification comparison: Naïve Bayes: Builds a model training data; Gives prediction probabilities; Strong assumptions about feature independence; One pass through data (counting). Perceptrons / MIRA: Makes less assumptions about data; Mistake-driven learning; Multiple passes through data (prediction); Often more accurate.\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       "Logistic regression has a number of advantages over naive Bayes. Naive Bayes has overly strong conditional independence assumptions. Consider two features which are strongly correlated; in fact, imagine that we just add the \\ \n",
       "same feature f1 twice. Naive Bayes will treat both copies of f1 as if they were separate, multiplying them both in, overestimating the evidence. By contrast, logistic regression is much more robust to correlated features; if two features f1 and f2 are perfectly correlated, regression will simply assign part of the weight to w1 and part to w2. Thus when there are many correlated features, logistic regression will assign a more accurate probability than naive Bayes. So logistic regression generally works better on larger documents or datasets and is a common default. Despite the less accurate probabilities, naive Bayes still often makes the correct classification decision. Furthermore, naive Bayes can work extremely well (sometimes even better than logistic regression) on very small datasets or short documents. Furthermore, naive Bayes is easy to implement and very fast to train (there’s no optimization step). So it’s still a reasonable approach to use in some situations.\n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       "\n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       "\n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       "\n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       "\n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       "\n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       "A neural unit is taking a weighted sum of its inputs, with one additional term in the sum called a bias term $z=b+\\sum_{i} w_ix_i$. \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       "Perceptron is a very simple neural unit that has a binary output and does not have a non-linear activation function. XOR is not a linearly separable function. While the XOR function cannot be calculated by a single perceptron, it can be calculated by a layered network of units. \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " A feedforward network is a multilayer network in which the units are connected with no cycles; the outputs from units in each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers. Simple feedforward networks have three kinds of nodes: input units, hidden units, and output units. The core of the neural network is the hidden layer h formed of hidden units hi, each of which is a neural unit. In the standard architecture, each layer is fully-connected, meaning that each unit in each layer takes as input the outputs from all the units in the previous layer, and there is a link between every pair of units from two adjacent layers. Thus each hidden unit sums over all the input units. One of the reasons we use non-linear activation functions for each layer in a neural network is that if we did not, the resulting network is exactly equivalent to a single-layer network. \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       "\n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       "Neural language models represent words in this prior context by their embeddings, rather than just by their word identity as used in n-gram language models. Using embeddings allows neural language models to generalize better to unseen data. Forward inference is the task, given an input, of running a forward pass on the network to produce a probability distribution over possible outputs, in this case next words. A one-hot vector is a vector that has one element equal to 1 — in the dimension corresponding to that word’s index in the vocabulary — while all the other elements are set to zero. \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       "First, we’ll need a loss function that models the distance between the system output and the gold output, and it’s common to use the loss function used for logistic regression, the cross-entropy loss. Second, to find the parameters that minimize this loss function, we’ll use the gradient descent optimization algorithm. Third, gradient descent requires knowing the gradient of the loss function, the vector that contains the partial derivative of the loss function with respect to each of the parameters. How do we partial out the loss over all those intermediate layers? The answer is the algorithm called error backpropagation or backward differentiation. Hard classification task: only one class is the correct one, and that there is one output unit in y for each class. Hence the cross-entropy loss is simply the log of the output probability corresponding to the correct class, and we therefore also call this the negative log likelihood loss. Backwards differentiation makes use of the chain rule in calculus, so let’s remind ourselves of that. Suppose we are computing the derivative of a composite function f(x) = u(v(x)). The derivative of f(x) is the derivative of u(x) with respect to v(x) times the derivative of v(x) with respect to x: $df/dx = du/dv\\cdot dv/dx$. Various forms of regularization are used to prevent overfitting. One of the mostimportant is dropout: randomly dropping some units and their connections from the network during training. Tuning of hyperparameters is also important. The parameters of a neural network are the weights W and biases b; those are learned by gradient descent. The hyperparameters are things that are chosen by the algorithm designer; optimal values are tuned on a devset rather than by gradient descent learning on the training set. Hyperparameters include the learning rate η, the mini-batch size, the model architecture (the number of layers, the number of hidden nodes per layer, the choice of activation functions), how to regularize, and so on. \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       "\n",
       "\n",
       "## Module 13 Lecture Notes\n",
       "Logistic regression solves sentiment classifier task by learning, from a training set, a vector of weights and a bias term. $z=\\sum_iw_ix_i+b$ Can also be written as a dot product: $z=w \\cdot x+b$. Sigmoid function: $y=1/(1+e^{-z})$. Probability: $P(y=1)= \\sigma (w \\cdot x+b)=1/1+e^{-(w \\cdot x+b)}$. Decision boundary: $ \\hat{y} =1 $ if P(y=1|x) > 0.5 or 0 otherwise. How do we get the weights of the model? We learn the parameters (weights + bias) via learning. This requires 2 components: 1. An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss; 2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function. Mean squared error is non convex. Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss. For one observation x, let’s maximize the probability of the correct label $P(y|x)= \\hat{y}^y(1- \\hat{y} )^{1-y}$. If y = 1, then P(y|x) = $\\hat{y}$ (as high as possible). if y = 0, then P(y|x) = 1 - $\\hat{y}$. Changes to logs: $\\log P(y|x)= \\log [\\hat{y}^y(1- \\hat{y} )^{1-y}]=y \\log \\hat{y} +(1-y)\\log (1-\\hat{y} )$. This tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we’ll flip the sign. \\ \n",
       "The result is cross-entropy loss: $L_{CE}(\\hat{y} ,y)=-\\log P(y|x)=-[y\\log \\hat{y} +(1-y)\\log (1-\\hat{y} )]$. Finally, plug in the definition for $\\hat{y} =\\sigma (w\\cdot x)+b$: $L_{CE}(\\hat{y} ,y)=-[y\\log \\sigma (w\\cdot x+b) +(1-y)\\log (1-\\sigma (w\\cdot x+b) )]$. Why does minimizing this negative log probability do what we want? We want the loss to be smaller if the model’s estimate is close to correct, and we want the loss to be bigger if it is confused. For logistic regression, this loss function is conveniently convex. A convex function has just one minimum, so there are no local minima to get stuck in. So gradient descent starting from any point is guaranteed to find the minimum. The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate $\\eta$. The derivative of the cross-entropy loss function of logistic regression for one observation vector x for a single weight $w_j$ is $\\partial {L_{CE}(w,b)} / \\partial {w_j}=[\\sigma (w \\cdot x+b)-y]x_j$. Average loss $Cost(w,b)=1/m \\sum_{i=1}^{m} L_{CE}(\\hat{y} ^{(i)},y^{(i)})=-1/m \\sum_{i=1}^{m} y^{(i)}\\log \\sigma (w \\cdot x^{(i)}+b)+(1-y^{(i)}) \\log (1-\\sigma (w \\cdot x^{(i)}+b))$. This is what we want to minimize. 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. An alternate is batch training, which computes the gradient over the entire dataset. This gives a much better estimate of which direction to move the weights but takes a long time to compute. A commonly used compromise is mini-batch training, where we train on a small batch. The batch size can be 512 or 1024, often selected based on computational resources, so that all examples in the mini-batch can be processed in parallel. The loss is then accumulated. Lasso regression uses L1 regularization. Ridge regression uses L2 regularization. Softmax function will be used for multinomial logistic regression. Multilayer network, all units are usually fully-connected, and no cycles. What do we need to train NN? A loss function – cross-entropy loss. An optimization algorithm – gradient descent. A way of computing the gradient of the loss function – error propagation. \n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       "\n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       "RNN: recurrent neural network. To compute an output yt for an input xt, we need the activation value for the hidden layer ht. To calculate this, we multiply the input xt with the weight matrix W, and the hidden layer from the previous time step ht−1 with the weight matrix U. We add these values together and pass them through a suitable activation function, g, to arrive at the activation value for the current hidden layer, ht. $h_t=g(Uh_{t-1}+Wx_t)$, $y_t=f(Vh_t)$. W = dh x din, U = dh x dh, and V = dout x dh. 3 sets of weights to update: W, the weights from the input layer to the hidden layer, U, the weights from the previous hidden layer to the current hidden layer, and finally V, the weights from the hidden layer to the output layer. Tailoring the backpropagation algorithm to this situation leads to a two-pass algorithm for training the weights in RNNs. In the first pass, we perform forward inference, computing ht, yt, accumulating the loss at each step in time, saving the value of the hidden layer at each step for use at the next time step. In the second phase, we process the sequence in reverse, computing the required gradients as we go, computing and saving the error term for use in the hidden layer for each step backward in time. This general approach is commonly referred to as Backpropagation Through Time. \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       "The input sequence X = [x1;...;xt;...;xN] consists of a series of word embeddings each represented as a one-hot vector of size |V|×1, and the output prediction, y, is a vector representing a probability distribution over the vocabulary. To train an RNN as a language model, we use a corpus of text as training material, having the model predict the next word at each time step t. We train the model to minimize the error in predicting the true next word in the training sequence, using cross-entropy as the loss function. In the case of language modeling, the correct distribution yt comes from knowing the next word. This is represented as a one-hot vector corresponding to the vocabulary where the entry for the actual next word is 1, and all the other entries are 0. Thus, the cross-entropy loss for language modeling is determined by the probability the model assigns to the correct next word. Teacher forcing: always give the model the correct history sequence to predict the next word.\n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       "Semantic field: a set of words which cover a particular semantic domain and bear structured relations with each other. Semantic frame: a set of words that denote perspectives or participants in a particular type of event. \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       "The idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived (in ways we’ll see) from the distributions of word neighbors. \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       "Vector or distributional models of meaning are generally based on a co-occurrence matrix. Information retrieval (IR) is the task of finding the document d from the D documents in some collection that best matches a query q. For documents, we saw that similar documents had similar vectors, because similar documents tend to have similar words. This same principle applies to words: similar words have similar vectors because they tend to occur in similar documents.\n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       "The cosine is based on the dot product operator from linear algebra, also called the inner product. This raw dot product, however, has a problem as a similarity metric: it favors long vectors. We modify the dot product to normalize for the vector length by dividing the dot product by the lengths of each of the two vectors. This normalized dot product turns out to be the same as the cosine of the angle between the two vectors, following from the definition of the dot product between two vectors a and b. \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       "Unlike the vectors, embeddings are short, with number of dimensions d ranging from 50-1000, rather than the much larger vocabulary size |V| or number of documents D we’ve seen. The vectors are dense: instead of vector entries being sparse, mostly-zero counts or functions of counts, the values will be real-valued numbers that can be negative. It turns out that dense vectors work better in every NLP task than sparse vectors. Dense vectors may also do a better job of capturing synonymy. Skip-gram with negative sampling (SGNS) loosely referred to as word2vec. The intuition of word2vec is that instead of counting how often each word w occurs near, say, apricot, we’ll instead train a classifier on a binary prediction task: “Is word w likely to show up near apricot?” We don’t actually care about this prediction task; instead we’ll take the learned classifier weights as the word embeddings. word2vec is a much simpler model than the neural network language model, in two ways. First, word2vec simplifies the task (making it binary classification instead of word prediction). Second, word2vec simplifies the architecture (training a logistic regression classifier instead of a multi-layer neural network with hidden layers that demand more sophisticated training algorithms). The intuition of the skipgram model is to base this probability on embedding similarity: a word is likely to occur near the target if its embedding vector is similar to the target embedding.\n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       "Different types of similarity or association: One parameter of vector semantic models that is relevant to both sparse tf-idf vectors and dense word2vec vectors is the size of the context window used to collect counts. This is generally between 1 and 10 words on each side of the target word (for a total context of 2-20 words). Analogy/Relational Similarity: Another semantic property of embeddings is their ability to capture relational meanings.\n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       "In addition to their ability to learn word meaning from text, embeddings, alas, also reproduce the implicit biases and stereotypes that were latent in the text. It turns out that embeddings don’t just reflect the statistics of their input, but also amplify bias. \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       "\n",
       "\n",
       "## Module 14 Lecture Notes\n",
       "Documents creatd by term-by-document or term-context matrices are long and sparse. Alternative: short and dense vactors. Why? Short vectors may be easier to use as features. Dense vectors may generalize better than storing explicit counts. Do better at capturing synonymy. Word2vec: Skip-Gram Task. \n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Embeddings** - vectors for representing words\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Template_for CIS521_midterm_2_notes.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
