{
 "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/",
     "height": 0
    },
    "id": "lzaavW96tcxM",
    "outputId": "1e014143-d106-407c-8e75-0bd2f06ae8cc"
   },
   "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/",
     "height": 0
    },
    "id": "8DvZ57A-djo1",
    "outputId": "84a10f7a-99a2-48e0-dbbc-88cadb7b6aac"
   },
   "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 = \"\"\" Your summary here \"\"\"\n",
    "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module8_lecture_notes = \"\"\" \n",
    "\n",
    "MDPs : \n",
    "\n",
    "- No longer deterministic environments : now task environment is probabilistic / STOCHASTIC\n",
    "\n",
    "  - This means that eg. when we select \"Up\", we go \"up\" X% of the time -> uncertainty \\\n",
    "in the resulting state\n",
    "\n",
    "- Sequential decision problem\n",
    "\n",
    "- for a fully observable environment\n",
    "\n",
    "- with a stochastic transition model\n",
    "\n",
    "- that has additive rewards\n",
    "\n",
    "Stochastic Transition model needed to replace our deterministic transition model:\n",
    "\n",
    "- Transition model T(s, a, s') is written as a probability : p(s' | s, a) : \\\n",
    "the probability of arriving in state s' given that we are in state s and selected action a\n",
    "\n",
    "- We ignore past states : MARKOV property : the prob of arriving to next state \\\n",
    "only depends on the current state s, and not the history of earlier states.\n",
    "\n",
    "Reward function, R(s,a,s') : \n",
    "\n",
    "- We must also specify a utility/reward function for agent. \n",
    "\n",
    "- Can be pos/neg, but must be bounded by some max value. \n",
    "\n",
    "- Since decision process is sequential, must specify the utility f'n on a sequence \\\n",
    "of states and actions. \n",
    "\n",
    "- Instead of giving a reward only at goal states, agent can recieve a reward \\\n",
    "at each time step, based on transition from s to s' via action a.\n",
    "\n",
    "  - Can also receive a negative reward at each time step except for entering \\\n",
    "  terminal state\n",
    "\n",
    "- Rewards are additive (PERFORMANCE of agent in MDP = sum of rewards for the transition it makes)\n",
    "\n",
    "To find a sol'n to an MDP, we need : \n",
    "\n",
    "1. set of states, s E S\n",
    "\n",
    "2. set of actions, a E A\n",
    "\n",
    "3. Transition function T(s, a, s')\n",
    "\n",
    "  - Prob that executing action a in s will lead to s' = P(s'|s,a)\n",
    "\n",
    "  - probability is called a MODEL\n",
    "\n",
    "4. Reward function R(s,a,s')\n",
    "\n",
    "5. Initial state s_0\n",
    "\n",
    "6. [optional] terminal states\n",
    "\n",
    "Solution to an MDP is called a POLICY, $\\pi$.\n",
    "\n",
    "A policy maps from a state onto the action to take if the agent is in that state.\n",
    "\n",
    "$$\\pi (S) = a $$\n",
    "\n",
    "^ Policy tells the agent what action to take at the particular state s. \n",
    "\n",
    "Optimal policy : $\\pi$* is the OPTIMAL policy : finds action that maximizes \\ \n",
    "the expected utility of being in state s' from state s.\n",
    "\n",
    "  - Remember that our model is stochastic : even if same policy is executed \\\n",
    "  several times, this may lead to different ENVIRONMENT HISTORY (sequence of \\\n",
    "   states and actions), and thus a different score under the reward function.\n",
    "\n",
    "   - Therefore, we need to compute the expected utility of all the possible \\\n",
    "   paths generated by a policy.\n",
    "\n",
    "   - Utility = sum of (discounted) rewards\n",
    "\n",
    "DISCOUNTING : \n",
    "\n",
    "- Another factor that impacts optimal policy is that rewards now are preferred  \\\n",
    "to rewards later. \n",
    "\n",
    "  - Solution : Exponentially decay the values of rewards so that sooner rewards \\\n",
    "  have higher utility than later rewards, and to ensure our algo converges.\n",
    "\n",
    "  - $U([r_0, r_1, ...]) = r_0 + \\gamma r_1 + \\gamma ^{2} r_2 +....$ where \\\n",
    "  $0 < \\gamma < 1$\n",
    "\n",
    "  - This ensures that $U([r_0, r_1, ...]) = \\sum_{t = 0}^{\\inf} \\gamma ^{t} R_{t} \\leq R_{max}/(1 - \\gamma)$\n",
    "\n",
    "  - Smaller $\\gamma$ means smaller \"horizon\" - shorter-time focus\n",
    "\n",
    "- Another way we could avoid the issue of infinite utilities, ie if game lasts \\\n",
    "forever, is to set a Finite horizon (like depth-limited search) : \n",
    "    \n",
    "    - Terminate episodes after a fixed T steps\n",
    "\n",
    "    - Give nonstationary policies ($\\PI$ depends on time left)\n",
    "\n",
    "Representing MDPs : MDP SEARCH TREES\n",
    "\n",
    "- Each MDP state projects an expectimax-like search tree\n",
    "\n",
    "  - Transition f'n encodes probability\n",
    "\n",
    "  - Reward f'n given at each state of the tree\n",
    "\n",
    "  - Value (utility) of state s : V*(s) = expected utility starting in s and acting optimally\n",
    "\n",
    "  - Value (utility) of a q-state (s,a) : \n",
    "\n",
    "    - Q*(s,a) = expected utility starting out having taken action a from state s \\\n",
    "    and thereafter acting optimally\n",
    "\n",
    "  - Optimal policy : \n",
    "\n",
    "    - $\\pi$*(s) = optimal action from state s\n",
    "\n",
    "- Fundamental operation : compute the EXPECTIMAX value of a state\n",
    "\n",
    "  - $V*(s) = max_a Q*(s,a)$ = max of choosing any of these actions\n",
    "\n",
    "  - where $Q*(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]\n",
    "\n",
    "  So we have :\n",
    "$$V*(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
    "\n",
    "In order to avoid the issue that the tree can go on forever, can perform a \\\n",
    "depth-limited computation, with increasing depths until change is small. \n",
    "\n",
    "  - We don't care about deep parts of the tree if $\\gamma < 1$.\n",
    "\n",
    "Other issue : states can be repeated!\n",
    "\n",
    "  - To avoid this, only compute needed quantitites once. \n",
    "\n",
    "\n",
    " Now,\n",
    "\n",
    " HOW TO CHOOSE OPTIMAL OUTCOME : \n",
    "\n",
    " 3 algos : \n",
    "\n",
    " 1. Value iteration \n",
    "\n",
    " 2. Policy Evaluation\n",
    "\n",
    " 3. Policy Iteration\n",
    "\n",
    "\n",
    "--\n",
    "\n",
    "1. VALUE ITERATION : \n",
    "\n",
    "  - Start with $V_{0}(s) = 0$ : no time steps left means an expected reward sum = 0\n",
    "\n",
    "  - Given vectors of $V_k (s)$ values, do one ply of expectimax from each state : \n",
    "  $$V_{k+1}(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
    "\n",
    "  - Repeat until convergence\n",
    "\n",
    "- Complexity of each iteration : $O(S^2 A)$\n",
    "\n",
    "- Theorem : algo will CONVERGE to unique optimal values, because of discount factor!\n",
    "\n",
    "  - Approximations get refined towards optimal values\n",
    "\n",
    "  - Policy may converge long before values do\n",
    "\n",
    "- See eg on sheet\n",
    "\n",
    "- PROBLEMS with value iteration : \n",
    "\n",
    "  1. Slow :  $O(S^2 A)$ per iteration\n",
    "\n",
    "  2. The \"max\" at each state rarely changes\n",
    "\n",
    "  3. Policy converges long before values (but algo will keep going until values \\\n",
    "   converge even if not necessary)\n",
    "\n",
    "BELLMAN EQUATIONS : \n",
    "\n",
    "Definition of \"optimal utility\" via expectimax recurrence gives a simple one-step\\\n",
    "lookahead relationship amongst optimal utility values : \n",
    "\n",
    "$$V*(s) = max_a Q*(s,a)$$\n",
    "$$Q*(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
    "$$ \\therefore V*(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
    "\n",
    "2. POLICY EVALUATION :\n",
    "\n",
    "- Evaluate by policy, not action : ie. if we fixed some policy, then the tree \\\n",
    "would be simpler as there would only be one action per state\n",
    "\n",
    "  - But tree's val would depend on which policy was taken. \n",
    "\n",
    "- Utility of state s under fixed policy $\\pi$ = $V^{\\pi}(s) = expected total \\\n",
    "discounted rewards starting in s and following $\\pi$.\n",
    "\n",
    "  - Using recusive Bellman Equation for one step look-ahead : \n",
    "\n",
    "  $$V_{0}^{\\pi} (s) = 0 //initial condition $$\n",
    "  $$V_{k+1}^{\\pi} (s) = \\sum_{s'} T(s,\\pi (s),s') [R(s, \\pi (s),s') + \\gamma V_{k}^{\\pi}(s')]$$\n",
    "\n",
    "  - Instead of calculating max, we sum over transitions and have $\\pi$(s) fixed.\n",
    "\n",
    "- Efficiency : $O(S^{2})$ per iteration.\n",
    "\n",
    "\n",
    "3. POLICY ITERATION : \n",
    "\n",
    "- Actions are easier to select from Q-values : $\\pi * (s) = argmax_a Q*(s,a)$\n",
    "\n",
    "- Is OPTIMAL, even if you start with any random policy! \n",
    "\n",
    "- Algo converges at an optimal policy.\n",
    "\n",
    "  1. Policy EVALUATION  : calculate utilities for some fixerd policy (not \\\n",
    "  necessarily optimal) until convergence\n",
    "\n",
    "  2. Policy IMPROVEMENT : update policy using one-step look ahead with resulting \\\n",
    "  converged (but not optimal!) utilities as future values (need to compare over \\\n",
    "  actions:)\n",
    "  $$\\pi_{i+1}(s) = argmax_a \\sum_{s'} T(s,a,s') [R(s, a,s') + \\gamma V^{\\pi}(s')]$$\n",
    "\n",
    "  3. Repeat steps until policy converges\n",
    "\n",
    "COMPARISON : \n",
    " \n",
    " - Both value iteration and policy iteration compute the same thing (all \\\n",
    " optimal values)\n",
    "\n",
    " - In VALUE ITERATION : \n",
    "\n",
    "  - Every iteration updates both the values and (implicitly) the policy.\n",
    "\n",
    "  - We don't track the policy, but taking the max over actions implicitly \\\n",
    "  recomputes it\n",
    "\n",
    "- In POLICY ITERATION : \n",
    "\n",
    "  - Do several passes that update utilities with fixed policy (but each pass \\\n",
    "  is faster because we only consider one action, not all, so no need to take max of actions)\n",
    "\n",
    "  - After the policy is evaluated, a new policy is chosen (slow like a value \\\n",
    "  iteration pass)\n",
    "\n",
    "  - The new policy will be better (or converged = done)\n",
    "\n",
    "- BOTH ARE DYNAMIC PROGRAMS FOR SOLVING MDPs\n",
    "\n",
    "If you want to : \n",
    "\n",
    "- Compute optimal values -> Value OR Policy Iteration\n",
    "\n",
    "- Compute values for a particular policy -> Policy Evaluation\n",
    "\n",
    "- Turn values into a policy -> Policy Extraction (one-step look ahead)\n",
    "\n",
    "**they are ALL variations of the Bellman updates! All use one-step lookahead \\\n",
    "expectimax fragments, only differ in whether we plug in a fixed policy or amx over \\\n",
    "actions.\n",
    "\n",
    "--\n",
    "\n",
    "Principle of MAXIMUM EXPECtED UTILITY (MEU) : \n",
    "\n",
    "- A rational agent should choose the action that maximizes is expected utility,\\\n",
    "given its knowledge. \n",
    "\n",
    "- For worst-case minimax reasoning, terminal function scale doesn't matter\n",
    "\n",
    "  - We just want better states to have higher evals\n",
    "\n",
    "    - -> called INSENSITIVITY to monotonic transformations\n",
    "\n",
    "- For avg-case expectimax, we need magnitudes to be meaningful.\n",
    "\n",
    "UTILITIES : \n",
    "\n",
    "- [Def] Utilities are functions from outcomes (states of the world) to real \\\n",
    "numbers that describe an agent's preferences.\n",
    "\n",
    "- Preferences : An agent must either have preferences ($A > B$ or be indifferent \\\n",
    "(A ~ B)\n",
    "\n",
    "- Need some constraints on preferences before we call them rational, such as : \n",
    "\n",
    "  - AXIOM OF TRANSITIVITY : $(A > B) \\land (B > C) -> (A > C)$\n",
    "\n",
    "  - ORDERABILITY : $(A > B) \\lor (B > A) \\lor (A ~ B)$ Given 2 lotteries, a \\\n",
    "  rational agent must prefer one or rathem equal (cannot avoid deciding)\n",
    "\n",
    "  - CONTINUITY : $A > B > C -> for all p, [p, A; (1-p), C] ~ B$ (some lotery B \\\n",
    "   between A, C, there exists probability p that makes you indifferent to B)\n",
    "\n",
    "  - SUBSTITUTABILITY : $A ~ B -> [p, A; (1-p), C] ~ [p, B; (1-p), C]$ (if neither \\\n",
    "  prefer A, B, then some lottery in between that u have equal preference over that lottery)\n",
    "\n",
    "  - MONOTONICITY : $A > B -> (p \\geq q <-> [p, A; (1-p), B] \\geq [q, A; (1-q), B])$\n",
    "   (if A better than B, i prefer greater p than q)\n",
    "\n",
    "- Theorem : Rational preferences imply behavior describable as MEU\n",
    "\n",
    "- In the case of money : \n",
    "\n",
    "  - Money does NOT behave as a utility function, but we can talk about the utility \\\n",
    "  of having money (or being in debt)\n",
    "\n",
    "    - Given a lotter L = [p, USD X; (1-p), USD Y] : \n",
    "\n",
    "      - EXPECTD MONETARY VALUE $(EMV(L)) = p*X + (1-p) * Y$\n",
    "\n",
    "      - $U(L) = p*U(X) + (1-p)*U(Y)$\n",
    "\n",
    "      - Typically, $U(L) < U(EMV(L))$\n",
    "\n",
    "        - So people are risk averse, and when in debt are risk-prone\n",
    "\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 8.\n",
    "# You can define any term in the textbook or lecture, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 25 words long.\n",
    "\n",
    "module8_definitions = {\n",
    "\"utility function\" : \"Your definition here\",\n",
    "\"expected utility\" : \"your definition here\",\n",
    "\"etc.\": \"your definition here\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "elCCgY64spuq"
   },
   "source": [
    "## Preview of your notes for Module 8\n",
    "\n",
    "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 4359
    },
    "id": "gYYeNcdM_maE",
    "outputId": "1a2aaaf5-027e-4085-8a51-d76c6f0324e3"
   },
   "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",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       " Your summary here \n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " \n",
       "\n",
       "MDPs : \n",
       "\n",
       "- No longer deterministic environments : now task environment is probabilistic / STOCHASTIC\n",
       "\n",
       "  - This means that eg. when we select \"Up\", we go \"up\" X% of the time -> uncertainty in the resulting state\n",
       "\n",
       "- Sequential decision problem\n",
       "\n",
       "- for a fully observable environment\n",
       "\n",
       "- with a stochastic transition model\n",
       "\n",
       "- that has additive rewards\n",
       "\n",
       "Stochastic Transition model needed to replace our deterministic transition model:\n",
       "\n",
       "- Transition model T(s, a, s') is written as a probability : p(s' | s, a) : the probability of arriving in state s' given that we are in state s and selected action a\n",
       "\n",
       "- We ignore past states : MARKOV property : the prob of arriving to next state only depends on the current state s, and not the history of earlier states.\n",
       "\n",
       "Reward function, R(s,a,s') : \n",
       "\n",
       "- We must also specify a utility/reward function for agent. \n",
       "\n",
       "- Can be pos/neg, but must be bounded by some max value. \n",
       "\n",
       "- Since decision process is sequential, must specify the utility f'n on a sequence of states and actions. \n",
       "\n",
       "- Instead of giving a reward only at goal states, agent can recieve a reward at each time step, based on transition from s to s' via action a.\n",
       "\n",
       "  - Can also receive a negative reward at each time step except for entering   terminal state\n",
       "\n",
       "- Rewards are additive (PERFORMANCE of agent in MDP = sum of rewards for the transition it makes)\n",
       "\n",
       "To find a sol'n to an MDP, we need : \n",
       "\n",
       "1. set of states, s E S\n",
       "\n",
       "2. set of actions, a E A\n",
       "\n",
       "3. Transition function T(s, a, s')\n",
       "\n",
       "  - Prob that executing action a in s will lead to s' = P(s'|s,a)\n",
       "\n",
       "  - probability is called a MODEL\n",
       "\n",
       "4. Reward function R(s,a,s')\n",
       "\n",
       "5. Initial state s_0\n",
       "\n",
       "6. [optional] terminal states\n",
       "\n",
       "Solution to an MDP is called a POLICY, $\\pi$.\n",
       "\n",
       "A policy maps from a state onto the action to take if the agent is in that state.\n",
       "\n",
       "$$\\pi (S) = a $$\n",
       "\n",
       "^ Policy tells the agent what action to take at the particular state s. \n",
       "\n",
       "Optimal policy : $\\pi$* is the OPTIMAL policy : finds action that maximizes \\ \n",
       "the expected utility of being in state s' from state s.\n",
       "\n",
       "  - Remember that our model is stochastic : even if same policy is executed   several times, this may lead to different ENVIRONMENT HISTORY (sequence of    states and actions), and thus a different score under the reward function.\n",
       "\n",
       "   - Therefore, we need to compute the expected utility of all the possible    paths generated by a policy.\n",
       "\n",
       "   - Utility = sum of (discounted) rewards\n",
       "\n",
       "DISCOUNTING : \n",
       "\n",
       "- Another factor that impacts optimal policy is that rewards now are preferred  to rewards later. \n",
       "\n",
       "  - Solution : Exponentially decay the values of rewards so that sooner rewards   have higher utility than later rewards, and to ensure our algo converges.\n",
       "\n",
       "  - $U([r_0, r_1, ...]) = r_0 + \\gamma r_1 + \\gamma ^{2} r_2 +....$ where   $0 < \\gamma < 1$\n",
       "\n",
       "  - This ensures that $U([r_0, r_1, ...]) = \\sum_{t = 0}^{\\inf} \\gamma ^{t} R_{t} \\leq R_{max}/(1 - \\gamma)$\n",
       "\n",
       "  - Smaller $\\gamma$ means smaller \"horizon\" - shorter-time focus\n",
       "\n",
       "- Another way we could avoid the issue of infinite utilities, ie if game lasts forever, is to set a Finite horizon (like depth-limited search) : \n",
       "    \n",
       "    - Terminate episodes after a fixed T steps\n",
       "\n",
       "    - Give nonstationary policies ($\\PI$ depends on time left)\n",
       "\n",
       "Representing MDPs : MDP SEARCH TREES\n",
       "\n",
       "- Each MDP state projects an expectimax-like search tree\n",
       "\n",
       "  - Transition f'n encodes probability\n",
       "\n",
       "  - Reward f'n given at each state of the tree\n",
       "\n",
       "  - Value (utility) of state s : V*(s) = expected utility starting in s and acting optimally\n",
       "\n",
       "  - Value (utility) of a q-state (s,a) : \n",
       "\n",
       "    - Q*(s,a) = expected utility starting out having taken action a from state s     and thereafter acting optimally\n",
       "\n",
       "  - Optimal policy : \n",
       "\n",
       "    - $\\pi$*(s) = optimal action from state s\n",
       "\n",
       "- Fundamental operation : compute the EXPECTIMAX value of a state\n",
       "\n",
       "  - $V*(s) = max_a Q*(s,a)$ = max of choosing any of these actions\n",
       "\n",
       "  - where $Q*(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]\n",
       "\n",
       "  So we have :\n",
       "$$V*(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "\n",
       "In order to avoid the issue that the tree can go on forever, can perform a depth-limited computation, with increasing depths until change is small. \n",
       "\n",
       "  - We don't care about deep parts of the tree if $\\gamma < 1$.\n",
       "\n",
       "Other issue : states can be repeated!\n",
       "\n",
       "  - To avoid this, only compute needed quantitites once. \n",
       "\n",
       "\n",
       " Now,\n",
       "\n",
       " HOW TO CHOOSE OPTIMAL OUTCOME : \n",
       "\n",
       " 3 algos : \n",
       "\n",
       " 1. Value iteration \n",
       "\n",
       " 2. Policy Evaluation\n",
       "\n",
       " 3. Policy Iteration\n",
       "\n",
       "\n",
       "--\n",
       "\n",
       "1. VALUE ITERATION : \n",
       "\n",
       "  - Start with $V_{0}(s) = 0$ : no time steps left means an expected reward sum = 0\n",
       "\n",
       "  - Given vectors of $V_k (s)$ values, do one ply of expectimax from each state : \n",
       "  $$V_{k+1}(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "\n",
       "  - Repeat until convergence\n",
       "\n",
       "- Complexity of each iteration : $O(S^2 A)$\n",
       "\n",
       "- Theorem : algo will CONVERGE to unique optimal values, because of discount factor!\n",
       "\n",
       "  - Approximations get refined towards optimal values\n",
       "\n",
       "  - Policy may converge long before values do\n",
       "\n",
       "- See eg on sheet\n",
       "\n",
       "- PROBLEMS with value iteration : \n",
       "\n",
       "  1. Slow :  $O(S^2 A)$ per iteration\n",
       "\n",
       "  2. The \"max\" at each state rarely changes\n",
       "\n",
       "  3. Policy converges long before values (but algo will keep going until values    converge even if not necessary)\n",
       "\n",
       "BELLMAN EQUATIONS : \n",
       "\n",
       "Definition of \"optimal utility\" via expectimax recurrence gives a simple one-steplookahead relationship amongst optimal utility values : \n",
       "\n",
       "$$V*(s) = max_a Q*(s,a)$$\n",
       "$$Q*(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "$$ \therefore V*(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "\n",
       "2. POLICY EVALUATION :\n",
       "\n",
       "- Evaluate by policy, not action : ie. if we fixed some policy, then the tree would be simpler as there would only be one action per state\n",
       "\n",
       "  - But tree's val would depend on which policy was taken. \n",
       "\n",
       "- Utility of state s under fixed policy $\\pi$ = $V^{\\pi}(s) = expected total discounted rewards starting in s and following $\\pi$.\n",
       "\n",
       "  - Using recusive Bellman Equation for one step look-ahead : \n",
       "\n",
       "  $$V_{0}^{\\pi} (s) = 0 //initial condition $$\n",
       "  $$V_{k+1}^{\\pi} (s) = \\sum_{s'} T(s,\\pi (s),s') [R(s, \\pi (s),s') + \\gamma V_{k}^{\\pi}(s')]$$\n",
       "\n",
       "  - Instead of calculating max, we sum over transitions and have $\\pi$(s) fixed.\n",
       "\n",
       "- Efficiency : $O(S^{2})$ per iteration.\n",
       "\n",
       "\n",
       "3. POLICY ITERATION : \n",
       "\n",
       "- Actions are easier to select from Q-values : $\\pi * (s) = argmax_a Q*(s,a)$\n",
       "\n",
       "- Is OPTIMAL, even if you start with any random policy! \n",
       "\n",
       "- Algo converges at an optimal policy.\n",
       "\n",
       "  1. Policy EVALUATION  : calculate utilities for some fixerd policy (not   necessarily optimal) until convergence\n",
       "\n",
       "  2. Policy IMPROVEMENT : update policy using one-step look ahead with resulting   converged (but not optimal!) utilities as future values (need to compare over   actions:)\n",
       "  $$\\pi_{i+1}(s) = argmax_a \\sum_{s'} T(s,a,s') [R(s, a,s') + \\gamma V^{\\pi}(s')]$$\n",
       "\n",
       "  3. Repeat steps until policy converges\n",
       "\n",
       "COMPARISON : \n",
       " \n",
       " - Both value iteration and policy iteration compute the same thing (all  optimal values)\n",
       "\n",
       " - In VALUE ITERATION : \n",
       "\n",
       "  - Every iteration updates both the values and (implicitly) the policy.\n",
       "\n",
       "  - We don't track the policy, but taking the max over actions implicitly   recomputes it\n",
       "\n",
       "- In POLICY ITERATION : \n",
       "\n",
       "  - Do several passes that update utilities with fixed policy (but each pass   is faster because we only consider one action, not all, so no need to take max of actions)\n",
       "\n",
       "  - After the policy is evaluated, a new policy is chosen (slow like a value   iteration pass)\n",
       "\n",
       "  - The new policy will be better (or converged = done)\n",
       "\n",
       "- BOTH ARE DYNAMIC PROGRAMS FOR SOLVING MDPs\n",
       "\n",
       "If you want to : \n",
       "\n",
       "- Compute optimal values -> Value OR Policy Iteration\n",
       "\n",
       "- Compute values for a particular policy -> Policy Evaluation\n",
       "\n",
       "- Turn values into a policy -> Policy Extraction (one-step look ahead)\n",
       "\n",
       "**they are ALL variations of the Bellman updates! All use one-step lookahead expectimax fragments, only differ in whether we plug in a fixed policy or amx over actions.\n",
       "\n",
       "--\n",
       "\n",
       "Principle of MAXIMUM EXPECtED UTILITY (MEU) : \n",
       "\n",
       "- A rational agent should choose the action that maximizes is expected utility,given its knowledge. \n",
       "\n",
       "- For worst-case minimax reasoning, terminal function scale doesn't matter\n",
       "\n",
       "  - We just want better states to have higher evals\n",
       "\n",
       "    - -> called INSENSITIVITY to monotonic transformations\n",
       "\n",
       "- For avg-case expectimax, we need magnitudes to be meaningful.\n",
       "\n",
       "UTILITIES : \n",
       "\n",
       "- [Def] Utilities are functions from outcomes (states of the world) to real numbers that describe an agent's preferences.\n",
       "\n",
       "- Preferences : An agent must either have preferences ($A > B$ or be indifferent (A ~ B)\n",
       "\n",
       "- Need some constraints on preferences before we call them rational, such as : \n",
       "\n",
       "  - AXIOM OF TRANSITIVITY : $(A > B) \\land (B > C) -> (A > C)$\n",
       "\n",
       "  - ORDERABILITY : $(A > B) \\lor (B > A) \\lor (A ~ B)$ Given 2 lotteries, a   rational agent must prefer one or rathem equal (cannot avoid deciding)\n",
       "\n",
       "  - CONTINUITY : $A > B > C -> for all p, [p, A; (1-p), C] ~ B$ (some lotery B    between A, C, there exists probability p that makes you indifferent to B)\n",
       "\n",
       "  - SUBSTITUTABILITY : $A ~ B -> [p, A; (1-p), C] ~ [p, B; (1-p), C]$ (if neither   prefer A, B, then some lottery in between that u have equal preference over that lottery)\n",
       "\n",
       "  - MONOTONICITY : $A > B -> (p \\geq q <-> [p, A; (1-p), B] \\geq [q, A; (1-q), B])$\n",
       "   (if A better than B, i prefer greater p than q)\n",
       "\n",
       "- Theorem : Rational preferences imply behavior describable as MEU\n",
       "\n",
       "- In the case of money : \n",
       "\n",
       "  - Money does NOT behave as a utility function, but we can talk about the utility   of having money (or being in debt)\n",
       "\n",
       "    - Given a lotter L = [p, USD X; (1-p), USD Y] : \n",
       "\n",
       "      - EXPECTD MONETARY VALUE $(EMV(L)) = p*X + (1-p) * Y$\n",
       "\n",
       "      - $U(L) = p*U(X) + (1-p)*U(Y)$\n",
       "\n",
       "      - Typically, $U(L) < U(EMV(L))$\n",
       "\n",
       "        - So people are risk averse, and when in debt are risk-prone\n",
       "\n",
       "      \n",
       "\n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Utility function** - Your definition here\n",
       "* **Expected utility** - your definition here\n",
       "* **Etc.** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "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",
    "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 =  \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
    "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
    "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
    "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
    "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
    "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module9_lecture_notes = \"\"\" \n",
    "In MDPs, we are given the Transition and reward functions.\n",
    "\n",
    "  - So solving MDPs required simply offline planning, where all quantities can \\\n",
    "  be computed given that we have the details. We don't actually need to play the game.\n",
    "\n",
    "In reinforcement learning, agent must learn both of these functions by interacting with \\\n",
    "the world.\n",
    "\n",
    "  - So now we don't know what the optimal policy is since we don't have the prob. distribution!\n",
    "\n",
    "Ideas in reinforcement learning : \n",
    "\n",
    "- EXPLORATION : have to try unknown actions to get info\n",
    "\n",
    "- EXPLOITATION : eventually, you have to use what you know to make decisions\n",
    "\n",
    "- REGRET : (measure of your total mistake cost : = expected rewards - optimal rewards. \\\n",
    "even if you learn intelligently, you make mistakes\n",
    "\n",
    "- SAMPLING : because of chance, you have to try things repeatedly\n",
    "\n",
    "- DIFFICULTY : learning can be much harder than solving a known MDP\n",
    "\n",
    "Basic Idea : \n",
    "\n",
    "- Recieve feedback in the form of rewards\n",
    "\n",
    "- Agent's utility is defined by the reward function.\n",
    "\n",
    "- Must learn to act so as to MAXIMIZE EXPECTED REWARDS\n",
    "\n",
    "- All learning is based on observed samples of outcomes\n",
    "\n",
    "Defining Reinforcement learning:\n",
    "\n",
    "- Still assume a MDP structure (with set of states S, set of actions A, model \\\n",
    "T(s,a,s'), reward f'n R(s,a,s'))\n",
    "\n",
    "- Still looking for policy $\\pi$ (s)\n",
    "\n",
    "- Don't know T or R (must learn)\n",
    "\n",
    "MODEL-BASED LEARNING : \n",
    "\n",
    "1. Learn empirical MDP Model : \n",
    "  \n",
    "  - Count outcomes s' for each (s,a)\n",
    "\n",
    "  - Normalize to give estimate of $ \\hat{T}(s,a,s')$\n",
    "\n",
    "  - Discover each $ \\hat{R}(s,a,s')$ when we experience (s,a,s')\n",
    "\n",
    "2. Solve the learned MVP (using techniques explored in Module 8)\n",
    "\n",
    "MODEL-FREE LEARNING : another way to do reinforcement learning:\n",
    "\n",
    "- Ie. passive reinforcement learning --> uses method called DIRECT EVALUATION\n",
    "\n",
    "- Goal : compute values for each state under a fixed $\\pi$. Still must execute the policy and learn from experience.\n",
    "\n",
    "  - Act accoridng to $\\pi$\n",
    "\n",
    "  - Every time you visit a state, write down what the sum of discounted rewards \\\n",
    "  turned out to be\n",
    "\n",
    "  - Average thse samples\n",
    "\n",
    "- What's GOOD with direct evaluation?\n",
    "\n",
    "  - easy to understand\n",
    "\n",
    "  - doesn't require any knowledge of T or R\n",
    "\n",
    "  - eventually computes correct avg values using sample transitions\n",
    "\n",
    "- What's BAD about it?\n",
    "\n",
    "  - wastes info about state connections\n",
    "\n",
    "  - states must be learned separately\n",
    "\n",
    "  - SO takes a long time to learn (need a lot of samples)\n",
    "\n",
    "Another approach : \n",
    "\n",
    "Why not use Policy Evaluation?\n",
    "\n",
    "TEMPORAL DIFFERENCE LEARNING\n",
    "\n",
    "- How can we use the Bellman Updates to calculate V for a fixed policy?\n",
    "\n",
    "  - We can get T and R from taking samples of outcomes s' by doing the action, and averaging. \n",
    "\n",
    "  - BUT we cannot guarantee we'll get to state s each n times!\n",
    "\n",
    "- So the big idea of TD earning : learn from every experience : \n",
    "\n",
    "  - Update V(s) each time we experience a transition (s,a,s', r)\n",
    "\n",
    "  - Likely outcome s' will contribute updates more often\n",
    "\n",
    "  - Policy still fixed, still doing evaluation\n",
    "\n",
    "  - Move values toward value of whatever successor occurs : running average\n",
    "\n",
    "  Sample of V(s) :\n",
    "\n",
    "$$ sample = R(s, \\pi (s), s\\) + \\gamma V^{\\pi}(s')$$\n",
    "    \n",
    "  Update to V(s) :\n",
    "\n",
    "$$V^{\\pi}(s) <- (1- \\alpha) V^{\\pi}(s) + (\\alpha) sample$$\n",
    "\n",
    "  Same update : \n",
    "\n",
    "$$V^{\\pi}(s) <- V^{\\pi}(s) + \\alpha(sample - V^{\\pi}(s))$$\n",
    "\n",
    "  - Exponential moving average : we wan to make recent samples more important, \\\n",
    "  so as to forget about the past (distance past values were wrong anyway)\n",
    "\n",
    "    - SO need a decreasing learning rate ( $\\alpha$ ) to give converging avgs : \n",
    "\n",
    "  - PROBLEMS with TD value learning : \n",
    "\n",
    "    - If we want to turn values into a NEW policy, we can't!\n",
    "\n",
    "    - We need to learn the Q-values, not values! Since $\\pi (s) = argmax_a Q(s,a)$\n",
    "\n",
    "How to find Q-values : \n",
    "\n",
    "Q-VALUE ITERATION\n",
    "\n",
    "- Use Bellman equ'n again to caluclate Q-values : \n",
    "\n",
    "  - Start with $Q_{0}(s,a) = 0$, which we know is right.\n",
    "\n",
    "  - Given $Q_k$, calculate the depth k+1 Q-vals for all Q-states : \n",
    "  $$Q_{k+1}(s,a) <- \\sum_{s'} T(s,a,s') [R(s, a, s') + \\gamma max_{a'}Q_k(s',a')]$$\n",
    "\n",
    "  - At each action, estimates of value of being in a Q state improves.\n",
    "\n",
    "  - Learn Q(s,a) values as you go : \n",
    "\n",
    "    - Receive sample (s,a,s',r)\n",
    "\n",
    "    - Consider old estimate : Q(s,a)\n",
    "\n",
    "    - Consider new sample estimate : $sample = R(s,a,s') + \\gamma max_{a'}Q(s',a')$\n",
    "\n",
    "    - Incorporate new estimate into a running avg : $Q(s,a) <- (1- \\alpha) Q(s,a) + \\alpha [sample]$\n",
    "\n",
    "      - Alpha parameter = how much we \"trust\" new info vs sample\n",
    "\n",
    "Results of Q-learning Properties : \n",
    "\n",
    "- Q-Learning converges to optimal policy EVEN IF ACTING SUBOPTIMALLY! --> OFF-POLICY LEARNING\n",
    "\n",
    "BUT, caveats : \n",
    "\n",
    "  - Have to explore enough\n",
    "\n",
    "  - have to eventually make the learning rate small enough, but not decrease too quickly\n",
    "\n",
    "Tradeoff between EXPLORATION VS EXPOITATION : \n",
    "\n",
    "- How to know when to explore new stuff (uncertain) or use existing stuff (certain)?\n",
    "\n",
    "- Exploration Function : \n",
    "\n",
    "  - Idea : explore areas whose badness is not yet established (ie. favour unvisited states)\n",
    "\n",
    "  - Take a value estimate u and a visit count n, and return an optimistic utility : \\\n",
    "  f(u,n) = u + k/n.\n",
    "\n",
    "    - n = number of times visited that state\n",
    "\n",
    "    - higher n = more certain about u; we want to factor this in.\n",
    "\n",
    "  - Modified Q-update : \n",
    "  \n",
    "  $$Q(s,a) <-_{\\alpha} R(s, a, s') + \\gamma max_{a'}f(Q(s',a'), N(s', a'))$$\n",
    "\n",
    "    - when n is small, we get a bonus when exploring.   \n",
    "\n",
    "  - This propagates the \"bonus\" back to states that lead to unknown states as well  \n",
    "\n",
    "  - We wish to minimize regret (which requires optimally learning to be optimal)\n",
    "\n",
    "    - Random exploration has more regret than exploration functions\n",
    "\n",
    "Now, we can't learn ALL states if there are too many, so we approximate for states : \n",
    "\n",
    "APPROXIMATE Q-LEARNING\n",
    "\n",
    "- Basic Q-Learning keeps a table of all q-vals, but in reality we can't learn \\\n",
    "about every single state! (too amny states to visit them all and to held in mem)\n",
    "\n",
    "- Instead, we wish to GENERALIZE : \n",
    "\n",
    "  - Learn about small number of training states from experience\n",
    "\n",
    "  - Generalize experience to new, similar situations\n",
    "\n",
    "  $$Q(s,a) = w_1 f_1(s,a) + ... + w_n f_n (s,a)$$\n",
    "\n",
    "- Advantage : experience summed up in a few powerful numbers\n",
    "\n",
    "- Disadvantage : states may share features but actually be very different in value\n",
    "\n",
    "- Q-learning with linear Q-functions;\n",
    "\n",
    "    - Transition = (s,a,r,s')\n",
    "\n",
    "    - difference = error term = $ [r + \\gamma max_{a'} Q(s',a')] - Q(s,a) $\n",
    "\n",
    "    - $Q(s,a) <- Q(s,a) + \\alpha[difference]$ (Exact Qs)\n",
    "\n",
    "      - $w_i = w_i + \\alpha[difference]f_i(s,a)$ (Approximate Qs)\n",
    "\n",
    "- Intuitive interpretation : \n",
    "\n",
    "  - Adjust weights of active features; ie. if something unexpectedly bad happens, \\\n",
    "  blame the features that were on : disprefer all states with that state's features. \n",
    "\n",
    "    - Eg. pacman : if near a ghost and you die, then start disprefering all states \\\n",
    "    where you're near a ghost.\n",
    "\n",
    "\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module9_definitions = {\n",
    "\"term\" : \"your definition here\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3201
    },
    "id": "ydOK__lwWgdp",
    "outputId": "71410c13-c603-4175-e79e-3d8560d471b6"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       " Your summary here \n",
       "\n",
       "## Module 9 Lecture Notes\n",
       " \n",
       "In MDPs, we are given the Transition and reward functions.\n",
       "\n",
       "  - So solving MDPs required simply offline planning, where all quantities can   be computed given that we have the details. We don't actually need to play the game.\n",
       "\n",
       "In reinforcement learning, agent must learn both of these functions by interacting with the world.\n",
       "\n",
       "  - So now we don't know what the optimal policy is since we don't have the prob. distribution!\n",
       "\n",
       "Ideas in reinforcement learning : \n",
       "\n",
       "- EXPLORATION : have to try unknown actions to get info\n",
       "\n",
       "- EXPLOITATION : eventually, you have to use what you know to make decisions\n",
       "\n",
       "- REGRET : (measure of your total mistake cost : = expected rewards - optimal rewards. even if you learn intelligently, you make mistakes\n",
       "\n",
       "- SAMPLING : because of chance, you have to try things repeatedly\n",
       "\n",
       "- DIFFICULTY : learning can be much harder than solving a known MDP\n",
       "\n",
       "Basic Idea : \n",
       "\n",
       "- Recieve feedback in the form of rewards\n",
       "\n",
       "- Agent's utility is defined by the reward function.\n",
       "\n",
       "- Must learn to act so as to MAXIMIZE EXPECTED REWARDS\n",
       "\n",
       "- All learning is based on observed samples of outcomes\n",
       "\n",
       "Defining Reinforcement learning:\n",
       "\n",
       "- Still assume a MDP structure (with set of states S, set of actions A, model T(s,a,s'), reward f'n R(s,a,s'))\n",
       "\n",
       "- Still looking for policy $\\pi$ (s)\n",
       "\n",
       "- Don't know T or R (must learn)\n",
       "\n",
       "MODEL-BASED LEARNING : \n",
       "\n",
       "1. Learn empirical MDP Model : \n",
       "  \n",
       "  - Count outcomes s' for each (s,a)\n",
       "\n",
       "  - Normalize to give estimate of $ \\hat{T}(s,a,s')$\n",
       "\n",
       "  - Discover each $ \\hat{R}(s,a,s')$ when we experience (s,a,s')\n",
       "\n",
       "2. Solve the learned MVP (using techniques explored in Module 8)\n",
       "\n",
       "MODEL-FREE LEARNING : another way to do reinforcement learning:\n",
       "\n",
       "- Ie. passive reinforcement learning --> uses method called DIRECT EVALUATION\n",
       "\n",
       "- Goal : compute values for each state under a fixed $\\pi$. Still must execute the policy and learn from experience.\n",
       "\n",
       "  - Act accoridng to $\\pi$\n",
       "\n",
       "  - Every time you visit a state, write down what the sum of discounted rewards   turned out to be\n",
       "\n",
       "  - Average thse samples\n",
       "\n",
       "- What's GOOD with direct evaluation?\n",
       "\n",
       "  - easy to understand\n",
       "\n",
       "  - doesn't require any knowledge of T or R\n",
       "\n",
       "  - eventually computes correct avg values using sample transitions\n",
       "\n",
       "- What's BAD about it?\n",
       "\n",
       "  - wastes info about state connections\n",
       "\n",
       "  - states must be learned separately\n",
       "\n",
       "  - SO takes a long time to learn (need a lot of samples)\n",
       "\n",
       "Another approach : \n",
       "\n",
       "Why not use Policy Evaluation?\n",
       "\n",
       "TEMPORAL DIFFERENCE LEARNING\n",
       "\n",
       "- How can we use the Bellman Updates to calculate V for a fixed policy?\n",
       "\n",
       "  - We can get T and R from taking samples of outcomes s' by doing the action, and averaging. \n",
       "\n",
       "  - BUT we cannot guarantee we'll get to state s each n times!\n",
       "\n",
       "- So the big idea of TD earning : learn from every experience : \n",
       "\n",
       "  - Update V(s) each time we experience a transition (s,a,s', r)\n",
       "\n",
       "  - Likely outcome s' will contribute updates more often\n",
       "\n",
       "  - Policy still fixed, still doing evaluation\n",
       "\n",
       "  - Move values toward value of whatever successor occurs : running average\n",
       "\n",
       "  Sample of V(s) :\n",
       "\n",
       "$$ sample = R(s, \\pi (s), s\\) + \\gamma V^{\\pi}(s')$$\n",
       "    \n",
       "  Update to V(s) :\n",
       "\n",
       "$$V^{\\pi}(s) <- (1- \u0007lpha) V^{\\pi}(s) + (\u0007lpha) sample$$\n",
       "\n",
       "  Same update : \n",
       "\n",
       "$$V^{\\pi}(s) <- V^{\\pi}(s) + \u0007lpha(sample - V^{\\pi}(s))$$\n",
       "\n",
       "  - Exponential moving average : we wan to make recent samples more important,   so as to forget about the past (distance past values were wrong anyway)\n",
       "\n",
       "    - SO need a decreasing learning rate ( $\u0007lpha$ ) to give converging avgs : \n",
       "\n",
       "  - PROBLEMS with TD value learning : \n",
       "\n",
       "    - If we want to turn values into a NEW policy, we can't!\n",
       "\n",
       "    - We need to learn the Q-values, not values! Since $\\pi (s) = argmax_a Q(s,a)$\n",
       "\n",
       "How to find Q-values : \n",
       "\n",
       "Q-VALUE ITERATION\n",
       "\n",
       "- Use Bellman equ'n again to caluclate Q-values : \n",
       "\n",
       "  - Start with $Q_{0}(s,a) = 0$, which we know is right.\n",
       "\n",
       "  - Given $Q_k$, calculate the depth k+1 Q-vals for all Q-states : \n",
       "  $$Q_{k+1}(s,a) <- \\sum_{s'} T(s,a,s') [R(s, a, s') + \\gamma max_{a'}Q_k(s',a')]$$\n",
       "\n",
       "  - At each action, estimates of value of being in a Q state improves.\n",
       "\n",
       "  - Learn Q(s,a) values as you go : \n",
       "\n",
       "    - Receive sample (s,a,s',r)\n",
       "\n",
       "    - Consider old estimate : Q(s,a)\n",
       "\n",
       "    - Consider new sample estimate : $sample = R(s,a,s') + \\gamma max_{a'}Q(s',a')$\n",
       "\n",
       "    - Incorporate new estimate into a running avg : $Q(s,a) <- (1- \u0007lpha) Q(s,a) + \u0007lpha [sample]$\n",
       "\n",
       "      - Alpha parameter = how much we \"trust\" new info vs sample\n",
       "\n",
       "Results of Q-learning Properties : \n",
       "\n",
       "- Q-Learning converges to optimal policy EVEN IF ACTING SUBOPTIMALLY! --> OFF-POLICY LEARNING\n",
       "\n",
       "BUT, caveats : \n",
       "\n",
       "  - Have to explore enough\n",
       "\n",
       "  - have to eventually make the learning rate small enough, but not decrease too quickly\n",
       "\n",
       "Tradeoff between EXPLORATION VS EXPOITATION : \n",
       "\n",
       "- How to know when to explore new stuff (uncertain) or use existing stuff (certain)?\n",
       "\n",
       "- Exploration Function : \n",
       "\n",
       "  - Idea : explore areas whose badness is not yet established (ie. favour unvisited states)\n",
       "\n",
       "  - Take a value estimate u and a visit count n, and return an optimistic utility :   f(u,n) = u + k/n.\n",
       "\n",
       "    - n = number of times visited that state\n",
       "\n",
       "    - higher n = more certain about u; we want to factor this in.\n",
       "\n",
       "  - Modified Q-update : \n",
       "  \n",
       "  $$Q(s,a) <-_{\u0007lpha} R(s, a, s') + \\gamma max_{a'}f(Q(s',a'), N(s', a'))$$\n",
       "\n",
       "    - when n is small, we get a bonus when exploring.   \n",
       "\n",
       "  - This propagates the \"bonus\" back to states that lead to unknown states as well  \n",
       "\n",
       "  - We wish to minimize regret (which requires optimally learning to be optimal)\n",
       "\n",
       "    - Random exploration has more regret than exploration functions\n",
       "\n",
       "Now, we can't learn ALL states if there are too many, so we approximate for states : \n",
       "\n",
       "APPROXIMATE Q-LEARNING\n",
       "\n",
       "- Basic Q-Learning keeps a table of all q-vals, but in reality we can't learn about every single state! (too amny states to visit them all and to held in mem)\n",
       "\n",
       "- Instead, we wish to GENERALIZE : \n",
       "\n",
       "  - Learn about small number of training states from experience\n",
       "\n",
       "  - Generalize experience to new, similar situations\n",
       "\n",
       "  $$Q(s,a) = w_1 f_1(s,a) + ... + w_n f_n (s,a)$$\n",
       "\n",
       "- Advantage : experience summed up in a few powerful numbers\n",
       "\n",
       "- Disadvantage : states may share features but actually be very different in value\n",
       "\n",
       "- Q-learning with linear Q-functions;\n",
       "\n",
       "    - Transition = (s,a,r,s')\n",
       "\n",
       "    - difference = error term = $ [r + \\gamma max_{a'} Q(s',a')] - Q(s,a) $\n",
       "\n",
       "    - $Q(s,a) <- Q(s,a) + \u0007lpha[difference]$ (Exact Qs)\n",
       "\n",
       "      - $w_i = w_i + \u0007lpha[difference]f_i(s,a)$ (Approximate Qs)\n",
       "\n",
       "- Intuitive interpretation : \n",
       "\n",
       "  - Adjust weights of active features; ie. if something unexpectedly bad happens,   blame the features that were on : disprefer all states with that state's features. \n",
       "\n",
       "    - Eg. pacman : if near a ghost and you die, then start disprefering all states     where you're near a ghost.\n",
       "\n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Term** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "\n",
    "module9_sections = [\n",
    "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
    "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
    "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
    "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
    "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
    "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
    "]\n",
    "\n",
    "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
    "display(Markdown(module9_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 10 - Probabilities and Language Models"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
    "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
    "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
    "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
    "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
    "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
    "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
    "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
    "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
    "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
    "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
    "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module10_lecture_notes = \"\"\" \n",
    "\n",
    "CONDITIONAL INDEPENDENCE : is a property of a distribution\n",
    "\n",
    "X and Y are INDEPENDENT if $$ for all x, y, P(x,y) = P(x)P(y) $$\n",
    "\n",
    "X and Y are CONDITIONALLY INDEPENDENT given Z if \n",
    "$$ for all x, y, z, P(x, y, z) = P(x|z)P(y|Z) $$\n",
    "\n",
    "BAYES RULE : \n",
    "$$P(A|B) =  (P(B|A)*P(A)) /P(B)$$\n",
    "\n",
    "Axioms of Probability : \n",
    "\n",
    "1. Prob is between 0 and 1\n",
    "\n",
    "2. Total prob of the set of all possible worlds = 1\n",
    "\n",
    "UNCERTAINTY\n",
    "\\n Observed Variables (evidence): agent knows certain things about state of world (e.g. sensor readings) \n",
    "\\n Unobserved Variables (states): agent needs to reason about other aspects (e.g. where object is) \n",
    "\\n Model: agent knows somethign about how the known variables relate to the unknown variables \n",
    "\\n Joint distribution (e.g. $P(X_1=x_1, X_2=x_2)$) - can calculate the probability of any event\n",
    "\\n Marginal Distributions are sumtables which elimiate variables (Marginalization=summing out: combine collapsed rows by adding)\n",
    "\\n Conditional Probabilities; simple relation between joint and conditional probabilities\n",
    "$$P(a|b) = P(a,b)/P(b)$$\n",
    "\n",
    "PROBABILISTIC INFERENCE: \n",
    "\n",
    "- compute a desired probability from other known probabilities (e.g conditional from joint)\n",
    "\n",
    "- We generally compute conditional probabilities (represent the agent's beliefs given the evidence) \n",
    "\n",
    "- Probabilities change with new evidence (observing new evidence causes beliefs to be updated)\n",
    "\n",
    "\n",
    "\\n INFERENCE BY ENUMERATION: we want $P(Q|e_1...e_k)$\n",
    "1. Select entries consistent w/evidence\n",
    "\n",
    "2. Sum out hidden variables to get joint of query and evidence.\n",
    "\n",
    "3. normalize \n",
    "\n",
    "\\n CHAIN RULE: write any joint distribution as an incremental product of conditional distributions \n",
    "\\n $P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2) $\n",
    "\\n = $P(x_1,..., x_n)\\prod_{i}^{} P(x_i|x_1....x_{i-1})$\n",
    "\n",
    "BAYES RULE : \n",
    "  \n",
    "  - $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
    "\n",
    "  - Helpful to build one conditional from its reverse; often times one conditional is \\\n",
    "  much simpler than the other\n",
    "\n",
    "\\n\n",
    "\n",
    "\\n PROBABILISTIC LANGUAGE MODELS: goal-assign a probability to a sentence\n",
    "\n",
    "\\n (1) autocomplete for texting (2) machine translation (3) spelling correction (4) speech recognition\n",
    "\\n PROBABILISTIC LANGUAGE MODELING: \n",
    "\\n Goal: compute probability of a sentence or seq of words $P(W) = P(w_1...w_n)$\n",
    "\\n Related Task: probability of an upcoming word $P(w_5|w_1...w_4)$\n",
    "\\n Model that computes either of these, $P(W) or P(w_n | w_1...w_{n-1})$ is a LANGUAGE MODEL\n",
    "\\n Compute this joint probability using chain rule \n",
    "\n",
    "\\n CHAIN RULE\n",
    "\\n Recall: P(B|A) = P(A, B) / P(A) ---> P(A, B) = P(A)P(B|A) \n",
    "\\n Chain rule in general: $P(x_1, x_2,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2)..P(x_n|x_1,x_2,...x_{n-1})$\n",
    "\n",
    "Joint prob of words in a sentence: $P(w_1w_2w_3..w_n) = \\prod_{i}^{} P(w_i|w_1w_2...w_{i-1})$\n",
    "\n",
    "We can make a MARKOV ASSUMPTION that we only care about the previous k words, not the whole context : \n",
    "\n",
    "$P(w_1w_2w_3..w_n) = \\prod_{i}^{n} P(w_i|w_{i-k}...w_{i-1})$, where k = # of context words to take into account\n",
    "\n",
    "\n",
    "\n",
    "\\n EXTRA NOTES:\n",
    "\\n If process is stationary, the conditional probability table does not change over time \n",
    "\\n Dynamic Bayesian Model (DBN), uncessary for construction: multiple state and evidence variables\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module10_definitions = {\n",
    "\"term\" : \"your definition here\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 2261
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "80e12dcd-00c6-4322-f76b-064fb02d534e"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       " Your summary here \n",
       "\n",
       "## Module 10 Lecture Notes\n",
       " \n",
       "\n",
       "CONDITIONAL INDEPENDENCE : is a property of a distribution\n",
       "\n",
       "X and Y are INDEPENDENT if $$ for all x, y, P(x,y) = P(x)P(y) $$\n",
       "\n",
       "X and Y are CONDITIONALLY INDEPENDENT given Z if \n",
       "$$ for all x, y, z, P(x, y, z) = P(x|z)P(y|Z) $$\n",
       "\n",
       "BAYES RULE : \n",
       "$$P(A|B) =  (P(B|A)*P(A)) /P(B)$$\n",
       "\n",
       "Axioms of Probability : \n",
       "\n",
       "1. Prob is between 0 and 1\n",
       "\n",
       "2. Total prob of the set of all possible worlds = 1\n",
       "\n",
       "UNCERTAINTY\n",
       "\n",
       " Observed Variables (evidence): agent knows certain things about state of world (e.g. sensor readings) \n",
       "\n",
       " Unobserved Variables (states): agent needs to reason about other aspects (e.g. where object is) \n",
       "\n",
       " Model: agent knows somethign about how the known variables relate to the unknown variables \n",
       "\n",
       " Joint distribution (e.g. $P(X_1=x_1, X_2=x_2)$) - can calculate the probability of any event\n",
       "\n",
       " Marginal Distributions are sumtables which elimiate variables (Marginalization=summing out: combine collapsed rows by adding)\n",
       "\n",
       " Conditional Probabilities; simple relation between joint and conditional probabilities\n",
       "$$P(a|b) = P(a,b)/P(b)$$\n",
       "\n",
       "PROBABILISTIC INFERENCE: \n",
       "\n",
       "- compute a desired probability from other known probabilities (e.g conditional from joint)\n",
       "\n",
       "- We generally compute conditional probabilities (represent the agent's beliefs given the evidence) \n",
       "\n",
       "- Probabilities change with new evidence (observing new evidence causes beliefs to be updated)\n",
       "\n",
       "\n",
       "\n",
       " INFERENCE BY ENUMERATION: we want $P(Q|e_1...e_k)$\n",
       "1. Select entries consistent w/evidence\n",
       "\n",
       "2. Sum out hidden variables to get joint of query and evidence.\n",
       "\n",
       "3. normalize \n",
       "\n",
       "\n",
       " CHAIN RULE: write any joint distribution as an incremental product of conditional distributions \n",
       "\n",
       " $P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2) $\n",
       "\n",
       " = $P(x_1,..., x_n)\\prod_{i}^{} P(x_i|x_1....x_{i-1})$\n",
       "\n",
       "BAYES RULE : \n",
       "  \n",
       "  - $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
       "\n",
       "  - Helpful to build one conditional from its reverse; often times one conditional is   much simpler than the other\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       " PROBABILISTIC LANGUAGE MODELS: goal-assign a probability to a sentence\n",
       "\n",
       "\n",
       " (1) autocomplete for texting (2) machine translation (3) spelling correction (4) speech recognition\n",
       "\n",
       " PROBABILISTIC LANGUAGE MODELING: \n",
       "\n",
       " Goal: compute probability of a sentence or seq of words $P(W) = P(w_1...w_n)$\n",
       "\n",
       " Related Task: probability of an upcoming word $P(w_5|w_1...w_4)$\n",
       "\n",
       " Model that computes either of these, $P(W) or P(w_n | w_1...w_{n-1})$ is a LANGUAGE MODEL\n",
       "\n",
       " Compute this joint probability using chain rule \n",
       "\n",
       "\n",
       " CHAIN RULE\n",
       "\n",
       " Recall: P(B|A) = P(A, B) / P(A) ---> P(A, B) = P(A)P(B|A) \n",
       "\n",
       " Chain rule in general: $P(x_1, x_2,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2)..P(x_n|x_1,x_2,...x_{n-1})$\n",
       "\n",
       "Joint prob of words in a sentence: $P(w_1w_2w_3..w_n) = \\prod_{i}^{} P(w_i|w_1w_2...w_{i-1})$\n",
       "\n",
       "We can make a MARKOV ASSUMPTION that we only care about the previous k words, not the whole context : \n",
       "\n",
       "$P(w_1w_2w_3..w_n) = \\prod_{i}^{n} P(w_i|w_{i-k}...w_{i-1})$, where k = # of context words to take into account\n",
       "\n",
       "\n",
       "\n",
       "\n",
       " EXTRA NOTES:\n",
       "\n",
       " If process is stationary, the conditional probability table does not change over time \n",
       "\n",
       " Dynamic Bayesian Model (DBN), uncessary for construction: multiple state and evidence variables\n",
       "\n",
       " \n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Term** - your definition here\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module10_sections = [\n",
    "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
    "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
    "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
    "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
    "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
    "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
    "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
    "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
    "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
    "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
    "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
    "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
    "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
    "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
    "]\n",
    "\n",
    "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
    "display(Markdown(module10_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
    "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module11_lecture_notes = \"\"\" \n",
    "Bayes Nets : \n",
    "We make use of conditional independence assumptions to model the world. \n",
    "Why? Because using full joint distribution tables as our probabilistic model is too hard : \n",
    "\n",
    "1. Joint is way too big to represent explicitly\n",
    "\n",
    "2. Hard to learn (estimate) anything empirically about more than a few variables at a time.\n",
    "\n",
    "3. Conditional independence is our most basic and robust form of knowledge about uncertain environments. \\\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Bayes nets are a technique for describing complex joint distributions (models) using simple, local \\\n",
    " distributions (conditional probabilities)\n",
    " - we describe how variable locally interact in a chain together to give global, \\\n",
    " indirect interactions. \n",
    "\n",
    " Graphical Model Notation of a Bayes Net : \n",
    " - Nodes : variables (with domains). Can be assigned (observed) or unassigned (unobserved).\n",
    " - Arcs : interactions. Ie. direct influence between variabels : encode conditional independence. \\\n",
    "\n",
    "\n",
    "Probabilities in BNs : \n",
    "We are guaranteed that $$P(x_{1}, ..., x_{n}) = \\prod_{i = 1}^{n} P(x_{i} | parents(X_{i}))$$ \\\n",
    "results in a proper joint distribution because of the CHAIN RULE and assuming conditional independence : \\\n",
    "\n",
    "- Chain rule : $P(x_{1}, ..., x_{n}) = \\prod_{i = 1}^{n} P(x_{i} | (X_{1},...,X_{i-1})$ \\\n",
    "\n",
    "- Assume conditional independences : $P(x_{1}, ..., x_{n}) = P(x_{i} | parents(X_{i})$\n",
    "\n",
    "NOTE : Not every BN can represent every joint distribution (topology enforces \\\n",
    "certain conditional independencies).\n",
    "- BNs don't actually need to be causal. \n",
    "  - sometimes no causal net exists over the domain (esp if variables are missing) \\\n",
    "  - end up with arrows that reflext corrolation, not causation \\\n",
    "- What do the arrows really mean :\\\n",
    "  - Topology may happen to encode causal structure \\\n",
    "  - Topology really encodes conditional independence \\\n",
    "\n",
    "SIZE of BNs :\n",
    "\n",
    "- Joint distribution over N boolean variables = $2^{N}$ \n",
    "\n",
    "- Size of N-node net if nodes have up to k parents : $O(N * 2^{k+1})$\n",
    "\n",
    "- BNs have huge space savings!\n",
    "\n",
    "D-Separation : \n",
    "\n",
    "Any complex BN example can be broken down into repetitions of the three \\\n",
    "canonical cases, to see if two variables are independent.\n",
    "\n",
    "1. CAUSAL CHAIN configuration : Z->Y->Z\n",
    "\n",
    "  - X NOT GUARANTEED INDEPENDENT OF Z : easy to find one example for which X \\\n",
    "  not independent of Z\n",
    "\n",
    "  - X IS guaranteed independent of Z given Y : suffices to show we can \\\n",
    "  write P(z|x, y) as P(z|x or P(z|y)) \n",
    "\n",
    "  $$P(z|x,y) = {P(x, y, z)} / {P(x,y)}$$\n",
    "  $$ = {P(x)P(y|x)P(z|y)} / {P(x)P(y|x)} \\\\from conditional indep' assumptions $$\n",
    "  $$ = P(z|y) $$\n",
    "\n",
    "2. COMMON CAUSE configuration : X <- Y -> Z\n",
    "\n",
    "  - X NOT GUARANTEED INDEPENDENT OF Z (since both due to common cause Y)\n",
    "\n",
    "  - X IS guaranteed independent of Z given Y : \n",
    "$$P(z|x,y) = {P(x, y, z)} / {P(x,y)}$$\n",
    "  $$ = {P(y)P(x|y)P(z|y)} / {P(y)P(x|y)} \\\\from conditional indep' assumptions $$\n",
    "  $$ = P(z|y) \\\\= YES $$\n",
    "\n",
    "3. COMMON EFFECT configuration : X -> Z <- Y\n",
    "\n",
    "  - X and Y ARE INDEPENDENT : they both impact z, but are not corrolated in any way\n",
    "\n",
    "  - X and Y are NOT indepentent given Z : since seeing Z means that both Z and Y \\\n",
    "are affected and competing as the explanation. \n",
    "\n",
    "  - This is backwards from other cases : observing an effect activates influence\\\n",
    "  between possible causes.\n",
    "\n",
    "D-separation algo : Given a BN structure, can run d-separation algo to build \\\n",
    "a complete list of conditional independences that are necesarily true\n",
    "\n",
    "1. Query : are X_i and X_j independent, given ${X_{k1},...,X_{kn}}$?\n",
    "\n",
    "2. CHeck all (undirected) paths between Xi and Xj \n",
    "\n",
    "  - If one or more path is active (ie each triple active), then independence NOT guaranteed\n",
    "\n",
    "  - Else, if all paths inactive, then independence guaranteed\n",
    "\n",
    "\n",
    "INFERENCE : **\\TODO : FINISH/EXPAND\n",
    "\n",
    "Calculating some useful quantity from a joint probability distribution.\n",
    "\n",
    "- Given unlimited time, inference in BNs is easy, but is very slow since \\\n",
    "we need to join up the whole joint distribution before we sum out the hidden variables.\n",
    "\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module11_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1635
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "ebe86e57-09ad-4713-ab9b-01911d13464d"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       " \n",
       "Bayes Nets : \n",
       "We make use of conditional independence assumptions to model the world. \n",
       "Why? Because using full joint distribution tables as our probabilistic model is too hard : \n",
       "\n",
       "1. Joint is way too big to represent explicitly\n",
       "\n",
       "2. Hard to learn (estimate) anything empirically about more than a few variables at a time.\n",
       "\n",
       "3. Conditional independence is our most basic and robust form of knowledge about uncertain environments. \n",
       "\n",
       "\n",
       "\n",
       "Bayes nets are a technique for describing complex joint distributions (models) using simple, local  distributions (conditional probabilities)\n",
       " - we describe how variable locally interact in a chain together to give global,  indirect interactions. \n",
       "\n",
       " Graphical Model Notation of a Bayes Net : \n",
       " - Nodes : variables (with domains). Can be assigned (observed) or unassigned (unobserved).\n",
       " - Arcs : interactions. Ie. direct influence between variabels : encode conditional independence. \n",
       "\n",
       "Probabilities in BNs : \n",
       "We are guaranteed that $$P(x_{1}, ..., x_{n}) = \\prod_{i = 1}^{n} P(x_{i} | parents(X_{i}))$$ results in a proper joint distribution because of the CHAIN RULE and assuming conditional independence : \n",
       "- Chain rule : $P(x_{1}, ..., x_{n}) = \\prod_{i = 1}^{n} P(x_{i} | (X_{1},...,X_{i-1})$ \n",
       "- Assume conditional independences : $P(x_{1}, ..., x_{n}) = P(x_{i} | parents(X_{i})$\n",
       "\n",
       "NOTE : Not every BN can represent every joint distribution (topology enforces certain conditional independencies).\n",
       "- BNs don't actually need to be causal. \n",
       "  - sometimes no causal net exists over the domain (esp if variables are missing)   - end up with arrows that reflext corrolation, not causation - What do the arrows really mean :  - Topology may happen to encode causal structure   - Topology really encodes conditional independence \n",
       "SIZE of BNs :\n",
       "\n",
       "- Joint distribution over N boolean variables = $2^{N}$ \n",
       "\n",
       "- Size of N-node net if nodes have up to k parents : $O(N * 2^{k+1})$\n",
       "\n",
       "- BNs have huge space savings!\n",
       "\n",
       "D-Separation : \n",
       "\n",
       "Any complex BN example can be broken down into repetitions of the three canonical cases, to see if two variables are independent.\n",
       "\n",
       "1. CAUSAL CHAIN configuration : Z->Y->Z\n",
       "\n",
       "  - X NOT GUARANTEED INDEPENDENT OF Z : easy to find one example for which X   not independent of Z\n",
       "\n",
       "  - X IS guaranteed independent of Z given Y : suffices to show we can   write P(z|x, y) as P(z|x or P(z|y)) \n",
       "\n",
       "  $$P(z|x,y) = {P(x, y, z)} / {P(x,y)}$$\n",
       "  $$ = {P(x)P(y|x)P(z|y)} / {P(x)P(y|x)} \\from conditional indep' assumptions $$\n",
       "  $$ = P(z|y) $$\n",
       "\n",
       "2. COMMON CAUSE configuration : X <- Y -> Z\n",
       "\n",
       "  - X NOT GUARANTEED INDEPENDENT OF Z (since both due to common cause Y)\n",
       "\n",
       "  - X IS guaranteed independent of Z given Y : \n",
       "$$P(z|x,y) = {P(x, y, z)} / {P(x,y)}$$\n",
       "  $$ = {P(y)P(x|y)P(z|y)} / {P(y)P(x|y)} \\from conditional indep' assumptions $$\n",
       "  $$ = P(z|y) \\= YES $$\n",
       "\n",
       "3. COMMON EFFECT configuration : X -> Z <- Y\n",
       "\n",
       "  - X and Y ARE INDEPENDENT : they both impact z, but are not corrolated in any way\n",
       "\n",
       "  - X and Y are NOT indepentent given Z : since seeing Z means that both Z and Y are affected and competing as the explanation. \n",
       "\n",
       "  - This is backwards from other cases : observing an effect activates influence  between possible causes.\n",
       "\n",
       "D-separation algo : Given a BN structure, can run d-separation algo to build a complete list of conditional independences that are necesarily true\n",
       "\n",
       "1. Query : are X_i and X_j independent, given ${X_{k1},...,X_{kn}}$?\n",
       "\n",
       "2. CHeck all (undirected) paths between Xi and Xj \n",
       "\n",
       "  - If one or more path is active (ie each triple active), then independence NOT guaranteed\n",
       "\n",
       "  - Else, if all paths inactive, then independence guaranteed\n",
       "\n",
       "\n",
       "INFERENCE : **\\TODO : FINISH/EXPAND\n",
       "\n",
       "Calculating some useful quantity from a joint probability distribution.\n",
       "\n",
       "- Given unlimited time, inference in BNs is easy, but is very slow since we need to join up the whole joint distribution before we sum out the hidden variables.\n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module11_sections = [\n",
    "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
    "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
    "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
    "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
    "]\n",
    "\n",
    "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
    "                         module11_sections, \n",
    "                         module11_definitions)\n",
    "display(Markdown(module11_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 12 - Naive Bayes and Perceptrons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
    "\n",
    "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
    "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module12_lecture_notes = \"\"\" \n",
    "MACHINE LEARNING BIG PICTURE :\n",
    "\n",
    "Up to now : how to use a model to make optimal decisions.\n",
    "\n",
    "ML : how to ACQUIRE A MODEL from data/experience\n",
    "\n",
    "- Learning parameters (ie. probabilities)\n",
    "\n",
    "- Learning structure (eg. BN graphs)\n",
    "\n",
    "- Learning hiddel concepts (eg. clustering)\n",
    "\n",
    "We cover a model-based classification with Naive Bayes and Perceptrons.\n",
    "\n",
    "Model-based Classification:\n",
    "\n",
    "- Build a model where both the label and features are random variables\n",
    "\n",
    "- Instantiate any observed features\n",
    "\n",
    "- Query for the distribution of the label conditioned on the features\n",
    "\n",
    "Challenges : What structure should BN have? How to learn its parameters?\n",
    "\n",
    "NAIVE BAYES : assume all features are INDEPENDENT EFFECTS of the label. \n",
    "\n",
    "While this is often too strong to perfectly represent reality, it is still \\\n",
    "helpful to easily estimate parameters of naive-based model.\n",
    "\n",
    "- We need to learn all the probability tables : prior prob, conditional prob.\n",
    "\n",
    "- General Naive Bayes model : has |Y| labels,  $|Y|*|F|^{n}$ values and \\\n",
    "$n*|F|*|Y|$ parameters.\n",
    "\n",
    "$$P(Y, F_{1},...,F_{n}) = P(Y) \\prod_{i} P(F_{i}|Y)$$\n",
    "\n",
    "Note : \n",
    "\n",
    "- we only have to specify how each feature depends on the CLASS. \n",
    "\n",
    "- Total number of params is LINEAR in number of features (PRO)\n",
    "\n",
    "- Model is very simplistic, but often works anyway\n",
    "\n",
    "INFERENCE for Naive Bayes : \n",
    "\n",
    "Goal : compute posterior distribution over label variable Y (see screenshot)\n",
    "\n",
    "1. get joint porbability of label and evidence for each label : \n",
    "\n",
    "  - $P(Y|f_{1},...,f_{n})$ = Joint probability table MATRIX of ($P(y_{i}, f_{1},...,f_{n})$) for all i in k)\n",
    "\n",
    "  - rewrite matrix using independence assumptions of Bayes net:\\\n",
    "\n",
    "$$P(y_{j} \\prod_{i} P(f_{i}| y_{j})) \\for j in k $$\n",
    "\n",
    "  - normalize by dividing by probability of evidence : $P(Y | f_{1},..,f_{n})$\n",
    "\n",
    "Next, we need ESTIMATES of local conditional probability tables : Both are\\\n",
    "denoted as the PARAMETERS of the model, $\\Theta$\n",
    "\n",
    "- P(Y) = prior probability over labels\n",
    "\n",
    "- $P(F_{i}|Y)$ : evidence variable for each feature\n",
    "\n",
    "These parameters are obtained from training data counts\n",
    "\n",
    "How data is used to obtain these parameters : Data split between training, \\\n",
    "held out, and test sets.\n",
    "\n",
    "1. Training data : should be a big chunk of your data. Used to learn parameters \\\n",
    "during Experimentation Cycle. \n",
    "\n",
    "2. Held out set : used for tuning hyperparameters\n",
    "\n",
    "3. Run model on test set, Compute accuracy (Evaluation Cycle)\n",
    "\n",
    "POTENTIAL ISSUES :\n",
    "\n",
    "1. OVERFITTING :fitting the training data very closely, but not generalized \\\n",
    "enough for other data\n",
    "\n",
    "2. UNDERFITTING : model does not find any trend in data\n",
    "\n",
    "Parameter estimation : use MAXIMUM LIKELIHOOD \n",
    "\n",
    "Relative frequencies are the maximum likelihood estimates : \n",
    "\n",
    "$$\\Theta _{ML} = argmax_{Theta} P(X| \\{Theta} )$$\n",
    "$$ = argmax_{Theta} \\prod_{i} P_{\\Theta}(X_{i})$$\n",
    "\n",
    "P(ML(x)) = count(x) / total samples.\n",
    "\n",
    "How to deal with avoiding zero probabilities?\n",
    "\n",
    "-> LAPLACE SMOOTHING : pretend you saw every outcome one more than you actually did.\n",
    "\n",
    "$$P_{LAP}(x) = C(x) + 1 / N + |X| $$\n",
    "\n",
    "Can also smooth with factor k.\n",
    "\n",
    "LaPlace smoothing for conditionals : \\\n",
    "\n",
    "$$P_{LAP}(x|y) = (C(x,y) + k) / (x(y) + k|X| $$\n",
    "\n",
    "An alternative to LaPlace smoothing : LINEAR INTERPOLATION\n",
    "\n",
    "- Which also gets the empirical P(X), given that estimate of P(X|Y) isn't too \\\n",
    "far from the empirical P(X). \\\n",
    "\n",
    "$$P_{LIN}(x|y) = \\alpha P_{hat}(x|y) + (1 - \\alpha)P_{hat}(x) $$\n",
    "\n",
    "- If alpha = 0 : no weight to conditional : just based on prior.\n",
    "\n",
    "- If alpha = 1 : same as MLE.\n",
    "\n",
    "CONFIDENCE from a classifier :\n",
    "\n",
    "Confidence of a probabilistic classifier : posterior over the top label\n",
    "\n",
    "- $confidence(x) = max_{y} P(y|x)$ : represents how SURE the classifier is of the \\\n",
    "classification\n",
    "\n",
    "- weak calibration : higher confidences = higher acuracy\n",
    "\n",
    "- strong calibration : confidence predicts accuracy rate\n",
    "\n",
    "What to do about errors : \n",
    "\n",
    "- Need more features!!\n",
    "\n",
    "/// NEW SECTION:\n",
    "\n",
    "PERCEPTRONS : \n",
    "\n",
    "Perceptrons = error-driven learning, does not use probabilities but WEIGHTS.\n",
    "\n",
    "Inputs are features representing something we wish to clasify. \n",
    "\n",
    "- Feature values for inputs are fixed\n",
    "\n",
    "- But we can choose different weight vectors, to get different classifiers. \n",
    "\n",
    "LINEAR classifiers : \n",
    "Inputs are feature values; each feature has a WEIGHT.\n",
    "\n",
    "Sum is the ACTIVATION.\n",
    "\n",
    "$$activation_{w}(x) = \\sum_{i} w_{i} * f_{i}(x) = w . f(x) $$\n",
    "\n",
    "- If activation + b > 0, pos : output is +1 (pos class)\n",
    "\n",
    "- If activation + b <0, neg : output is -1 (neg class)\n",
    "\n",
    "b = bias = -theshhold.\n",
    "\n",
    "In the binary case, we compare features to a weight vector. \n",
    "\n",
    "Learning : we need to figure out the weight vector from examples\n",
    "\n",
    "Binary Perceptron algorithm : we want to learn the weight vector.\n",
    "1. Start with weights = 0\n",
    "\n",
    "2. For each training instance ; \n",
    "  - Classify input with current weights\n",
    "\n",
    "  - If correct (y = y*), no change\n",
    "\n",
    "  - Else, if wrong : adjust the weight vector by adding or substracting the \\\n",
    "  feature vector. Substract if y* is -1. $w = w + y^{*} * f$.\n",
    "\n",
    "MULTICLASS for more than 2 labels : similar, but pick the label by \\\n",
    "calculating argmax of the activation of class y:\n",
    "1. Start with weights = 0\n",
    "\n",
    "2. For each training instance : \n",
    "  - Classify with current weights : $y = argmax_y w_y * f(x)$\n",
    "\n",
    "  - If correct, no change\n",
    "\n",
    "  - If wrong : LOWER score of WRONG answer, RAISE score of RIGHT  answer.\n",
    "\n",
    "    - $w_y = w_y - f(x)$ : lower score of wrong predicted\n",
    "\n",
    "    - $w_{y^{*}} = w_{y^{*}} + f(x)$ : raise score of right\n",
    "\n",
    "\n",
    "PROPERTIES of perceptrons : \n",
    "- SEPARABILITY : data is separable if some parameters get the training set \\\n",
    "perfectly correct.\n",
    "- CONVERGENCE : if training is separable, perceptron will eventually converge\\\n",
    "(binary case)\n",
    "- MISTAKE BOUND : the maximum number of mistakes (binary case) related to the \\\n",
    "'MARGIN'(or degree, or space between classes) of separability is bounded :\\\n",
    " $mistakes < \\frac{k}{margin^{2}}$\n",
    "\n",
    "\n",
    "PROBLEMS with the perceptron : \n",
    "1. NOISE : if the data is not separable, weights might thrash\n",
    "  - Sol : avg perceptron : avg weight vectors over time\n",
    "\n",
    "2. Mediocre generalization : finds the \"barely\" separable solution, but not the best.\n",
    "\n",
    "3. Overtraining : test accuracy peaks, then falls. Is a kind of overfitting.\n",
    "\n",
    "\n",
    "FIXING the perceptron : \n",
    "- MIRA : Margin-infused Relaxed Algorithm : chooses an update size that fixes \\\n",
    "the current mistake, but minimizes the change to w. \n",
    "\n",
    "$$min_{w} \\frac{1}{2} \\sum_{y} ||w_{y} - w'_{y}||^{2}$$ s.t.\n",
    "\n",
    "$$ w_{y^{*}} . f(x) >= w_{y} . f(x) + 1  /the +1 helps to generalize $$\n",
    "\n",
    "Maximum Step Size : \n",
    "- In practice, it's bad to make updates too large, esp. for non-separable data.\n",
    "  - Example may be labeled incorrectly\n",
    "  - May not have enough features\n",
    "\n",
    "- Sol : cap the maximum possible values of Tau with constant C\n",
    "  - Converges faster than perceptron, and better for noisy data\n",
    "\n",
    "For Linear separators, how to tell what the optimal one is?\n",
    "- SUPPORT VECTOR MACHINES : ie. MIRA but optimize over all examples at once, \n",
    "  - ie. minimize distance of point and separator for all data points\n",
    "\n",
    "\n",
    "OVERALL SUMMARY : Naive Bayes vs Perceptrons/MIRA:\n",
    "\n",
    "Naive Bayes:\n",
    "-  builds a modek training data, gives prediction probabilities.\n",
    "- strong assumptions about feature independence\n",
    "- one pass through data (counting)\n",
    "\n",
    "Perceptrons / MIRA : \n",
    "- Make less assumptions about data\n",
    "- Mistake-driven learning\n",
    "- multiple passes thorugh data(prediction)\n",
    "- often more accurate\n",
    "\"\"\"\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": 4257
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "c532fbea-5f4a-4161-83b0-243998694806"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       " Your summary here \n",
       "\n",
       "## Module 12 Lecture Notes\n",
       " \n",
       "MACHINE LEARNING BIG PICTURE :\n",
       "\n",
       "Up to now : how to use a model to make optimal decisions.\n",
       "\n",
       "ML : how to ACQUIRE A MODEL from data/experience\n",
       "\n",
       "- Learning parameters (ie. probabilities)\n",
       "\n",
       "- Learning structure (eg. BN graphs)\n",
       "\n",
       "- Learning hiddel concepts (eg. clustering)\n",
       "\n",
       "We cover a model-based classification with Naive Bayes and Perceptrons.\n",
       "\n",
       "Model-based Classification:\n",
       "\n",
       "- Build a model where both the label and features are random variables\n",
       "\n",
       "- Instantiate any observed features\n",
       "\n",
       "- Query for the distribution of the label conditioned on the features\n",
       "\n",
       "Challenges : What structure should BN have? How to learn its parameters?\n",
       "\n",
       "NAIVE BAYES : assume all features are INDEPENDENT EFFECTS of the label. \n",
       "\n",
       "While this is often too strong to perfectly represent reality, it is still helpful to easily estimate parameters of naive-based model.\n",
       "\n",
       "- We need to learn all the probability tables : prior prob, conditional prob.\n",
       "\n",
       "- General Naive Bayes model : has |Y| labels,  $|Y|*|F|^{n}$ values and $n*|F|*|Y|$ parameters.\n",
       "\n",
       "$$P(Y, F_{1},...,F_{n}) = P(Y) \\prod_{i} P(F_{i}|Y)$$\n",
       "\n",
       "Note : \n",
       "\n",
       "- we only have to specify how each feature depends on the CLASS. \n",
       "\n",
       "- Total number of params is LINEAR in number of features (PRO)\n",
       "\n",
       "- Model is very simplistic, but often works anyway\n",
       "\n",
       "INFERENCE for Naive Bayes : \n",
       "\n",
       "Goal : compute posterior distribution over label variable Y (see screenshot)\n",
       "\n",
       "1. get joint porbability of label and evidence for each label : \n",
       "\n",
       "  - $P(Y|f_{1},...,f_{n})$ = Joint probability table MATRIX of ($P(y_{i}, f_{1},...,f_{n})$) for all i in k)\n",
       "\n",
       "  - rewrite matrix using independence assumptions of Bayes net:\n",
       "$$P(y_{j} \\prod_{i} P(f_{i}| y_{j})) \f",
       "or j in k $$\n",
       "\n",
       "  - normalize by dividing by probability of evidence : $P(Y | f_{1},..,f_{n})$\n",
       "\n",
       "Next, we need ESTIMATES of local conditional probability tables : Both aredenoted as the PARAMETERS of the model, $\\Theta$\n",
       "\n",
       "- P(Y) = prior probability over labels\n",
       "\n",
       "- $P(F_{i}|Y)$ : evidence variable for each feature\n",
       "\n",
       "These parameters are obtained from training data counts\n",
       "\n",
       "How data is used to obtain these parameters : Data split between training, held out, and test sets.\n",
       "\n",
       "1. Training data : should be a big chunk of your data. Used to learn parameters during Experimentation Cycle. \n",
       "\n",
       "2. Held out set : used for tuning hyperparameters\n",
       "\n",
       "3. Run model on test set, Compute accuracy (Evaluation Cycle)\n",
       "\n",
       "POTENTIAL ISSUES :\n",
       "\n",
       "1. OVERFITTING :fitting the training data very closely, but not generalized enough for other data\n",
       "\n",
       "2. UNDERFITTING : model does not find any trend in data\n",
       "\n",
       "Parameter estimation : use MAXIMUM LIKELIHOOD \n",
       "\n",
       "Relative frequencies are the maximum likelihood estimates : \n",
       "\n",
       "$$\\Theta _{ML} = argmax_{Theta} P(X| \\{Theta} )$$\n",
       "$$ = argmax_{Theta} \\prod_{i} P_{\\Theta}(X_{i})$$\n",
       "\n",
       "P(ML(x)) = count(x) / total samples.\n",
       "\n",
       "How to deal with avoiding zero probabilities?\n",
       "\n",
       "-> LAPLACE SMOOTHING : pretend you saw every outcome one more than you actually did.\n",
       "\n",
       "$$P_{LAP}(x) = C(x) + 1 / N + |X| $$\n",
       "\n",
       "Can also smooth with factor k.\n",
       "\n",
       "LaPlace smoothing for conditionals : \n",
       "$$P_{LAP}(x|y) = (C(x,y) + k) / (x(y) + k|X| $$\n",
       "\n",
       "An alternative to LaPlace smoothing : LINEAR INTERPOLATION\n",
       "\n",
       "- Which also gets the empirical P(X), given that estimate of P(X|Y) isn't too far from the empirical P(X). \n",
       "$$P_{LIN}(x|y) = \u0007lpha P_{hat}(x|y) + (1 - \u0007lpha)P_{hat}(x) $$\n",
       "\n",
       "- If alpha = 0 : no weight to conditional : just based on prior.\n",
       "\n",
       "- If alpha = 1 : same as MLE.\n",
       "\n",
       "CONFIDENCE from a classifier :\n",
       "\n",
       "Confidence of a probabilistic classifier : posterior over the top label\n",
       "\n",
       "- $confidence(x) = max_{y} P(y|x)$ : represents how SURE the classifier is of the classification\n",
       "\n",
       "- weak calibration : higher confidences = higher acuracy\n",
       "\n",
       "- strong calibration : confidence predicts accuracy rate\n",
       "\n",
       "What to do about errors : \n",
       "\n",
       "- Need more features!!\n",
       "\n",
       "/// NEW SECTION:\n",
       "\n",
       "PERCEPTRONS : \n",
       "\n",
       "Perceptrons = error-driven learning, does not use probabilities but WEIGHTS.\n",
       "\n",
       "Inputs are features representing something we wish to clasify. \n",
       "\n",
       "- Feature values for inputs are fixed\n",
       "\n",
       "- But we can choose different weight vectors, to get different classifiers. \n",
       "\n",
       "LINEAR classifiers : \n",
       "Inputs are feature values; each feature has a WEIGHT.\n",
       "\n",
       "Sum is the ACTIVATION.\n",
       "\n",
       "$$activation_{w}(x) = \\sum_{i} w_{i} * f_{i}(x) = w . f(x) $$\n",
       "\n",
       "- If activation + b > 0, pos : output is +1 (pos class)\n",
       "\n",
       "- If activation + b <0, neg : output is -1 (neg class)\n",
       "\n",
       "b = bias = -theshhold.\n",
       "\n",
       "In the binary case, we compare features to a weight vector. \n",
       "\n",
       "Learning : we need to figure out the weight vector from examples\n",
       "\n",
       "Binary Perceptron algorithm : we want to learn the weight vector.\n",
       "1. Start with weights = 0\n",
       "\n",
       "2. For each training instance ; \n",
       "  - Classify input with current weights\n",
       "\n",
       "  - If correct (y = y*), no change\n",
       "\n",
       "  - Else, if wrong : adjust the weight vector by adding or substracting the   feature vector. Substract if y* is -1. $w = w + y^{*} * f$.\n",
       "\n",
       "MULTICLASS for more than 2 labels : similar, but pick the label by calculating argmax of the activation of class y:\n",
       "1. Start with weights = 0\n",
       "\n",
       "2. For each training instance : \n",
       "  - Classify with current weights : $y = argmax_y w_y * f(x)$\n",
       "\n",
       "  - If correct, no change\n",
       "\n",
       "  - If wrong : LOWER score of WRONG answer, RAISE score of RIGHT  answer.\n",
       "\n",
       "    - $w_y = w_y - f(x)$ : lower score of wrong predicted\n",
       "\n",
       "    - $w_{y^{*}} = w_{y^{*}} + f(x)$ : raise score of right\n",
       "\n",
       "\n",
       "PROPERTIES of perceptrons : \n",
       "- SEPARABILITY : data is separable if some parameters get the training set perfectly correct.\n",
       "- CONVERGENCE : if training is separable, perceptron will eventually converge(binary case)\n",
       "- MISTAKE BOUND : the maximum number of mistakes (binary case) related to the 'MARGIN'(or degree, or space between classes) of separability is bounded : $mistakes < \f",
       "rac{k}{margin^{2}}$\n",
       "\n",
       "\n",
       "PROBLEMS with the perceptron : \n",
       "1. NOISE : if the data is not separable, weights might thrash\n",
       "  - Sol : avg perceptron : avg weight vectors over time\n",
       "\n",
       "2. Mediocre generalization : finds the \"barely\" separable solution, but not the best.\n",
       "\n",
       "3. Overtraining : test accuracy peaks, then falls. Is a kind of overfitting.\n",
       "\n",
       "\n",
       "FIXING the perceptron : \n",
       "- MIRA : Margin-infused Relaxed Algorithm : chooses an update size that fixes the current mistake, but minimizes the change to w. \n",
       "\n",
       "$$min_{w} \f",
       "rac{1}{2} \\sum_{y} ||w_{y} - w'_{y}||^{2}$$ s.t.\n",
       "\n",
       "$$ w_{y^{*}} . f(x) >= w_{y} . f(x) + 1  /the +1 helps to generalize $$\n",
       "\n",
       "Maximum Step Size : \n",
       "- In practice, it's bad to make updates too large, esp. for non-separable data.\n",
       "  - Example may be labeled incorrectly\n",
       "  - May not have enough features\n",
       "\n",
       "- Sol : cap the maximum possible values of Tau with constant C\n",
       "  - Converges faster than perceptron, and better for noisy data\n",
       "\n",
       "For Linear separators, how to tell what the optimal one is?\n",
       "- SUPPORT VECTOR MACHINES : ie. MIRA but optimize over all examples at once, \n",
       "  - ie. minimize distance of point and separator for all data points\n",
       "\n",
       "\n",
       "OVERALL SUMMARY : Naive Bayes vs Perceptrons/MIRA:\n",
       "\n",
       "Naive Bayes:\n",
       "-  builds a modek training data, gives prediction probabilities.\n",
       "- strong assumptions about feature independence\n",
       "- one pass through data (counting)\n",
       "\n",
       "Perceptrons / MIRA : \n",
       "- Make less assumptions about data\n",
       "- Mistake-driven learning\n",
       "- multiple passes thorugh data(prediction)\n",
       "- often more accurate\n",
       "\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 5.1 Game Theory\", chapter19_1),\n",
    "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
    "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
    "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
    "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
    "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
    "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
    "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
    "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
    "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
    "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
    "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
    "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
    "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
    "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
    "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
    "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
    "]\n",
    "\n",
    "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
    "                         module12_sections, \n",
    "                         module12_definitions)\n",
    "display(Markdown(module12_markdown))"
   ]
  },
  {
   "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 = \"\"\" \"\"\"\n",
    "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
    "\n",
    "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module13_lecture_notes = \"\"\" \n",
    "Neural Networks, Big Picture : \n",
    "\n",
    "Essentially a bunch of stacked perceptrons, like \"neurons\" working together.\n",
    "\n",
    "Neural network has 4 Classifier components : \n",
    "1. Feature representation of the input : for each input observation $x^{i}, \\\n",
    "vector of features $[x_{1},..,x_{n}].\n",
    "\n",
    "2. Classification function : computes the estimated class $y^{\\^} via $p(y|x):\n",
    "- $y^{\\^} = max_{y}(P(y|x))$.\n",
    "\n",
    "3. Objective function : for learning : minimize error on training egs (ie. LOSS fn)\n",
    "\n",
    "4. Algorith for optimizing the objective function\n",
    "\n",
    "SENTIMENT CLASSIFIIER\n",
    "\n",
    "Consider input obs x represented by a vector of features [x_1, ..., x_n]. \n",
    "\n",
    "Classifier output y can be 1 (pos) or 0 (neg).. We wish to estimate P(y = 1 | x_vec).\n",
    "\n",
    "LOGISTIC REGRESSION solves this by learning from a training set a vector \\\n",
    "of weights and a bias term : \n",
    "$$z = \\sum_{i} w_{i}x_{i} + b = w . x + b \\ dot product $$\n",
    "\n",
    "We normalize z to be between 0 and 1 by passing it through a SIGMOID f'n \\\n",
    "(also called logistic f'n) : \n",
    "$$y = 1/(1+e^{-z}) $$\n",
    "\n",
    "So we have $P(y = 1) = \\sigma(w . x + b) = 1/(1+e^{-(w . x + b)})$\n",
    "\n",
    "DECISION BOUNDARY : how to make the decision? Set threshhold : \n",
    "\n",
    "$y_{hat} = 1, if P(y = 1|x) > 0.5, 0 otherwise $\n",
    "\n",
    "^ theshhold = 0.5.\n",
    "\n",
    "Another way we can analyse if pos or neg sentiment : FEATURE EXTRACTION\n",
    "\n",
    "We count the instances of each feature, and we give each a weight corresponding \\\n",
    "to how much they contribute to the class. \n",
    "\n",
    "Take dot product of features and weights to find z (z = w . x + b), and pass  \\\n",
    "through Sigmoid(Z).\n",
    "\n",
    "Next:\n",
    "\n",
    "LEARNING in logisit regression, ie. how to get the weights of the model : \n",
    "\n",
    "We learn the parameters (weights and bias) via learning, which requires : \n",
    "\n",
    "1. An objective, or LOSS function, that tells us the distance between the \\\n",
    "system output and the gold output. \n",
    "  - We use CROSS-ENTROPY LOSS.\n",
    "\n",
    "2. Algo for optimizing the objective function. \n",
    "  - We use STOCHASTIC GRADIENT DESCENT to minimize the Loss function.\n",
    "\n",
    "Loss functions: ie how much the classifier output (y^) is close to correct output (y).\n",
    "\n",
    "L(y^, y) = how much y^ differs from the true y. \n",
    "\n",
    "One eg. is Mean-Squared Error (MSE) : \n",
    "$$L_{MSE}(\\hat{y},y) = 1/2(\\hat{y} - y)^{2}$$\n",
    "\n",
    "Loss functions for probabilistic classification : \n",
    "\n",
    "We use a loss f'n that prefers the correct class labels of the training example \\\n",
    "to be more likely.\n",
    "\n",
    "Conditional max likelihood estimation : Choose params w_vec, b that MAXIMIZE \\\n",
    "the (log) probs of the true labels in the training data.\n",
    "\n",
    "Resulting loss function is the NEGATIVE LOG LIKELIHOOD loss ie. CROSS-ENTROPY LOSS.\n",
    "\n",
    "(directionality is preserved in log space)\n",
    "\n",
    "$$log p(y|x) = log[\\hat{y}^{y}(1-\\hat{y})^{1-y}]$$\n",
    "$$ = ylog \\hat{y}, + (1-y)log(1-\\hat{y})$$\n",
    "For loss function we want to minimize, so flip the sign and plug in our expression \\\n",
    "for y' : \n",
    "$$L_{CE}(\\hat{y}, y) = -log p(y|x) = -[y log \\sigma(w . x + b) + (1-y) log(1-\\sigma(w . x + b))]$$\n",
    "\n",
    "Why does minimizing the negative log probability work:?\n",
    "\n",
    "- We want the LOSS to be SMALLER if the model's estimate is close to correct,\n",
    "\n",
    "- and we want the loss to be BIGGER if it is confused.\n",
    "\n",
    "- -log of a small val becomes infinitely large\n",
    "\n",
    "Now, loss on ALL training exmpls : \n",
    "\n",
    "$$log p(training labels) = log \\prod_{i =1}^{m} p(y^{i} | x^{i}) $$\n",
    "$$ = \\sum_{i = 1}^{m} log p(y^{i} | x^{i}) $$\n",
    "$$ = - \\sum_{i = 1}^{m} L_{CE}(\\hat{y}^{i} | y^{i})$$\n",
    "\n",
    "\n",
    "Now, how to find good parameters : \n",
    "\n",
    "GRADIENT DESCENT to find good settings by minimizing loss function\n",
    "\n",
    "$$\\Theta = argmin_{\\Theta} 1/m \\sum_{i = 1}^{m} L_{CE}(y^{i}, x^{i}; \\Theta) $$\n",
    "\n",
    "Gradient descent is a method that finds a minimum of a function by figuring \\\n",
    "out in which direction (in the space of the parametres $\\Theta$ the f'ns \\\n",
    "slope is risinhg the most steeply, and moving in the opposite direction. \n",
    "\n",
    "CAN't get stuck on a local min :\n",
    "For logistic regression, the loss function is CONVEX = only one minimum! Great,\\\n",
    "we can't get stuck in a local minima. \n",
    "\n",
    "Gradient descent starting from any point is GUARANTEED to find the minimum.\n",
    "\n",
    "Size of learning rate, ie. magnitude of amount to move in gradient descent, \\\n",
    "is the value of the slope weighted by a learning rate $\\eta$\n",
    "\n",
    "A higher/faster learning rate = more w more on each step.\n",
    "\n",
    "$$w^{t + 1} = w^t - \\eta * d/dw (f(x;w))$$\n",
    "\n",
    " = old weight - eta (step size) * derivative (slope) of f'n \n",
    "\n",
    " NOW, for many dimensions:\n",
    "\n",
    " each dimension will impact the loss f'n.\n",
    "\n",
    "//TODO : finish the section introducing sigmoid and PERCEPTRON stuff\n",
    "\n",
    "NEURAL NETWORKS intro : \n",
    "\n",
    "- We will be looking at feedforward neural networks, with hidden layers that \\\n",
    "are essentially layers of perceptron. Output of one later = input of next.\n",
    "\n",
    "- We use the sigmoid function for neurons insteaed of the perceptron (step f'n) \\\n",
    "to smooth out the neuron, so that small changes in the weights w_j and in \\\n",
    "the bias b will only produce a small change of the output from the neuron. \n",
    "\n",
    "- Non-linear activation functions we can choose: Sigmoid, tanh, ReLU (see sheet)\n",
    "\n",
    "- Simplest kind of NN = Feed forward NN : \n",
    "  \n",
    "  - Multilayer, all units fully connected, no cycles. \n",
    "\n",
    "- Equations for a feedforward NN : \n",
    "\n",
    "  - A single hidden unit has params w_vec and b (bias scalar). \n",
    "\n",
    "  - We represent the parameters for the entire hiddne layer by combining the \\\n",
    "  weight vector w_i and bias b_i for each unit i into a single weight matrix \\\n",
    "  W and a single bias vector b_vec for the whole layer. \n",
    "\n",
    "    - Can easily compute outout : $h = \\sigma (Wx + b)$\n",
    "\n",
    "  - Ouput layer has a weight matrix U, multiplied by input vec h_vec to produce \\\n",
    "  the intermediate output z : $z = Uh$.\n",
    "\n",
    "  - We then pass z through a softmax function to output the probability distribution y : \n",
    "    - $y = softmax(z)\n",
    "\n",
    "TRAINING neural nets : \n",
    "\n",
    "Like logisitic regresssion, we wish to learn the best params for the NN to make \\\n",
    "predicitons $\\hat{y}$ as close to possible as the gold standards labels from \\\n",
    "training data, y.\n",
    "\n",
    "We need : \n",
    "\n",
    "1. A loss f'n : Cross-entropy loss\n",
    "\n",
    "2. an Optimization algo : gradient descent\n",
    "\n",
    "3. A way of computing the gradient of the loss function : error back propagation \\\n",
    "(since we have more layers of indirection)\n",
    "\n",
    "How to compute the gradient : which direction to \"nudge\" the params?\n",
    "\n",
    "Since we have multiple layers now, we must compute the BACKWARD DIFFERENTIATION \\\n",
    "across the layers.\n",
    "\n",
    "- Error back-propogation enables us to correctly update all layers in the NN.\n",
    "\n",
    "- Represent the model as a COMPUTATION GRAPH (see sheet). Use chain rule to \\\n",
    "express in terms of partial derivatives\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module13_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3268
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "3c134570-de1a-42d9-a452-ee3c07af6e64"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       " \n",
       "Neural Networks, Big Picture : \n",
       "\n",
       "Essentially a bunch of stacked perceptrons, like \"neurons\" working together.\n",
       "\n",
       "Neural network has 4 Classifier components : \n",
       "1. Feature representation of the input : for each input observation $x^{i}, vector of features $[x_{1},..,x_{n}].\n",
       "\n",
       "2. Classification function : computes the estimated class $y^{\\^} via $p(y|x):\n",
       "- $y^{\\^} = max_{y}(P(y|x))$.\n",
       "\n",
       "3. Objective function : for learning : minimize error on training egs (ie. LOSS fn)\n",
       "\n",
       "4. Algorith for optimizing the objective function\n",
       "\n",
       "SENTIMENT CLASSIFIIER\n",
       "\n",
       "Consider input obs x represented by a vector of features [x_1, ..., x_n]. \n",
       "\n",
       "Classifier output y can be 1 (pos) or 0 (neg).. We wish to estimate P(y = 1 | x_vec).\n",
       "\n",
       "LOGISTIC REGRESSION solves this by learning from a training set a vector of weights and a bias term : \n",
       "$$z = \\sum_{i} w_{i}x_{i} + b = w . x + b \\ dot product $$\n",
       "\n",
       "We normalize z to be between 0 and 1 by passing it through a SIGMOID f'n (also called logistic f'n) : \n",
       "$$y = 1/(1+e^{-z}) $$\n",
       "\n",
       "So we have $P(y = 1) = \\sigma(w . x + b) = 1/(1+e^{-(w . x + b)})$\n",
       "\n",
       "DECISION BOUNDARY : how to make the decision? Set threshhold : \n",
       "\n",
       "$y_{hat} = 1, if P(y = 1|x) > 0.5, 0 otherwise $\n",
       "\n",
       "^ theshhold = 0.5.\n",
       "\n",
       "Another way we can analyse if pos or neg sentiment : FEATURE EXTRACTION\n",
       "\n",
       "We count the instances of each feature, and we give each a weight corresponding to how much they contribute to the class. \n",
       "\n",
       "Take dot product of features and weights to find z (z = w . x + b), and pass  through Sigmoid(Z).\n",
       "\n",
       "Next:\n",
       "\n",
       "LEARNING in logisit regression, ie. how to get the weights of the model : \n",
       "\n",
       "We learn the parameters (weights and bias) via learning, which requires : \n",
       "\n",
       "1. An objective, or LOSS function, that tells us the distance between the system output and the gold output. \n",
       "  - We use CROSS-ENTROPY LOSS.\n",
       "\n",
       "2. Algo for optimizing the objective function. \n",
       "  - We use STOCHASTIC GRADIENT DESCENT to minimize the Loss function.\n",
       "\n",
       "Loss functions: ie how much the classifier output (y^) is close to correct output (y).\n",
       "\n",
       "L(y^, y) = how much y^ differs from the true y. \n",
       "\n",
       "One eg. is Mean-Squared Error (MSE) : \n",
       "$$L_{MSE}(\\hat{y},y) = 1/2(\\hat{y} - y)^{2}$$\n",
       "\n",
       "Loss functions for probabilistic classification : \n",
       "\n",
       "We use a loss f'n that prefers the correct class labels of the training example to be more likely.\n",
       "\n",
       "Conditional max likelihood estimation : Choose params w_vec, b that MAXIMIZE the (log) probs of the true labels in the training data.\n",
       "\n",
       "Resulting loss function is the NEGATIVE LOG LIKELIHOOD loss ie. CROSS-ENTROPY LOSS.\n",
       "\n",
       "(directionality is preserved in log space)\n",
       "\n",
       "$$log p(y|x) = log[\\hat{y}^{y}(1-\\hat{y})^{1-y}]$$\n",
       "$$ = ylog \\hat{y}, + (1-y)log(1-\\hat{y})$$\n",
       "For loss function we want to minimize, so flip the sign and plug in our expression for y' : \n",
       "$$L_{CE}(\\hat{y}, y) = -log p(y|x) = -[y log \\sigma(w . x + b) + (1-y) log(1-\\sigma(w . x + b))]$$\n",
       "\n",
       "Why does minimizing the negative log probability work:?\n",
       "\n",
       "- We want the LOSS to be SMALLER if the model's estimate is close to correct,\n",
       "\n",
       "- and we want the loss to be BIGGER if it is confused.\n",
       "\n",
       "- -log of a small val becomes infinitely large\n",
       "\n",
       "Now, loss on ALL training exmpls : \n",
       "\n",
       "$$log p(training labels) = log \\prod_{i =1}^{m} p(y^{i} | x^{i}) $$\n",
       "$$ = \\sum_{i = 1}^{m} log p(y^{i} | x^{i}) $$\n",
       "$$ = - \\sum_{i = 1}^{m} L_{CE}(\\hat{y}^{i} | y^{i})$$\n",
       "\n",
       "\n",
       "Now, how to find good parameters : \n",
       "\n",
       "GRADIENT DESCENT to find good settings by minimizing loss function\n",
       "\n",
       "$$\\Theta = argmin_{\\Theta} 1/m \\sum_{i = 1}^{m} L_{CE}(y^{i}, x^{i}; \\Theta) $$\n",
       "\n",
       "Gradient descent is a method that finds a minimum of a function by figuring out in which direction (in the space of the parametres $\\Theta$ the f'ns slope is risinhg the most steeply, and moving in the opposite direction. \n",
       "\n",
       "CAN't get stuck on a local min :\n",
       "For logistic regression, the loss function is CONVEX = only one minimum! Great,we can't get stuck in a local minima. \n",
       "\n",
       "Gradient descent starting from any point is GUARANTEED to find the minimum.\n",
       "\n",
       "Size of learning rate, ie. magnitude of amount to move in gradient descent, is the value of the slope weighted by a learning rate $\\eta$\n",
       "\n",
       "A higher/faster learning rate = more w more on each step.\n",
       "\n",
       "$$w^{t + 1} = w^t - \\eta * d/dw (f(x;w))$$\n",
       "\n",
       " = old weight - eta (step size) * derivative (slope) of f'n \n",
       "\n",
       " NOW, for many dimensions:\n",
       "\n",
       " each dimension will impact the loss f'n.\n",
       "\n",
       "//TODO : finish the section introducing sigmoid and PERCEPTRON stuff\n",
       "\n",
       "NEURAL NETWORKS intro : \n",
       "\n",
       "- We will be looking at feedforward neural networks, with hidden layers that are essentially layers of perceptron. Output of one later = input of next.\n",
       "\n",
       "- We use the sigmoid function for neurons insteaed of the perceptron (step f'n) to smooth out the neuron, so that small changes in the weights w_j and in the bias b will only produce a small change of the output from the neuron. \n",
       "\n",
       "- Non-linear activation functions we can choose: Sigmoid, tanh, ReLU (see sheet)\n",
       "\n",
       "- Simplest kind of NN = Feed forward NN : \n",
       "  \n",
       "  - Multilayer, all units fully connected, no cycles. \n",
       "\n",
       "- Equations for a feedforward NN : \n",
       "\n",
       "  - A single hidden unit has params w_vec and b (bias scalar). \n",
       "\n",
       "  - We represent the parameters for the entire hiddne layer by combining the   weight vector w_i and bias b_i for each unit i into a single weight matrix   W and a single bias vector b_vec for the whole layer. \n",
       "\n",
       "    - Can easily compute outout : $h = \\sigma (Wx + b)$\n",
       "\n",
       "  - Ouput layer has a weight matrix U, multiplied by input vec h_vec to produce   the intermediate output z : $z = Uh$.\n",
       "\n",
       "  - We then pass z through a softmax function to output the probability distribution y : \n",
       "    - $y = softmax(z)\n",
       "\n",
       "TRAINING neural nets : \n",
       "\n",
       "Like logisitic regresssion, we wish to learn the best params for the NN to make predicitons $\\hat{y}$ as close to possible as the gold standards labels from training data, y.\n",
       "\n",
       "We need : \n",
       "\n",
       "1. A loss f'n : Cross-entropy loss\n",
       "\n",
       "2. an Optimization algo : gradient descent\n",
       "\n",
       "3. A way of computing the gradient of the loss function : error back propagation (since we have more layers of indirection)\n",
       "\n",
       "How to compute the gradient : which direction to \"nudge\" the params?\n",
       "\n",
       "Since we have multiple layers now, we must compute the BACKWARD DIFFERENTIATION across the layers.\n",
       "\n",
       "- Error back-propogation enables us to correctly update all layers in the NN.\n",
       "\n",
       "- Represent the model as a COMPUTATION GRAPH (see sheet). Use chain rule to express in terms of partial derivatives\n",
       "\n",
       " \n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module13_sections = [\n",
    "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
    "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
    "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
    "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
    "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
    "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
    "\n",
    "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
    "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
    "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
    "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
    "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
    "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
    "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
    "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
    "]\n",
    "\n",
    "module13_markdown = format_module(13, \"Neural Networks\", \n",
    "                         module13_sections, \n",
    "                         module13_definitions)\n",
    "display(Markdown(module13_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "# Module 14 - Natural Language Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
    "\n",
    "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
    "\n",
    "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module14_lecture_notes = \"\"\" \n",
    "Neural Language Models : \n",
    "Have several advantages over n-gram LMs : \n",
    "\n",
    "- Don't need smoothing\n",
    "\n",
    "- Can handle much longer histories\n",
    "\n",
    "- They can generalize over contexts of similar words.\n",
    "\n",
    "- Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
    "\n",
    "DISADVANTAGE : slower to train than traditional n-gram LMs.\n",
    "\n",
    "Idea : \n",
    "\n",
    "1. Associate each word in vocab with vector-rep : thereby creating a notion of \\\n",
    "similarity between words\n",
    "\n",
    "2. Express joint prob f'n of a word sequence in terms of word vectors for words \\\n",
    "in sentence\n",
    "\n",
    "3. Simultaneously learn the word vectors and parameters of the f'n.\n",
    "\n",
    "- Prob. f'n is expressed through the product of conditional probs of the next \\\n",
    "word given the previous word using a multi-layer, feed -forward neural network\n",
    "\n",
    "Neural LMs : \n",
    "\n",
    "- INPUT = k-0gram of words $w_{1:k}$\n",
    "\n",
    "- OUTPUT = prob distribution over next word\n",
    "\n",
    "- k context words are treated as a word window. Each word is associated with an embedding vector\n",
    "\n",
    "Advantage also is that we get training for \"free\" from the corpus (large body of text)!\n",
    " egs are simply word k-grams from corpus. \n",
    "\n",
    "Then train as usual using cross-entropy loss\n",
    "\n",
    "Current state of the art neural LMs : \n",
    "\n",
    "- ELMo\n",
    "\n",
    "- GPT 2/3\n",
    "\n",
    "- BERT\n",
    "\n",
    "MEANING in NLP :\n",
    "\n",
    "How to represent meaning of a word?\n",
    "\n",
    "- In N-gram LMs, we just represented words as a string of letters, ie. tokens, '\\\n",
    "so we did not care about understanding meaning.\n",
    "\n",
    "- Ideally, we want a meaning representation to encode :\n",
    "\n",
    "  - Synonyms\n",
    "\n",
    "  - Antonyms\n",
    "\n",
    "  - Connotations - words that are pos or neg\n",
    "\n",
    "  - Semantic Roles - eg. buy, sell and pay are different parts of same underlying puchasing event\n",
    "\n",
    "  - Support for entailment\n",
    "\n",
    "VECTOR SPACE MODELS : \n",
    "\n",
    "- Allows us to see how semantically similar words are (clustered together by meaning)\n",
    "\n",
    "- Really important to be able to understand similarity, not necessarily synonymous (eg. cat and dog)\n",
    "\n",
    "- Solution : \"Distributional Hypothesis\" - Zellig Harris. Similarity can be detected \\\n",
    "by how similar the environment (or context) the words appear in. \n",
    "\n",
    "\n",
    "TERM-DOCUMENT MATRIX : \n",
    "\n",
    "- matrix where each column vector represents a document\n",
    "\n",
    "- each row vector = represents a Term\n",
    "\n",
    "- Each cell = how often that term occured in document\n",
    "\n",
    "- Length of the document vectors is the size of the vocabulary (ie. number of rows)\n",
    "\n",
    "  - Meaning that the document vectors (columns) can be very sparse\n",
    "\n",
    "- We can measure how similar two documents are by comparing their column vectors.\n",
    "\n",
    "- Potential use cases = plagiarism detection.\n",
    "\n",
    "- Comparing two rows = comparing how similar both terms are (ie. how much they both \\\n",
    "fit in the same context)\n",
    "\n",
    "- Document vecot\n",
    "How to identify word similarity : \n",
    "\n",
    "1. VECTOR COMPARISONS : \n",
    "\n",
    "- Can plot each point on a graph and use Euclidean distance to relate words to \\\n",
    "each other.\n",
    "$$\\sqrt{\\sum_{i=1}^{n} |u_{i}-v_{i}|^{2}}$$\n",
    "  - PROBLEM with this is that we are affected by FREQUENCY of the word, so for eg. it could \\\n",
    "  wrongly put \"good\" closer to \"disappointing\" than \"superb\".\n",
    "\n",
    "- Solution : NORMALIZE : Vector L2 (length) normalization, solves for freq. issue.\n",
    "$$||u|| = \\sqrt{\\sum_{i=1}^{n} u_{i}^{2}}$$\n",
    "\n",
    "  -   Divide each vector by its L2 length.  \n",
    "\n",
    "Another method to get similarity :\n",
    "\n",
    "2. COSINE DISTANCE : Does the L2 normalization too. \n",
    "\n",
    "- Cosine angle between vectorsr tells us their similarity\n",
    "\n",
    "\n",
    "Language structure : \n",
    "\n",
    "- Languages have long distance dependencies\n",
    "\n",
    "  - Eg. noun-verb-adj structure can be split by sub-clauses eg. \"photographs \\\n",
    "  of the man ARE lovely\"\n",
    "\n",
    "Another way of modeling :\n",
    "\n",
    "TERM-TERM MATRIX : instead of term-by-document matrix where we count how often \\\n",
    "a word occurs in a document.\n",
    "\n",
    "-  Length = size of vocab |V| vs # documents in collection      \n",
    "\n",
    "- We count instances of a word appearing in a context window (eg. 2 words before \\\n",
    "and 2 words after) in the same sentence of the same doc.\n",
    "\n",
    "- But this ignores the fact that languages have long-distnace dependencies!\n",
    "\n",
    "- We must use syntax to define a word's context\n",
    "\n",
    "\n",
    "Alternative to counts : \n",
    "\n",
    "- Raw word frequency is not a great measure of association between words. \n",
    "\n",
    "- Skews common words such as \"the\" and \"of\" as very important because very frequent,\\\n",
    "even if they are not the most discriminative (and common in all documents)\n",
    "\n",
    "- Must instead hav a measure that asks whether a context word is particularly \\\n",
    "informative about the target word. \n",
    "\n",
    "- Instead of raw counts, TRANSFORM VECTORS using TF-IDF or PPMI\n",
    "\n",
    "TF-IDF : \n",
    "\n",
    "- Term Frequency * (Inverse Document Frequency)\n",
    "\n",
    "  - TF = how often a word occured in a doc\n",
    "\n",
    "  - IDF = 1/(# docs word occurred in) ie a measure of how unique this word is \\\n",
    "  to this particular text / context.\n",
    "\n",
    "\n",
    "More modern approach to word vectors : \n",
    "\n",
    "- So far, word vectors are super LONG (length = |V|) and SPARSE (most elements = 0)\n",
    "\n",
    "- Alternatively, more modern approaches use SHORT (length = 100-1000) and DENSE vectors\n",
    "\n",
    "How to get dense vectors? --> Train a classifier\n",
    "\n",
    "1. Treat target word and neighboring context word as positive examples\n",
    "\n",
    "2. Randomly sample other words in the lexicon that don't show up in neighbor \\\n",
    "to get negative samples.\n",
    "\n",
    "3. Train logisitic regression classifier starting with a randomly initialized \\\n",
    "set of weights to distinguish whether 2 words co-occur in corpus or not. Weights \\\n",
    "create dense vector representation : Use learned weights as word representation.\n",
    "\n",
    "  - Formed basis of Google's 'Word2Vec\" : leanrn embeddings as part of the process \\\n",
    "  of word prediction. \n",
    "\n",
    "  - Advantages : fast, easy to train (faster than SVD), open-source\n",
    "\n",
    "Word2Vec : \n",
    "\n",
    "- Predict each neighboring word in a context window of 2C of surrounding words\n",
    "\n",
    "- Instaed of counting, we can train a classifier on a binary perceptron task. \n",
    "\n",
    "  - Use the learned classifier weights as the word embeddings. \n",
    "\n",
    "  - This means we can use running text as implicitly supervised training data! \\\n",
    "  = no need for hand-labeled supervision.\n",
    "\n",
    "SKIP-GRAM ALGORITHM : \n",
    "\n",
    "- Treat target word and a neighboring context word as positive exxamples.\n",
    "\n",
    "- Randomly sample other words in the lexicon to get negative samples.\n",
    "\n",
    "- Use logistic regression to train a classifier to distinguish those two cases.\n",
    "\n",
    "- Use the weights as embeddings. (vector rep of meaning of the words.)\n",
    "\n",
    "  - NOTE : still need to compute the following way : \n",
    "\n",
    "  1. Compute p(+|t,c) by calculating DOT PRODUCT : similarity(t,c) ~= t . c\n",
    "\n",
    "  2. Next, turn dot product into probability : plug it into the sigmoid function\n",
    "\n",
    "  3. For ALL context words, assume all context words are independent : \n",
    "\n",
    "$$P(+ |t, c_{1:k}) = \\prod_{i=1}^{K} 1 / (1 + e^{-t*c_i}) $$\n",
    "\n",
    "  4. Take the log to turn product into sum, and move log inside sum\n",
    "\n",
    "  5. We want to MAXIMIZE the similariy of (t,c) paris from the POSitive data \\\n",
    "   and MINIMIZE the similarity of the (t,c) paris from the NEGative data.\n",
    "\n",
    "$$L(\\Theta) = log P(+|t,c) + \\sum_{i = 1}^{k} log P(- | t, n_i) $$\n",
    "\n",
    "$$ = log \\sigma (c . t) + \\sum_{i = 1}^{k} log \\sigma (- n_i . t) $$\n",
    "\n",
    "where sigma = sigmoid f'n\n",
    "\n",
    "  6. Finally, we train using gradient descent and we learn two separate embedding \\\n",
    "  matrices W and C. \n",
    "\n",
    "    - We can use W and throw away C or merge them.\n",
    "\n",
    "\n",
    "- How to evaluate the embeddings?\n",
    "\n",
    "  - COmpare to human scores on word similarity-type tasks eg wordSim-353\n",
    "\n",
    "\n",
    "How to choose noise words :\n",
    "\n",
    "- Pick word accoridng to their unigram frequency, and favor rare words : \n",
    "\n",
    "$$P_{\\alpha} (w) = count(w)^{\\alpha} / \\sum_{w} count(w)^{\\alpha} $$\n",
    "\n",
    "- alpha = 3/4 workds well for giving rare noise words slightly higher probability\n",
    "\n",
    "\n",
    "- Embeddings capture relational meanings : eg. binary gender associations : \\\n",
    " man->woman, uncle->aunt\n",
    "\n",
    "  - Vector arithmetic for relational meanings : \n",
    "  - eg. vector('king') - vector('man') + vector('queen') = vector('woman')\n",
    "\n",
    "- Can expose biases in data especially over time\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module14_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3808
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "d2719e7a-4ed2-4f84-a6f9-175e42c08d39"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       " Your summary here \n",
       "\n",
       "## Module 14 Lecture Notes\n",
       " \n",
       "Neural Language Models : \n",
       "Have several advantages over n-gram LMs : \n",
       "\n",
       "- Don't need smoothing\n",
       "\n",
       "- Can handle much longer histories\n",
       "\n",
       "- They can generalize over contexts of similar words.\n",
       "\n",
       "- Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
       "\n",
       "DISADVANTAGE : slower to train than traditional n-gram LMs.\n",
       "\n",
       "Idea : \n",
       "\n",
       "1. Associate each word in vocab with vector-rep : thereby creating a notion of similarity between words\n",
       "\n",
       "2. Express joint prob f'n of a word sequence in terms of word vectors for words in sentence\n",
       "\n",
       "3. Simultaneously learn the word vectors and parameters of the f'n.\n",
       "\n",
       "- Prob. f'n is expressed through the product of conditional probs of the next word given the previous word using a multi-layer, feed -forward neural network\n",
       "\n",
       "Neural LMs : \n",
       "\n",
       "- INPUT = k-0gram of words $w_{1:k}$\n",
       "\n",
       "- OUTPUT = prob distribution over next word\n",
       "\n",
       "- k context words are treated as a word window. Each word is associated with an embedding vector\n",
       "\n",
       "Advantage also is that we get training for \"free\" from the corpus (large body of text)!\n",
       " egs are simply word k-grams from corpus. \n",
       "\n",
       "Then train as usual using cross-entropy loss\n",
       "\n",
       "Current state of the art neural LMs : \n",
       "\n",
       "- ELMo\n",
       "\n",
       "- GPT 2/3\n",
       "\n",
       "- BERT\n",
       "\n",
       "MEANING in NLP :\n",
       "\n",
       "How to represent meaning of a word?\n",
       "\n",
       "- In N-gram LMs, we just represented words as a string of letters, ie. tokens, 'so we did not care about understanding meaning.\n",
       "\n",
       "- Ideally, we want a meaning representation to encode :\n",
       "\n",
       "  - Synonyms\n",
       "\n",
       "  - Antonyms\n",
       "\n",
       "  - Connotations - words that are pos or neg\n",
       "\n",
       "  - Semantic Roles - eg. buy, sell and pay are different parts of same underlying puchasing event\n",
       "\n",
       "  - Support for entailment\n",
       "\n",
       "VECTOR SPACE MODELS : \n",
       "\n",
       "- Allows us to see how semantically similar words are (clustered together by meaning)\n",
       "\n",
       "- Really important to be able to understand similarity, not necessarily synonymous (eg. cat and dog)\n",
       "\n",
       "- Solution : \"Distributional Hypothesis\" - Zellig Harris. Similarity can be detected by how similar the environment (or context) the words appear in. \n",
       "\n",
       "\n",
       "TERM-DOCUMENT MATRIX : \n",
       "\n",
       "- matrix where each column vector represents a document\n",
       "\n",
       "- each row vector = represents a Term\n",
       "\n",
       "- Each cell = how often that term occured in document\n",
       "\n",
       "- Length of the document vectors is the size of the vocabulary (ie. number of rows)\n",
       "\n",
       "  - Meaning that the document vectors (columns) can be very sparse\n",
       "\n",
       "- We can measure how similar two documents are by comparing their column vectors.\n",
       "\n",
       "- Potential use cases = plagiarism detection.\n",
       "\n",
       "- Comparing two rows = comparing how similar both terms are (ie. how much they both fit in the same context)\n",
       "\n",
       "- Document vecot\n",
       "How to identify word similarity : \n",
       "\n",
       "1. VECTOR COMPARISONS : \n",
       "\n",
       "- Can plot each point on a graph and use Euclidean distance to relate words to each other.\n",
       "$$\\sqrt{\\sum_{i=1}^{n} |u_{i}-v_{i}|^{2}}$$\n",
       "  - PROBLEM with this is that we are affected by FREQUENCY of the word, so for eg. it could   wrongly put \"good\" closer to \"disappointing\" than \"superb\".\n",
       "\n",
       "- Solution : NORMALIZE : Vector L2 (length) normalization, solves for freq. issue.\n",
       "$$||u|| = \\sqrt{\\sum_{i=1}^{n} u_{i}^{2}}$$\n",
       "\n",
       "  -   Divide each vector by its L2 length.  \n",
       "\n",
       "Another method to get similarity :\n",
       "\n",
       "2. COSINE DISTANCE : Does the L2 normalization too. \n",
       "\n",
       "- Cosine angle between vectorsr tells us their similarity\n",
       "\n",
       "\n",
       "Language structure : \n",
       "\n",
       "- Languages have long distance dependencies\n",
       "\n",
       "  - Eg. noun-verb-adj structure can be split by sub-clauses eg. \"photographs   of the man ARE lovely\"\n",
       "\n",
       "Another way of modeling :\n",
       "\n",
       "TERM-TERM MATRIX : instead of term-by-document matrix where we count how often a word occurs in a document.\n",
       "\n",
       "-  Length = size of vocab |V| vs # documents in collection      \n",
       "\n",
       "- We count instances of a word appearing in a context window (eg. 2 words before and 2 words after) in the same sentence of the same doc.\n",
       "\n",
       "- But this ignores the fact that languages have long-distnace dependencies!\n",
       "\n",
       "- We must use syntax to define a word's context\n",
       "\n",
       "\n",
       "Alternative to counts : \n",
       "\n",
       "- Raw word frequency is not a great measure of association between words. \n",
       "\n",
       "- Skews common words such as \"the\" and \"of\" as very important because very frequent,even if they are not the most discriminative (and common in all documents)\n",
       "\n",
       "- Must instead hav a measure that asks whether a context word is particularly informative about the target word. \n",
       "\n",
       "- Instead of raw counts, TRANSFORM VECTORS using TF-IDF or PPMI\n",
       "\n",
       "TF-IDF : \n",
       "\n",
       "- Term Frequency * (Inverse Document Frequency)\n",
       "\n",
       "  - TF = how often a word occured in a doc\n",
       "\n",
       "  - IDF = 1/(# docs word occurred in) ie a measure of how unique this word is   to this particular text / context.\n",
       "\n",
       "\n",
       "More modern approach to word vectors : \n",
       "\n",
       "- So far, word vectors are super LONG (length = |V|) and SPARSE (most elements = 0)\n",
       "\n",
       "- Alternatively, more modern approaches use SHORT (length = 100-1000) and DENSE vectors\n",
       "\n",
       "How to get dense vectors? --> Train a classifier\n",
       "\n",
       "1. Treat target word and neighboring context word as positive examples\n",
       "\n",
       "2. Randomly sample other words in the lexicon that don't show up in neighbor to get negative samples.\n",
       "\n",
       "3. Train logisitic regression classifier starting with a randomly initialized set of weights to distinguish whether 2 words co-occur in corpus or not. Weights create dense vector representation : Use learned weights as word representation.\n",
       "\n",
       "  - Formed basis of Google's 'Word2Vec\" : leanrn embeddings as part of the process   of word prediction. \n",
       "\n",
       "  - Advantages : fast, easy to train (faster than SVD), open-source\n",
       "\n",
       "Word2Vec : \n",
       "\n",
       "- Predict each neighboring word in a context window of 2C of surrounding words\n",
       "\n",
       "- Instaed of counting, we can train a classifier on a binary perceptron task. \n",
       "\n",
       "  - Use the learned classifier weights as the word embeddings. \n",
       "\n",
       "  - This means we can use running text as implicitly supervised training data!   = no need for hand-labeled supervision.\n",
       "\n",
       "SKIP-GRAM ALGORITHM : \n",
       "\n",
       "- Treat target word and a neighboring context word as positive exxamples.\n",
       "\n",
       "- Randomly sample other words in the lexicon to get negative samples.\n",
       "\n",
       "- Use logistic regression to train a classifier to distinguish those two cases.\n",
       "\n",
       "- Use the weights as embeddings. (vector rep of meaning of the words.)\n",
       "\n",
       "  - NOTE : still need to compute the following way : \n",
       "\n",
       "  1. Compute p(+|t,c) by calculating DOT PRODUCT : similarity(t,c) ~= t . c\n",
       "\n",
       "  2. Next, turn dot product into probability : plug it into the sigmoid function\n",
       "\n",
       "  3. For ALL context words, assume all context words are independent : \n",
       "\n",
       "$$P(+ |t, c_{1:k}) = \\prod_{i=1}^{K} 1 / (1 + e^{-t*c_i}) $$\n",
       "\n",
       "  4. Take the log to turn product into sum, and move log inside sum\n",
       "\n",
       "  5. We want to MAXIMIZE the similariy of (t,c) paris from the POSitive data    and MINIMIZE the similarity of the (t,c) paris from the NEGative data.\n",
       "\n",
       "$$L(\\Theta) = log P(+|t,c) + \\sum_{i = 1}^{k} log P(- | t, n_i) $$\n",
       "\n",
       "$$ = log \\sigma (c . t) + \\sum_{i = 1}^{k} log \\sigma (- n_i . t) $$\n",
       "\n",
       "where sigma = sigmoid f'n\n",
       "\n",
       "  6. Finally, we train using gradient descent and we learn two separate embedding   matrices W and C. \n",
       "\n",
       "    - We can use W and throw away C or merge them.\n",
       "\n",
       "\n",
       "- How to evaluate the embeddings?\n",
       "\n",
       "  - COmpare to human scores on word similarity-type tasks eg wordSim-353\n",
       "\n",
       "\n",
       "How to choose noise words :\n",
       "\n",
       "- Pick word accoridng to their unigram frequency, and favor rare words : \n",
       "\n",
       "$$P_{\u0007lpha} (w) = count(w)^{\u0007lpha} / \\sum_{w} count(w)^{\u0007lpha} $$\n",
       "\n",
       "- alpha = 3/4 workds well for giving rare noise words slightly higher probability\n",
       "\n",
       "\n",
       "- Embeddings capture relational meanings : eg. binary gender associations :  man->woman, uncle->aunt\n",
       "\n",
       "  - Vector arithmetic for relational meanings : \n",
       "  - eg. vector('king') - vector('man') + vector('queen') = vector('woman')\n",
       "\n",
       "- Can expose biases in data especially over time\n",
       "\n",
       " \n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Concept** - definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "\n",
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module14_sections = [\n",
    "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
    "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
    "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
    "\n",
    "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
    "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
    "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
    "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
    "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
    "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
    "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
    "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
    "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
    "]\n",
    "\n",
    "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
    "                         module14_sections, \n",
    "                         module14_definitions)\n",
    "display(Markdown(module14_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vX7lbnJd4sT5"
   },
   "source": [
    "# Your Exam Notes\n",
    "\n",
    "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
    "\n",
    "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
    "* Run the cell below. \n",
    "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 23914
    },
    "id": "T3cm1WV542_a",
    "outputId": "a65253de-c8c8-4e4d-b3d8-92fcbbab066a"
   },
   "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",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       " Your summary here \n",
       "\n",
       "## Module 8 Lecture Notes\n",
       " \n",
       "\n",
       "MDPs : \n",
       "\n",
       "- No longer deterministic environments : now task environment is probabilistic / STOCHASTIC\n",
       "\n",
       "  - This means that eg. when we select \"Up\", we go \"up\" X% of the time -> uncertainty in the resulting state\n",
       "\n",
       "- Sequential decision problem\n",
       "\n",
       "- for a fully observable environment\n",
       "\n",
       "- with a stochastic transition model\n",
       "\n",
       "- that has additive rewards\n",
       "\n",
       "Stochastic Transition model needed to replace our deterministic transition model:\n",
       "\n",
       "- Transition model T(s, a, s') is written as a probability : p(s' | s, a) : the probability of arriving in state s' given that we are in state s and selected action a\n",
       "\n",
       "- We ignore past states : MARKOV property : the prob of arriving to next state only depends on the current state s, and not the history of earlier states.\n",
       "\n",
       "Reward function, R(s,a,s') : \n",
       "\n",
       "- We must also specify a utility/reward function for agent. \n",
       "\n",
       "- Can be pos/neg, but must be bounded by some max value. \n",
       "\n",
       "- Since decision process is sequential, must specify the utility f'n on a sequence of states and actions. \n",
       "\n",
       "- Instead of giving a reward only at goal states, agent can recieve a reward at each time step, based on transition from s to s' via action a.\n",
       "\n",
       "  - Can also receive a negative reward at each time step except for entering   terminal state\n",
       "\n",
       "- Rewards are additive (PERFORMANCE of agent in MDP = sum of rewards for the transition it makes)\n",
       "\n",
       "To find a sol'n to an MDP, we need : \n",
       "\n",
       "1. set of states, s E S\n",
       "\n",
       "2. set of actions, a E A\n",
       "\n",
       "3. Transition function T(s, a, s')\n",
       "\n",
       "  - Prob that executing action a in s will lead to s' = P(s'|s,a)\n",
       "\n",
       "  - probability is called a MODEL\n",
       "\n",
       "4. Reward function R(s,a,s')\n",
       "\n",
       "5. Initial state s_0\n",
       "\n",
       "6. [optional] terminal states\n",
       "\n",
       "Solution to an MDP is called a POLICY, $\\pi$.\n",
       "\n",
       "A policy maps from a state onto the action to take if the agent is in that state.\n",
       "\n",
       "$$\\pi (S) = a $$\n",
       "\n",
       "^ Policy tells the agent what action to take at the particular state s. \n",
       "\n",
       "Optimal policy : $\\pi$* is the OPTIMAL policy : finds action that maximizes \\ \n",
       "the expected utility of being in state s' from state s.\n",
       "\n",
       "  - Remember that our model is stochastic : even if same policy is executed   several times, this may lead to different ENVIRONMENT HISTORY (sequence of    states and actions), and thus a different score under the reward function.\n",
       "\n",
       "   - Therefore, we need to compute the expected utility of all the possible    paths generated by a policy.\n",
       "\n",
       "   - Utility = sum of (discounted) rewards\n",
       "\n",
       "DISCOUNTING : \n",
       "\n",
       "- Another factor that impacts optimal policy is that rewards now are preferred  to rewards later. \n",
       "\n",
       "  - Solution : Exponentially decay the values of rewards so that sooner rewards   have higher utility than later rewards, and to ensure our algo converges.\n",
       "\n",
       "  - $U([r_0, r_1, ...]) = r_0 + \\gamma r_1 + \\gamma ^{2} r_2 +....$ where   $0 < \\gamma < 1$\n",
       "\n",
       "  - This ensures that $U([r_0, r_1, ...]) = \\sum_{t = 0}^{\\inf} \\gamma ^{t} R_{t} \\leq R_{max}/(1 - \\gamma)$\n",
       "\n",
       "  - Smaller $\\gamma$ means smaller \"horizon\" - shorter-time focus\n",
       "\n",
       "- Another way we could avoid the issue of infinite utilities, ie if game lasts forever, is to set a Finite horizon (like depth-limited search) : \n",
       "    \n",
       "    - Terminate episodes after a fixed T steps\n",
       "\n",
       "    - Give nonstationary policies ($\\PI$ depends on time left)\n",
       "\n",
       "Representing MDPs : MDP SEARCH TREES\n",
       "\n",
       "- Each MDP state projects an expectimax-like search tree\n",
       "\n",
       "  - Transition f'n encodes probability\n",
       "\n",
       "  - Reward f'n given at each state of the tree\n",
       "\n",
       "  - Value (utility) of state s : V*(s) = expected utility starting in s and acting optimally\n",
       "\n",
       "  - Value (utility) of a q-state (s,a) : \n",
       "\n",
       "    - Q*(s,a) = expected utility starting out having taken action a from state s     and thereafter acting optimally\n",
       "\n",
       "  - Optimal policy : \n",
       "\n",
       "    - $\\pi$*(s) = optimal action from state s\n",
       "\n",
       "- Fundamental operation : compute the EXPECTIMAX value of a state\n",
       "\n",
       "  - $V*(s) = max_a Q*(s,a)$ = max of choosing any of these actions\n",
       "\n",
       "  - where $Q*(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]\n",
       "\n",
       "  So we have :\n",
       "$$V*(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "\n",
       "In order to avoid the issue that the tree can go on forever, can perform a depth-limited computation, with increasing depths until change is small. \n",
       "\n",
       "  - We don't care about deep parts of the tree if $\\gamma < 1$.\n",
       "\n",
       "Other issue : states can be repeated!\n",
       "\n",
       "  - To avoid this, only compute needed quantitites once. \n",
       "\n",
       "\n",
       " Now,\n",
       "\n",
       " HOW TO CHOOSE OPTIMAL OUTCOME : \n",
       "\n",
       " 3 algos : \n",
       "\n",
       " 1. Value iteration \n",
       "\n",
       " 2. Policy Evaluation\n",
       "\n",
       " 3. Policy Iteration\n",
       "\n",
       "\n",
       "--\n",
       "\n",
       "1. VALUE ITERATION : \n",
       "\n",
       "  - Start with $V_{0}(s) = 0$ : no time steps left means an expected reward sum = 0\n",
       "\n",
       "  - Given vectors of $V_k (s)$ values, do one ply of expectimax from each state : \n",
       "  $$V_{k+1}(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "\n",
       "  - Repeat until convergence\n",
       "\n",
       "- Complexity of each iteration : $O(S^2 A)$\n",
       "\n",
       "- Theorem : algo will CONVERGE to unique optimal values, because of discount factor!\n",
       "\n",
       "  - Approximations get refined towards optimal values\n",
       "\n",
       "  - Policy may converge long before values do\n",
       "\n",
       "- See eg on sheet\n",
       "\n",
       "- PROBLEMS with value iteration : \n",
       "\n",
       "  1. Slow :  $O(S^2 A)$ per iteration\n",
       "\n",
       "  2. The \"max\" at each state rarely changes\n",
       "\n",
       "  3. Policy converges long before values (but algo will keep going until values    converge even if not necessary)\n",
       "\n",
       "BELLMAN EQUATIONS : \n",
       "\n",
       "Definition of \"optimal utility\" via expectimax recurrence gives a simple one-steplookahead relationship amongst optimal utility values : \n",
       "\n",
       "$$V*(s) = max_a Q*(s,a)$$\n",
       "$$Q*(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "$$ \therefore V*(s) = max_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V*(s')]$$\n",
       "\n",
       "2. POLICY EVALUATION :\n",
       "\n",
       "- Evaluate by policy, not action : ie. if we fixed some policy, then the tree would be simpler as there would only be one action per state\n",
       "\n",
       "  - But tree's val would depend on which policy was taken. \n",
       "\n",
       "- Utility of state s under fixed policy $\\pi$ = $V^{\\pi}(s) = expected total discounted rewards starting in s and following $\\pi$.\n",
       "\n",
       "  - Using recusive Bellman Equation for one step look-ahead : \n",
       "\n",
       "  $$V_{0}^{\\pi} (s) = 0 //initial condition $$\n",
       "  $$V_{k+1}^{\\pi} (s) = \\sum_{s'} T(s,\\pi (s),s') [R(s, \\pi (s),s') + \\gamma V_{k}^{\\pi}(s')]$$\n",
       "\n",
       "  - Instead of calculating max, we sum over transitions and have $\\pi$(s) fixed.\n",
       "\n",
       "- Efficiency : $O(S^{2})$ per iteration.\n",
       "\n",
       "\n",
       "3. POLICY ITERATION : \n",
       "\n",
       "- Actions are easier to select from Q-values : $\\pi * (s) = argmax_a Q*(s,a)$\n",
       "\n",
       "- Is OPTIMAL, even if you start with any random policy! \n",
       "\n",
       "- Algo converges at an optimal policy.\n",
       "\n",
       "  1. Policy EVALUATION  : calculate utilities for some fixerd policy (not   necessarily optimal) until convergence\n",
       "\n",
       "  2. Policy IMPROVEMENT : update policy using one-step look ahead with resulting   converged (but not optimal!) utilities as future values (need to compare over   actions:)\n",
       "  $$\\pi_{i+1}(s) = argmax_a \\sum_{s'} T(s,a,s') [R(s, a,s') + \\gamma V^{\\pi}(s')]$$\n",
       "\n",
       "  3. Repeat steps until policy converges\n",
       "\n",
       "COMPARISON : \n",
       " \n",
       " - Both value iteration and policy iteration compute the same thing (all  optimal values)\n",
       "\n",
       " - In VALUE ITERATION : \n",
       "\n",
       "  - Every iteration updates both the values and (implicitly) the policy.\n",
       "\n",
       "  - We don't track the policy, but taking the max over actions implicitly   recomputes it\n",
       "\n",
       "- In POLICY ITERATION : \n",
       "\n",
       "  - Do several passes that update utilities with fixed policy (but each pass   is faster because we only consider one action, not all, so no need to take max of actions)\n",
       "\n",
       "  - After the policy is evaluated, a new policy is chosen (slow like a value   iteration pass)\n",
       "\n",
       "  - The new policy will be better (or converged = done)\n",
       "\n",
       "- BOTH ARE DYNAMIC PROGRAMS FOR SOLVING MDPs\n",
       "\n",
       "If you want to : \n",
       "\n",
       "- Compute optimal values -> Value OR Policy Iteration\n",
       "\n",
       "- Compute values for a particular policy -> Policy Evaluation\n",
       "\n",
       "- Turn values into a policy -> Policy Extraction (one-step look ahead)\n",
       "\n",
       "**they are ALL variations of the Bellman updates! All use one-step lookahead expectimax fragments, only differ in whether we plug in a fixed policy or amx over actions.\n",
       "\n",
       "--\n",
       "\n",
       "Principle of MAXIMUM EXPECtED UTILITY (MEU) : \n",
       "\n",
       "- A rational agent should choose the action that maximizes is expected utility,given its knowledge. \n",
       "\n",
       "- For worst-case minimax reasoning, terminal function scale doesn't matter\n",
       "\n",
       "  - We just want better states to have higher evals\n",
       "\n",
       "    - -> called INSENSITIVITY to monotonic transformations\n",
       "\n",
       "- For avg-case expectimax, we need magnitudes to be meaningful.\n",
       "\n",
       "UTILITIES : \n",
       "\n",
       "- [Def] Utilities are functions from outcomes (states of the world) to real numbers that describe an agent's preferences.\n",
       "\n",
       "- Preferences : An agent must either have preferences ($A > B$ or be indifferent (A ~ B)\n",
       "\n",
       "- Need some constraints on preferences before we call them rational, such as : \n",
       "\n",
       "  - AXIOM OF TRANSITIVITY : $(A > B) \\land (B > C) -> (A > C)$\n",
       "\n",
       "  - ORDERABILITY : $(A > B) \\lor (B > A) \\lor (A ~ B)$ Given 2 lotteries, a   rational agent must prefer one or rathem equal (cannot avoid deciding)\n",
       "\n",
       "  - CONTINUITY : $A > B > C -> for all p, [p, A; (1-p), C] ~ B$ (some lotery B    between A, C, there exists probability p that makes you indifferent to B)\n",
       "\n",
       "  - SUBSTITUTABILITY : $A ~ B -> [p, A; (1-p), C] ~ [p, B; (1-p), C]$ (if neither   prefer A, B, then some lottery in between that u have equal preference over that lottery)\n",
       "\n",
       "  - MONOTONICITY : $A > B -> (p \\geq q <-> [p, A; (1-p), B] \\geq [q, A; (1-q), B])$\n",
       "   (if A better than B, i prefer greater p than q)\n",
       "\n",
       "- Theorem : Rational preferences imply behavior describable as MEU\n",
       "\n",
       "- In the case of money : \n",
       "\n",
       "  - Money does NOT behave as a utility function, but we can talk about the utility   of having money (or being in debt)\n",
       "\n",
       "    - Given a lotter L = [p, USD X; (1-p), USD Y] : \n",
       "\n",
       "      - EXPECTD MONETARY VALUE $(EMV(L)) = p*X + (1-p) * Y$\n",
       "\n",
       "      - $U(L) = p*U(X) + (1-p)*U(Y)$\n",
       "\n",
       "      - Typically, $U(L) < U(EMV(L))$\n",
       "\n",
       "        - So people are risk averse, and when in debt are risk-prone\n",
       "\n",
       "      \n",
       "\n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Utility function** - Your definition here\n",
       "* **Expected utility** - your definition here\n",
       "* **Etc.** - your definition here\n",
       "\n",
       "\n",
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       " Your summary here \n",
       "\n",
       "## Module 9 Lecture Notes\n",
       " \n",
       "In MDPs, we are given the Transition and reward functions.\n",
       "\n",
       "  - So solving MDPs required simply offline planning, where all quantities can   be computed given that we have the details. We don't actually need to play the game.\n",
       "\n",
       "In reinforcement learning, agent must learn both of these functions by interacting with the world.\n",
       "\n",
       "  - So now we don't know what the optimal policy is since we don't have the prob. distribution!\n",
       "\n",
       "Ideas in reinforcement learning : \n",
       "\n",
       "- EXPLORATION : have to try unknown actions to get info\n",
       "\n",
       "- EXPLOITATION : eventually, you have to use what you know to make decisions\n",
       "\n",
       "- REGRET : (measure of your total mistake cost : = expected rewards - optimal rewards. even if you learn intelligently, you make mistakes\n",
       "\n",
       "- SAMPLING : because of chance, you have to try things repeatedly\n",
       "\n",
       "- DIFFICULTY : learning can be much harder than solving a known MDP\n",
       "\n",
       "Basic Idea : \n",
       "\n",
       "- Recieve feedback in the form of rewards\n",
       "\n",
       "- Agent's utility is defined by the reward function.\n",
       "\n",
       "- Must learn to act so as to MAXIMIZE EXPECTED REWARDS\n",
       "\n",
       "- All learning is based on observed samples of outcomes\n",
       "\n",
       "Defining Reinforcement learning:\n",
       "\n",
       "- Still assume a MDP structure (with set of states S, set of actions A, model T(s,a,s'), reward f'n R(s,a,s'))\n",
       "\n",
       "- Still looking for policy $\\pi$ (s)\n",
       "\n",
       "- Don't know T or R (must learn)\n",
       "\n",
       "MODEL-BASED LEARNING : \n",
       "\n",
       "1. Learn empirical MDP Model : \n",
       "  \n",
       "  - Count outcomes s' for each (s,a)\n",
       "\n",
       "  - Normalize to give estimate of $ \\hat{T}(s,a,s')$\n",
       "\n",
       "  - Discover each $ \\hat{R}(s,a,s')$ when we experience (s,a,s')\n",
       "\n",
       "2. Solve the learned MVP (using techniques explored in Module 8)\n",
       "\n",
       "MODEL-FREE LEARNING : another way to do reinforcement learning:\n",
       "\n",
       "- Ie. passive reinforcement learning --> uses method called DIRECT EVALUATION\n",
       "\n",
       "- Goal : compute values for each state under a fixed $\\pi$. Still must execute the policy and learn from experience.\n",
       "\n",
       "  - Act accoridng to $\\pi$\n",
       "\n",
       "  - Every time you visit a state, write down what the sum of discounted rewards   turned out to be\n",
       "\n",
       "  - Average thse samples\n",
       "\n",
       "- What's GOOD with direct evaluation?\n",
       "\n",
       "  - easy to understand\n",
       "\n",
       "  - doesn't require any knowledge of T or R\n",
       "\n",
       "  - eventually computes correct avg values using sample transitions\n",
       "\n",
       "- What's BAD about it?\n",
       "\n",
       "  - wastes info about state connections\n",
       "\n",
       "  - states must be learned separately\n",
       "\n",
       "  - SO takes a long time to learn (need a lot of samples)\n",
       "\n",
       "Another approach : \n",
       "\n",
       "Why not use Policy Evaluation?\n",
       "\n",
       "TEMPORAL DIFFERENCE LEARNING\n",
       "\n",
       "- How can we use the Bellman Updates to calculate V for a fixed policy?\n",
       "\n",
       "  - We can get T and R from taking samples of outcomes s' by doing the action, and averaging. \n",
       "\n",
       "  - BUT we cannot guarantee we'll get to state s each n times!\n",
       "\n",
       "- So the big idea of TD earning : learn from every experience : \n",
       "\n",
       "  - Update V(s) each time we experience a transition (s,a,s', r)\n",
       "\n",
       "  - Likely outcome s' will contribute updates more often\n",
       "\n",
       "  - Policy still fixed, still doing evaluation\n",
       "\n",
       "  - Move values toward value of whatever successor occurs : running average\n",
       "\n",
       "  Sample of V(s) :\n",
       "\n",
       "$$ sample = R(s, \\pi (s), s\\) + \\gamma V^{\\pi}(s')$$\n",
       "    \n",
       "  Update to V(s) :\n",
       "\n",
       "$$V^{\\pi}(s) <- (1- \u0007lpha) V^{\\pi}(s) + (\u0007lpha) sample$$\n",
       "\n",
       "  Same update : \n",
       "\n",
       "$$V^{\\pi}(s) <- V^{\\pi}(s) + \u0007lpha(sample - V^{\\pi}(s))$$\n",
       "\n",
       "  - Exponential moving average : we wan to make recent samples more important,   so as to forget about the past (distance past values were wrong anyway)\n",
       "\n",
       "    - SO need a decreasing learning rate ( $\u0007lpha$ ) to give converging avgs : \n",
       "\n",
       "  - PROBLEMS with TD value learning : \n",
       "\n",
       "    - If we want to turn values into a NEW policy, we can't!\n",
       "\n",
       "    - We need to learn the Q-values, not values! Since $\\pi (s) = argmax_a Q(s,a)$\n",
       "\n",
       "How to find Q-values : \n",
       "\n",
       "Q-VALUE ITERATION\n",
       "\n",
       "- Use Bellman equ'n again to caluclate Q-values : \n",
       "\n",
       "  - Start with $Q_{0}(s,a) = 0$, which we know is right.\n",
       "\n",
       "  - Given $Q_k$, calculate the depth k+1 Q-vals for all Q-states : \n",
       "  $$Q_{k+1}(s,a) <- \\sum_{s'} T(s,a,s') [R(s, a, s') + \\gamma max_{a'}Q_k(s',a')]$$\n",
       "\n",
       "  - At each action, estimates of value of being in a Q state improves.\n",
       "\n",
       "  - Learn Q(s,a) values as you go : \n",
       "\n",
       "    - Receive sample (s,a,s',r)\n",
       "\n",
       "    - Consider old estimate : Q(s,a)\n",
       "\n",
       "    - Consider new sample estimate : $sample = R(s,a,s') + \\gamma max_{a'}Q(s',a')$\n",
       "\n",
       "    - Incorporate new estimate into a running avg : $Q(s,a) <- (1- \u0007lpha) Q(s,a) + \u0007lpha [sample]$\n",
       "\n",
       "      - Alpha parameter = how much we \"trust\" new info vs sample\n",
       "\n",
       "Results of Q-learning Properties : \n",
       "\n",
       "- Q-Learning converges to optimal policy EVEN IF ACTING SUBOPTIMALLY! --> OFF-POLICY LEARNING\n",
       "\n",
       "BUT, caveats : \n",
       "\n",
       "  - Have to explore enough\n",
       "\n",
       "  - have to eventually make the learning rate small enough, but not decrease too quickly\n",
       "\n",
       "Tradeoff between EXPLORATION VS EXPOITATION : \n",
       "\n",
       "- How to know when to explore new stuff (uncertain) or use existing stuff (certain)?\n",
       "\n",
       "- Exploration Function : \n",
       "\n",
       "  - Idea : explore areas whose badness is not yet established (ie. favour unvisited states)\n",
       "\n",
       "  - Take a value estimate u and a visit count n, and return an optimistic utility :   f(u,n) = u + k/n.\n",
       "\n",
       "    - n = number of times visited that state\n",
       "\n",
       "    - higher n = more certain about u; we want to factor this in.\n",
       "\n",
       "  - Modified Q-update : \n",
       "  \n",
       "  $$Q(s,a) <-_{\u0007lpha} R(s, a, s') + \\gamma max_{a'}f(Q(s',a'), N(s', a'))$$\n",
       "\n",
       "    - when n is small, we get a bonus when exploring.   \n",
       "\n",
       "  - This propagates the \"bonus\" back to states that lead to unknown states as well  \n",
       "\n",
       "  - We wish to minimize regret (which requires optimally learning to be optimal)\n",
       "\n",
       "    - Random exploration has more regret than exploration functions\n",
       "\n",
       "Now, we can't learn ALL states if there are too many, so we approximate for states : \n",
       "\n",
       "APPROXIMATE Q-LEARNING\n",
       "\n",
       "- Basic Q-Learning keeps a table of all q-vals, but in reality we can't learn about every single state! (too amny states to visit them all and to held in mem)\n",
       "\n",
       "- Instead, we wish to GENERALIZE : \n",
       "\n",
       "  - Learn about small number of training states from experience\n",
       "\n",
       "  - Generalize experience to new, similar situations\n",
       "\n",
       "  $$Q(s,a) = w_1 f_1(s,a) + ... + w_n f_n (s,a)$$\n",
       "\n",
       "- Advantage : experience summed up in a few powerful numbers\n",
       "\n",
       "- Disadvantage : states may share features but actually be very different in value\n",
       "\n",
       "- Q-learning with linear Q-functions;\n",
       "\n",
       "    - Transition = (s,a,r,s')\n",
       "\n",
       "    - difference = error term = $ [r + \\gamma max_{a'} Q(s',a')] - Q(s,a) $\n",
       "\n",
       "    - $Q(s,a) <- Q(s,a) + \u0007lpha[difference]$ (Exact Qs)\n",
       "\n",
       "      - $w_i = w_i + \u0007lpha[difference]f_i(s,a)$ (Approximate Qs)\n",
       "\n",
       "- Intuitive interpretation : \n",
       "\n",
       "  - Adjust weights of active features; ie. if something unexpectedly bad happens,   blame the features that were on : disprefer all states with that state's features. \n",
       "\n",
       "    - Eg. pacman : if near a ghost and you die, then start disprefering all states     where you're near a ghost.\n",
       "\n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Term** - your definition here\n",
       "\n",
       "\n",
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       " Your summary here \n",
       "\n",
       "## Module 10 Lecture Notes\n",
       " \n",
       "\n",
       "CONDITIONAL INDEPENDENCE : is a property of a distribution\n",
       "\n",
       "X and Y are INDEPENDENT if $$ for all x, y, P(x,y) = P(x)P(y) $$\n",
       "\n",
       "X and Y are CONDITIONALLY INDEPENDENT given Z if \n",
       "$$ for all x, y, z, P(x, y, z) = P(x|z)P(y|Z) $$\n",
       "\n",
       "BAYES RULE : \n",
       "$$P(A|B) =  (P(B|A)*P(A)) /P(B)$$\n",
       "\n",
       "Axioms of Probability : \n",
       "\n",
       "1. Prob is between 0 and 1\n",
       "\n",
       "2. Total prob of the set of all possible worlds = 1\n",
       "\n",
       "UNCERTAINTY\n",
       "\n",
       " Observed Variables (evidence): agent knows certain things about state of world (e.g. sensor readings) \n",
       "\n",
       " Unobserved Variables (states): agent needs to reason about other aspects (e.g. where object is) \n",
       "\n",
       " Model: agent knows somethign about how the known variables relate to the unknown variables \n",
       "\n",
       " Joint distribution (e.g. $P(X_1=x_1, X_2=x_2)$) - can calculate the probability of any event\n",
       "\n",
       " Marginal Distributions are sumtables which elimiate variables (Marginalization=summing out: combine collapsed rows by adding)\n",
       "\n",
       " Conditional Probabilities; simple relation between joint and conditional probabilities\n",
       "$$P(a|b) = P(a,b)/P(b)$$\n",
       "\n",
       "PROBABILISTIC INFERENCE: \n",
       "\n",
       "- compute a desired probability from other known probabilities (e.g conditional from joint)\n",
       "\n",
       "- We generally compute conditional probabilities (represent the agent's beliefs given the evidence) \n",
       "\n",
       "- Probabilities change with new evidence (observing new evidence causes beliefs to be updated)\n",
       "\n",
       "\n",
       "\n",
       " INFERENCE BY ENUMERATION: we want $P(Q|e_1...e_k)$\n",
       "1. Select entries consistent w/evidence\n",
       "\n",
       "2. Sum out hidden variables to get joint of query and evidence.\n",
       "\n",
       "3. normalize \n",
       "\n",
       "\n",
       " CHAIN RULE: write any joint distribution as an incremental product of conditional distributions \n",
       "\n",
       " $P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2) $\n",
       "\n",
       " = $P(x_1,..., x_n)\\prod_{i}^{} P(x_i|x_1....x_{i-1})$\n",
       "\n",
       "BAYES RULE : \n",
       "  \n",
       "  - $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
       "\n",
       "  - Helpful to build one conditional from its reverse; often times one conditional is   much simpler than the other\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       " PROBABILISTIC LANGUAGE MODELS: goal-assign a probability to a sentence\n",
       "\n",
       "\n",
       " (1) autocomplete for texting (2) machine translation (3) spelling correction (4) speech recognition\n",
       "\n",
       " PROBABILISTIC LANGUAGE MODELING: \n",
       "\n",
       " Goal: compute probability of a sentence or seq of words $P(W) = P(w_1...w_n)$\n",
       "\n",
       " Related Task: probability of an upcoming word $P(w_5|w_1...w_4)$\n",
       "\n",
       " Model that computes either of these, $P(W) or P(w_n | w_1...w_{n-1})$ is a LANGUAGE MODEL\n",
       "\n",
       " Compute this joint probability using chain rule \n",
       "\n",
       "\n",
       " CHAIN RULE\n",
       "\n",
       " Recall: P(B|A) = P(A, B) / P(A) ---> P(A, B) = P(A)P(B|A) \n",
       "\n",
       " Chain rule in general: $P(x_1, x_2,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2)..P(x_n|x_1,x_2,...x_{n-1})$\n",
       "\n",
       "Joint prob of words in a sentence: $P(w_1w_2w_3..w_n) = \\prod_{i}^{} P(w_i|w_1w_2...w_{i-1})$\n",
       "\n",
       "We can make a MARKOV ASSUMPTION that we only care about the previous k words, not the whole context : \n",
       "\n",
       "$P(w_1w_2w_3..w_n) = \\prod_{i}^{n} P(w_i|w_{i-k}...w_{i-1})$, where k = # of context words to take into account\n",
       "\n",
       "\n",
       "\n",
       "\n",
       " EXTRA NOTES:\n",
       "\n",
       " If process is stationary, the conditional probability table does not change over time \n",
       "\n",
       " Dynamic Bayesian Model (DBN), uncessary for construction: multiple state and evidence variables\n",
       "\n",
       " \n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Term** - your definition here\n",
       "\n",
       "\n",
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       " Your summary here \n",
       "\n",
       "## Module 11 Lecture Notes\n",
       " \n",
       "Bayes Nets : \n",
       "We make use of conditional independence assumptions to model the world. \n",
       "Why? Because using full joint distribution tables as our probabilistic model is too hard : \n",
       "\n",
       "1. Joint is way too big to represent explicitly\n",
       "\n",
       "2. Hard to learn (estimate) anything empirically about more than a few variables at a time.\n",
       "\n",
       "3. Conditional independence is our most basic and robust form of knowledge about uncertain environments. \n",
       "\n",
       "\n",
       "\n",
       "Bayes nets are a technique for describing complex joint distributions (models) using simple, local  distributions (conditional probabilities)\n",
       " - we describe how variable locally interact in a chain together to give global,  indirect interactions. \n",
       "\n",
       " Graphical Model Notation of a Bayes Net : \n",
       " - Nodes : variables (with domains). Can be assigned (observed) or unassigned (unobserved).\n",
       " - Arcs : interactions. Ie. direct influence between variabels : encode conditional independence. \n",
       "\n",
       "Probabilities in BNs : \n",
       "We are guaranteed that $$P(x_{1}, ..., x_{n}) = \\prod_{i = 1}^{n} P(x_{i} | parents(X_{i}))$$ results in a proper joint distribution because of the CHAIN RULE and assuming conditional independence : \n",
       "- Chain rule : $P(x_{1}, ..., x_{n}) = \\prod_{i = 1}^{n} P(x_{i} | (X_{1},...,X_{i-1})$ \n",
       "- Assume conditional independences : $P(x_{1}, ..., x_{n}) = P(x_{i} | parents(X_{i})$\n",
       "\n",
       "NOTE : Not every BN can represent every joint distribution (topology enforces certain conditional independencies).\n",
       "- BNs don't actually need to be causal. \n",
       "  - sometimes no causal net exists over the domain (esp if variables are missing)   - end up with arrows that reflext corrolation, not causation - What do the arrows really mean :  - Topology may happen to encode causal structure   - Topology really encodes conditional independence \n",
       "SIZE of BNs :\n",
       "\n",
       "- Joint distribution over N boolean variables = $2^{N}$ \n",
       "\n",
       "- Size of N-node net if nodes have up to k parents : $O(N * 2^{k+1})$\n",
       "\n",
       "- BNs have huge space savings!\n",
       "\n",
       "D-Separation : \n",
       "\n",
       "Any complex BN example can be broken down into repetitions of the three canonical cases, to see if two variables are independent.\n",
       "\n",
       "1. CAUSAL CHAIN configuration : Z->Y->Z\n",
       "\n",
       "  - X NOT GUARANTEED INDEPENDENT OF Z : easy to find one example for which X   not independent of Z\n",
       "\n",
       "  - X IS guaranteed independent of Z given Y : suffices to show we can   write P(z|x, y) as P(z|x or P(z|y)) \n",
       "\n",
       "  $$P(z|x,y) = {P(x, y, z)} / {P(x,y)}$$\n",
       "  $$ = {P(x)P(y|x)P(z|y)} / {P(x)P(y|x)} \\from conditional indep' assumptions $$\n",
       "  $$ = P(z|y) $$\n",
       "\n",
       "2. COMMON CAUSE configuration : X <- Y -> Z\n",
       "\n",
       "  - X NOT GUARANTEED INDEPENDENT OF Z (since both due to common cause Y)\n",
       "\n",
       "  - X IS guaranteed independent of Z given Y : \n",
       "$$P(z|x,y) = {P(x, y, z)} / {P(x,y)}$$\n",
       "  $$ = {P(y)P(x|y)P(z|y)} / {P(y)P(x|y)} \\from conditional indep' assumptions $$\n",
       "  $$ = P(z|y) \\= YES $$\n",
       "\n",
       "3. COMMON EFFECT configuration : X -> Z <- Y\n",
       "\n",
       "  - X and Y ARE INDEPENDENT : they both impact z, but are not corrolated in any way\n",
       "\n",
       "  - X and Y are NOT indepentent given Z : since seeing Z means that both Z and Y are affected and competing as the explanation. \n",
       "\n",
       "  - This is backwards from other cases : observing an effect activates influence  between possible causes.\n",
       "\n",
       "D-separation algo : Given a BN structure, can run d-separation algo to build a complete list of conditional independences that are necesarily true\n",
       "\n",
       "1. Query : are X_i and X_j independent, given ${X_{k1},...,X_{kn}}$?\n",
       "\n",
       "2. CHeck all (undirected) paths between Xi and Xj \n",
       "\n",
       "  - If one or more path is active (ie each triple active), then independence NOT guaranteed\n",
       "\n",
       "  - Else, if all paths inactive, then independence guaranteed\n",
       "\n",
       "\n",
       "INFERENCE : **\\TODO : FINISH/EXPAND\n",
       "\n",
       "Calculating some useful quantity from a joint probability distribution.\n",
       "\n",
       "- Given unlimited time, inference in BNs is easy, but is very slow since we need to join up the whole joint distribution before we sum out the hidden variables.\n",
       "\n",
       "\n",
       " \n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       " Your summary here \n",
       "\n",
       "## Module 12 Lecture Notes\n",
       " \n",
       "MACHINE LEARNING BIG PICTURE :\n",
       "\n",
       "Up to now : how to use a model to make optimal decisions.\n",
       "\n",
       "ML : how to ACQUIRE A MODEL from data/experience\n",
       "\n",
       "- Learning parameters (ie. probabilities)\n",
       "\n",
       "- Learning structure (eg. BN graphs)\n",
       "\n",
       "- Learning hiddel concepts (eg. clustering)\n",
       "\n",
       "We cover a model-based classification with Naive Bayes and Perceptrons.\n",
       "\n",
       "Model-based Classification:\n",
       "\n",
       "- Build a model where both the label and features are random variables\n",
       "\n",
       "- Instantiate any observed features\n",
       "\n",
       "- Query for the distribution of the label conditioned on the features\n",
       "\n",
       "Challenges : What structure should BN have? How to learn its parameters?\n",
       "\n",
       "NAIVE BAYES : assume all features are INDEPENDENT EFFECTS of the label. \n",
       "\n",
       "While this is often too strong to perfectly represent reality, it is still helpful to easily estimate parameters of naive-based model.\n",
       "\n",
       "- We need to learn all the probability tables : prior prob, conditional prob.\n",
       "\n",
       "- General Naive Bayes model : has |Y| labels,  $|Y|*|F|^{n}$ values and $n*|F|*|Y|$ parameters.\n",
       "\n",
       "$$P(Y, F_{1},...,F_{n}) = P(Y) \\prod_{i} P(F_{i}|Y)$$\n",
       "\n",
       "Note : \n",
       "\n",
       "- we only have to specify how each feature depends on the CLASS. \n",
       "\n",
       "- Total number of params is LINEAR in number of features (PRO)\n",
       "\n",
       "- Model is very simplistic, but often works anyway\n",
       "\n",
       "INFERENCE for Naive Bayes : \n",
       "\n",
       "Goal : compute posterior distribution over label variable Y (see screenshot)\n",
       "\n",
       "1. get joint porbability of label and evidence for each label : \n",
       "\n",
       "  - $P(Y|f_{1},...,f_{n})$ = Joint probability table MATRIX of ($P(y_{i}, f_{1},...,f_{n})$) for all i in k)\n",
       "\n",
       "  - rewrite matrix using independence assumptions of Bayes net:\n",
       "$$P(y_{j} \\prod_{i} P(f_{i}| y_{j})) \f",
       "or j in k $$\n",
       "\n",
       "  - normalize by dividing by probability of evidence : $P(Y | f_{1},..,f_{n})$\n",
       "\n",
       "Next, we need ESTIMATES of local conditional probability tables : Both aredenoted as the PARAMETERS of the model, $\\Theta$\n",
       "\n",
       "- P(Y) = prior probability over labels\n",
       "\n",
       "- $P(F_{i}|Y)$ : evidence variable for each feature\n",
       "\n",
       "These parameters are obtained from training data counts\n",
       "\n",
       "How data is used to obtain these parameters : Data split between training, held out, and test sets.\n",
       "\n",
       "1. Training data : should be a big chunk of your data. Used to learn parameters during Experimentation Cycle. \n",
       "\n",
       "2. Held out set : used for tuning hyperparameters\n",
       "\n",
       "3. Run model on test set, Compute accuracy (Evaluation Cycle)\n",
       "\n",
       "POTENTIAL ISSUES :\n",
       "\n",
       "1. OVERFITTING :fitting the training data very closely, but not generalized enough for other data\n",
       "\n",
       "2. UNDERFITTING : model does not find any trend in data\n",
       "\n",
       "Parameter estimation : use MAXIMUM LIKELIHOOD \n",
       "\n",
       "Relative frequencies are the maximum likelihood estimates : \n",
       "\n",
       "$$\\Theta _{ML} = argmax_{Theta} P(X| \\{Theta} )$$\n",
       "$$ = argmax_{Theta} \\prod_{i} P_{\\Theta}(X_{i})$$\n",
       "\n",
       "P(ML(x)) = count(x) / total samples.\n",
       "\n",
       "How to deal with avoiding zero probabilities?\n",
       "\n",
       "-> LAPLACE SMOOTHING : pretend you saw every outcome one more than you actually did.\n",
       "\n",
       "$$P_{LAP}(x) = C(x) + 1 / N + |X| $$\n",
       "\n",
       "Can also smooth with factor k.\n",
       "\n",
       "LaPlace smoothing for conditionals : \n",
       "$$P_{LAP}(x|y) = (C(x,y) + k) / (x(y) + k|X| $$\n",
       "\n",
       "An alternative to LaPlace smoothing : LINEAR INTERPOLATION\n",
       "\n",
       "- Which also gets the empirical P(X), given that estimate of P(X|Y) isn't too far from the empirical P(X). \n",
       "$$P_{LIN}(x|y) = \u0007lpha P_{hat}(x|y) + (1 - \u0007lpha)P_{hat}(x) $$\n",
       "\n",
       "- If alpha = 0 : no weight to conditional : just based on prior.\n",
       "\n",
       "- If alpha = 1 : same as MLE.\n",
       "\n",
       "CONFIDENCE from a classifier :\n",
       "\n",
       "Confidence of a probabilistic classifier : posterior over the top label\n",
       "\n",
       "- $confidence(x) = max_{y} P(y|x)$ : represents how SURE the classifier is of the classification\n",
       "\n",
       "- weak calibration : higher confidences = higher acuracy\n",
       "\n",
       "- strong calibration : confidence predicts accuracy rate\n",
       "\n",
       "What to do about errors : \n",
       "\n",
       "- Need more features!!\n",
       "\n",
       "/// NEW SECTION:\n",
       "\n",
       "PERCEPTRONS : \n",
       "\n",
       "Perceptrons = error-driven learning, does not use probabilities but WEIGHTS.\n",
       "\n",
       "Inputs are features representing something we wish to clasify. \n",
       "\n",
       "- Feature values for inputs are fixed\n",
       "\n",
       "- But we can choose different weight vectors, to get different classifiers. \n",
       "\n",
       "LINEAR classifiers : \n",
       "Inputs are feature values; each feature has a WEIGHT.\n",
       "\n",
       "Sum is the ACTIVATION.\n",
       "\n",
       "$$activation_{w}(x) = \\sum_{i} w_{i} * f_{i}(x) = w . f(x) $$\n",
       "\n",
       "- If activation + b > 0, pos : output is +1 (pos class)\n",
       "\n",
       "- If activation + b <0, neg : output is -1 (neg class)\n",
       "\n",
       "b = bias = -theshhold.\n",
       "\n",
       "In the binary case, we compare features to a weight vector. \n",
       "\n",
       "Learning : we need to figure out the weight vector from examples\n",
       "\n",
       "Binary Perceptron algorithm : we want to learn the weight vector.\n",
       "1. Start with weights = 0\n",
       "\n",
       "2. For each training instance ; \n",
       "  - Classify input with current weights\n",
       "\n",
       "  - If correct (y = y*), no change\n",
       "\n",
       "  - Else, if wrong : adjust the weight vector by adding or substracting the   feature vector. Substract if y* is -1. $w = w + y^{*} * f$.\n",
       "\n",
       "MULTICLASS for more than 2 labels : similar, but pick the label by calculating argmax of the activation of class y:\n",
       "1. Start with weights = 0\n",
       "\n",
       "2. For each training instance : \n",
       "  - Classify with current weights : $y = argmax_y w_y * f(x)$\n",
       "\n",
       "  - If correct, no change\n",
       "\n",
       "  - If wrong : LOWER score of WRONG answer, RAISE score of RIGHT  answer.\n",
       "\n",
       "    - $w_y = w_y - f(x)$ : lower score of wrong predicted\n",
       "\n",
       "    - $w_{y^{*}} = w_{y^{*}} + f(x)$ : raise score of right\n",
       "\n",
       "\n",
       "PROPERTIES of perceptrons : \n",
       "- SEPARABILITY : data is separable if some parameters get the training set perfectly correct.\n",
       "- CONVERGENCE : if training is separable, perceptron will eventually converge(binary case)\n",
       "- MISTAKE BOUND : the maximum number of mistakes (binary case) related to the 'MARGIN'(or degree, or space between classes) of separability is bounded : $mistakes < \f",
       "rac{k}{margin^{2}}$\n",
       "\n",
       "\n",
       "PROBLEMS with the perceptron : \n",
       "1. NOISE : if the data is not separable, weights might thrash\n",
       "  - Sol : avg perceptron : avg weight vectors over time\n",
       "\n",
       "2. Mediocre generalization : finds the \"barely\" separable solution, but not the best.\n",
       "\n",
       "3. Overtraining : test accuracy peaks, then falls. Is a kind of overfitting.\n",
       "\n",
       "\n",
       "FIXING the perceptron : \n",
       "- MIRA : Margin-infused Relaxed Algorithm : chooses an update size that fixes the current mistake, but minimizes the change to w. \n",
       "\n",
       "$$min_{w} \f",
       "rac{1}{2} \\sum_{y} ||w_{y} - w'_{y}||^{2}$$ s.t.\n",
       "\n",
       "$$ w_{y^{*}} . f(x) >= w_{y} . f(x) + 1  /the +1 helps to generalize $$\n",
       "\n",
       "Maximum Step Size : \n",
       "- In practice, it's bad to make updates too large, esp. for non-separable data.\n",
       "  - Example may be labeled incorrectly\n",
       "  - May not have enough features\n",
       "\n",
       "- Sol : cap the maximum possible values of Tau with constant C\n",
       "  - Converges faster than perceptron, and better for noisy data\n",
       "\n",
       "For Linear separators, how to tell what the optimal one is?\n",
       "- SUPPORT VECTOR MACHINES : ie. MIRA but optimize over all examples at once, \n",
       "  - ie. minimize distance of point and separator for all data points\n",
       "\n",
       "\n",
       "OVERALL SUMMARY : Naive Bayes vs Perceptrons/MIRA:\n",
       "\n",
       "Naive Bayes:\n",
       "-  builds a modek training data, gives prediction probabilities.\n",
       "- strong assumptions about feature independence\n",
       "- one pass through data (counting)\n",
       "\n",
       "Perceptrons / MIRA : \n",
       "- Make less assumptions about data\n",
       "- Mistake-driven learning\n",
       "- multiple passes thorugh data(prediction)\n",
       "- often more accurate\n",
       "\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       " \n",
       "Neural Networks, Big Picture : \n",
       "\n",
       "Essentially a bunch of stacked perceptrons, like \"neurons\" working together.\n",
       "\n",
       "Neural network has 4 Classifier components : \n",
       "1. Feature representation of the input : for each input observation $x^{i}, vector of features $[x_{1},..,x_{n}].\n",
       "\n",
       "2. Classification function : computes the estimated class $y^{\\^} via $p(y|x):\n",
       "- $y^{\\^} = max_{y}(P(y|x))$.\n",
       "\n",
       "3. Objective function : for learning : minimize error on training egs (ie. LOSS fn)\n",
       "\n",
       "4. Algorith for optimizing the objective function\n",
       "\n",
       "SENTIMENT CLASSIFIIER\n",
       "\n",
       "Consider input obs x represented by a vector of features [x_1, ..., x_n]. \n",
       "\n",
       "Classifier output y can be 1 (pos) or 0 (neg).. We wish to estimate P(y = 1 | x_vec).\n",
       "\n",
       "LOGISTIC REGRESSION solves this by learning from a training set a vector of weights and a bias term : \n",
       "$$z = \\sum_{i} w_{i}x_{i} + b = w . x + b \\ dot product $$\n",
       "\n",
       "We normalize z to be between 0 and 1 by passing it through a SIGMOID f'n (also called logistic f'n) : \n",
       "$$y = 1/(1+e^{-z}) $$\n",
       "\n",
       "So we have $P(y = 1) = \\sigma(w . x + b) = 1/(1+e^{-(w . x + b)})$\n",
       "\n",
       "DECISION BOUNDARY : how to make the decision? Set threshhold : \n",
       "\n",
       "$y_{hat} = 1, if P(y = 1|x) > 0.5, 0 otherwise $\n",
       "\n",
       "^ theshhold = 0.5.\n",
       "\n",
       "Another way we can analyse if pos or neg sentiment : FEATURE EXTRACTION\n",
       "\n",
       "We count the instances of each feature, and we give each a weight corresponding to how much they contribute to the class. \n",
       "\n",
       "Take dot product of features and weights to find z (z = w . x + b), and pass  through Sigmoid(Z).\n",
       "\n",
       "Next:\n",
       "\n",
       "LEARNING in logisit regression, ie. how to get the weights of the model : \n",
       "\n",
       "We learn the parameters (weights and bias) via learning, which requires : \n",
       "\n",
       "1. An objective, or LOSS function, that tells us the distance between the system output and the gold output. \n",
       "  - We use CROSS-ENTROPY LOSS.\n",
       "\n",
       "2. Algo for optimizing the objective function. \n",
       "  - We use STOCHASTIC GRADIENT DESCENT to minimize the Loss function.\n",
       "\n",
       "Loss functions: ie how much the classifier output (y^) is close to correct output (y).\n",
       "\n",
       "L(y^, y) = how much y^ differs from the true y. \n",
       "\n",
       "One eg. is Mean-Squared Error (MSE) : \n",
       "$$L_{MSE}(\\hat{y},y) = 1/2(\\hat{y} - y)^{2}$$\n",
       "\n",
       "Loss functions for probabilistic classification : \n",
       "\n",
       "We use a loss f'n that prefers the correct class labels of the training example to be more likely.\n",
       "\n",
       "Conditional max likelihood estimation : Choose params w_vec, b that MAXIMIZE the (log) probs of the true labels in the training data.\n",
       "\n",
       "Resulting loss function is the NEGATIVE LOG LIKELIHOOD loss ie. CROSS-ENTROPY LOSS.\n",
       "\n",
       "(directionality is preserved in log space)\n",
       "\n",
       "$$log p(y|x) = log[\\hat{y}^{y}(1-\\hat{y})^{1-y}]$$\n",
       "$$ = ylog \\hat{y}, + (1-y)log(1-\\hat{y})$$\n",
       "For loss function we want to minimize, so flip the sign and plug in our expression for y' : \n",
       "$$L_{CE}(\\hat{y}, y) = -log p(y|x) = -[y log \\sigma(w . x + b) + (1-y) log(1-\\sigma(w . x + b))]$$\n",
       "\n",
       "Why does minimizing the negative log probability work:?\n",
       "\n",
       "- We want the LOSS to be SMALLER if the model's estimate is close to correct,\n",
       "\n",
       "- and we want the loss to be BIGGER if it is confused.\n",
       "\n",
       "- -log of a small val becomes infinitely large\n",
       "\n",
       "Now, loss on ALL training exmpls : \n",
       "\n",
       "$$log p(training labels) = log \\prod_{i =1}^{m} p(y^{i} | x^{i}) $$\n",
       "$$ = \\sum_{i = 1}^{m} log p(y^{i} | x^{i}) $$\n",
       "$$ = - \\sum_{i = 1}^{m} L_{CE}(\\hat{y}^{i} | y^{i})$$\n",
       "\n",
       "\n",
       "Now, how to find good parameters : \n",
       "\n",
       "GRADIENT DESCENT to find good settings by minimizing loss function\n",
       "\n",
       "$$\\Theta = argmin_{\\Theta} 1/m \\sum_{i = 1}^{m} L_{CE}(y^{i}, x^{i}; \\Theta) $$\n",
       "\n",
       "Gradient descent is a method that finds a minimum of a function by figuring out in which direction (in the space of the parametres $\\Theta$ the f'ns slope is risinhg the most steeply, and moving in the opposite direction. \n",
       "\n",
       "CAN't get stuck on a local min :\n",
       "For logistic regression, the loss function is CONVEX = only one minimum! Great,we can't get stuck in a local minima. \n",
       "\n",
       "Gradient descent starting from any point is GUARANTEED to find the minimum.\n",
       "\n",
       "Size of learning rate, ie. magnitude of amount to move in gradient descent, is the value of the slope weighted by a learning rate $\\eta$\n",
       "\n",
       "A higher/faster learning rate = more w more on each step.\n",
       "\n",
       "$$w^{t + 1} = w^t - \\eta * d/dw (f(x;w))$$\n",
       "\n",
       " = old weight - eta (step size) * derivative (slope) of f'n \n",
       "\n",
       " NOW, for many dimensions:\n",
       "\n",
       " each dimension will impact the loss f'n.\n",
       "\n",
       "//TODO : finish the section introducing sigmoid and PERCEPTRON stuff\n",
       "\n",
       "NEURAL NETWORKS intro : \n",
       "\n",
       "- We will be looking at feedforward neural networks, with hidden layers that are essentially layers of perceptron. Output of one later = input of next.\n",
       "\n",
       "- We use the sigmoid function for neurons insteaed of the perceptron (step f'n) to smooth out the neuron, so that small changes in the weights w_j and in the bias b will only produce a small change of the output from the neuron. \n",
       "\n",
       "- Non-linear activation functions we can choose: Sigmoid, tanh, ReLU (see sheet)\n",
       "\n",
       "- Simplest kind of NN = Feed forward NN : \n",
       "  \n",
       "  - Multilayer, all units fully connected, no cycles. \n",
       "\n",
       "- Equations for a feedforward NN : \n",
       "\n",
       "  - A single hidden unit has params w_vec and b (bias scalar). \n",
       "\n",
       "  - We represent the parameters for the entire hiddne layer by combining the   weight vector w_i and bias b_i for each unit i into a single weight matrix   W and a single bias vector b_vec for the whole layer. \n",
       "\n",
       "    - Can easily compute outout : $h = \\sigma (Wx + b)$\n",
       "\n",
       "  - Ouput layer has a weight matrix U, multiplied by input vec h_vec to produce   the intermediate output z : $z = Uh$.\n",
       "\n",
       "  - We then pass z through a softmax function to output the probability distribution y : \n",
       "    - $y = softmax(z)\n",
       "\n",
       "TRAINING neural nets : \n",
       "\n",
       "Like logisitic regresssion, we wish to learn the best params for the NN to make predicitons $\\hat{y}$ as close to possible as the gold standards labels from training data, y.\n",
       "\n",
       "We need : \n",
       "\n",
       "1. A loss f'n : Cross-entropy loss\n",
       "\n",
       "2. an Optimization algo : gradient descent\n",
       "\n",
       "3. A way of computing the gradient of the loss function : error back propagation (since we have more layers of indirection)\n",
       "\n",
       "How to compute the gradient : which direction to \"nudge\" the params?\n",
       "\n",
       "Since we have multiple layers now, we must compute the BACKWARD DIFFERENTIATION across the layers.\n",
       "\n",
       "- Error back-propogation enables us to correctly update all layers in the NN.\n",
       "\n",
       "- Represent the model as a COMPUTATION GRAPH (see sheet). Use chain rule to express in terms of partial derivatives\n",
       "\n",
       " \n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       " Your summary here \n",
       "\n",
       "## Module 14 Lecture Notes\n",
       " \n",
       "Neural Language Models : \n",
       "Have several advantages over n-gram LMs : \n",
       "\n",
       "- Don't need smoothing\n",
       "\n",
       "- Can handle much longer histories\n",
       "\n",
       "- They can generalize over contexts of similar words.\n",
       "\n",
       "- Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
       "\n",
       "DISADVANTAGE : slower to train than traditional n-gram LMs.\n",
       "\n",
       "Idea : \n",
       "\n",
       "1. Associate each word in vocab with vector-rep : thereby creating a notion of similarity between words\n",
       "\n",
       "2. Express joint prob f'n of a word sequence in terms of word vectors for words in sentence\n",
       "\n",
       "3. Simultaneously learn the word vectors and parameters of the f'n.\n",
       "\n",
       "- Prob. f'n is expressed through the product of conditional probs of the next word given the previous word using a multi-layer, feed -forward neural network\n",
       "\n",
       "Neural LMs : \n",
       "\n",
       "- INPUT = k-0gram of words $w_{1:k}$\n",
       "\n",
       "- OUTPUT = prob distribution over next word\n",
       "\n",
       "- k context words are treated as a word window. Each word is associated with an embedding vector\n",
       "\n",
       "Advantage also is that we get training for \"free\" from the corpus (large body of text)!\n",
       " egs are simply word k-grams from corpus. \n",
       "\n",
       "Then train as usual using cross-entropy loss\n",
       "\n",
       "Current state of the art neural LMs : \n",
       "\n",
       "- ELMo\n",
       "\n",
       "- GPT 2/3\n",
       "\n",
       "- BERT\n",
       "\n",
       "MEANING in NLP :\n",
       "\n",
       "How to represent meaning of a word?\n",
       "\n",
       "- In N-gram LMs, we just represented words as a string of letters, ie. tokens, 'so we did not care about understanding meaning.\n",
       "\n",
       "- Ideally, we want a meaning representation to encode :\n",
       "\n",
       "  - Synonyms\n",
       "\n",
       "  - Antonyms\n",
       "\n",
       "  - Connotations - words that are pos or neg\n",
       "\n",
       "  - Semantic Roles - eg. buy, sell and pay are different parts of same underlying puchasing event\n",
       "\n",
       "  - Support for entailment\n",
       "\n",
       "VECTOR SPACE MODELS : \n",
       "\n",
       "- Allows us to see how semantically similar words are (clustered together by meaning)\n",
       "\n",
       "- Really important to be able to understand similarity, not necessarily synonymous (eg. cat and dog)\n",
       "\n",
       "- Solution : \"Distributional Hypothesis\" - Zellig Harris. Similarity can be detected by how similar the environment (or context) the words appear in. \n",
       "\n",
       "\n",
       "TERM-DOCUMENT MATRIX : \n",
       "\n",
       "- matrix where each column vector represents a document\n",
       "\n",
       "- each row vector = represents a Term\n",
       "\n",
       "- Each cell = how often that term occured in document\n",
       "\n",
       "- Length of the document vectors is the size of the vocabulary (ie. number of rows)\n",
       "\n",
       "  - Meaning that the document vectors (columns) can be very sparse\n",
       "\n",
       "- We can measure how similar two documents are by comparing their column vectors.\n",
       "\n",
       "- Potential use cases = plagiarism detection.\n",
       "\n",
       "- Comparing two rows = comparing how similar both terms are (ie. how much they both fit in the same context)\n",
       "\n",
       "- Document vecot\n",
       "How to identify word similarity : \n",
       "\n",
       "1. VECTOR COMPARISONS : \n",
       "\n",
       "- Can plot each point on a graph and use Euclidean distance to relate words to each other.\n",
       "$$\\sqrt{\\sum_{i=1}^{n} |u_{i}-v_{i}|^{2}}$$\n",
       "  - PROBLEM with this is that we are affected by FREQUENCY of the word, so for eg. it could   wrongly put \"good\" closer to \"disappointing\" than \"superb\".\n",
       "\n",
       "- Solution : NORMALIZE : Vector L2 (length) normalization, solves for freq. issue.\n",
       "$$||u|| = \\sqrt{\\sum_{i=1}^{n} u_{i}^{2}}$$\n",
       "\n",
       "  -   Divide each vector by its L2 length.  \n",
       "\n",
       "Another method to get similarity :\n",
       "\n",
       "2. COSINE DISTANCE : Does the L2 normalization too. \n",
       "\n",
       "- Cosine angle between vectorsr tells us their similarity\n",
       "\n",
       "\n",
       "Language structure : \n",
       "\n",
       "- Languages have long distance dependencies\n",
       "\n",
       "  - Eg. noun-verb-adj structure can be split by sub-clauses eg. \"photographs   of the man ARE lovely\"\n",
       "\n",
       "Another way of modeling :\n",
       "\n",
       "TERM-TERM MATRIX : instead of term-by-document matrix where we count how often a word occurs in a document.\n",
       "\n",
       "-  Length = size of vocab |V| vs # documents in collection      \n",
       "\n",
       "- We count instances of a word appearing in a context window (eg. 2 words before and 2 words after) in the same sentence of the same doc.\n",
       "\n",
       "- But this ignores the fact that languages have long-distnace dependencies!\n",
       "\n",
       "- We must use syntax to define a word's context\n",
       "\n",
       "\n",
       "Alternative to counts : \n",
       "\n",
       "- Raw word frequency is not a great measure of association between words. \n",
       "\n",
       "- Skews common words such as \"the\" and \"of\" as very important because very frequent,even if they are not the most discriminative (and common in all documents)\n",
       "\n",
       "- Must instead hav a measure that asks whether a context word is particularly informative about the target word. \n",
       "\n",
       "- Instead of raw counts, TRANSFORM VECTORS using TF-IDF or PPMI\n",
       "\n",
       "TF-IDF : \n",
       "\n",
       "- Term Frequency * (Inverse Document Frequency)\n",
       "\n",
       "  - TF = how often a word occured in a doc\n",
       "\n",
       "  - IDF = 1/(# docs word occurred in) ie a measure of how unique this word is   to this particular text / context.\n",
       "\n",
       "\n",
       "More modern approach to word vectors : \n",
       "\n",
       "- So far, word vectors are super LONG (length = |V|) and SPARSE (most elements = 0)\n",
       "\n",
       "- Alternatively, more modern approaches use SHORT (length = 100-1000) and DENSE vectors\n",
       "\n",
       "How to get dense vectors? --> Train a classifier\n",
       "\n",
       "1. Treat target word and neighboring context word as positive examples\n",
       "\n",
       "2. Randomly sample other words in the lexicon that don't show up in neighbor to get negative samples.\n",
       "\n",
       "3. Train logisitic regression classifier starting with a randomly initialized set of weights to distinguish whether 2 words co-occur in corpus or not. Weights create dense vector representation : Use learned weights as word representation.\n",
       "\n",
       "  - Formed basis of Google's 'Word2Vec\" : leanrn embeddings as part of the process   of word prediction. \n",
       "\n",
       "  - Advantages : fast, easy to train (faster than SVD), open-source\n",
       "\n",
       "Word2Vec : \n",
       "\n",
       "- Predict each neighboring word in a context window of 2C of surrounding words\n",
       "\n",
       "- Instaed of counting, we can train a classifier on a binary perceptron task. \n",
       "\n",
       "  - Use the learned classifier weights as the word embeddings. \n",
       "\n",
       "  - This means we can use running text as implicitly supervised training data!   = no need for hand-labeled supervision.\n",
       "\n",
       "SKIP-GRAM ALGORITHM : \n",
       "\n",
       "- Treat target word and a neighboring context word as positive exxamples.\n",
       "\n",
       "- Randomly sample other words in the lexicon to get negative samples.\n",
       "\n",
       "- Use logistic regression to train a classifier to distinguish those two cases.\n",
       "\n",
       "- Use the weights as embeddings. (vector rep of meaning of the words.)\n",
       "\n",
       "  - NOTE : still need to compute the following way : \n",
       "\n",
       "  1. Compute p(+|t,c) by calculating DOT PRODUCT : similarity(t,c) ~= t . c\n",
       "\n",
       "  2. Next, turn dot product into probability : plug it into the sigmoid function\n",
       "\n",
       "  3. For ALL context words, assume all context words are independent : \n",
       "\n",
       "$$P(+ |t, c_{1:k}) = \\prod_{i=1}^{K} 1 / (1 + e^{-t*c_i}) $$\n",
       "\n",
       "  4. Take the log to turn product into sum, and move log inside sum\n",
       "\n",
       "  5. We want to MAXIMIZE the similariy of (t,c) paris from the POSitive data    and MINIMIZE the similarity of the (t,c) paris from the NEGative data.\n",
       "\n",
       "$$L(\\Theta) = log P(+|t,c) + \\sum_{i = 1}^{k} log P(- | t, n_i) $$\n",
       "\n",
       "$$ = log \\sigma (c . t) + \\sum_{i = 1}^{k} log \\sigma (- n_i . t) $$\n",
       "\n",
       "where sigma = sigmoid f'n\n",
       "\n",
       "  6. Finally, we train using gradient descent and we learn two separate embedding   matrices W and C. \n",
       "\n",
       "    - We can use W and throw away C or merge them.\n",
       "\n",
       "\n",
       "- How to evaluate the embeddings?\n",
       "\n",
       "  - COmpare to human scores on word similarity-type tasks eg wordSim-353\n",
       "\n",
       "\n",
       "How to choose noise words :\n",
       "\n",
       "- Pick word accoridng to their unigram frequency, and favor rare words : \n",
       "\n",
       "$$P_{\u0007lpha} (w) = count(w)^{\u0007lpha} / \\sum_{w} count(w)^{\u0007lpha} $$\n",
       "\n",
       "- alpha = 3/4 workds well for giving rare noise words slightly higher probability\n",
       "\n",
       "\n",
       "- Embeddings capture relational meanings : eg. binary gender associations :  man->woman, uncle->aunt\n",
       "\n",
       "  - Vector arithmetic for relational meanings : \n",
       "  - eg. vector('king') - vector('man') + vector('queen') = vector('woman')\n",
       "\n",
       "- Can expose biases in data especially over time\n",
       "\n",
       " \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))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "FINAL 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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
