{
 "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": "54580f1e-22eb-4657-8e14-104a615b6276"
   },
   "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": "2cd4c8a2-805b-483a-8fae-409ce38e0560"
   },
   "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 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
    "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
    "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
    "chapter17_1 = r\"\"\" **Nonstationary policy** depends on time. **Proper policy** guaranteed to reach a terminal state. Optimal policy is independent of starting state if using discounted \\\n",
    "utilities with infinite horizons. **Q-function** is action-utility function, or expected utility of taking a given action from a state. Table representation of MDP T and R is with 3D table \\\n",
    "of size $|S|^2|A|$, but most tables are sparse since only some states can be reached from any state, so table size is $O(|S||A|)$. **Contraction** is concept that shows value iteration \\\n",
    "converges (Bellman update is contraction by factor of $\\gamma$ on space of utility vectors); value iteration converges exponntially fast. **Modified policy iteration**: simplified value \\\n",
    "iteration steps with fixed policy (not exact policy evaluation, but good approx). **Asynchronous policy iteration** doesn't update utility/policy for all states at once, and can apply \\\n",
    "either policy improvement or simplified value iteration on subsets of states. \"\"\"\n",
    "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module8_lecture_notes = r\"\"\" Stochastic environment with probabilistic transition model. **MDP**: sequential decision problem for fully observable enviro, stochastic transition model, \\\n",
    "additive rewards (non-deterministic search problems, can use expectimax); require state/action sets, transition/reward function, initial state, optional terminal state(s). **Policy**: \\\n",
    "maps action to take at state. $\\pi^{*} (s) = a$ is optimal policy. **Environment history**: sequence of past states/actions. **Absorbing state**: terminal state guaranteed to eventually be reached \\\n",
    "for every policy. **Optimal quantities**: V\\*(s) = exp. utility starting in s moving optimally; Q\\*(s,a) = exp. utility taking action a from s and moving optimally from there; pi\\*(s) = \\\n",
    "optimal action from s. **Recursive value definition/Bellman equations**: $V^*(s) = \\text{max}_a Q^*(s, a)$ // $Q^*(s,a) = \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$. **Time-limited values**: optimal $V_k(s)$ based on \\\n",
    "gamme ending in k more steps. **Value iteration**: $V_{k+1}(s) = \\text{max}_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ (do one ply of expectimax from each state given vector of $v_k(s)$ \\\n",
    "values then repeat until convergence), Bellman update, propagate info through state space by means of local updates. Complexity of each iteration is $O(S^2A)$. Bellman gives optimal utility using one step lookahead. **Policy evaluation**: calculate Vs for fixed policy \\\n",
    "by turning recursive Bellman equations into updates with $O(S^2)$ per iteration; becomes linear system without maxes. **Policy extraction**: do one step expectimax if have optimal values to \\\n",
    "find policy implied by values $\\pi^*(s) = \\text{argmax}_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$; if you have optimal q-values, then very easy (pick policy with max Q\\*). **Policy \\\n",
    "Iteration**: policy evaluation (calculate utilities for fixed policy to convergence) then policy improvement (update policy with resulting converged utilities as future values) the repeat \\\n",
    "until policy converges. Optimal and can converge faster. \"\"\"\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\" : \"reward function, either +/- but bounded by max value\",\n",
    "\"expected utility\" : \"probability weighted utility\",\n",
    "\"Markovian\": \"probability of arriving in state only depends on current state and not history\",\n",
    "\"Principle of MEU\" : \"rational agent should choose action that max expected utility, given its knowledge\"\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": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "gYYeNcdM_maE",
    "outputId": "fd8e2758-e608-422b-905e-dd265249d5ae"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       " **Nonstationary policy** depends on time. **Proper policy** guaranteed to reach a terminal state. Optimal policy is independent of starting state if using discounted \\\n",
       "utilities with infinite horizons. **Q-function** is action-utility function, or expected utility of taking a given action from a state. Table representation of MDP T and R is with 3D table \\\n",
       "of size $|S|^2|A|$, but most tables are sparse since only some states can be reached from any state, so table size is $O(|S||A|)$. **Contraction** is concept that shows value iteration \\\n",
       "converges (Bellman update is contraction by factor of $\\gamma$ on space of utility vectors); value iteration converges exponntially fast. **Modified policy iteration**: simplified value \\\n",
       "iteration steps with fixed policy (not exact policy evaluation, but good approx). **Asynchronous policy iteration** doesn't update utility/policy for all states at once, and can apply \\\n",
       "either policy improvement or simplified value iteration on subsets of states. \n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       " Your summary here \n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " Stochastic environment with probabilistic transition model. **MDP**: sequential decision problem for fully observable enviro, stochastic transition model, \\\n",
       "additive rewards (non-deterministic search problems, can use expectimax); require state/action sets, transition/reward function, initial state, optional terminal state(s). **Policy**: \\\n",
       "maps action to take at state. $\\pi^{*} (s) = a$ is optimal policy. **Environment history**: sequence of past states/actions. **Absorbing state**: terminal state guaranteed to eventually be reached \\\n",
       "for every policy. **Optimal quantities**: V\\*(s) = exp. utility starting in s moving optimally; Q\\*(s,a) = exp. utility taking action a from s and moving optimally from there; pi\\*(s) = \\\n",
       "optimal action from s. **Recursive value definition/Bellman equations**: $V^*(s) = \\text{max}_a Q^*(s, a)$ // $Q^*(s,a) = \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$. **Time-limited values**: optimal $V_k(s)$ based on \\\n",
       "gamme ending in k more steps. **Value iteration**: $V_{k+1}(s) = \\text{max}_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ (do one ply of expectimax from each state given vector of $v_k(s)$ \\\n",
       "values then repeat until convergence), Bellman update, propagate info through state space by means of local updates. Complexity of each iteration is $O(S^2A)$. Bellman gives optimal utility using one step lookahead. **Policy evaluation**: calculate Vs for fixed policy \\\n",
       "by turning recursive Bellman equations into updates with $O(S^2)$ per iteration; becomes linear system without maxes. **Policy extraction**: do one step expectimax if have optimal values to \\\n",
       "find policy implied by values $\\pi^*(s) = \\text{argmax}_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$; if you have optimal q-values, then very easy (pick policy with max Q\\*). **Policy \\\n",
       "Iteration**: policy evaluation (calculate utilities for fixed policy to convergence) then policy improvement (update policy with resulting converged utilities as future values) the repeat \\\n",
       "until policy converges. Optimal and can converge faster. \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Utility function** - reward function, either +/- but bounded by max value\n",
       "* **Expected utility** - probability weighted utility\n",
       "* **Markovian** - probability of arriving in state only depends on current state and not history\n",
       "* **Principle of meu** - rational agent should choose action that max expected utility, given its knowledge\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-armed bandit** is slot machine with n levers. **Exploitation vs. exploration**: exploit current best action or try unknown states to gain info. **Bandit problems** \\\n",
    "have each arm a MDP with only 1 action, and the overall bandit problem is an MDP (arms are independent). **Exploration bonus** for arms that have only been tried a few times. Selection problem \\\n",
    "makes good decision as fast as possible, doesn't have to minimize failures. **Bandit superprocess* has each arm as full MDP (not restricted to one action). \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
    "chapter22_1 =  \"\"\" **Supervised learning**: passively observing example input/output provided by teacher. **Sparse rewards** give only reward signal in a few states. \"\"\"\n",
    "chapter22_2 =  \"\"\" **Direct utility estimation**: utility of state defined as expected total reward from the state onward (or **reward-to-go**), and each trial is a sample of this for each \\\n",
    "state visited. **Adaptive dynamic programming (ADP)**: takes advantage of constraints among utilities of states by learning transition model that connects them, then solving MDP (utilizes \\\n",
    "the Bellman equation). Passive TD learner learns slower than ADP and more variability, but simpler and less computation per observation. TD does not need transition model to do updates. \\\n",
    "ADP can be made more efficient with approx, using heuristics like prioritized sweeping heuristic that prefers adjustments to states whose likely successors just had a large adjustment in \\\n",
    "their own utility. \"\"\"\n",
    "chapter22_3 =  \"\"\" Active reinforcement learners should be greedy in the limit of infinite exploitation. **Exploration function** determines how greed (preference for high values for utility) \\\n",
    "trades off with curiosity (actions that haven't been tried frequently), used to calculate optimistic utility/value; rapidly converges to 0 policy loss. \"\"\"\n",
    "chapter22_4 =  \"\"\"  \"\"\"\n",
    "chapter22_5 =  \"\"\" Policy search: keep changing policy until performance stops improving. Uses stochastic probability representaiton of likelihood of selecting an action with softmax. \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module9_lecture_notes = r\"\"\" Offline planning: solve MDPs through computations but not playing. **Recursive learning**: learn to max expected rewards by receiving feedback via rewards; \\\n",
    "agent utility defined by reward function; still MDP but to solve (looking for policy) but don't know T or R. MDPs are offline solutions whereas RL is online learning. **Model-based \\\n",
    "learning**: approx model based on experiences; learn empirical MDP (count s' by testing action a from s multiple times to estimate T and R) then solve learned MDP (i.e. value iteration). \\\n",
    "**Model-free learning.** doesn't know or learns the transition model. **Passive reinforcement learning**: policy evaluation (fixed policy) but don't know T and R, execute policy and learn from experience. Direct evaluation: compute values under pi, \\\n",
    "average observed values for each state. Temporal difference learning: allows us to do policy evaluation by updating V(s) after each transition with exponential moving average \\\n",
    "$V^{\\pi}(s) = (1-\\alpha)V^{\\pi}(s) + (\\alpha)sample$, where sample is $R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')$. **Active reinforcement learning**: learn optimal policies (like value \\\n",
    "iteration) with explore/exploit tradeoff. Q-value iteration: $Q_{k+1}(s,a) = \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma \\text{max}_a' Q_{k}(s',a')]$; use Q-learning for active RL \\\n",
    "$Q(s,a) = (1-\\alpha)Q(s,a) + (\\alpha)sample$, where sample is $R(s,\\pi(s),s') + \\gamma \\text{max}_a' Q_{k}(s',a')$. Off-policy learning: Q-learning converges to optimal policy \\\n",
    "even if act suboptimally. **Exploration function**: explore areas that are not yet established (instead of random); modified Q-update $Q(s,a) = (1-\\alpha)Q(s,a) + (\\alpha)R(s,\\pi(s),s') + \\gamma \\text{max}_a' f(Q_{k}(s',a'), N(s',a'))$ \\\n",
    "where $f(u, n) = u + k/n$ returns an optimistic utility that provides higher bump to less visited (lower n) states. **Regret**: measure of total mistake cost (expected minus optimal rewards). \\\n",
    "**Approximate Q-learning**: adjust weights of active features, adjust weight by adding alpha \\* difference between new Q and old Q \\* feature (from need to generalize to new states instead of holding everything in memory; \\\n",
    "representing states as feature representation with weights). \"\"\"\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module9_definitions = {\n",
    "\"exploration\" : \"try unknown actions to get info\",\n",
    "\"exploitation\" : \"use what you do know\",\n",
    "\"regret\" : \"still make mistakes even if learn intelligently\",\n",
    "\"sampling\" : \"try things repeatedly because of chance\",\n",
    "\"difficulty\" : \"learning can be much harder than solving known MDP\",\n",
    "\"off-policy learning\" : \"Q-learning converges to optimal policy even if starting with suboptimal policy\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "ydOK__lwWgdp",
    "outputId": "f4485a5e-3b5c-4f62-a66e-678d2b9dd083"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       " **N-armed bandit** is slot machine with n levers. **Exploitation vs. exploration**: exploit current best action or try unknown states to gain info. **Bandit problems** have each arm a MDP with only 1 action, and the overall bandit problem is an MDP (arms are independent). **Exploration bonus** for arms that have only been tried a few times. Selection problem makes good decision as fast as possible, doesn't have to minimize failures. **Bandit superprocess* has each arm as full MDP (not restricted to one action). \n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       " **Supervised learning**: passively observing example input/output provided by teacher. **Sparse rewards** give only reward signal in a few states. \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       " **Direct utility estimation**: utility of state defined as expected total reward from the state onward (or **reward-to-go**), and each trial is a sample of this for each state visited. **Adaptive dynamic programming (ADP)**: takes advantage of constraints among utilities of states by learning transition model that connects them, then solving MDP (utilizes the Bellman equation). Passive TD learner learns slower than ADP and more variability, but simpler and less computation per observation. TD does not need transition model to do updates. ADP can be made more efficient with approx, using heuristics like prioritized sweeping heuristic that prefers adjustments to states whose likely successors just had a large adjustment in their own utility. \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       " Active reinforcement learners should be greedy in the limit of infinite exploitation. **Exploration function** determines how greed (preference for high values for utility) trades off with curiosity (actions that haven't been tried frequently), used to calculate optimistic utility/value; rapidly converges to 0 policy loss. \n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       "  \n",
       "\n",
       "## Module 9 Lecture Notes\n",
       " Offline planning: solve MDPs through computations but not playing. **Recursive learning**: learn to max expected rewards by receiving feedback via rewards; \\\n",
       "agent utility defined by reward function; still MDP but to solve (looking for policy) but don't know T or R. MDPs are offline solutions whereas RL is online learning. **Model-based \\\n",
       "learning**: approx model based on experiences; learn empirical MDP (count s' by testing action a from s multiple times to estimate T and R) then solve learned MDP (i.e. value iteration). \\\n",
       "**Model-free learning.** doesn't know or learns the transition model. **Passive reinforcement learning**: policy evaluation (fixed policy) but don't know T and R, execute policy and learn from experience. Direct evaluation: compute values under pi, \\\n",
       "average observed values for each state. Temporal difference learning: allows us to do policy evaluation by updating V(s) after each transition with exponential moving average \\\n",
       "$V^{\\pi}(s) = (1-\\alpha)V^{\\pi}(s) + (\\alpha)sample$, where sample is $R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')$. **Active reinforcement learning**: learn optimal policies (like value \\\n",
       "iteration) with explore/exploit tradeoff. Q-value iteration: $Q_{k+1}(s,a) = \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma \\text{max}_a' Q_{k}(s',a')]$; use Q-learning for active RL \\\n",
       "$Q(s,a) = (1-\\alpha)Q(s,a) + (\\alpha)sample$, where sample is $R(s,\\pi(s),s') + \\gamma \\text{max}_a' Q_{k}(s',a')$. Off-policy learning: Q-learning converges to optimal policy \\\n",
       "even if act suboptimally. **Exploration function**: explore areas that are not yet established (instead of random); modified Q-update $Q(s,a) = (1-\\alpha)Q(s,a) + (\\alpha)R(s,\\pi(s),s') + \\gamma \\text{max}_a' f(Q_{k}(s',a'), N(s',a'))$ \\\n",
       "where $f(u, n) = u + k/n$ returns an optimistic utility that provides higher bump to less visited (lower n) states. **Regret**: measure of total mistake cost (expected minus optimal rewards). \\\n",
       "**Approximate Q-learning**: adjust weights of active features, adjust weight by adding alpha \\* difference between new Q and old Q \\* feature (from need to generalize to new states instead of holding everything in memory; \\\n",
       "representing states as feature representation with weights). \n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Exploration** - try unknown actions to get info\n",
       "* **Exploitation** - use what you do know\n",
       "* **Regret** - still make mistakes even if learn intelligently\n",
       "* **Sampling** - try things repeatedly because of chance\n",
       "* **Difficulty** - learning can be much harder than solving known MDP\n",
       "* **Off-policy learning** - Q-learning converges to optimal policy even if starting with suboptimal policy\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": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
    "chapter12_1 = \"\"\"  \"\"\"\n",
    "chapter12_2 = \"\"\" **Joint probability distribution**: all combinations of values of two variables. \"\"\"\n",
    "chapter12_3 = \"\"\" **Marginal probability**: summing out for each possible value of other variables to remove them from the equation. \"\"\"\n",
    "chapter12_4 = \"\"\"  \"\"\"\n",
    "chapter12_5 = \"\"\"  \"\"\"\n",
    "chapter12_6 = r\"\"\" **Naive Bayes Model**: $P(cause, effect,...) = P(cause)\\prod_i P(effect_i | cause)$. Naive means that it uses simplifying assumption that effects are independent \\\n",
    "given the cause. For each cause, multiply prior probability of cause by product of conditional probabilities of observed effects given the cause, then normalize. Runtime is linear on \\\n",
    "number of effects. \"\"\"\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 = r\"\"\" **N-gram MLE normalization**: $P(w_n|w_{n-1})=\\frac{C(w_{n-1}w_{n})}{\\sum_w C(w_{n-1}w)}$; all times the n-gram appears divided by all times the given context appears, \\\n",
    "called relative frequency. Probability of sentence is just product of n-grams. Add probabilities in log space rather than multiply in linear space to reduce underflow risk. \"\"\"\n",
    "SLP_chapter3_2 = r\"\"\" Extrinsic evaluation: embed LM in application and see how it improves. Intrinsic evaluation: measures quality of model independent of any application. Use **perplexity** \\\n",
    "to evaluate LM: inverse probability of test set, normalized by number of words. For test set $W = w_1, w_2,...,w_N$, $PP(W)=\\sqrt[N]{\\prod_{i=0}^N \\frac{1}{P(w_i|w_1...w_{i-1})}}$; for \\\n",
    "bigram, it is $PP(W)=\\sqrt[N]{\\prod_{i=0}^N \\frac{1}{P(w_i|w_{i-1})}}$. Higher conditional probability of sequence, lower the perplexity -- minimize perplexity is maximize test set prob. \\\n",
    "Perplexity is also weighted average branching factor (how many words can come after the current word). \"\"\"\n",
    "SLP_chapter3_3 = \"\"\" Sparsity: some n-grams appear limited to no times in corpus. \"\"\"\n",
    "SLP_chapter3_4 = r\"\"\" **Laplace smoothing**: add one to all counts $P(w_i)=\\frac{c_i+1}{N+V}$. **Add-k smoothing** adds some number k instead of one $P(w_i)=\\frac{c_i+k}{N+kV}$. \\\n",
    "**Backoff**: go to lower order n-gram if zero evidence for higher order. **Interpolation**: mix prob estimates from all n-gram estimators, weight using some parameter alpha. **Discounting** higher frequency words and \\\n",
    "provide probability to never seen words. **Kneser-Ney discounting**: uses unigram distribution for new words based on how likely a word is to appear in a novel continuation (depending on \\\n",
    "how many contexts it has appeared in). \"\"\"\n",
    "SLP_chapter3_5 = \"\"\"  \"\"\"\n",
    "SLP_chapter3_7 = \"\"\" Lower cross-entropy is more accurate. Perplexity is exponent function of cross-entropy. \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module10_lecture_notes = r\"\"\" **Conditional probability**: P(a|b) = P(a,b)/P(b). **Product rule**: P(y)P(x|y)=P(x,y). **Chain rule**: write joint distribution as incremental product of \\\n",
    "conditional distributions. **Bayes rule**: P(x|y) = P(y|x)P(x)/P(y). **Probability Language Models**: **Markov assumption**: P(word|k last words), only depends on k last words, not \\\n",
    "entire context. Estimating bigram probabilities using MLE $P(w_i | w_{i-1})=\\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$. Problem with MLE is zeros (may have something in test that you \\\n",
    "haven't seen in train) - doing things in log space solves this and is faster. \"\"\"\n",
    "\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module10_definitions = {\n",
    "\"language model\" : \"models that assign prob to sequence of words\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "9a64474d-4752-4715-d5ec-d917350b41de"
   },
   "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",
       " **Joint probability distribution**: all combinations of values of two variables. \n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       " **Marginal probability**: summing out for each possible value of other variables to remove them from the equation. \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",
       " **Naive Bayes Model**: $P(cause, effect,...) = P(cause)\\prod_i P(effect_i | cause)$. Naive means that it uses simplifying assumption that effects are independent \\\n",
       "given the cause. For each cause, multiply prior probability of cause by product of conditional probabilities of observed effects given the cause, then normalize. Runtime is linear on \\\n",
       "number of effects. \n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       "  \n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       " **N-gram MLE normalization**: $P(w_n|w_{n-1})=\\frac{C(w_{n-1}w_{n})}{\\sum_w C(w_{n-1}w)}$; all times the n-gram appears divided by all times the given context appears, \\\n",
       "called relative frequency. Probability of sentence is just product of n-grams. Add probabilities in log space rather than multiply in linear space to reduce underflow risk. \n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       " Extrinsic evaluation: embed LM in application and see how it improves. Intrinsic evaluation: measures quality of model independent of any application. Use **perplexity** \\\n",
       "to evaluate LM: inverse probability of test set, normalized by number of words. For test set $W = w_1, w_2,...,w_N$, $PP(W)=\\sqrt[N]{\\prod_{i=0}^N \\frac{1}{P(w_i|w_1...w_{i-1})}}$; for \\\n",
       "bigram, it is $PP(W)=\\sqrt[N]{\\prod_{i=0}^N \\frac{1}{P(w_i|w_{i-1})}}$. Higher conditional probability of sequence, lower the perplexity -- minimize perplexity is maximize test set prob. \\\n",
       "Perplexity is also weighted average branching factor (how many words can come after the current word). \n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       " Sparsity: some n-grams appear limited to no times in corpus. \n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       " **Laplace smoothing**: add one to all counts $P(w_i)=\\frac{c_i+1}{N+V}$. **Add-k smoothing** adds some number k instead of one $P(w_i)=\\frac{c_i+k}{N+kV}$. \\\n",
       "**Backoff**: go to lower order n-gram if zero evidence for higher order. **Interpolation**: mix prob estimates from all n-gram estimators, weight using some parameter alpha. **Discounting** higher frequency words and \\\n",
       "provide probability to never seen words. **Kneser-Ney discounting**: uses unigram distribution for new words based on how likely a word is to appear in a novel continuation (depending on \\\n",
       "how many contexts it has appeared in). \n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       "  \n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       " Lower cross-entropy is more accurate. Perplexity is exponent function of cross-entropy. \n",
       "\n",
       "## Module 10 Lecture Notes\n",
       " **Conditional probability**: P(a|b) = P(a,b)/P(b). **Product rule**: P(y)P(x|y)=P(x,y). **Chain rule**: write joint distribution as incremental product of \\\n",
       "conditional distributions. **Bayes rule**: P(x|y) = P(y|x)P(x)/P(y). **Probability Language Models**: **Markov assumption**: P(word|k last words), only depends on k last words, not \\\n",
       "entire context. Estimating bigram probabilities using MLE $P(w_i | w_{i-1})=\\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$. Problem with MLE is zeros (may have something in test that you \\\n",
       "haven't seen in train) - doing things in log space solves this and is faster. \n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Language model** - models that assign prob to sequence of 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",
    "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 = \"\"\" **Bayes' Net**: DAG, each node is random variable with probability info that quantifies the effect of parents on the node using finite number of parameters. \"\"\"\n",
    "chapter13_2 = r\"\"\" Syntax: a directed acyclic graph with some local probability information attached to each node. Semantics: defines how the syntax corresponds to a joint distribution \\\n",
    "over the variables of the network. Joint distribution: $P(x_1,...,x_n)=\\prod_{i=1}^n \\theta (x_i | parents(X_i))$; each entry in joint distribution is product of local conditional \\\n",
    "distributions. **Locally structured/sparse systems**: each subcomponent intercts directly with a limited number of other components (associated with linear growth). Causal better than \\\n",
    "diagnostic: having to specify fewer numbers, and numbers will often be easier to come up with. **Each variable is conditionally indep. on its non-descendants, given parents.** \\\n",
    "**Markov blanket**: variable is conditionally indep. of all other nodes in network, given its parents, children, and children's parents. \"\"\"\n",
    "chapter13_3 = \"\"\" **Inference by enumeration**: solving for conditional prob by summing up terms from full joint distribution. **Variable elimination algo**: improves upon exponential \\\n",
    "enumeration algo by using dynamic programming to do calculations once and save for later. Clustering: join individual nodes to form meganodes. \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module11_lecture_notes = \"\"\" Independence allows compacting probability outcomes table from $2^n$ to $2n$. Conditional independence if two probabilities are independent given another event \\\n",
    "[if D is conditionally independent of T given C, then P(D | T, C) = P(D | C), P(T | D, C) = P(T | C), P(T, D | C) = P(T | C) * P(D | C)]. Unconditional (absolute) independence is rare and \\\n",
    "it doesn't help make inferences about other variables, whereas conditional independence is basic/robust form of knowledge about uncertain environments. Two big problems with full joint \\\n",
    "probability tables: 1) too big unless few variables and 2) hard to learn/estimate anything empirically about more than a couple varaibles at a time. **Bayes' Nets/graphical models** is a technique that \\\n",
    "can describe complex joint distributions (models) using simple local distributions (conditional probabilities). Nodes are variables with domains (either assigned/observed or unassigned), \\\n",
    "arcs are interactions that encode \"direct influence\", and two variables are conditionally independent if no arc but both have arcs to a variable. Bayes' Net is set of nodes for each variable \\\n",
    "that is a directed, acyclic graph with a conditional distribution for each node (topology/graph + local conditional probabilities). Joint distributions implicitly encoded as product of \\\n",
    "local conditional distributions. Usually want to reflect causal relationships because easier and simpler (but can just be correlation). Joint distribution over N boolean variables is \\\n",
    "$O(2^N)$; N-node net if nodes have up to k parents is $O(N*2^{k+1})$ (huge space saving). **D-separation** algorithm based on triples of variables. Causal chain is x -> y -> z: x is not \\\n",
    "guaranteed independent of z, but is conditionally independent given y. Common cause is y -> x, y -> z: x is not guaranted independent of z, but is conditionally independent given y. \\\n",
    "Common effect is x -> z, y -> z; x is independent of y, but x and y are not conditionally independent given z. If all paths are inactive (have an observed variable in middle of path), \\\n",
    "then independence guaranteed; else, not guaranteed. \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module11_definitions = {\n",
    "\"Conditional independence\" : \"x is conditionally independent of Y given Z iff $\\\\forall x, y, z : P(x, y|z) = P(x|z)P(y|z)$ or $P(x|z,y) = P(x|z)$\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "bd3a48f6-6420-4414-f373-d5d9964d7270"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       " **Bayes' Net**: DAG, each node is random variable with probability info that quantifies the effect of parents on the node using finite number of parameters. \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       " Syntax: a directed acyclic graph with some local probability information attached to each node. Semantics: defines how the syntax corresponds to a joint distribution \\\n",
       "over the variables of the network. Joint distribution: $P(x_1,...,x_n)=\\prod_{i=1}^n \\theta (x_i | parents(X_i))$; each entry in joint distribution is product of local conditional \\\n",
       "distributions. **Locally structured/sparse systems**: each subcomponent intercts directly with a limited number of other components (associated with linear growth). Causal better than \\\n",
       "diagnostic: having to specify fewer numbers, and numbers will often be easier to come up with. **Each variable is conditionally indep. on its non-descendants, given parents.** \\\n",
       "**Markov blanket**: variable is conditionally indep. of all other nodes in network, given its parents, children, and children's parents. \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       " **Inference by enumeration**: solving for conditional prob by summing up terms from full joint distribution. **Variable elimination algo**: improves upon exponential enumeration algo by using dynamic programming to do calculations once and save for later. Clustering: join individual nodes to form meganodes. \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       " Independence allows compacting probability outcomes table from $2^n$ to $2n$. Conditional independence if two probabilities are independent given another event [if D is conditionally independent of T given C, then P(D | T, C) = P(D | C), P(T | D, C) = P(T | C), P(T, D | C) = P(T | C) * P(D | C)]. Unconditional (absolute) independence is rare and it doesn't help make inferences about other variables, whereas conditional independence is basic/robust form of knowledge about uncertain environments. Two big problems with full joint probability tables: 1) too big unless few variables and 2) hard to learn/estimate anything empirically about more than a couple varaibles at a time. **Bayes' Nets/graphical models** is a technique that can describe complex joint distributions (models) using simple local distributions (conditional probabilities). Nodes are variables with domains (either assigned/observed or unassigned), arcs are interactions that encode \"direct influence\", and two variables are conditionally independent if no arc but both have arcs to a variable. Bayes' Net is set of nodes for each variable that is a directed, acyclic graph with a conditional distribution for each node (topology/graph + local conditional probabilities). Joint distributions implicitly encoded as product of local conditional distributions. Usually want to reflect causal relationships because easier and simpler (but can just be correlation). Joint distribution over N boolean variables is $O(2^N)$; N-node net if nodes have up to k parents is $O(N*2^{k+1})$ (huge space saving). **D-separation** algorithm based on triples of variables. Causal chain is x -> y -> z: x is not guaranteed independent of z, but is conditionally independent given y. Common cause is y -> x, y -> z: x is not guaranted independent of z, but is conditionally independent given y. Common effect is x -> z, y -> z; x is independent of y, but x and y are not conditionally independent given z. If all paths are inactive (have an observed variable in middle of path), then independence guaranteed; else, not guaranteed. \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Conditional independence** - x is conditionally independent of Y given Z iff $\\forall x, y, z : P(x, y|z) = P(x|z)P(y|z)$ or $P(x|z,y) = P(x|z)$\n"
      ],
      "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 = \"\"\"  \"\"\"\n",
    "chapter19_2 = \"\"\" Bias: tendency of predictive hypothesis to deviate from expected value over many training sets. Bias-variance tradeoff: choice between complex/low-bias hypotheses that \\\n",
    "fit training data vs. simpler/low-variance hypotheses that generalize better. \"\"\"\n",
    "chapter19_3 = \"\"\" **Entropy**: notion of info gain; more info, less entropy. \"\"\"\n",
    "chapter19_4 = \"\"\" Hyperparameters: parameters on model class, not individual model. Loss function: identify whether FP or FN are worse. \"\"\"\n",
    "chapter19_5 = \"\"\"  \"\"\"\n",
    "chapter19_6 = r\"\"\" Loss function is convex for linear regression. **Gradient descent** looks to minimize loss by using parameter $\\alpha$ (step size / learning rate) to move downhill \\\n",
    "toward local min loss. $\\alpha$ is either fixed or decays with time. Stochastic gradient descent randomly selects small number of training samples at each step and updates. **Decision \\\n",
    "boundary**: line/surface that separates two classes. **Perceptron learning rule**: if output correct, then weights unchanged; otherwise, weights are increased if actual is 1 and predicted \\\n",
    "is 0 and vice versa. \"\"\"\n",
    "\n",
    "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
    "slp_chapter4_1 = r\"\"\" Generative classifiers (naive Bayes) build model of how a class could generate some input data; discrimitive classifiers (logit) return what features from input are most \\\n",
    "telling of classification. **Bag of words**: representation of text as unordered set of words (position ignored), keeping only frequency. **Naive Bayes** is probabilistic classifier that \\\n",
    "returns class which has max posterior prob given the text doc $\\hat{c}=\\text{argmax}_{c \\in C} P(c|d)$. Since document stays the same, we can drop Bayes denominator to choose class that \\\n",
    "maximizes $\\hat{c}=\\text{argmax}_{c \\in C} P(d|c)P(c)$ -- choose class with highest product of likelihood of document given class and prior probability of class, where doc can be represented \\\n",
    "as set of features that are naively assumed to be conditionally independent given c. Linear function of input features in log space. \"\"\"\n",
    "slp_chapter4_2 = r\"\"\" To find prior, divide frequency of docs in training data with class c by total number of docs. Assume features is just existence of word in doc's bag of words, \\\n",
    "so $P(f_i|c)=P(w_i|c)=\\frac{count(w_i,c)}{\\sum_{w \\in V} count(w,c)}$, or number of times word appears in all docs with topic c divided by all words in all docs with topic c (can use \\\n",
    "Laplace smoothing). Drop unknown words in test data. \"\"\"\n",
    "slp_chapter4_3 = \"\"\"  \"\"\"\n",
    "slp_chapter4_4 = \"\"\" Binary NB clips word count to 1 for each document (does the word exist in the doc or not). Deal with negation by prepending NOT_ to words after a negative token until \\\n",
    "next punctuation. \"\"\"\n",
    "slp_chapter4_5 = \"\"\"  \"\"\"\n",
    "slp_chapter4_6 = r\"\"\" Find probabilty of sentence by multiplying $P(w|sentiment)$ for all words (this is just likelihood of NB, would still need to multiply by prior). \"\"\"\n",
    "slp_chapter4_7 = \"\"\" F1 score is 2PR / (P + R). \"\"\"\n",
    "slp_chapter4_8 = \"\"\"  \"\"\"\n",
    "slp_chapter4_9 = \"\"\"  \"\"\"\n",
    "slp_chapter4_10 = \"\"\"  \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module12_lecture_notes = r\"\"\" General Naive Bayes: $P(Y, F_1, F_2,...,F_n) = P(Y) \\prod_i P(F_i|Y)$; total parameters is linear in number of features. **Binary perceptron**: if true class \\\n",
    "is positive but predicted negative, then add feature vector to weight; if true class is negative but predicted positive, then subtract feature vector from weight. **Multiclass perceptron**: has weight vector for each label; classify \\\n",
    "based on highest dot product. If classification is wrong, then update weight vector for correct one by adding feature vector to weight vector, then update incorrect one by subtracting \\\n",
    "feature vector from it (bias is always 1 for feature vector). Perceptron will converge if perfectably linearly separable. **MIRA update** scale down the update. **SVM** maximizes margin to \\\n",
    "create best separation plane. Mapping data to higher-dimension could make linearly separable. \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module12_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "e5ae05c7-5d3d-4021-cf22-44b528348fca"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 19.1 Forms of Learning\n",
       "  \n",
       "\n",
       "## AIMA Chapter 19.2 Supervised Learning\n",
       " Bias: tendency of predictive hypothesis to deviate from expected value over many training sets. Bias-variance tradeoff: choice between complex/low-bias hypotheses that fit training data vs. simpler/low-variance hypotheses that generalize better. \n",
       "\n",
       "## AIMA Chapter 19.3 Learning Decision Trees\n",
       " **Entropy**: notion of info gain; more info, less entropy. \n",
       "\n",
       "## AIMA Chapter 19.4 Model Selection and Optimization\n",
       " Hyperparameters: parameters on model class, not individual model. Loss function: identify whether FP or FN are worse. \n",
       "\n",
       "## AIMA Chapter 19.5 The Theory of Learning\n",
       "  \n",
       "\n",
       "## AIMA Chapter 19.6 Linear Regression and Classification\n",
       " Loss function is convex for linear regression. **Gradient descent** looks to minimize loss by using parameter $\\alpha$ (step size / learning rate) to move downhill \\\n",
       "toward local min loss. $\\alpha$ is either fixed or decays with time. Stochastic gradient descent randomly selects small number of training samples at each step and updates. **Decision \\\n",
       "boundary**: line/surface that separates two classes. **Perceptron learning rule**: if output correct, then weights unchanged; otherwise, weights are increased if actual is 1 and predicted \\\n",
       "is 0 and vice versa. \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Generative classifiers (naive Bayes) build model of how a class could generate some input data; discrimitive classifiers (logit) return what features from input are most \\\n",
       "telling of classification. **Bag of words**: representation of text as unordered set of words (position ignored), keeping only frequency. **Naive Bayes** is probabilistic classifier that \\\n",
       "returns class which has max posterior prob given the text doc $\\hat{c}=\\text{argmax}_{c \\in C} P(c|d)$. Since document stays the same, we can drop Bayes denominator to choose class that \\\n",
       "maximizes $\\hat{c}=\\text{argmax}_{c \\in C} P(d|c)P(c)$ -- choose class with highest product of likelihood of document given class and prior probability of class, where doc can be represented \\\n",
       "as set of features that are naively assumed to be conditionally independent given c. Linear function of input features in log space. \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " To find prior, divide frequency of docs in training data with class c by total number of docs. Assume features is just existence of word in doc's bag of words, \\\n",
       "so $P(f_i|c)=P(w_i|c)=\\frac{count(w_i,c)}{\\sum_{w \\in V} count(w,c)}$, or number of times word appears in all docs with topic c divided by all words in all docs with topic c (can use \\\n",
       "Laplace smoothing). Drop unknown words in test data. \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       "  \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Binary NB clips word count to 1 for each document (does the word exist in the doc or not). Deal with negation by prepending NOT_ to words after a negative token until next punctuation. \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",
       " Find probabilty of sentence by multiplying $P(w|sentiment)$ for all words (this is just likelihood of NB, would still need to multiply by prior). \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " F1 score is 2PR / (P + R). \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       "  \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",
       " General Naive Bayes: $P(Y, F_1, F_2,...,F_n) = P(Y) \\prod_i P(F_i|Y)$; total parameters is linear in number of features. **Binary perceptron**: if true class \\\n",
       "is positive but predicted negative, then add feature vector to weight; if true class is negative but predicted positive, then subtract feature vector from weight. **Multiclass perceptron**: has weight vector for each label; classify \\\n",
       "based on highest dot product. If classification is wrong, then update weight vector for correct one by adding feature vector to weight vector, then update incorrect one by subtracting \\\n",
       "feature vector from it (bias is always 1 for feature vector). Perceptron will converge if perfectably linearly separable. **MIRA update** scale down the update. **SVM** maximizes margin to \\\n",
       "create best separation plane. Mapping data to higher-dimension could make linearly separable. \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 = \"\"\" Machine learning system has 4 components: feature representation, classification function (sigmoid), objective function for learning (min errors like cross-entropy \\\n",
    "function), algo for optimizing objective function (SGD). \"\"\"\n",
    "slp_chapter5_2 = \"\"\"  \"\"\"\n",
    "slp_chapter5_3 = r\"\"\" Minimize **cross-entropy loss**; loss smaller if model estimate closer to being correct. \"\"\"\n",
    "slp_chapter5_4 = \"\"\" Goal is to find weights that minimize loss function, averaged over all examples. Loss function is convex for logistic regression, just one minimum for SGD. \"\"\"\n",
    "slp_chapter5_5 = \"\"\" Regularization penalizes large weights. \"\"\"\n",
    "slp_chapter5_6 = \"\"\" Use softmax for multinomial logistic regression. \"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
    "\n",
    "slp_chapter7_1 = \"\"\" tanh often used as activation function more than sigmoid. ReLU is simplest activation function but most often used. \"\"\"\n",
    "slp_chapter7_2 = \"\"\"  \"\"\"\n",
    "slp_chapter7_3 = r\"\"\" **Fully connected**: each unit in each layer in feed forward NN takes as inputs each output from all units in the previous layer. 2-layer network includes: \\\n",
    "$h = \\sigma(Wx+b)$, $z=Uh$, $y=softmax(z)$. Can replace bias with dummy variable that is always 1. \"\"\"\n",
    "slp_chapter7_4 = r\"\"\" Cross-entropy for multinomial classifier is: $L_{CE} (\\hat{y}, y) = - \\sum_{i=1}^C y_i \\log \\hat{y_i}$. \"\"\"\n",
    "slp_chapter7_5 = \"\"\"  \"\"\"\n",
    "slp_chapter7_6 = \"\"\"  \"\"\"\n",
    "slp_chapter7_7 = \"\"\"  \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module13_lecture_notes = r\"\"\" **Classifier components**: feature representation (represent each observation as feature vector), classification function (computes yhat), objective function (min \\\n",
    "error on training examples for learning), algorithm to optimize objective. **Logistic regression**: learns vector of weights and bias term $z = w \\cdot x + b$ then assigned to probability $P(y=1)=\\sigma(w \\cdot x + b) = \\frac{1}{1+e^{-(w \\cdot x + b)}}$. \\\n",
    "Decision boundary usually set to 0.5 for yes/no classification. Learning weights using minimize the loss (objective) function. **Cross-entropy loss**: maximize prob of correct label $p(y|x)=\\hat{y}^{y}(1-\\hat{y})^{1-y}$, \\\n",
    "then take log and make negative so you can minimize this loss function to get $L_{CE}(\\hat{y},y)=-[y\\log(\\sigma(w \\cdot x + b))+(1-y)\\log(1-\\sigma(w \\cdot x + b))]$. **Gradient descent**: \\\n",
    "finds min of function by going in direction of downward slope, use to find good weights/bias by minimizing loss function $\\hat{\\theta}=\\text{argmin}_{\\theta}\\frac{1}{m}\\sum_{i=1}^{m}L_{CE}(y^i,x^i;\\theta)$. \\\n",
    "(1/m for average loss). Magnitude of move step in gradient descent is slope weighted by learning rate $\\eta$ such that $w^{t+1}=w^t-\\eta \\frac{d}{dw}f(x;w)$; for updating each dimension, we do $\\theta_{t+1}=\\theta_t-\\eta \\nabla L(f(x;\\theta),y)$, \\\n",
    "where $\\nabla$ is learning rate. Gradient (derivative) for loss function for single observation vector and weight is $\\frac{\\partial L_{CE}(w,b)}{\\partial w_j}= [\\sigma(w \\cdot x + b)-y]x_j$, \\\n",
    "or the difference between prediction y and true y times input value (so just adjusting weights by scaled portion of feature vector rather than raw feature vector like perceptrons). Gradient is sum of individual gradients. Loss for entire dataset is average loss over m examples: $cost(w,b)=-\\frac{1}{m}\\sum_{i=1}^{m} y\\log(\\sigma(w \\cdot x + b))+(1-y)\\log(1-\\sigma(w \\cdot x + b))$ \\\n",
    "and gradient for multiple datapoints is sum of individual gradients $\\frac{\\partial cost(w,b)}{\\partial w_j}=\\sum_{i=1}^m [\\sigma(w \\cdot x + b)-y]x_j$. **Batch-training**: compute gradient \\\n",
    "over entire dataset (longer time) vs. **stochastic GD** that chooses single random example; commonly used mini-batch training. *Regularization**: penalizes high weights associated with features \\\n",
    "appearing in only one class to prevent overfitting (Lasso/Ridge add regularization term to loss function). **Multinomial logit**: uses softmax function (generalization of sigmoid). \\\n",
    "**Neural networks**: combines perceptrons such that there are hidden layers in addition to output layer. Smoothness in output function is critical to take derivative (i.e. sigmoid) to create \\\n",
    "**activation function** (common include sigmoid, tanh, rectified linear unit [ReLU]). **Feed-forward NN**: simplest, multilayer, all units fully connected (each unit connect to every unit \\\n",
    "in next layer). Respresent entire hidden layer by combining weight vectors into single weight matrix W and single bias vector b. Computation: multiply W by input vector x, add bias vector, \\\n",
    "apply activation function g; output for hidden layer is $h = \\sigma(Wx+b)$. Normalize output by softmax. **Error backpropagation algorithm**: compute gradient looking back through all layers \\\n",
    "even though loss only computed for the output. Related to backward differentiation (using calculus chain rule) of computational graphs. Neural net uses cross-entropy loss function, \\\n",
    "gradient descent for optimization, and error back propagation to compute gradient for loss function. \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module13_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "02ab2328-eabb-4541-889a-dfc8d9785b5b"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " Machine learning system has 4 components: feature representation, classification function (sigmoid), objective function for learning (min errors like cross-entropy function), algo for optimizing objective function (SGD). \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       "  \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Minimize **cross-entropy loss**; loss smaller if model estimate closer to being correct. \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Goal is to find weights that minimize loss function, averaged over all examples. Loss function is convex for logistic regression, just one minimum for SGD. \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Regularization penalizes large weights. \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Use softmax for multinomial logistic regression. \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " tanh often used as activation function more than sigmoid. ReLU is simplest activation function but most often used. \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       "  \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " **Fully connected**: each unit in each layer in feed forward NN takes as inputs each output from all units in the previous layer. 2-layer network includes: \\\n",
       "$h = \\sigma(Wx+b)$, $z=Uh$, $y=softmax(z)$. Can replace bias with dummy variable that is always 1. \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Cross-entropy for multinomial classifier is: $L_{CE} (\\hat{y}, y) = - \\sum_{i=1}^C y_i \\log \\hat{y_i}$. \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       "  \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       "  \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       "  \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       " **Classifier components**: feature representation (represent each observation as feature vector), classification function (computes yhat), objective function (min \\\n",
       "error on training examples for learning), algorithm to optimize objective. **Logistic regression**: learns vector of weights and bias term $z = w \\cdot x + b$ then assigned to probability $P(y=1)=\\sigma(w \\cdot x + b) = \\frac{1}{1+e^{-(w \\cdot x + b)}}$. \\\n",
       "Decision boundary usually set to 0.5 for yes/no classification. Learning weights using minimize the loss (objective) function. **Cross-entropy loss**: maximize prob of correct label $p(y|x)=\\hat{y}^{y}(1-\\hat{y})^{1-y}$, \\\n",
       "then take log and make negative so you can minimize this loss function to get $L_{CE}(\\hat{y},y)=-[y\\log(\\sigma(w \\cdot x + b))+(1-y)\\log(1-\\sigma(w \\cdot x + b))]$. **Gradient descent**: \\\n",
       "finds min of function by going in direction of downward slope, use to find good weights/bias by minimizing loss function $\\hat{\\theta}=\\text{argmin}_{\\theta}\\frac{1}{m}\\sum_{i=1}^{m}L_{CE}(y^i,x^i;\\theta)$. \\\n",
       "(1/m for average loss). Magnitude of move step in gradient descent is slope weighted by learning rate $\\eta$ such that $w^{t+1}=w^t-\\eta \\frac{d}{dw}f(x;w)$; for updating each dimension, we do $\\theta_{t+1}=\\theta_t-\\eta \\nabla L(f(x;\\theta),y)$, \\\n",
       "where $\\nabla$ is learning rate. Gradient (derivative) for loss function for single observation vector and weight is $\\frac{\\partial L_{CE}(w,b)}{\\partial w_j}= [\\sigma(w \\cdot x + b)-y]x_j$, \\\n",
       "or the difference between prediction y and true y times input value (so just adjusting weights by scaled portion of feature vector rather than raw feature vector like perceptrons). Gradient is sum of individual gradients. Loss for entire dataset is average loss over m examples: $cost(w,b)=-\\frac{1}{m}\\sum_{i=1}^{m} y\\log(\\sigma(w \\cdot x + b))+(1-y)\\log(1-\\sigma(w \\cdot x + b))$ \\\n",
       "and gradient for multiple datapoints is sum of individual gradients $\\frac{\\partial cost(w,b)}{\\partial w_j}=\\sum_{i=1}^m [\\sigma(w \\cdot x + b)-y]x_j$. **Batch-training**: compute gradient \\\n",
       "over entire dataset (longer time) vs. **stochastic GD** that chooses single random example; commonly used mini-batch training. *Regularization**: penalizes high weights associated with features \\\n",
       "appearing in only one class to prevent overfitting (Lasso/Ridge add regularization term to loss function). **Multinomial logit**: uses softmax function (generalization of sigmoid). \\\n",
       "**Neural networks**: combines perceptrons such that there are hidden layers in addition to output layer. Smoothness in output function is critical to take derivative (i.e. sigmoid) to create \\\n",
       "**activation function** (common include sigmoid, tanh, rectified linear unit [ReLU]). **Feed-forward NN**: simplest, multilayer, all units fully connected (each unit connect to every unit \\\n",
       "in next layer). Respresent entire hidden layer by combining weight vectors into single weight matrix W and single bias vector b. Computation: multiply W by input vector x, add bias vector, \\\n",
       "apply activation function g; output for hidden layer is $h = \\sigma(Wx+b)$. Normalize output by softmax. **Error backpropagation algorithm**: compute gradient looking back through all layers \\\n",
       "even though loss only computed for the output. Related to backward differentiation (using calculus chain rule) of computational graphs. Neural net uses cross-entropy loss function, \\\n",
       "gradient descent for optimization, and error back propagation to compute gradient for loss function. \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": 19,
   "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 = \"\"\" Recurrent NN contains cycle; utilizes value of hidden layer at previous time step as memory. \"\"\"\n",
    "slp_chapter9_3 = \"\"\"  \"\"\"\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 = \"\"\" **Distributional hypothesis**: words in similar contexts have similar meanings. \"\"\"\n",
    "slp_chapter6_2 = \"\"\" **Vector semantics**: idea is to represent word as a point in multidimensional semantics space derived from the distributions of neighbors; vectors for representing \\\n",
    "words are called **embeddings**. \"\"\"\n",
    "slp_chapter6_3 = \"\"\" **Term-document matrix**: row represents word in vocab, column represents document, each cell represents frequency of words in document. **Term-context matrix**: \\\n",
    "columns are words rather than documents, show how often term and context co-occur in some context in corpus. These are **sparse** vector representations since most of the numbers are zero. \"\"\"\n",
    "slp_chapter6_4 = r\"\"\" Measure similarity between two word vectors using cosine angle between them: $cosine(v, w)=\\frac{v \\cdot w}{|v||w|}=\\frac{\\sum_{i=1}^N v_i w_i}{\\sqrt{\\sum_{i=1}^N v_i^2}\\sqrt{\\sum_{i=1}^N w_i^2}}$. \"\"\"\n",
    "slp_chapter6_8 = r\"\"\" Embeddings are short, dense vectors. **Word2vec** embeddings are static (one fixed embedding for each word in vocab); instead of counting frequency, trains classifier \\\n",
    "to see if a word is likely to appear near the target word -- care about the learned classifier weights as word embeddings. This uses self-supervision (don't need hand-labeled supervision, \\\n",
    "since just see if word shows up near target word in training data). Intuition: treat target word and context as positive examples, randomly select other words in vocab as negative examples, \\\n",
    "use logistic regression to train classifier to distinguish pos/neg, use learned weights as embeddings. Uses simplifying assumption that all context words are independent, so multiply prob \\\n",
    "from sigmoid function. Parameter $k$ determines how many noise words to include for each positive word, parameter $\\alpha < 1$ downweights unigram probability of frequent words vs. rare words \\\n",
    "or 1 if there is no adjustment. Maximize dot product of word with actual context words and minimize dot product with noise words. \"\"\"\n",
    "slp_chapter6_10 = \"\"\" Shorter context windows lead to more syntactic representations (semantically similar with same part of speech), while longer context windows have topically related \\\n",
    "but not similar. First-order co-occurance if typically nearby each other; second-order if they have similar neighbors. Parallelogram vector model for analogies show how embeddings capture \\\n",
    "relational meanings. \"\"\"\n",
    "slp_chapter6_11 = \"\"\"  \"\"\"\n",
    "slp_chapter6_12 = \"\"\"  \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module14_lecture_notes = r\"\"\" NL model advantages over n-grams: don't need smoothing, can handle longer histories, generalize over contexts of similar words, neural LMs tend to have \\\n",
    "higher predictive accuracy than n-gram LMs; disad is that it is slower to train. **Neural LM**: associated each word with vector (similarity btw words), express joint prob function of \\\n",
    "word sequence in terms of word vectors for words in sequence, simultaneously learn word vectors and parameters of function; prob function expressed using prod of cond. prob of next word \\\n",
    "given previous word using mutlilayer feed-forward NN. Input: sequence of words; output: prob dist over next word; each word associated with embedding vector; input vector x glues together \\\n",
    "v(w) for each of k words. Difficulty: \"curse of dimensionality\" with too many parameters to accurately estimate. **Distributional hypothesis**: probability of enviros occuring with \\\n",
    "particular elements; identical enviros/context then considered synonyms. **Vector space models**: vector comparisons using L2 (length) normalization ($||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$), then \\\n",
    "measure cosine angles between them to see how similar they are. Dependency matrix to track long distance dependencies between words. Transform vectors using Term Frequency Inverse Document \\\n",
    "Frequency (TF-IDF) = how often a word occured in doc \\* 1 over number of docs that it occured in. To get dense vectors, can train classifier. Reduce dimensionality using Word2Vec. \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module14_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "b2324894-c38f-4e55-e703-937d0bb51abe"
   },
   "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",
       " Recurrent NN contains cycle; utilizes value of hidden layer at previous time step as memory. \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       "  \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " **Distributional hypothesis**: words in similar contexts have similar meanings. \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " **Vector semantics**: idea is to represent word as a point in multidimensional semantics space derived from the distributions of neighbors; vectors for representing words are called **embeddings**. \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " **Term-document matrix**: row represents word in vocab, column represents document, each cell represents frequency of words in document. **Term-context matrix**: columns are words rather than documents, show how often term and context co-occur in some context in corpus. These are **sparse** vector representations since most of the numbers are zero. \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Measure similarity between two word vectors using cosine angle between them: $cosine(v, w)=\\frac{v \\cdot w}{|v||w|}=\\frac{\\sum_{i=1}^N v_i w_i}{\\sqrt{\\sum_{i=1}^N v_i^2}\\sqrt{\\sum_{i=1}^N w_i^2}}$. \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Embeddings are short, dense vectors. **Word2vec** embeddings are static (one fixed embedding for each word in vocab); instead of counting frequency, trains classifier \\\n",
       "to see if a word is likely to appear near the target word -- care about the learned classifier weights as word embeddings. This uses self-supervision (don't need hand-labeled supervision, \\\n",
       "since just see if word shows up near target word in training data). Intuition: treat target word and context as positive examples, randomly select other words in vocab as negative examples, \\\n",
       "use logistic regression to train classifier to distinguish pos/neg, use learned weights as embeddings. Uses simplifying assumption that all context words are independent, so multiply prob \\\n",
       "from sigmoid function. Parameter $k$ determines how many noise words to include for each positive word, parameter $\\alpha < 1$ downweights unigram probability of frequent words vs. rare words \\\n",
       "or 1 if there is no adjustment. Maximize dot product of word with actual context words and minimize dot product with noise words. \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Shorter context windows lead to more syntactic representations (semantically similar with same part of speech), while longer context windows have topically related but not similar. First-order co-occurance if typically nearby each other; second-order if they have similar neighbors. Parallelogram vector model for analogies show how embeddings capture relational meanings. \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       "  \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       "  \n",
       "\n",
       "## Module 14 Lecture Notes\n",
       " NL model advantages over n-grams: don't need smoothing, can handle longer histories, generalize over contexts of similar words, neural LMs tend to have \\\n",
       "higher predictive accuracy than n-gram LMs; disad is that it is slower to train. **Neural LM**: associated each word with vector (similarity btw words), express joint prob function of \\\n",
       "word sequence in terms of word vectors for words in sequence, simultaneously learn word vectors and parameters of function; prob function expressed using prod of cond. prob of next word \\\n",
       "given previous word using mutlilayer feed-forward NN. Input: sequence of words; output: prob dist over next word; each word associated with embedding vector; input vector x glues together \\\n",
       "v(w) for each of k words. Difficulty: \"curse of dimensionality\" with too many parameters to accurately estimate. **Distributional hypothesis**: probability of enviros occuring with \\\n",
       "particular elements; identical enviros/context then considered synonyms. **Vector space models**: vector comparisons using L2 (length) normalization ($||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$), then \\\n",
       "measure cosine angles between them to see how similar they are. Dependency matrix to track long distance dependencies between words. Transform vectors using Term Frequency Inverse Document \\\n",
       "Frequency (TF-IDF) = how often a word occured in doc \\* 1 over number of docs that it occured in. To get dense vectors, can train classifier. Reduce dimensionality using Word2Vec. \n",
       "\n",
       "## Module 14 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",
    "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": 23,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "T3cm1WV542_a",
    "outputId": "356e772c-fb4d-4882-9e02-0242cc5bf456"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       " **Nonstationary policy** depends on time. **Proper policy** guaranteed to reach a terminal state. Optimal policy is independent of starting state if using discounted \\\n",
       "utilities with infinite horizons. **Q-function** is action-utility function, or expected utility of taking a given action from a state. Table representation of MDP T and R is with 3D table \\\n",
       "of size $|S|^2|A|$, but most tables are sparse since only some states can be reached from any state, so table size is $O(|S||A|)$. **Contraction** is concept that shows value iteration \\\n",
       "converges (Bellman update is contraction by factor of $\\gamma$ on space of utility vectors); value iteration converges exponntially fast. **Modified policy iteration**: simplified value \\\n",
       "iteration steps with fixed policy (not exact policy evaluation, but good approx). **Asynchronous policy iteration** doesn't update utility/policy for all states at once, and can apply \\\n",
       "either policy improvement or simplified value iteration on subsets of states. \n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       " Your summary here \n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " Stochastic environment with probabilistic transition model. **MDP**: sequential decision problem for fully observable enviro, stochastic transition model, \\\n",
       "additive rewards (non-deterministic search problems, can use expectimax); require state/action sets, transition/reward function, initial state, optional terminal state(s). **Policy**: \\\n",
       "maps action to take at state. $\\pi^{*} (s) = a$ is optimal policy. **Environment history**: sequence of past states/actions. **Absorbing state**: terminal state guaranteed to eventually be reached \\\n",
       "for every policy. **Optimal quantities**: V\\*(s) = exp. utility starting in s moving optimally; Q\\*(s,a) = exp. utility taking action a from s and moving optimally from there; pi\\*(s) = \\\n",
       "optimal action from s. **Recursive value definition/Bellman equations**: $V^*(s) = \\text{max}_a Q^*(s, a)$ // $Q^*(s,a) = \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$. **Time-limited values**: optimal $V_k(s)$ based on \\\n",
       "gamme ending in k more steps. **Value iteration**: $V_{k+1}(s) = \\text{max}_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ (do one ply of expectimax from each state given vector of $v_k(s)$ \\\n",
       "values then repeat until convergence), Bellman update, propagate info through state space by means of local updates. Complexity of each iteration is $O(S^2A)$. Bellman gives optimal utility using one step lookahead. **Policy evaluation**: calculate Vs for fixed policy \\\n",
       "by turning recursive Bellman equations into updates with $O(S^2)$ per iteration; becomes linear system without maxes. **Policy extraction**: do one step expectimax if have optimal values to \\\n",
       "find policy implied by values $\\pi^*(s) = \\text{argmax}_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$; if you have optimal q-values, then very easy (pick policy with max Q\\*). **Policy \\\n",
       "Iteration**: policy evaluation (calculate utilities for fixed policy to convergence) then policy improvement (update policy with resulting converged utilities as future values) the repeat \\\n",
       "until policy converges. Optimal and can converge faster. \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Utility function** - reward function, either +/- but bounded by max value\n",
       "* **Expected utility** - probability weighted utility\n",
       "* **Markovian** - probability of arriving in state only depends on current state and not history\n",
       "* **Principle of meu** - rational agent should choose action that max expected utility, given its knowledge\n",
       "\n",
       "\n",
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       " **N-armed bandit** is slot machine with n levers. **Exploitation vs. exploration**: exploit current best action or try unknown states to gain info. **Bandit problems** have each arm a MDP with only 1 action, and the overall bandit problem is an MDP (arms are independent). **Exploration bonus** for arms that have only been tried a few times. Selection problem makes good decision as fast as possible, doesn't have to minimize failures. **Bandit superprocess* has each arm as full MDP (not restricted to one action). \n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       " **Supervised learning**: passively observing example input/output provided by teacher. **Sparse rewards** give only reward signal in a few states. \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       " **Direct utility estimation**: utility of state defined as expected total reward from the state onward (or **reward-to-go**), and each trial is a sample of this for each state visited. **Adaptive dynamic programming (ADP)**: takes advantage of constraints among utilities of states by learning transition model that connects them, then solving MDP (utilizes the Bellman equation). Passive TD learner learns slower than ADP and more variability, but simpler and less computation per observation. TD does not need transition model to do updates. ADP can be made more efficient with approx, using heuristics like prioritized sweeping heuristic that prefers adjustments to states whose likely successors just had a large adjustment in their own utility. \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       " Active reinforcement learners should be greedy in the limit of infinite exploitation. **Exploration function** determines how greed (preference for high values for utility) trades off with curiosity (actions that haven't been tried frequently), used to calculate optimistic utility/value; rapidly converges to 0 policy loss. \n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       "  \n",
       "\n",
       "## Module 9 Lecture Notes\n",
       " Offline planning: solve MDPs through computations but not playing. **Recursive learning**: learn to max expected rewards by receiving feedback via rewards; \\\n",
       "agent utility defined by reward function; still MDP but to solve (looking for policy) but don't know T or R. MDPs are offline solutions whereas RL is online learning. **Model-based \\\n",
       "learning**: approx model based on experiences; learn empirical MDP (count s' by testing action a from s multiple times to estimate T and R) then solve learned MDP (i.e. value iteration). \\\n",
       "**Model-free learning.** doesn't know or learns the transition model. **Passive reinforcement learning**: policy evaluation (fixed policy) but don't know T and R, execute policy and learn from experience. Direct evaluation: compute values under pi, \\\n",
       "average observed values for each state. Temporal difference learning: allows us to do policy evaluation by updating V(s) after each transition with exponential moving average \\\n",
       "$V^{\\pi}(s) = (1-\\alpha)V^{\\pi}(s) + (\\alpha)sample$, where sample is $R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')$. **Active reinforcement learning**: learn optimal policies (like value \\\n",
       "iteration) with explore/exploit tradeoff. Q-value iteration: $Q_{k+1}(s,a) = \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma \\text{max}_a' Q_{k}(s',a')]$; use Q-learning for active RL \\\n",
       "$Q(s,a) = (1-\\alpha)Q(s,a) + (\\alpha)sample$, where sample is $R(s,\\pi(s),s') + \\gamma \\text{max}_a' Q_{k}(s',a')$. Off-policy learning: Q-learning converges to optimal policy \\\n",
       "even if act suboptimally. **Exploration function**: explore areas that are not yet established (instead of random); modified Q-update $Q(s,a) = (1-\\alpha)Q(s,a) + (\\alpha)R(s,\\pi(s),s') + \\gamma \\text{max}_a' f(Q_{k}(s',a'), N(s',a'))$ \\\n",
       "where $f(u, n) = u + k/n$ returns an optimistic utility that provides higher bump to less visited (lower n) states. **Regret**: measure of total mistake cost (expected minus optimal rewards). \\\n",
       "**Approximate Q-learning**: adjust weights of active features, adjust weight by adding alpha \\* difference between new Q and old Q \\* feature (from need to generalize to new states instead of holding everything in memory; \\\n",
       "representing states as feature representation with weights). \n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Exploration** - try unknown actions to get info\n",
       "* **Exploitation** - use what you do know\n",
       "* **Regret** - still make mistakes even if learn intelligently\n",
       "* **Sampling** - try things repeatedly because of chance\n",
       "* **Difficulty** - learning can be much harder than solving known MDP\n",
       "* **Off-policy learning** - Q-learning converges to optimal policy even if starting with suboptimal policy\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",
       " **Joint probability distribution**: all combinations of values of two variables. \n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       " **Marginal probability**: summing out for each possible value of other variables to remove them from the equation. \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",
       " **Naive Bayes Model**: $P(cause, effect,...) = P(cause)\\prod_i P(effect_i | cause)$. Naive means that it uses simplifying assumption that effects are independent \\\n",
       "given the cause. For each cause, multiply prior probability of cause by product of conditional probabilities of observed effects given the cause, then normalize. Runtime is linear on \\\n",
       "number of effects. \n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       "  \n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       " **N-gram MLE normalization**: $P(w_n|w_{n-1})=\\frac{C(w_{n-1}w_{n})}{\\sum_w C(w_{n-1}w)}$; all times the n-gram appears divided by all times the given context appears, \\\n",
       "called relative frequency. Probability of sentence is just product of n-grams. Add probabilities in log space rather than multiply in linear space to reduce underflow risk. \n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       " Extrinsic evaluation: embed LM in application and see how it improves. Intrinsic evaluation: measures quality of model independent of any application. Use **perplexity** \\\n",
       "to evaluate LM: inverse probability of test set, normalized by number of words. For test set $W = w_1, w_2,...,w_N$, $PP(W)=\\sqrt[N]{\\prod_{i=0}^N \\frac{1}{P(w_i|w_1...w_{i-1})}}$; for \\\n",
       "bigram, it is $PP(W)=\\sqrt[N]{\\prod_{i=0}^N \\frac{1}{P(w_i|w_{i-1})}}$. Higher conditional probability of sequence, lower the perplexity -- minimize perplexity is maximize test set prob. \\\n",
       "Perplexity is also weighted average branching factor (how many words can come after the current word). \n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       " Sparsity: some n-grams appear limited to no times in corpus. \n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       " **Laplace smoothing**: add one to all counts $P(w_i)=\\frac{c_i+1}{N+V}$. **Add-k smoothing** adds some number k instead of one $P(w_i)=\\frac{c_i+k}{N+kV}$. \\\n",
       "**Backoff**: go to lower order n-gram if zero evidence for higher order. **Interpolation**: mix prob estimates from all n-gram estimators, weight using some parameter alpha. **Discounting** higher frequency words and \\\n",
       "provide probability to never seen words. **Kneser-Ney discounting**: uses unigram distribution for new words based on how likely a word is to appear in a novel continuation (depending on \\\n",
       "how many contexts it has appeared in). \n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       "  \n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       " Lower cross-entropy is more accurate. Perplexity is exponent function of cross-entropy. \n",
       "\n",
       "## Module 10 Lecture Notes\n",
       " **Conditional probability**: P(a|b) = P(a,b)/P(b). **Product rule**: P(y)P(x|y)=P(x,y). **Chain rule**: write joint distribution as incremental product of \\\n",
       "conditional distributions. **Bayes rule**: P(x|y) = P(y|x)P(x)/P(y). **Probability Language Models**: **Markov assumption**: P(word|k last words), only depends on k last words, not \\\n",
       "entire context. Estimating bigram probabilities using MLE $P(w_i | w_{i-1})=\\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$. Problem with MLE is zeros (may have something in test that you \\\n",
       "haven't seen in train) - doing things in log space solves this and is faster. \n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Language model** - models that assign prob to sequence of words\n",
       "\n",
       "\n",
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       " **Bayes' Net**: DAG, each node is random variable with probability info that quantifies the effect of parents on the node using finite number of parameters. \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       " Syntax: a directed acyclic graph with some local probability information attached to each node. Semantics: defines how the syntax corresponds to a joint distribution \\\n",
       "over the variables of the network. Joint distribution: $P(x_1,...,x_n)=\\prod_{i=1}^n \\theta (x_i | parents(X_i))$; each entry in joint distribution is product of local conditional \\\n",
       "distributions. **Locally structured/sparse systems**: each subcomponent intercts directly with a limited number of other components (associated with linear growth). Causal better than \\\n",
       "diagnostic: having to specify fewer numbers, and numbers will often be easier to come up with. **Each variable is conditionally indep. on its non-descendants, given parents.** \\\n",
       "**Markov blanket**: variable is conditionally indep. of all other nodes in network, given its parents, children, and children's parents. \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       " **Inference by enumeration**: solving for conditional prob by summing up terms from full joint distribution. **Variable elimination algo**: improves upon exponential enumeration algo by using dynamic programming to do calculations once and save for later. Clustering: join individual nodes to form meganodes. \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       " Independence allows compacting probability outcomes table from $2^n$ to $2n$. Conditional independence if two probabilities are independent given another event [if D is conditionally independent of T given C, then P(D | T, C) = P(D | C), P(T | D, C) = P(T | C), P(T, D | C) = P(T | C) * P(D | C)]. Unconditional (absolute) independence is rare and it doesn't help make inferences about other variables, whereas conditional independence is basic/robust form of knowledge about uncertain environments. Two big problems with full joint probability tables: 1) too big unless few variables and 2) hard to learn/estimate anything empirically about more than a couple varaibles at a time. **Bayes' Nets/graphical models** is a technique that can describe complex joint distributions (models) using simple local distributions (conditional probabilities). Nodes are variables with domains (either assigned/observed or unassigned), arcs are interactions that encode \"direct influence\", and two variables are conditionally independent if no arc but both have arcs to a variable. Bayes' Net is set of nodes for each variable that is a directed, acyclic graph with a conditional distribution for each node (topology/graph + local conditional probabilities). Joint distributions implicitly encoded as product of local conditional distributions. Usually want to reflect causal relationships because easier and simpler (but can just be correlation). Joint distribution over N boolean variables is $O(2^N)$; N-node net if nodes have up to k parents is $O(N*2^{k+1})$ (huge space saving). **D-separation** algorithm based on triples of variables. Causal chain is x -> y -> z: x is not guaranteed independent of z, but is conditionally independent given y. Common cause is y -> x, y -> z: x is not guaranted independent of z, but is conditionally independent given y. Common effect is x -> z, y -> z; x is independent of y, but x and y are not conditionally independent given z. If all paths are inactive (have an observed variable in middle of path), then independence guaranteed; else, not guaranteed. \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Conditional independence** - x is conditionally independent of Y given Z iff $\\forall x, y, z : P(x, y|z) = P(x|z)P(y|z)$ or $P(x|z,y) = P(x|z)$\n",
       "\n",
       "\n",
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 19.1 Forms of Learning\n",
       "  \n",
       "\n",
       "## AIMA Chapter 19.2 Supervised Learning\n",
       " Bias: tendency of predictive hypothesis to deviate from expected value over many training sets. Bias-variance tradeoff: choice between complex/low-bias hypotheses that fit training data vs. simpler/low-variance hypotheses that generalize better. \n",
       "\n",
       "## AIMA Chapter 19.3 Learning Decision Trees\n",
       " **Entropy**: notion of info gain; more info, less entropy. \n",
       "\n",
       "## AIMA Chapter 19.4 Model Selection and Optimization\n",
       " Hyperparameters: parameters on model class, not individual model. Loss function: identify whether FP or FN are worse. \n",
       "\n",
       "## AIMA Chapter 19.5 The Theory of Learning\n",
       "  \n",
       "\n",
       "## AIMA Chapter 19.6 Linear Regression and Classification\n",
       " Loss function is convex for linear regression. **Gradient descent** looks to minimize loss by using parameter $\\alpha$ (step size / learning rate) to move downhill \\\n",
       "toward local min loss. $\\alpha$ is either fixed or decays with time. Stochastic gradient descent randomly selects small number of training samples at each step and updates. **Decision \\\n",
       "boundary**: line/surface that separates two classes. **Perceptron learning rule**: if output correct, then weights unchanged; otherwise, weights are increased if actual is 1 and predicted \\\n",
       "is 0 and vice versa. \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Generative classifiers (naive Bayes) build model of how a class could generate some input data; discrimitive classifiers (logit) return what features from input are most \\\n",
       "telling of classification. **Bag of words**: representation of text as unordered set of words (position ignored), keeping only frequency. **Naive Bayes** is probabilistic classifier that \\\n",
       "returns class which has max posterior prob given the text doc $\\hat{c}=\\text{argmax}_{c \\in C} P(c|d)$. Since document stays the same, we can drop Bayes denominator to choose class that \\\n",
       "maximizes $\\hat{c}=\\text{argmax}_{c \\in C} P(d|c)P(c)$ -- choose class with highest product of likelihood of document given class and prior probability of class, where doc can be represented \\\n",
       "as set of features that are naively assumed to be conditionally independent given c. Linear function of input features in log space. \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " To find prior, divide frequency of docs in training data with class c by total number of docs. Assume features is just existence of word in doc's bag of words, \\\n",
       "so $P(f_i|c)=P(w_i|c)=\\frac{count(w_i,c)}{\\sum_{w \\in V} count(w,c)}$, or number of times word appears in all docs with topic c divided by all words in all docs with topic c (can use \\\n",
       "Laplace smoothing). Drop unknown words in test data. \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       "  \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Binary NB clips word count to 1 for each document (does the word exist in the doc or not). Deal with negation by prepending NOT_ to words after a negative token until next punctuation. \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",
       " Find probabilty of sentence by multiplying $P(w|sentiment)$ for all words (this is just likelihood of NB, would still need to multiply by prior). \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " F1 score is 2PR / (P + R). \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       "  \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",
       " General Naive Bayes: $P(Y, F_1, F_2,...,F_n) = P(Y) \\prod_i P(F_i|Y)$; total parameters is linear in number of features. **Binary perceptron**: if true class \\\n",
       "is positive but predicted negative, then add feature vector to weight; if true class is negative but predicted positive, then subtract feature vector from weight. **Multiclass perceptron**: has weight vector for each label; classify \\\n",
       "based on highest dot product. If classification is wrong, then update weight vector for correct one by adding feature vector to weight vector, then update incorrect one by subtracting \\\n",
       "feature vector from it (bias is always 1 for feature vector). Perceptron will converge if perfectably linearly separable. **MIRA update** scale down the update. **SVM** maximizes margin to \\\n",
       "create best separation plane. Mapping data to higher-dimension could make linearly separable. \n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " Machine learning system has 4 components: feature representation, classification function (sigmoid), objective function for learning (min errors like cross-entropy function), algo for optimizing objective function (SGD). \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       "  \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Minimize **cross-entropy loss**; loss smaller if model estimate closer to being correct. \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Goal is to find weights that minimize loss function, averaged over all examples. Loss function is convex for logistic regression, just one minimum for SGD. \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Regularization penalizes large weights. \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Use softmax for multinomial logistic regression. \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " tanh often used as activation function more than sigmoid. ReLU is simplest activation function but most often used. \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       "  \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " **Fully connected**: each unit in each layer in feed forward NN takes as inputs each output from all units in the previous layer. 2-layer network includes: \\\n",
       "$h = \\sigma(Wx+b)$, $z=Uh$, $y=softmax(z)$. Can replace bias with dummy variable that is always 1. \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Cross-entropy for multinomial classifier is: $L_{CE} (\\hat{y}, y) = - \\sum_{i=1}^C y_i \\log \\hat{y_i}$. \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       "  \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       "  \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       "  \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       " **Classifier components**: feature representation (represent each observation as feature vector), classification function (computes yhat), objective function (min \\\n",
       "error on training examples for learning), algorithm to optimize objective. **Logistic regression**: learns vector of weights and bias term $z = w \\cdot x + b$ then assigned to probability $P(y=1)=\\sigma(w \\cdot x + b) = \\frac{1}{1+e^{-(w \\cdot x + b)}}$. \\\n",
       "Decision boundary usually set to 0.5 for yes/no classification. Learning weights using minimize the loss (objective) function. **Cross-entropy loss**: maximize prob of correct label $p(y|x)=\\hat{y}^{y}(1-\\hat{y})^{1-y}$, \\\n",
       "then take log and make negative so you can minimize this loss function to get $L_{CE}(\\hat{y},y)=-[y\\log(\\sigma(w \\cdot x + b))+(1-y)\\log(1-\\sigma(w \\cdot x + b))]$. **Gradient descent**: \\\n",
       "finds min of function by going in direction of downward slope, use to find good weights/bias by minimizing loss function $\\hat{\\theta}=\\text{argmin}_{\\theta}\\frac{1}{m}\\sum_{i=1}^{m}L_{CE}(y^i,x^i;\\theta)$. \\\n",
       "(1/m for average loss). Magnitude of move step in gradient descent is slope weighted by learning rate $\\eta$ such that $w^{t+1}=w^t-\\eta \\frac{d}{dw}f(x;w)$; for updating each dimension, we do $\\theta_{t+1}=\\theta_t-\\eta \\nabla L(f(x;\\theta),y)$, \\\n",
       "where $\\nabla$ is learning rate. Gradient (derivative) for loss function for single observation vector and weight is $\\frac{\\partial L_{CE}(w,b)}{\\partial w_j}= [\\sigma(w \\cdot x + b)-y]x_j$, \\\n",
       "or the difference between prediction y and true y times input value (so just adjusting weights by scaled portion of feature vector rather than raw feature vector like perceptrons). Gradient is sum of individual gradients. Loss for entire dataset is average loss over m examples: $cost(w,b)=-\\frac{1}{m}\\sum_{i=1}^{m} y\\log(\\sigma(w \\cdot x + b))+(1-y)\\log(1-\\sigma(w \\cdot x + b))$ \\\n",
       "and gradient for multiple datapoints is sum of individual gradients $\\frac{\\partial cost(w,b)}{\\partial w_j}=\\sum_{i=1}^m [\\sigma(w \\cdot x + b)-y]x_j$. **Batch-training**: compute gradient \\\n",
       "over entire dataset (longer time) vs. **stochastic GD** that chooses single random example; commonly used mini-batch training. *Regularization**: penalizes high weights associated with features \\\n",
       "appearing in only one class to prevent overfitting (Lasso/Ridge add regularization term to loss function). **Multinomial logit**: uses softmax function (generalization of sigmoid). \\\n",
       "**Neural networks**: combines perceptrons such that there are hidden layers in addition to output layer. Smoothness in output function is critical to take derivative (i.e. sigmoid) to create \\\n",
       "**activation function** (common include sigmoid, tanh, rectified linear unit [ReLU]). **Feed-forward NN**: simplest, multilayer, all units fully connected (each unit connect to every unit \\\n",
       "in next layer). Respresent entire hidden layer by combining weight vectors into single weight matrix W and single bias vector b. Computation: multiply W by input vector x, add bias vector, \\\n",
       "apply activation function g; output for hidden layer is $h = \\sigma(Wx+b)$. Normalize output by softmax. **Error backpropagation algorithm**: compute gradient looking back through all layers \\\n",
       "even though loss only computed for the output. Related to backward differentiation (using calculus chain rule) of computational graphs. Neural net uses cross-entropy loss function, \\\n",
       "gradient descent for optimization, and error back propagation to compute gradient for loss function. \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",
       " Recurrent NN contains cycle; utilizes value of hidden layer at previous time step as memory. \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       "  \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " **Distributional hypothesis**: words in similar contexts have similar meanings. \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " **Vector semantics**: idea is to represent word as a point in multidimensional semantics space derived from the distributions of neighbors; vectors for representing words are called **embeddings**. \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " **Term-document matrix**: row represents word in vocab, column represents document, each cell represents frequency of words in document. **Term-context matrix**: columns are words rather than documents, show how often term and context co-occur in some context in corpus. These are **sparse** vector representations since most of the numbers are zero. \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Measure similarity between two word vectors using cosine angle between them: $cosine(v, w)=\\frac{v \\cdot w}{|v||w|}=\\frac{\\sum_{i=1}^N v_i w_i}{\\sqrt{\\sum_{i=1}^N v_i^2}\\sqrt{\\sum_{i=1}^N w_i^2}}$. \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Embeddings are short, dense vectors. **Word2vec** embeddings are static (one fixed embedding for each word in vocab); instead of counting frequency, trains classifier \\\n",
       "to see if a word is likely to appear near the target word -- care about the learned classifier weights as word embeddings. This uses self-supervision (don't need hand-labeled supervision, \\\n",
       "since just see if word shows up near target word in training data). Intuition: treat target word and context as positive examples, randomly select other words in vocab as negative examples, \\\n",
       "use logistic regression to train classifier to distinguish pos/neg, use learned weights as embeddings. Uses simplifying assumption that all context words are independent, so multiply prob \\\n",
       "from sigmoid function. Parameter $k$ determines how many noise words to include for each positive word, parameter $\\alpha < 1$ downweights unigram probability of frequent words vs. rare words \\\n",
       "or 1 if there is no adjustment. Maximize dot product of word with actual context words and minimize dot product with noise words. \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Shorter context windows lead to more syntactic representations (semantically similar with same part of speech), while longer context windows have topically related but not similar. First-order co-occurance if typically nearby each other; second-order if they have similar neighbors. Parallelogram vector model for analogies show how embeddings capture relational meanings. \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       "  \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       "  \n",
       "\n",
       "## Module 14 Lecture Notes\n",
       " NL model advantages over n-grams: don't need smoothing, can handle longer histories, generalize over contexts of similar words, neural LMs tend to have \\\n",
       "higher predictive accuracy than n-gram LMs; disad is that it is slower to train. **Neural LM**: associated each word with vector (similarity btw words), express joint prob function of \\\n",
       "word sequence in terms of word vectors for words in sequence, simultaneously learn word vectors and parameters of function; prob function expressed using prod of cond. prob of next word \\\n",
       "given previous word using mutlilayer feed-forward NN. Input: sequence of words; output: prob dist over next word; each word associated with embedding vector; input vector x glues together \\\n",
       "v(w) for each of k words. Difficulty: \"curse of dimensionality\" with too many parameters to accurately estimate. **Distributional hypothesis**: probability of enviros occuring with \\\n",
       "particular elements; identical enviros/context then considered synonyms. **Vector space models**: vector comparisons using L2 (length) normalization ($||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$), then \\\n",
       "measure cosine angles between them to see how similar they are. Dependency matrix to track long distance dependencies between words. Transform vectors using Term Frequency Inverse Document \\\n",
       "Frequency (TF-IDF) = how often a word occured in doc \\* 1 over number of docs that it occured in. To get dense vectors, can train classifier. Reduce dimensionality using Word2Vec. \n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Concept** - definition\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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "DJZkdaRmqkc1"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
