{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes & definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy & 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, & fill in all the summaries for each chapter & 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 h&written 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 L&scape 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 & pasted), & 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 & 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 & Martin's Speech & Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "cba7543a-70c8-45c9-a592-80b30c3ac0fa"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "4987c10a-e673-4fcb-be2d-9c5d090ab3c0"
      },
      "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 bl&it 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 bl&it 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 bl&it 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 bl&it \\\n",
        " volutpat maecenas volutpat bl&it aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3020\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, & you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell & 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 = \"\"\"\n",
        "- Agent assigns probability P(s) to each possible current state s\n",
        "- Transition model: given by P(s' | s,a), the probability that action a in state s reaches state s'\n",
        "- P(Result(a) = s') = sum(P(s) * P(s'|s,a))\n",
        "- Utility function U(s): agent's preferences captured in a single number to express desirability of a state\n",
        "- Expected utility of an action given evidence EU(a): average utility value of the outcomes weighted by the probability that the outcome occurs\n",
        "- Principle of maximum expected utility (MEU): rational agent should choose action that maximizes agent's expected utility\n",
        "  - Maximizing utility doesn't mean the problem is solved by the definition: formalizes that agent should 'do the right thing' but doesn't operationalize that advice\n",
        "- If an agent acts to maximize a utility function that correctly reflects the performance measure, then agent will achieve the highest possible performance score (averaged over all possible environments)\n",
        "\"\"\"  ##+ sample_equation\n",
        "\n",
        "chapter16_2 =  \"\"\"\n",
        "- Constraints on rational preferences\n",
        "\t- Can think of set of outcomes for each action as a lottery; each action = ticket\n",
        "\t- Primary issue for utility theory: underst& how preferences between complex lotteries are related to preferences between the underlying state in those lotteries\n",
        "\t\t- Axioms of utility theory: 6 constraints that we require any reasonable preference relation to obey:\n",
        "\t\t\t- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable; cannot avoid deciding\n",
        "\t\t\t- Transitivity: Given any three lotteries, if an agent prefers A to B & prefers B to C, then the agent must prefer A to C\n",
        "\t\t\t- Continuity: If some lottery B is between A & C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure & the lottery that yields A with probability p & C with probability 1-p\n",
        "\t\t\t- Substitutability: If an agent is indifferent between two lotteries A & B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n",
        "\t\t\t- Monotonicity: Suppose two lotteries have the same two possible outcomes, A & B. If agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A\n",
        "\t\t\t- Decomposability:  Compound lotteries can be reduced to simpler ones using the laws of probability\n",
        "- 16.2.2 Rational preferences lead to utility\n",
        "\t- From axioms of utility, can derive the following:\n",
        "    - Existence of utility function: if agent's preferences obey the axioms of utility, then there exists a function U such that U(A)>U(B) iff A is preferred to B & U(A)=U(B) iff agent is indifferent between A & B\n",
        "    - Expected utility of a lottery: utility of lottery = sum[probability of each outcome * utility of that outcome]\n",
        "  - Once the probabilities & utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined\n",
        "\t- In a deterministic environment, an agent needs only a preference ranking on states (numbers don't matter)\n",
        "\t\t- Called a value function or ordinal utility function\n",
        "  - Existence of utility function that describes agent's preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\"\n",
        "- Preference elicitation: process to work out what a human's utility function is by presenting choices to them & using observed preferences to pin down the underlying utility function\n",
        "- Useful to establish some scale on which utilities can be recorded & compared for any particular problem by fixing the utilities of any two particular outcomes (best vs worst possible)\n",
        "\t- Normalized utilities: scale between 0 & 1\n",
        "- Utility of money almost exactly proportional to log of the amount\n",
        "  - Most people have a utility function that is concave for positive wealth\n",
        "  - Agent with linear curve: risk-neutral\n",
        "- Expected utility & post-decision disappointment\n",
        "\t- Rational way to choose best action: maximize expected utility\n",
        "\t- Model usually oversimplifies real situation: either because we don't know enough or because the computation of the true expected utility is too difficult\n",
        "\t\t- Therefore working with estimates of true expected utility\n",
        "\t\t- Assume estimates are unbiased: expected value of error is zero\n",
        "- Real outcome will usually be significantly worse than we estimated, even though estimate was unbiased\n",
        "\t- Optimizer's curse: tendency for the estimated expected utility of the best choice to be too high\n",
        "\t\t- Can avoid with Bayesian approach that uses an explicit probability model P(EU_hat | EU) of the error in the utility estimates\n",
        "- Decision theory = normative theory: describes how a rational agent should act\n",
        "- Descriptive theory: describes how actual agents really do act\n",
        "- Certainty effect: people are strongly attracted to gains that are certain --> explanation for apparently irrational preferences\n",
        "\t- People may prefer to reduce their computational burden (don't have to calculate probabilities)\n",
        "\t- People may distrust the legitimacy of the stated probabilities\n",
        "\t- People may be accounting for their emotional state as well as their financial state (avoid feeling like an idiot if you lose)\n",
        "- Ambiguity aversion: people elect the known probability rather than unknown unknowns\n",
        "- Framing effect: exact wording of a decision problem can have a big impact on agent's choices\n",
        "- Anchoring effect: people feel more comfortable making relative utility judgments rather than absolute ones\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell & Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "- Bc decision prob=sequential, utility fn will depend on seq of states & actions (environment history) rather than on single state\n",
        "- MDP: sequential decision prob for fully observable, stochastic env w/ Markovian transition model & additive rewards\n",
        "\t- Consists of set of states & actions in each state, transition model, reward function\n",
        "- Solving MDPs => dynamic programming: simplifying prob by recursively breaking into smaller pieces & remember optimal solns to the pieces\n",
        "- Policy: soln that specifies what agent should do for any state that agent might reach\n",
        "\t- No matter outcome of action, resulting state will be in policy & agent will know what to do next\n",
        "\t- Quality of policy measured by exp utility of possible env histories generated by that policy (bc stochastic nature of env may lead to different env history)\n",
        "\t- Optimal policy: yields highest exp utility (π*)\n",
        "- Balance of risk & reward changes depending on value of r=R(s,a,s') for transitions between nonterminal states\n",
        "- Finite horizon (nonstationary policy): fixed time N after which nothing matters (game is over) => optimal action in given state may depend on how much time left\n",
        "- Infinite horizon (stationary policy): no fixed deadline (simpler to solve)\n",
        "- How to calc utility of state seq: additive disc. rewards\n",
        "\t- Discount factor describes pref of agent for current rewards over future rewards\n",
        "\t\t-  Close to 0: rewards in distant future viewed as insig\n",
        "\t\t-  Close to 1: agent more willing to wait for long-term rewards\n",
        "\t\t-  Exactly 1: disc. rewards reduce to special case of purely additive rewards\n",
        "- If env not contain terminal state or if agent never reaches one=> all env histories will be infinitely long & utilities w/ additive undiscounted rewards will generally be infinite\n",
        "\t- Solns: w/ disc. rewards, utility of infinite seq is finite\n",
        "- If env contains terminal states & if agent guaranteed to get to one eventually, then never need to compare infinite seqs\n",
        "\t- Proper policy: guaranteed to reach terminal state\n",
        "- Infinite seqs can be compared in terms of avg reward obtained per time step\n",
        "- Utility of given history: sum of disc. rewards => compare policies by comparing exp utilities obtained when executing them\n",
        "- Consequence of using disc. utilities w/ infinite horizons => optimal policy is independent of starting state\n",
        "- True utility of state: expected sum of disc. rewards if agent executes optimal policy\n",
        "- Direct relationship between utility of state & utility of its neighbors\n",
        "\t- Bellman equation: utility of state = expected reward for next transition plus disc. utility of next state assuming that agent chooses optimal action\n",
        "- Action-utility fn (Q-fn): Q(s,a)=expected utility of taking given action in given state\n",
        "- Scale of utilities is arbitrary: affine transformation leaves optimal decision unchanged\n",
        "\t- Similar transformation of rewards will leave optimal policy unchanged in MDP\n",
        "\"\"\"\n",
        "\n",
        "chapter17_2 =  \"\"\"\n",
        "- 4 alg for solving MDPs: Generate exact solns offline (value/policy iteration,linear programming) & fam of online approx alg (Monte Carlo planning)\n",
        "- Value iter: If there are n possible states, then there are n Bellman eqs, one for each state (n eqns contain n unknowns (util of states))\n",
        "\t- Problem: eqns are nonlinear (max operator = not linear) => Can try solve using iterative approach (refer to module notes)\n",
        "\t- Value iter: propagates information through state space by means of local updates\n",
        "\t- Convergence of value iteration (exponentially fast): Contraction=fn of 1 argument that, when applied to 2 different inputs in turn, produces 2 output val that're \"closer together\" by at least some constant factor than orig inputs (i.e. divide by two)\n",
        "\t\t- Two important properties: Only has 1 fixed point (unchanged by application of fn) // When fn applied to any argument, val must get closer to fixed point\n",
        "\t\t- Bellman update=contraction by factor of gamma on space of util vectors => valiter always converges to unique soln of Bellman equations whenever gamma < 1\n",
        "\t\t- Can use contraction to analyze rate of convergence to soln\n",
        "- Policy iter\n",
        "\t- Possible to get optimal policy even when util fn estimate=inaccurate\n",
        "\t- Eqns=linear bc max operator has been removed\n",
        "\t- For state spaces: Small[policy eval using exact soln methods most efficient] // Large[O(n3) might be prohibitive]\n",
        "\t\t- Soln: don't need to do exact policy eval => can perform some # of simplified valiter steps (simplified bc policy is fixed) to give reasonably good approx of util\n",
        "\t- Asynchronous policyiter: on each iter, pick any subset of states & apply either kind of updating (policy improve or simplified valueiter) to that subset\n",
        "\t\t- Given certain conditions on init policy & init util fn => guaranteed to converge to optimal policy\n",
        "- Linear programming: general approach for forumlating constrained optimization problems\n",
        "\t- Basic idea: consider as vars in LP util of each state, noting that util for optimal policy are highest util attainable that are consistent with Bellman eqs\n",
        "- Offline alg: value & policy iter => generate optimal soln for prob when can then be executed by simple agent\n",
        "\t- For sufficiently large MDPs => exact offline soln not possible\n",
        "- Most straightforward: simplification of Expectminimax\n",
        "- Real-time dynamic programming (RTDP) (effective in moderate-sized domains)\n",
        "\t- In larger domains, issues: State space such that any manageable set of explored states contains very few repeated states (so might as well use expectimax tree) // Simple heuristic for frontier nodes may not be enough to guide agent, particularly if rewards are sparse\n",
        "\t- Potential fixes: Apply RL to generate more accurate heuristic // Look further ahead in MDP using Monte Carlo approach\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "- Transitions are Markovian: the probability of arriving in s' only depends on s & not the history of earlier states\n",
        "- We will specify a utility or reward function for the agent => the 'rewards' can be + or - but are bounded by some maximum value\n",
        "- Because the decision process is sequential, we must specify the utility function on a sequence of states & actions\n",
        "- Instead of only giving a reward at the goal states, the agent can receive a reward at each time step, based on its transition from s to s’ via action a\n",
        "- MDP is a sequential decision problem for a fully observable environment with a stochastic transition model that has additive rewards\n",
        "- Expectimax node: outcome is uncertain. In expectimax search, we calculate their expected utilities.\n",
        "- MDPs: non-deterministic search problems. One way of solving them is via expectimax search.\n",
        "- Solution to MDP is a policy\n",
        "- Performance of agent in MDP = sum of rewards for the transitions it takes\n",
        "- Discounting: prefer rewards now to rewards later => values of rewards decay exponentially\n",
        "- Stationary preferences: two ways to define utilities => additive & discounted\n",
        "- Problem: what if game lasts forever?? Solutions:\n",
        "  - Finite horizon (like depth-limited search): terminate after fixed T steps & gives nonstationary policies\n",
        "  - Discounting\n",
        "  - Absorbing state: guarantee that for every policy, a terminal state will eventually be reached\n",
        "- Optimal quantities\n",
        "  - Value of state s V*(s) = expected utility starting in s & acting optimally\n",
        "  - Value of q-state Q*(s,a) = expected utility starting out having taken action a from state s & (thereafter) acting optimally\n",
        "  - Optimal policy: optimal action from state s\n",
        "- Value Iteration => complexity of each iteration: O(S^2*A)\n",
        "  - Start with V0(s) = 0: no time steps left means an expected reward sum of zero\n",
        "  - Given vector of Vk(s) values: do (refer to written notes)\n",
        "  - Repeat until convergence\n",
        "- Theorem: will converge to unique optimal values ==> Basic idea: approximations get refined towards optimal values; policy may converge long before values do\n",
        "- How do we know the Vk vectors are going to converge?\n",
        "  - Case 1: If the tree has maximum depth M, then VM holds the actual untruncated values\n",
        "  - Case 2: If the discount is less than 1\n",
        "    - Sketch: For any state Vk & Vk+1 can be viewed as depth k+1 expectimax results in nearly identical search trees\n",
        "    - The difference is that on the bottom layer, Vk+1 has actual rewards while Vk has zeros\n",
        "    - That last layer is at best all RMAX; at worst RMIN\n",
        "    - But everything is discounted by γk that far out\n",
        "    - So Vk & Vk+1 are at most γk max|R| different\n",
        "    - So as k increases, the values converge\n",
        "- Bellman equations: definition of \"optimal utility\" via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values\n",
        "- Problems with Value Iteration: repeats Bellman updates\n",
        "  - It's slow O(S^2 * A) per iteration\n",
        "  - The max at each state rarely changes\n",
        "  - The policy often converges long before the values\n",
        "- Policy iteration: optimal & converges faster\n",
        "  - Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n",
        "  - Policy improvement: update policy using one-step look-ahead with resulting converged (but not optimal!) utilities as future values\n",
        "  - Repeat steps until policy converges\n",
        "- Comparison: both value & policy iteration compute the same thing (all optimal values) // both are dynamic programs for solving MDPs\n",
        "  - In value, every iteration updates both the values & (implicitly) the policy; we don't track the policy, but taking the max over actions implicitly recomputes it\n",
        "  - In policy, we do several passes that update utilities with fixed policy (each pass is fast bc we consider only one action, not all of them)\n",
        "    - After policy is evaluated, a new policy is chosen (slow like a value iteration pass)\n",
        "    - The new policy will be better (or we're done)\n",
        "- If you want to:\n",
        "  - Compute optimal values: use value iteration or policy iteration\n",
        "  - Compute values for a particular policy: use policy evaluation\n",
        "  - Turn your values into a policy: use policy extraction (one-step lookahead)\n",
        "- Above differ only in whether we plug in a fixed policy or max over actions\n",
        "- Principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes its expected utility, given its knowledge\n",
        "- Utilities => agent must have preferences among choices\n",
        "  - Preference: A > B\n",
        "  - Indifference A ~ B\n",
        "- Rational preferences imply behavior describable as maximization of expected utility\n",
        "- Utility scales: normalized; micromorts; QALYs (quality-adjusted life years)\n",
        "  - With deterministic prizes only (no lottery choices), only ordinal utility can be determined\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",
        "    \"\":\"\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 4561
        },
        "cellView": "form",
        "outputId": "59861580-283b-4236-87ef-5bc5d54008b5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs & Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs & Desires under Uncertainty\n\n- Agent assigns probability P(s) to each possible current state s\n- Transition model: given by P(s' | s,a), the probability that action a in state s reaches state s'\n- P(Result(a) = s') = sum(P(s) * P(s'|s,a))\n- Utility function U(s): agent's preferences captured in a single number to express desirability of a state\n- Expected utility of an action given evidence EU(a): average utility value of the outcomes weighted by the probability that the outcome occurs\n- Principle of maximum expected utility (MEU): rational agent should choose action that maximizes agent's expected utility\n  - Maximizing utility doesn't mean the problem is solved by the definition: formalizes that agent should 'do the right thing' but doesn't operationalize that advice\n- If an agent acts to maximize a utility function that correctly reflects the performance measure, then agent will achieve the highest possible performance score (averaged over all possible environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- Constraints on rational preferences\n\t- Can think of set of outcomes for each action as a lottery; each action = ticket\n\t- Primary issue for utility theory: underst& how preferences between complex lotteries are related to preferences between the underlying state in those lotteries\n\t\t- Axioms of utility theory: 6 constraints that we require any reasonable preference relation to obey:\n\t\t\t- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable; cannot avoid deciding\n\t\t\t- Transitivity: Given any three lotteries, if an agent prefers A to B & prefers B to C, then the agent must prefer A to C\n\t\t\t- Continuity: If some lottery B is between A & C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure & the lottery that yields A with probability p & C with probability 1-p\n\t\t\t- Substitutability: If an agent is indifferent between two lotteries A & B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n\t\t\t- Monotonicity: Suppose two lotteries have the same two possible outcomes, A & B. If agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A\n\t\t\t- Decomposability:  Compound lotteries can be reduced to simpler ones using the laws of probability\n- 16.2.2 Rational preferences lead to utility\n\t- From axioms of utility, can derive the following:\n    - Existence of utility function: if agent's preferences obey the axioms of utility, then there exists a function U such that U(A)>U(B) iff A is preferred to B & U(A)=U(B) iff agent is indifferent between A & B\n    - Expected utility of a lottery: utility of lottery = sum[probability of each outcome * utility of that outcome]\n  - Once the probabilities & utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined\n\t- In a deterministic environment, an agent needs only a preference ranking on states (numbers don't matter)\n\t\t- Called a value function or ordinal utility function\n  - Existence of utility function that describes agent's preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- Preference elicitation: process to work out what a human's utility function is by presenting choices to them & using observed preferences to pin down the underlying utility function\n- Useful to establish some scale on which utilities can be recorded & compared for any particular problem by fixing the utilities of any two particular outcomes (best vs worst possible)\n\t- Normalized utilities: scale between 0 & 1\n- Utility of money almost exactly proportional to log of the amount\n  - Most people have a utility function that is concave for positive wealth\n  - Agent with linear curve: risk-neutral\n- Expected utility & post-decision disappointment\n\t- Rational way to choose best action: maximize expected utility\n\t- Model usually oversimplifies real situation: either because we don't know enough or because the computation of the true expected utility is too difficult\n\t\t- Therefore working with estimates of true expected utility\n\t\t- Assume estimates are unbiased: expected value of error is zero\n- Real outcome will usually be significantly worse than we estimated, even though estimate was unbiased\n\t- Optimizer's curse: tendency for the estimated expected utility of the best choice to be too high\n\t\t- Can avoid with Bayesian approach that uses an explicit probability model P(EU_hat | EU) of the error in the utility estimates\n- Decision theory = normative theory: describes how a rational agent should act\n- Descriptive theory: describes how actual agents really do act\n- Certainty effect: people are strongly attracted to gains that are certain --> explanation for apparently irrational preferences\n\t- People may prefer to reduce their computational burden (don't have to calculate probabilities)\n\t- People may distrust the legitimacy of the stated probabilities\n\t- People may be accounting for their emotional state as well as their financial state (avoid feeling like an idiot if you lose)\n- Ambiguity aversion: people elect the known probability rather than unknown unknowns\n- Framing effect: exact wording of a decision problem can have a big impact on agent's choices\n- Anchoring effect: people feel more comfortable making relative utility judgments rather than absolute ones\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- Bc decision prob=sequential, utility fn will depend on seq of states & actions (environment history) rather than on single state\n- MDP: sequential decision prob for fully observable, stochastic env w/ Markovian transition model & additive rewards\n\t- Consists of set of states & actions in each state, transition model, reward function\n- Solving MDPs => dynamic programming: simplifying prob by recursively breaking into smaller pieces & remember optimal solns to the pieces\n- Policy: soln that specifies what agent should do for any state that agent might reach\n\t- No matter outcome of action, resulting state will be in policy & agent will know what to do next\n\t- Quality of policy measured by exp utility of possible env histories generated by that policy (bc stochastic nature of env may lead to different env history)\n\t- Optimal policy: yields highest exp utility (π*)\n- Balance of risk & reward changes depending on value of r=R(s,a,s') for transitions between nonterminal states\n- Finite horizon (nonstationary policy): fixed time N after which nothing matters (game is over) => optimal action in given state may depend on how much time left\n- Infinite horizon (stationary policy): no fixed deadline (simpler to solve)\n- How to calc utility of state seq: additive disc. rewards\n\t- Discount factor describes pref of agent for current rewards over future rewards\n\t\t-  Close to 0: rewards in distant future viewed as insig\n\t\t-  Close to 1: agent more willing to wait for long-term rewards\n\t\t-  Exactly 1: disc. rewards reduce to special case of purely additive rewards\n- If env not contain terminal state or if agent never reaches one=> all env histories will be infinitely long & utilities w/ additive undiscounted rewards will generally be infinite\n\t- Solns: w/ disc. rewards, utility of infinite seq is finite\n- If env contains terminal states & if agent guaranteed to get to one eventually, then never need to compare infinite seqs\n\t- Proper policy: guaranteed to reach terminal state\n- Infinite seqs can be compared in terms of avg reward obtained per time step\n- Utility of given history: sum of disc. rewards => compare policies by comparing exp utilities obtained when executing them\n- Consequence of using disc. utilities w/ infinite horizons => optimal policy is independent of starting state\n- True utility of state: expected sum of disc. rewards if agent executes optimal policy\n- Direct relationship between utility of state & utility of its neighbors\n\t- Bellman equation: utility of state = expected reward for next transition plus disc. utility of next state assuming that agent chooses optimal action\n- Action-utility fn (Q-fn): Q(s,a)=expected utility of taking given action in given state\n- Scale of utilities is arbitrary: affine transformation leaves optimal decision unchanged\n\t- Similar transformation of rewards will leave optimal policy unchanged in MDP\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- 4 alg for solving MDPs: Generate exact solns offline (value/policy iteration,linear programming) & fam of online approx alg (Monte Carlo planning)\n- Value iter: If there are n possible states, then there are n Bellman eqs, one for each state (n eqns contain n unknowns (util of states))\n\t- Problem: eqns are nonlinear (max operator = not linear) => Can try solve using iterative approach (refer to module notes)\n\t- Value iter: propagates information through state space by means of local updates\n\t- Convergence of value iteration (exponentially fast): Contraction=fn of 1 argument that, when applied to 2 different inputs in turn, produces 2 output val that're \"closer together\" by at least some constant factor than orig inputs (i.e. divide by two)\n\t\t- Two important properties: Only has 1 fixed point (unchanged by application of fn) // When fn applied to any argument, val must get closer to fixed point\n\t\t- Bellman update=contraction by factor of gamma on space of util vectors => valiter always converges to unique soln of Bellman equations whenever gamma < 1\n\t\t- Can use contraction to analyze rate of convergence to soln\n- Policy iter\n\t- Possible to get optimal policy even when util fn estimate=inaccurate\n\t- Eqns=linear bc max operator has been removed\n\t- For state spaces: Small[policy eval using exact soln methods most efficient] // Large[O(n3) might be prohibitive]\n\t\t- Soln: don't need to do exact policy eval => can perform some # of simplified valiter steps (simplified bc policy is fixed) to give reasonably good approx of util\n\t- Asynchronous policyiter: on each iter, pick any subset of states & apply either kind of updating (policy improve or simplified valueiter) to that subset\n\t\t- Given certain conditions on init policy & init util fn => guaranteed to converge to optimal policy\n- Linear programming: general approach for forumlating constrained optimization problems\n\t- Basic idea: consider as vars in LP util of each state, noting that util for optimal policy are highest util attainable that are consistent with Bellman eqs\n- Offline alg: value & policy iter => generate optimal soln for prob when can then be executed by simple agent\n\t- For sufficiently large MDPs => exact offline soln not possible\n- Most straightforward: simplification of Expectminimax\n- Real-time dynamic programming (RTDP) (effective in moderate-sized domains)\n\t- In larger domains, issues: State space such that any manageable set of explored states contains very few repeated states (so might as well use expectimax tree) // Simple heuristic for frontier nodes may not be enough to guide agent, particularly if rewards are sparse\n\t- Potential fixes: Apply RL to generate more accurate heuristic // Look further ahead in MDP using Monte Carlo approach\n\n\n## Module 8 Lecture Notes\n\n- Transitions are Markovian: the probability of arriving in s' only depends on s & not the history of earlier states\n- We will specify a utility or reward function for the agent => the 'rewards' can be + or - but are bounded by some maximum value\n- Because the decision process is sequential, we must specify the utility function on a sequence of states & actions\n- Instead of only giving a reward at the goal states, the agent can receive a reward at each time step, based on its transition from s to s’ via action a\n- MDP is a sequential decision problem for a fully observable environment with a stochastic transition model that has additive rewards\n- Expectimax node: outcome is uncertain. In expectimax search, we calculate their expected utilities.\n- MDPs: non-deterministic search problems. One way of solving them is via expectimax search.\n- Solution to MDP is a policy\n- Performance of agent in MDP = sum of rewards for the transitions it takes\n- Discounting: prefer rewards now to rewards later => values of rewards decay exponentially\n- Stationary preferences: two ways to define utilities => additive & discounted\n- Problem: what if game lasts forever?? Solutions:\n  - Finite horizon (like depth-limited search): terminate after fixed T steps & gives nonstationary policies\n  - Discounting\n  - Absorbing state: guarantee that for every policy, a terminal state will eventually be reached\n- Optimal quantities\n  - Value of state s V*(s) = expected utility starting in s & acting optimally\n  - Value of q-state Q*(s,a) = expected utility starting out having taken action a from state s & (thereafter) acting optimally\n  - Optimal policy: optimal action from state s\n- Value Iteration => complexity of each iteration: O(S^2*A)\n  - Start with V0(s) = 0: no time steps left means an expected reward sum of zero\n  - Given vector of Vk(s) values: do (refer to written notes)\n  - Repeat until convergence\n- Theorem: will converge to unique optimal values ==> Basic idea: approximations get refined towards optimal values; policy may converge long before values do\n- How do we know the Vk vectors are going to converge?\n  - Case 1: If the tree has maximum depth M, then VM holds the actual untruncated values\n  - Case 2: If the discount is less than 1\n    - Sketch: For any state Vk & Vk+1 can be viewed as depth k+1 expectimax results in nearly identical search trees\n    - The difference is that on the bottom layer, Vk+1 has actual rewards while Vk has zeros\n    - That last layer is at best all RMAX; at worst RMIN\n    - But everything is discounted by γk that far out\n    - So Vk & Vk+1 are at most γk max|R| different\n    - So as k increases, the values converge\n- Bellman equations: definition of \"optimal utility\" via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values\n- Problems with Value Iteration: repeats Bellman updates\n  - It's slow O(S^2 * A) per iteration\n  - The max at each state rarely changes\n  - The policy often converges long before the values\n- Policy iteration: optimal & converges faster\n  - Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n  - Policy improvement: update policy using one-step look-ahead with resulting converged (but not optimal!) utilities as future values\n  - Repeat steps until policy converges\n- Comparison: both value & policy iteration compute the same thing (all optimal values) // both are dynamic programs for solving MDPs\n  - In value, every iteration updates both the values & (implicitly) the policy; we don't track the policy, but taking the max over actions implicitly recomputes it\n  - In policy, we do several passes that update utilities with fixed policy (each pass is fast bc we consider only one action, not all of them)\n    - After policy is evaluated, a new policy is chosen (slow like a value iteration pass)\n    - The new policy will be better (or we're done)\n- If you want to:\n  - Compute optimal values: use value iteration or policy iteration\n  - Compute values for a particular policy: use policy evaluation\n  - Turn your values into a policy: use policy extraction (one-step lookahead)\n- Above differ only in whether we plug in a fixed policy or max over actions\n- Principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes its expected utility, given its knowledge\n- Utilities => agent must have preferences among choices\n  - Preference: A > B\n  - Indifference A ~ B\n- Rational preferences imply behavior describable as maximization of expected utility\n- Utility scales: normalized; micromorts; QALYs (quality-adjusted life years)\n  - With deterministic prizes only (no lottery choices), only ordinal utility can be determined\n\n\n## Module 8 Definitions\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell & Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "- Ubiquitous tradeoff between:\n",
        "\t- Exploitation of the current best action to obtain rewards\n",
        "\t- Exploration of previously unknown states & actions to gain info\n",
        "- Definitions of bandit problems (Overall bandit problem is MDP)\n",
        "\t- Each arm is a Markov reward process (MRP), an MDP with only one possible action\n",
        "- Key property: arms are independent, coupled only by fact that agent can work on only one arm at a time\n",
        "- Optimal strategy is to run arm M up to time T & then switches to Mλ the rest of the time (where λ is the discount factor)\n",
        "- Gittins index of M: Provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins indices\n",
        "- Calculating the Gittins index\n",
        "\t- To calculate the Gittins index for a general arm M & current state s, we simply make the following observation: at the tipping point where an optimal policy is indifferent between choosing arm M & choosing the fixed arm Mλ, the value of choosing M is the same as the value of choosing an infinite sequence of λ-rewards\n",
        "\t- Restart MDP\n",
        "- Bernoulli bandit\n",
        "\t- Each arm Mi produces reward of 0 or 1 with fixed but unknown probability µi\n",
        "\t- The state of arm Mi is defined by si & fi the counts of successes (1s) & failures (0s) so far for that arm\n",
        "\t- Transition probability predicts the next outcome to be 1 with probability si / (si + fi) & 0 with probability fi / (si + fi)\n",
        "\t- Assign exploration bonus associated with arms that have only been tried a few times\n",
        "- Approximately optimal bandit policies\n",
        "\t- Calculating Gittins indices for more realistic problems is rarely easy, but can create \"nearly as good\" policies\n",
        "\t- Upper confidence bound (UCB) heuristic: use the samples from each arm to establish CI for value of the arm, that is, range within which value can be estimated to lie w/ high confidence; then choose arm w/ highest upper bound on its CI\n",
        "\t- Thompson sampling: chooses arm randomly according to probability that the arm is in fact optimal, given the samples so far\n",
        "- Non-indexable variants\n",
        "\t- Selection problem: there's fixed cost for each test, but don't have to minimize test failures; just try to make good decision asap\n",
        "\t\t- No index function exists for selection problems\n",
        "\t- Bandit superprocess (BSP): generalization of bandit process in which each arm is a full MDP in its own right, rather than being MRP w/ only one possible action\n",
        "\t- How to solve BSPs\n",
        "\t\t- Impractical but optimal: convert into global MDP on Cartesian-product state space\n",
        "\t\t- Take advantage of loose nature of interaction between arms\n",
        "\t\t\t- Interaction arises only from agent's limited ability to attend to arms simultaneously\n",
        "\t\t\t\t- Interaction can be modeled by notion of opportunity cost: how much utility is given up per time step by not devoting that time step to another arm\n",
        "\t\t\t- Dominating policy?\n",
        "\"\"\"\n",
        "\n",
        "# Russell & Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "- Reinforcement learning (RL): agent interacts with world & periodically receives rewards (reinforcements) that reflect how well it's doing\n",
        "\t- Goal is the same as MDPs: maximize expected sum of rewards\n",
        "\t- Differs from MDP bc agent is not given the MDP to solve; it's IN the MDP (may not know transition model or reward function so has to act to learn more)\n",
        "- Providing reward signal is usually much easier than providing labeled examples of how to behave\n",
        "\t- Very concise & easy to specify\n",
        "\t- Don't have to be experts capable of supplying the correct action in any situation (but a little expertise goes a long way)\n",
        "\t\t- Sparse rewards: in vast majority of states, agent is given no informative reward signal at all\n",
        "\t\t- Intermediate rewards make learning easier\n",
        "- Different RL algorithms:\n",
        "\t- Model-based RL: agent uses transition model of environment to help interpret the reward signals & to make decisions about how to act\n",
        "\t\t- Model may be initially unknown (so agent learns from observing effects of its actions) or known\n",
        "\t\t- In partially observable environments: transition model is also useful for state estimation\n",
        "\t\t- Utility function = sum of rewards from state s onwards\n",
        "\t- Model-free RL: agent neither knows nor learns a transition model for environment; it learns a more direct representation of how to behave\n",
        "\t\t- Action-utility learning: agent choose what to do in s by finding action with highest q-value (Q(s,a) = sum of rewards from state s onward if action a is taken)\n",
        "\t\t- Policy search: agent learns a policy that maps directly from states to actions (reflex agent)\n",
        "- Passive RL: agent's policy is fixed & the task is to learn the utilities of states\n",
        "  - Passive learning agent: agent trying to learn utility function Uπ(s) (the expected total discounted reward if policy π is executed beginning in state s)\n",
        "  - Passive learning task similar to policy eval task => Difference: PL agent doesn't know T or R\n",
        "  - PL agent executes a set of trials in environment using its policy π\n",
        "\t- Percepts supply both current state & reward received for the transition that just occurred to reach that state\n",
        "\t- Each transition annotated with both action taken & reward received at next state\n",
        "\t- Agent will use info about rewards to learn expected utility associated with each nonterminal state s\n",
        "\t\t- Utility: expected sum of (discounted) rewards obtained if policy π is followed\n",
        "- Active RL: agent must also figure out what to do\n",
        "\t- Will need to learn complete T w/ outcome probabilities for all actions instead of just model for fixed policy\n",
        "\t- Has choice of actions => needs to learn utilities defined by optimal policy\n",
        "- Main issue is exploration: agent must experience as much as possible of its environment in order to learn how to behave in it (can use inductive learning to learn much faster)\n",
        "\"\"\"\n",
        "\n",
        "chapter22_2 =  \"\"\"\n",
        "- Direct utility est: util of state defined as exp total reward from that state onward that each trial provides sample of this quantity for each state visited\n",
        "\t- RL => standard supervised learning prob => each example = (state, reward-to-go)\n",
        "\t\t- Constraint: util of state determined by reward & exp util of successor states (util values obey Bellman for fixed policy)\n",
        "\t\t\t- Ignoring connections between states: DUE misses opps for learning\n",
        "\t- Can view DUE as searching for U in hypothesis space that's much larger than needed (includes many functions that violate Bellman)\n",
        "- Adaptive dynamic programming (ADP): agent takes advantage of constraints among utils of states by learning T that connects them & solving corresponding MDP using DP\n",
        "\t- Take PL agent, plug in T & observed R to calc utils of states\n",
        "\t- Alsocan take approach of modified policyiter: using simplified valiter to update util estimates after each change to learned model\n",
        "\t\t- Since model usu only changes slightly w/ each obs, valueiter can use prev util esimates as init vals & converge very quickly\n",
        "\t- Learning T=easy bc env is fully observable\n",
        "\t- How quickly val ests improve=> ADP agent limited only by ability to learn T (intractable for large state spaces)\n",
        "- TD learning: Can use observed transitions to adj utils of observed states so that they agree w/ constraint eqns\n",
        "\t- New update rule uses diff in utils between successive states/times (TD eqn)\n",
        "\t\t- TD term = error signal (update is intended to reduce error)\n",
        "\t- All TD methods work by adj util ests toward ideal equilib that holds locally when util ests=correct\n",
        "\t- TD agent learns slower than ADP agent & shows higher variability, but much simpler & requires much less computation per obs\n",
        "\t\t- TD doesn't need T to perform updates: env itself supplies connection between neighboring states in form of observed transitions\n",
        "\t- ADP & TD approaches both try to make local adj to util estimates to make each state \"agree\" w/ its successors. Diffs:\n",
        "\t\t- TD adj state to agree w/ its observed successor; ADP adj to agree w/ all of successors that might occur, weighted by their probabilities\n",
        "\t\t\t- Diff disappears when effects of TD adj are averaged over large # of transitions (freq of each successor in set of transitions approx. proportional to its probability)\n",
        "\t\t- TD makes single adj per observed transition; ADP makes as many as needed to restore consistency between util ests U & transition model P\n",
        "\t\t\t- TD=crude but efficient first approx to ADP\n",
        "\t- From TD POV, each adj made by ADP = result of pseudoexperience generated by simulating current T\n",
        "\t\t- TD agent can generate large # of imaginary transitions for each observed transition => resulting util ests will approx more closely those of ADP\n",
        "\t- Can generate more efficient versions of ADP by directly approxing algs for value/policyiter\n",
        "\t\t- Can generate good answers quickly by bounding # of adj made after each observed transition\n",
        "\t- Approx ADP algs can learn roughly as fast as full ADP but can be much more efficient\n",
        "\"\"\"\n",
        "\n",
        "chapter22_3 =  \"\"\"\n",
        "- Greedy agent: always take constant believed optimal action: can lead to suboptimal results => learned model =/= true env\n",
        "\t- Overlooks: actions provide rewards AND info\n",
        "\t- GLIE: try each action in each state unbounded # of times to avoid having finite probability that optimal action is missed\n",
        "\t\t- Choose random action at time step t with probability 1/t otherwise follow greedy policy (will slowly converge)\n",
        "\t\t- Give weight to less-tried actions but avoiding possible low util\n",
        "- Exploration fn f(u,n): determines how greed (pref for high values of util u) traded off against curiosity (pref for actions not tried often, low count n) => increasing u & decreasing n\n",
        "\n",
        "- Worst case: agent enters absorbing state bc model unknown (actively explore in bad direction) or incorrect (don't know given action is disastrous)\n",
        "- Better: choose okay policy that works for range of models that have chance of being true model, even if policy suboptimal for maximum-likelihood model (Bayesian RL)\n",
        "\t- Robust control theory: allows for set of possible models H w/o assigning probabilities to them & defines optimal robust policy = gives best outcome in worst case over H (too conservative)\n",
        "\t\t- H = set of models that exceed some likelihood threshold on posterior P(h|e) (Bayesian & robust are related)\n",
        "- Human knowledge can help keep sys safe: record actions by expert so sys acts reasonably from start or write down constraints on sys & have prog outside of RL sys enforce\n",
        "\n",
        "- Active TD learning agent: have to learn T to choose action based on U(s) via one-step look-ahead\n",
        "- Model acq prob still identical to ADP agent & TD update rule remains unchanged\n",
        "- Q-learn method: learns action-utility Q(s,a) not utility U(s) => act optimally (choose argmax)\n",
        "\t- TD Q-learn agent doesn't need T for learning or action selection\n",
        "\t- Cons: q-learn agent no way look into future=> may have difficulty when rewards=sparse & long action seq must be constructed to reach them\n",
        "- Like Q-learn: SARSA (state, action, reward, state', action')\n",
        "\t- Update rule like Q-learn except SARSA updates w/ q-value of action a' actually taken\n",
        "\t- Q-learn backs up q-value from best action in s' ==> SARSA waits until action taken & backs up q-value for that action\n",
        "\t\t- If agent=greedy & always takes action w/ best q-value: two algs are identical\n",
        "\t\t- If explore happening: if yields negative reward, SARSA penalizes action; Q-learning doesn't\n",
        "- Q-learn = off-policy: learns q-values that answer: \"what would action be worth in state, assuming that I switch to policy that chooses best action?\"\n",
        "- SARSA = on-policy: learns q-values that answers: \"what would action be worth in state, assuming that I stick w/ my policy?\"\n",
        "- Q-learn more flexible: can learn how to behave well when under control of wide variety of exploration policies\n",
        "- SARSA appropriate if overall policy is even partly controlled by other agents or progs\n",
        "- Both learn optimal pol=> much slower than ADP agent (local updates don't enforce consistency among all q-values via model)\n",
        "\"\"\"\n",
        "\n",
        "chapter22_4 =  \"\"\"\n",
        "- Function approx with look-ahead search ==> produce more accurate decisions\n",
        "\t- Effective behavior can result from much simpler util fn approximator that's learnable from fewer experiences\n",
        "  - Makes it practical to represent util (or Q) fns for large spaces\n",
        "  - Allows for inductive generalization: can generalize from states visited to states not yet visited\n",
        "  - Approximating DUE: learn faster if use fn approximator if hypothesis space not too large & includes some fn that're reasonably good fit to true util fn\n",
        "- Approximating TD learning: adj params to reduce TD between successive states\n",
        "\t- For passive TD learning, update rule can converge to closest possible approx to true fn when fn approximator is linear in features\n",
        "\t- For active learning & nonlinear functions (neural nets): params can go to infinity w/ these update rules even if good solutions in hypothesis space\n",
        "\t- Catastrophic forgetting: if agent learns too well (flat value fn, so quadratic features get zero weight, but then nonzero weight on linear features cause abrupt change)\n",
        "\t\t- Solution: experience replay (ensures agent relives youthful bad behavior at intervals to ensure value fn still accurate for parts of state space no longer visits)\n",
        "- Deep RL system: RL system that uses deep network as fn approximator\n",
        "\t- 2 reasons why we need to go beyond linear fn approximators:\n",
        "\t\t- May be no good linear fn that comes close to approximating util fn or Q-function\n",
        "\t\t- May not be able to invent necessary features, particularly in new domains\n",
        "\t- Deep NN discovers useful features for itself: final layer linear => can see what features network used to build own linear fn approximator\n",
        "\t- Deep NN = fn parameterized by theta except fn much more complicated => params are all weights in layers of network (but gradient same as in supervised learning)\n",
        "- Reward shaping\n",
        "\t- Prob of credit assignment: other than going through process a million times before rewards propagate back to actions responsible for it\n",
        "\t- Reward shaping: supplying agent with additional rewards for \"making progress\" (pseudorewards)\n",
        "\t\t- Risk that agent will learn to maximize pseudorewards rather than true rewards\n",
        "- Hierarchical reinforcement learning: break up very long action seqs into few smaller pieces, then break those into smaller pieces still, and so on until action sequences are short enough to make learning easy\n",
        "\t- Partial program: outlines hierarchical structure for agent's behavior\n",
        "\t- HRL includes ordinary RL as a special case\n",
        "\t- Choose operator allows agent to choose any element of specified set\n",
        "\t- Learning process converts partial agent program into a complete program by learning how each choice should be made\n",
        "\t- Can be effective method for learning complex behaviors\n",
        "  - Important characteristic: lower-level skills are not fixed subroutines ==> their choices are sensitive to entire internal state of agent program so they behave differently depending on where they are invoked within that program and what is going on at the time\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "- Idea is to keep twiddling the policy as long as performance improves, then stop\n",
        "- Interested primarily in parameterized representations of π that have far fewer parameters than there are states in the state space\n",
        "- If policy is represented by Q-functions ==> policy search results in process that learns Q-functions\n",
        "\t- Not the same as Q-learning!\n",
        "\t\t- Q-learning: finds value of theta to approximate Q*\n",
        "\t\t- Policy search: finds value of theta that results in good performance (may be far from estimating true utility function)\n",
        "- Policy = discontinuous function of parameters when actions are discrete\n",
        "\t- Will be values of theta such that the smallest change will cause the policy to switch from one action to another\n",
        "\t- Will use a stochastic policy representation which specifies probability of select action a in state s (i.e. softmax)\n",
        "\t\t- β > 0 modulates softness of softmax\n",
        "\t\t- If large: approaches hard max\n",
        "    - If close to 0: approaches uniform random choice among actions\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "- Solving MDPs = offline planning\n",
        "  - Determine all quantities through computation\n",
        "  - Need to know the details of the MDP\n",
        "  - Do not actually play the game\n",
        "- Regret: even if you learn intelligently, you make mistakes\n",
        "- Sampling: bc of chance, you have to try things repeatedly\n",
        "- Difficulty: learning can be much harder than solving a known MDP\n",
        "- RL basic idea:\n",
        "  - Receive feedback in the form of rewards\n",
        "  - Agent's utility is defined by the reward function\n",
        "  - Must (learn to) act so as to maximize expected rewards\n",
        "  - All learning is based on observed samples of outcomes\n",
        "- Still assume MDP: set of states, set of actions, transition model, reward function => still looking for a policy\n",
        "  - New twist: don't know the transition model or reward function: must actually try actions & states out to learn\n",
        "- Model-based learning: estimate T & R & plug in\n",
        "  - Learn an approximate model based on experiences & solve for values as if the learned model were correct\n",
        "  - Step 1: learn empirical MDP model\n",
        "    - Count outcomes s' for each s,a\n",
        "    - Normalize to give an estimate of T(s,a,s')\n",
        "    - Discover each R(s,a,s') when we experience (s,a,s')\n",
        "  - Step 2: solve the learned MDP (i.e. use value iteration)\n",
        "- Model-free learning: don't build explicit transition model\n",
        "  - Take action, compare results to what we thought was going to happen to what actually happens\n",
        "  - When something deviates from expectation, take values & adjust them up or down\n",
        "  - Track values of being in certain states, don't track transition or reward values\n",
        "- Passive RL: instead of us picking the policy, let someone else choose & we'll try it out\n",
        "  - Don't figure out how to act optimally, instead see how good this policy is\n",
        "  - Simplified task: policy evaluation where input=fixed policy, but don't know T or R ==> goal: learn state values\n",
        "  - Learner is \"along for the ride\" & has no choice about what actions to take => just execute the policy & learn from experience\n",
        "- Direct evaluation: goal is to compute values for each state under policy\n",
        "  - Idea: average together observed sample values\n",
        "    - Act according to policy\n",
        "    - Every time you visit a state, write down what the sum of discounted rewards turned out to be\n",
        "    - Average those samples\n",
        "  - Pros: easy to understand, doesn't require knowledge of T or R, eventually computes the correct avg values using just sample transitions\n",
        "  - Cons: wastes info about state connections, each state must be learned separately => takes a long time to learn\n",
        "- Temporal Difference Learning: solution to policy eval since we don't know T or R\n",
        "  - Want to improve our estimate of V by computing these averages by taking samples of outcomes s' (by doing the action!) & average, but we can't rewind time to get sample after sample from state s\n",
        "- TD learning: learn from every experience => Update V(s) each time we experience a transition (s,a,s',r) => Likely outcomes s' will contribute updates more often\n",
        "  - Policy still fixed, still doing evaluation\n",
        "  - Move values toward value of whatever successor occurs: running average\n",
        "  - Exponential moving average: makes recent samples more important & forgets about the past (distant past values were wrong anyway)\n",
        "    - Decreasing learning rate (alpha) can give converging averages\n",
        "  - Problems with TD value learning: model-free way to do policy eval, mimicking Bellman updates with running sample averages; however, if we want to turn values into a (new) policy, we're sunk\n",
        "    - Idea: learn Q-values, not values\n",
        "    - Makes action selection model-free too\n",
        "- Active RL: don't know T or R but we choose the actions now => learn the optimal policy/values\n",
        "  - Learner makes choices => fundamental tradeoff between exploration vs exploitation\n",
        "  - Q-learning: sample-based Q-value iteration (refer to written notes)\n",
        "    - Off-policy learning: Q-learning converges to optimal policy even if you're acting suboptimally\n",
        "    - Caveats: have to explore enough, have to eventually make the learning rate small enough (but don't decrease it too quickly) => but in the limit, doesn't matter how you select actions\n",
        "- Exploration vs Exploitation\n",
        "  - Problem with epsilon greedy: eventually explore the space, but keep thrashing around once learning is done (soln: lower epsilon over time OR exploration functions (explore areas whose badness is not yet established))\n",
        "    - Exploration function: refer to written notes\n",
        "  - Basic Q-learning keeps a table of all q-values: not realistic! => too many states to visit them all in training & to hold q-tables in memory\n",
        "    - Want to generalize: learn about some small # of training states from experience => generalize that experience to new, similar situations\n",
        "    - Approximate Q-learning: adjust weights of active features as positive or negative\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"prioritized sweeping heuristic\" : \"make adj to states whose likely successors have just undergone a large adjustment in their own utility estimates\",\n",
        "\"absorbing state\":\"state where no actions have any effect & no rewards are received\",\n",
        "\"GLIE\":\"greedy in limit of infinite exploration\",\n",
        "\"evaluation function\":\"measure of desirability for potentially vast state spaces (approximate utility function)\",\n",
        "\"function approximation\":\"process of constructing a compact approximation of the true utility function or Q-function\"\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 6138
        },
        "cellView": "form",
        "outputId": "a52def7b-f618-4fd1-87ff-517389fceff1"
      },
      "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",
        "  (\"AIMA Chapter 22.5 Policy Search\", chapter22_5),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- Ubiquitous tradeoff between:\n\t- Exploitation of the current best action to obtain rewards\n\t- Exploration of previously unknown states & actions to gain info\n- Definitions of bandit problems (Overall bandit problem is MDP)\n\t- Each arm is a Markov reward process (MRP), an MDP with only one possible action\n- Key property: arms are independent, coupled only by fact that agent can work on only one arm at a time\n- Optimal strategy is to run arm M up to time T & then switches to Mλ the rest of the time (where λ is the discount factor)\n- Gittins index of M: Provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins indices\n- Calculating the Gittins index\n\t- To calculate the Gittins index for a general arm M & current state s, we simply make the following observation: at the tipping point where an optimal policy is indifferent between choosing arm M & choosing the fixed arm Mλ, the value of choosing M is the same as the value of choosing an infinite sequence of λ-rewards\n\t- Restart MDP\n- Bernoulli bandit\n\t- Each arm Mi produces reward of 0 or 1 with fixed but unknown probability µi\n\t- The state of arm Mi is defined by si & fi the counts of successes (1s) & failures (0s) so far for that arm\n\t- Transition probability predicts the next outcome to be 1 with probability si / (si + fi) & 0 with probability fi / (si + fi)\n\t- Assign exploration bonus associated with arms that have only been tried a few times\n- Approximately optimal bandit policies\n\t- Calculating Gittins indices for more realistic problems is rarely easy, but can create \"nearly as good\" policies\n\t- Upper confidence bound (UCB) heuristic: use the samples from each arm to establish CI for value of the arm, that is, range within which value can be estimated to lie w/ high confidence; then choose arm w/ highest upper bound on its CI\n\t- Thompson sampling: chooses arm randomly according to probability that the arm is in fact optimal, given the samples so far\n- Non-indexable variants\n\t- Selection problem: there's fixed cost for each test, but don't have to minimize test failures; just try to make good decision asap\n\t\t- No index function exists for selection problems\n\t- Bandit superprocess (BSP): generalization of bandit process in which each arm is a full MDP in its own right, rather than being MRP w/ only one possible action\n\t- How to solve BSPs\n\t\t- Impractical but optimal: convert into global MDP on Cartesian-product state space\n\t\t- Take advantage of loose nature of interaction between arms\n\t\t\t- Interaction arises only from agent's limited ability to attend to arms simultaneously\n\t\t\t\t- Interaction can be modeled by notion of opportunity cost: how much utility is given up per time step by not devoting that time step to another arm\n\t\t\t- Dominating policy?\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- Reinforcement learning (RL): agent interacts with world & periodically receives rewards (reinforcements) that reflect how well it's doing\n\t- Goal is the same as MDPs: maximize expected sum of rewards\n\t- Differs from MDP bc agent is not given the MDP to solve; it's IN the MDP (may not know transition model or reward function so has to act to learn more)\n- Providing reward signal is usually much easier than providing labeled examples of how to behave\n\t- Very concise & easy to specify\n\t- Don't have to be experts capable of supplying the correct action in any situation (but a little expertise goes a long way)\n\t\t- Sparse rewards: in vast majority of states, agent is given no informative reward signal at all\n\t\t- Intermediate rewards make learning easier\n- Different RL algorithms:\n\t- Model-based RL: agent uses transition model of environment to help interpret the reward signals & to make decisions about how to act\n\t\t- Model may be initially unknown (so agent learns from observing effects of its actions) or known\n\t\t- In partially observable environments: transition model is also useful for state estimation\n\t\t- Utility function = sum of rewards from state s onwards\n\t- Model-free RL: agent neither knows nor learns a transition model for environment; it learns a more direct representation of how to behave\n\t\t- Action-utility learning: agent choose what to do in s by finding action with highest q-value (Q(s,a) = sum of rewards from state s onward if action a is taken)\n\t\t- Policy search: agent learns a policy that maps directly from states to actions (reflex agent)\n- Passive RL: agent's policy is fixed & the task is to learn the utilities of states\n  - Passive learning agent: agent trying to learn utility function Uπ(s) (the expected total discounted reward if policy π is executed beginning in state s)\n  - Passive learning task similar to policy eval task => Difference: PL agent doesn't know T or R\n  - PL agent executes a set of trials in environment using its policy π\n\t- Percepts supply both current state & reward received for the transition that just occurred to reach that state\n\t- Each transition annotated with both action taken & reward received at next state\n\t- Agent will use info about rewards to learn expected utility associated with each nonterminal state s\n\t\t- Utility: expected sum of (discounted) rewards obtained if policy π is followed\n- Active RL: agent must also figure out what to do\n\t- Will need to learn complete T w/ outcome probabilities for all actions instead of just model for fixed policy\n\t- Has choice of actions => needs to learn utilities defined by optimal policy\n- Main issue is exploration: agent must experience as much as possible of its environment in order to learn how to behave in it (can use inductive learning to learn much faster)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n- Direct utility est: util of state defined as exp total reward from that state onward that each trial provides sample of this quantity for each state visited\n\t- RL => standard supervised learning prob => each example = (state, reward-to-go)\n\t\t- Constraint: util of state determined by reward & exp util of successor states (util values obey Bellman for fixed policy)\n\t\t\t- Ignoring connections between states: DUE misses opps for learning\n\t- Can view DUE as searching for U in hypothesis space that's much larger than needed (includes many functions that violate Bellman)\n- Adaptive dynamic programming (ADP): agent takes advantage of constraints among utils of states by learning T that connects them & solving corresponding MDP using DP\n\t- Take PL agent, plug in T & observed R to calc utils of states\n\t- Alsocan take approach of modified policyiter: using simplified valiter to update util estimates after each change to learned model\n\t\t- Since model usu only changes slightly w/ each obs, valueiter can use prev util esimates as init vals & converge very quickly\n\t- Learning T=easy bc env is fully observable\n\t- How quickly val ests improve=> ADP agent limited only by ability to learn T (intractable for large state spaces)\n- TD learning: Can use observed transitions to adj utils of observed states so that they agree w/ constraint eqns\n\t- New update rule uses diff in utils between successive states/times (TD eqn)\n\t\t- TD term = error signal (update is intended to reduce error)\n\t- All TD methods work by adj util ests toward ideal equilib that holds locally when util ests=correct\n\t- TD agent learns slower than ADP agent & shows higher variability, but much simpler & requires much less computation per obs\n\t\t- TD doesn't need T to perform updates: env itself supplies connection between neighboring states in form of observed transitions\n\t- ADP & TD approaches both try to make local adj to util estimates to make each state \"agree\" w/ its successors. Diffs:\n\t\t- TD adj state to agree w/ its observed successor; ADP adj to agree w/ all of successors that might occur, weighted by their probabilities\n\t\t\t- Diff disappears when effects of TD adj are averaged over large # of transitions (freq of each successor in set of transitions approx. proportional to its probability)\n\t\t- TD makes single adj per observed transition; ADP makes as many as needed to restore consistency between util ests U & transition model P\n\t\t\t- TD=crude but efficient first approx to ADP\n\t- From TD POV, each adj made by ADP = result of pseudoexperience generated by simulating current T\n\t\t- TD agent can generate large # of imaginary transitions for each observed transition => resulting util ests will approx more closely those of ADP\n\t- Can generate more efficient versions of ADP by directly approxing algs for value/policyiter\n\t\t- Can generate good answers quickly by bounding # of adj made after each observed transition\n\t- Approx ADP algs can learn roughly as fast as full ADP but can be much more efficient\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- Greedy agent: always take constant believed optimal action: can lead to suboptimal results => learned model =/= true env\n\t- Overlooks: actions provide rewards AND info\n\t- GLIE: try each action in each state unbounded # of times to avoid having finite probability that optimal action is missed\n\t\t- Choose random action at time step t with probability 1/t otherwise follow greedy policy (will slowly converge)\n\t\t- Give weight to less-tried actions but avoiding possible low util\n- Exploration fn f(u,n): determines how greed (pref for high values of util u) traded off against curiosity (pref for actions not tried often, low count n) => increasing u & decreasing n\n\n- Worst case: agent enters absorbing state bc model unknown (actively explore in bad direction) or incorrect (don't know given action is disastrous)\n- Better: choose okay policy that works for range of models that have chance of being true model, even if policy suboptimal for maximum-likelihood model (Bayesian RL)\n\t- Robust control theory: allows for set of possible models H w/o assigning probabilities to them & defines optimal robust policy = gives best outcome in worst case over H (too conservative)\n\t\t- H = set of models that exceed some likelihood threshold on posterior P(h|e) (Bayesian & robust are related)\n- Human knowledge can help keep sys safe: record actions by expert so sys acts reasonably from start or write down constraints on sys & have prog outside of RL sys enforce\n\n- Active TD learning agent: have to learn T to choose action based on U(s) via one-step look-ahead\n- Model acq prob still identical to ADP agent & TD update rule remains unchanged\n- Q-learn method: learns action-utility Q(s,a) not utility U(s) => act optimally (choose argmax)\n\t- TD Q-learn agent doesn't need T for learning or action selection\n\t- Cons: q-learn agent no way look into future=> may have difficulty when rewards=sparse & long action seq must be constructed to reach them\n- Like Q-learn: SARSA (state, action, reward, state', action')\n\t- Update rule like Q-learn except SARSA updates w/ q-value of action a' actually taken\n\t- Q-learn backs up q-value from best action in s' ==> SARSA waits until action taken & backs up q-value for that action\n\t\t- If agent=greedy & always takes action w/ best q-value: two algs are identical\n\t\t- If explore happening: if yields negative reward, SARSA penalizes action; Q-learning doesn't\n- Q-learn = off-policy: learns q-values that answer: \"what would action be worth in state, assuming that I switch to policy that chooses best action?\"\n- SARSA = on-policy: learns q-values that answers: \"what would action be worth in state, assuming that I stick w/ my policy?\"\n- Q-learn more flexible: can learn how to behave well when under control of wide variety of exploration policies\n- SARSA appropriate if overall policy is even partly controlled by other agents or progs\n- Both learn optimal pol=> much slower than ADP agent (local updates don't enforce consistency among all q-values via model)\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n- Function approx with look-ahead search ==> produce more accurate decisions\n\t- Effective behavior can result from much simpler util fn approximator that's learnable from fewer experiences\n  - Makes it practical to represent util (or Q) fns for large spaces\n  - Allows for inductive generalization: can generalize from states visited to states not yet visited\n  - Approximating DUE: learn faster if use fn approximator if hypothesis space not too large & includes some fn that're reasonably good fit to true util fn\n- Approximating TD learning: adj params to reduce TD between successive states\n\t- For passive TD learning, update rule can converge to closest possible approx to true fn when fn approximator is linear in features\n\t- For active learning & nonlinear functions (neural nets): params can go to infinity w/ these update rules even if good solutions in hypothesis space\n\t- Catastrophic forgetting: if agent learns too well (flat value fn, so quadratic features get zero weight, but then nonzero weight on linear features cause abrupt change)\n\t\t- Solution: experience replay (ensures agent relives youthful bad behavior at intervals to ensure value fn still accurate for parts of state space no longer visits)\n- Deep RL system: RL system that uses deep network as fn approximator\n\t- 2 reasons why we need to go beyond linear fn approximators:\n\t\t- May be no good linear fn that comes close to approximating util fn or Q-function\n\t\t- May not be able to invent necessary features, particularly in new domains\n\t- Deep NN discovers useful features for itself: final layer linear => can see what features network used to build own linear fn approximator\n\t- Deep NN = fn parameterized by theta except fn much more complicated => params are all weights in layers of network (but gradient same as in supervised learning)\n- Reward shaping\n\t- Prob of credit assignment: other than going through process a million times before rewards propagate back to actions responsible for it\n\t- Reward shaping: supplying agent with additional rewards for \"making progress\" (pseudorewards)\n\t\t- Risk that agent will learn to maximize pseudorewards rather than true rewards\n- Hierarchical reinforcement learning: break up very long action seqs into few smaller pieces, then break those into smaller pieces still, and so on until action sequences are short enough to make learning easy\n\t- Partial program: outlines hierarchical structure for agent's behavior\n\t- HRL includes ordinary RL as a special case\n\t- Choose operator allows agent to choose any element of specified set\n\t- Learning process converts partial agent program into a complete program by learning how each choice should be made\n\t- Can be effective method for learning complex behaviors\n  - Important characteristic: lower-level skills are not fixed subroutines ==> their choices are sensitive to entire internal state of agent program so they behave differently depending on where they are invoked within that program and what is going on at the time\n\n\n## AIMA Chapter 22.5 Policy Search\n\n- Idea is to keep twiddling the policy as long as performance improves, then stop\n- Interested primarily in parameterized representations of π that have far fewer parameters than there are states in the state space\n- If policy is represented by Q-functions ==> policy search results in process that learns Q-functions\n\t- Not the same as Q-learning!\n\t\t- Q-learning: finds value of theta to approximate Q*\n\t\t- Policy search: finds value of theta that results in good performance (may be far from estimating true utility function)\n- Policy = discontinuous function of parameters when actions are discrete\n\t- Will be values of theta such that the smallest change will cause the policy to switch from one action to another\n\t- Will use a stochastic policy representation which specifies probability of select action a in state s (i.e. softmax)\n\t\t- β > 0 modulates softness of softmax\n\t\t- If large: approaches hard max\n    - If close to 0: approaches uniform random choice among actions\n\n\n## Module 9 Lecture Notes\n\n- Solving MDPs = offline planning\n  - Determine all quantities through computation\n  - Need to know the details of the MDP\n  - Do not actually play the game\n- Regret: even if you learn intelligently, you make mistakes\n- Sampling: bc of chance, you have to try things repeatedly\n- Difficulty: learning can be much harder than solving a known MDP\n- RL basic idea:\n  - Receive feedback in the form of rewards\n  - Agent's utility is defined by the reward function\n  - Must (learn to) act so as to maximize expected rewards\n  - All learning is based on observed samples of outcomes\n- Still assume MDP: set of states, set of actions, transition model, reward function => still looking for a policy\n  - New twist: don't know the transition model or reward function: must actually try actions & states out to learn\n- Model-based learning: estimate T & R & plug in\n  - Learn an approximate model based on experiences & solve for values as if the learned model were correct\n  - Step 1: learn empirical MDP model\n    - Count outcomes s' for each s,a\n    - Normalize to give an estimate of T(s,a,s')\n    - Discover each R(s,a,s') when we experience (s,a,s')\n  - Step 2: solve the learned MDP (i.e. use value iteration)\n- Model-free learning: don't build explicit transition model\n  - Take action, compare results to what we thought was going to happen to what actually happens\n  - When something deviates from expectation, take values & adjust them up or down\n  - Track values of being in certain states, don't track transition or reward values\n- Passive RL: instead of us picking the policy, let someone else choose & we'll try it out\n  - Don't figure out how to act optimally, instead see how good this policy is\n  - Simplified task: policy evaluation where input=fixed policy, but don't know T or R ==> goal: learn state values\n  - Learner is \"along for the ride\" & has no choice about what actions to take => just execute the policy & learn from experience\n- Direct evaluation: goal is to compute values for each state under policy\n  - Idea: average together observed sample values\n    - Act according to policy\n    - Every time you visit a state, write down what the sum of discounted rewards turned out to be\n    - Average those samples\n  - Pros: easy to understand, doesn't require knowledge of T or R, eventually computes the correct avg values using just sample transitions\n  - Cons: wastes info about state connections, each state must be learned separately => takes a long time to learn\n- Temporal Difference Learning: solution to policy eval since we don't know T or R\n  - Want to improve our estimate of V by computing these averages by taking samples of outcomes s' (by doing the action!) & average, but we can't rewind time to get sample after sample from state s\n- TD learning: learn from every experience => Update V(s) each time we experience a transition (s,a,s',r) => Likely outcomes s' will contribute updates more often\n  - Policy still fixed, still doing evaluation\n  - Move values toward value of whatever successor occurs: running average\n  - Exponential moving average: makes recent samples more important & forgets about the past (distant past values were wrong anyway)\n    - Decreasing learning rate (alpha) can give converging averages\n  - Problems with TD value learning: model-free way to do policy eval, mimicking Bellman updates with running sample averages; however, if we want to turn values into a (new) policy, we're sunk\n    - Idea: learn Q-values, not values\n    - Makes action selection model-free too\n- Active RL: don't know T or R but we choose the actions now => learn the optimal policy/values\n  - Learner makes choices => fundamental tradeoff between exploration vs exploitation\n  - Q-learning: sample-based Q-value iteration (refer to written notes)\n    - Off-policy learning: Q-learning converges to optimal policy even if you're acting suboptimally\n    - Caveats: have to explore enough, have to eventually make the learning rate small enough (but don't decrease it too quickly) => but in the limit, doesn't matter how you select actions\n- Exploration vs Exploitation\n  - Problem with epsilon greedy: eventually explore the space, but keep thrashing around once learning is done (soln: lower epsilon over time OR exploration functions (explore areas whose badness is not yet established))\n    - Exploration function: refer to written notes\n  - Basic Q-learning keeps a table of all q-values: not realistic! => too many states to visit them all in training & to hold q-tables in memory\n    - Want to generalize: learn about some small # of training states from experience => generalize that experience to new, similar situations\n    - Approximate Q-learning: adjust weights of active features as positive or negative\n\n\n## Module 9 Definitions\n* **Prioritized sweeping heuristic** - make adj to states whose likely successors have just undergone a large adjustment in their own utility estimates\n* **Absorbing state** - state where no actions have any effect & no rewards are received\n* **Glie** - greedy in limit of infinite exploration\n* **Evaluation function** - measure of desirability for potentially vast state spaces (approximate utility function)\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities & Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell & Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"\n",
        "- Problem-solving & logical agents handle uncertainty by keeping track of belief state and generate contingency plan that handles every possible eventuality that its sensors may report during execution\n",
        "\t- Belief state: representation of the set of all possible world states that it might be in\n",
        "\t- Drawbacks:\n",
        "\t\t- Agent must consider every possible explanation for its sensor observations, no matter how unlikely\n",
        "\t\t- Plan can grow very large and must consider arbitrarily unlikely contingencies\n",
        "\t\t- Sometimes there's no plan that's guaranteed to achieve the goal\n",
        "- Rational decision depends on both relative importance of various goals and the likelihood that they will be achieved\n",
        "- Summarizing uncertainty\n",
        "\t- Enumerating all possible logical rules (i.e. for medical diagnosis) might fail due to:\n",
        "    - Laziness (too much work to do this)\n",
        "    - Theoretical ignorance (there is no complete theory for the domain)\n",
        "    - Practical ignorance (even if we know all the rules, might still be uncertain)\n",
        "\t- Agent's knowledge can at best provide only degree of belief in relevant sentences => deal with it using probability theory\n",
        "\t\t- Ontological commitments of logic and probability theory are the same: world is composed of facts that do or don't hold in any particular case\n",
        "\t\t- Epistemological commitments: logical agent believes each sentence to be T/F or has no opinion; probabilistic agent may have a numerical degree of belief between 0 and 1\n",
        "\t- Theory of probability provides way of summarizing the uncertainty that comes from our laziness and ignorance\n",
        "\t- Probability statements are made wrt knowledge state, not real world\n",
        "- Uncertainty and rational decisions\n",
        "\t- Agent must have preferences among different possible outcomes of various plans\n",
        "\t\t- Use utility theory to represent preferences and reason quantitatively with them\n",
        "\t\t- Utility of a state: relative to an agent\n",
        "\t\t- No accounting for taste or preferences (can't think agent is irrational bc preferences is odd)\n",
        "\t- Decision theory = probability theory + utility theory\n",
        "\t\t- Fundamental idea: agent is rational iff it chooses the action that yields the highest expected utility, averaged over all possible outcomes of the action\n",
        "\t\t\t- Maximum expected utility (MEU)\n",
        "  - Decision-theoretic agent's belief state represents not just possibilities for world states but also their probabilities\n",
        "\"\"\"\n",
        "\n",
        "chapter12_2 = \"\"\"\n",
        "- What probabilities are about\n",
        "\t- Logical assertions: which possible worlds are strictly ruled out ==> probabilistic assertions: how probable the various worlds are\n",
        "\t- Sample space: set of all possible worlds (mutually exclusive & exhaustive)\n",
        "\t- Probability model: associates numerical probability with each possible world\n",
        "\t- Unconditional / prior probabilities: degrees of belief in propositions in the absence of any other information\n",
        "\t\t- Most of the time, we do have evidence (some information)\n",
        "\t- When making decisions, an agent needs to condition on all evidence it has observed\n",
        "- The language of propositions in probability assertions\n",
        "\t- Every random variable RV is a function that maps from domain of possible worlds to some range: set of possible values it can take on\n",
        "\t- Probabilities are unitless numbers whereas density functions are measured with a unit\n",
        "\t- Joint probability distribution (i.e. P(Weather,Cavity) = probabilities of all combos of values of Weather and Cavity)\n",
        "\t- Possible world defined to be an assignment of values to all of the RVs under consideration\n",
        "- Probability axioms and their reasonableness\n",
        "\t- Inclusion-exclusion principle: P(a or b) = P(a) + P(b) - P(a and b)\n",
        "\t- Finetti's argument for axioms of probability: if an agent has some degree of belief in a proposition a, then the agent should be able to state odds at which it is indifferent to a bet for or against a\n",
        "    - If agent1 expresses a set of degrees of belief that violate the axioms of probability theory, then there is a combo of bets by agent2 that guarantees agent1 will lose money every time\n",
        "\"\"\"\n",
        "\n",
        "chapter12_3 = \"\"\"\n",
        "- Probabilistic inference: computation of posterior probabilities for query propositions given observed evidence\n",
        "- Not used in practice because it requires input table of size O(2^n) in time and space\n",
        "\"\"\"\n",
        "\n",
        "chapter12_4 = \"\"\"\n",
        "- If two events are independent:\n",
        "\t- P(a|b) = P(a)\n",
        "\t- P(b|a) = P(b)\n",
        "\t- P(a&b) = P(a)*P(b)\n",
        "- Independence assertions usually based on knowledge of domain\n",
        "\"\"\"\n",
        "\n",
        "chapter12_5 = \"\"\"\n",
        "- P(effect|cause): quantifies relationship in causal direction\n",
        "- P(cause|effect): quantifies in diagnostic direction\n",
        "- Conditional independence of two variables given a third: P(Cavity | toothache & catch) = P(toothache | Cavity)*P(catch | Cavity)*P(Cavity)\n",
        "\t- Conditional independence of two variables X and Y given a third variable Z: P(X,Y | Z) = P(X|Z)*P(Y|Z)\n",
        "- Conditional independence assertions can allow probabilistic systems to scale up; moreover, they are much more commonly available than absolute independence assertions\n",
        "- Decomposition of large probabilistic domains into weakly connected subsets through conditional independence is one of the most important developments in the recent history of AI\n",
        "\"\"\"\n",
        "\n",
        "chapter12_6 = \"\"\"\n",
        "- \"Naïve\" bc used in cases where \"effect\" of variables aren't strictly independent given the cause variable\n",
        "- For each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause; then normalize result\n",
        "\t- Runtime of calculation is linear in number of observed effects and doesn't depend on number of unobserved effects\n",
        "- Even though bc of assumption of conditional independence, model is overconfident in its predictions; however, even with these errors, the ranking of possible categories is often quite accurate\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky & Martin, Speech & Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\"\n",
        "- Get MLE estimate for the parameters of an n-gram model by getting counts from a corpus and normalizing the counts so they lie between 0 and 1\n",
        "  - Relative frequency: estimate n-gram probability by dividing the observed frequency of a particular sequence by the observed frequency of a prefix\n",
        "- Use log probabilities and not raw probabilities to keep numbers from getting too small\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "- Extrinsic evaluation: best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves\n",
        "  - Only way to know if a particular improvement in a component is really going to help the task at hand\n",
        "  - Unfortunately, running big NLP systems end-to-end is very expensive\n",
        "- Intrinsic evaluation: measures quality of a model independent of any application\n",
        "- Training on test set introduces bias that makes probabilities all look too high and causes huge inaccuracies in perplexity\n",
        "- Perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words\n",
        "  - Higher the conditional probability of the word sequence, the lower the perplexity\n",
        "  - Minimizing perplexity = maximizing the test set probability according to LM\n",
        "- Since seq will cross many sentence boundaries => need to include begin- and end-sentence markers <s> and </s> in probability computation\n",
        "- Another way of thinking about perplexity: weighted average branching factor of a language\n",
        "  - Branching factor of language = # of possible next words that can follow any word\n",
        "- Perplexity used to compare different n-gram models: more info the n-gram gives us about the word seq, the lower the perplexity\n",
        "- In computing perplexities, n-gram model must be constructed without any knowledge of test set or any prior knowledge of the vocab of test set\n",
        "- Intrinsic improvement in perplexity does not guarantee an extrinsic improvement in performance of a language processing task\n",
        "- Model's improvement in perplexity should always be confirmed by an end-to-end evaluation of a real task before concluding the evaluation of the model\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "- N-gram model depends on training set => probabilities often encode specific facts about given training corpus and n-grams do a better and better job of modeling the training corpus as N increases\n",
        "- The longer the context on which we train the model, the more coherent the sentences\n",
        "  - Unigram sentences: no coherent relation between words or any sentence-final punctuation\n",
        "- What if training and test sets have no overlap? => no, must be similar genre and in appropriate dialect or variety of test set\n",
        "- Problem of sparsity: have cases of \"zero probability n-grams\" that should have non-zero probability\n",
        "- Problems of zeros:\n",
        "  - We underestimate the probability of all sorts of words that might occur\n",
        "  - If probability of any word in the test set = 0, entire probability of test set is 0\n",
        "- Out of vocabulary (OOV) words = unknown\n",
        "  - OOV rate: % of OOV words that appear in test set\n",
        "- To train probabilities of unknown:\n",
        "  - Turn problem back into closed vocab by choosing a fixed vocab in advance:\n",
        "    - Choose vocab that is fixed in advance\n",
        "    - Covert any word that's not in this set to <unk>\n",
        "    - Estimate probabilities for <unk> from its counts just like other regular words in the set\n",
        "  - If we don't have prior vocab in advance: create vocab implicitly, replacing words in the training data by <unk> based on their frequency\n",
        "- Exact choice of <unk> model affects metrics like perplexity: should only be compared across LMs with same vocabs\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "- Laplace (add-one) smoothing: add one to all bigram counts before normalizing into probabilities\n",
        "  - Does not perform well enough to be used in modern n-gram models, but it usefully introduces many of the concepts in other smoothing algs, gives a useful baseline, and is practical for tasks like text classification\n",
        "- Relative discount d: ratio of discounted counts to original counts\n",
        "- Add-k smoothing: move a bit less of probability mass from seen to unseen events => instead of 1, add fractional count k (i.e. 0.5)\n",
        "  - k is hyperparam that needs tuning\n",
        "  - Still doesn't work great for language modeling\n",
        "- Sometimes using less context is good, helping to generalize more for contexts that the model hasn't learned much about\n",
        "  - Backoff: use trigram if evidence is sufficient, else bigram, else unigram\n",
        "  - Interpolation: always mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram and unigram counts\n",
        "    - Linear: Weight each with lambda such that sum of lambda = 1\n",
        "    - Other: each lambda weight is computed by conditioning on the context\n",
        "      - If we have particularly accurate counts for a particular bigram, can assume that counts of the trigrams based on this bigram will be more trustworth so we can make the lambdas for those trigrams higher and thus give that trigram more weight in the interpolation\n",
        "  - Lambdas are set and tuned using a held-out corpus: can use EM alg\n",
        "  - In backoff n-gram model, if the n-gram we need has zero counts, approximate it by backing off to the (N-1)-gram => keep backing off until reach a history that has some counts\n",
        "    - Have to discount the higher-order n-grams to save some probability mass for lower order n-grams\n",
        "    - Katz backoff: rely on discounted probability P* if we've seen n-gram before\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "- Kneser-Ney has its roots in absolute discounting: subtract a fixed (absolute) discount d from each count\n",
        "- Idea was to look at a held-out corpus and just see what the count is for all those bigrams that had count 4 in training set\n",
        "- Kneser-Ney discounting augments absolute discounting with a more sophisticated way to handle the lower-order unigram distribution\n",
        "- Want to create unigram model PCONTINUATION that answers the question \"How likely is w to appear as a novel continuation?\"\n",
        "- Kneser-Ney intuition is to base our estimate of PCONTINUATION on the # of different contexts word w has appeared in (# of bigram types it completes)\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "- Entropy is a lower bound on # of bits it would take to encode a certain decision or piece of info in the optimal coding scheme\n",
        "- Entropy rate: entropy of seq divided by # of words\n",
        "- Stochastic process: stationary if probabilities it assigns to a seq are invariant wrt shifts in the time index\n",
        "  - Markov models (and hence n-grams) are stationary\n",
        "  - But natural language is not stationary: probability of upcoming words can be dependent on events that were arbitrarily distant and time dependent\n",
        "- By making some incorrect but convenient simplifying assumptions, can compute the entropy of some stochastic process by taking a very long sample of the output and computing its average log probability\n",
        "- Cross-entropy: useful when we don't know the actual probability distribution p that generated some data\n",
        "  - Draw sequences according to probability distribution p, but sum the log of their probabilities according to m (some model of p)\n",
        "  - Can estimate the cross-entropy of a model m on some distribution p by taking a single seq that is long enough instead of summing over all possible seq\n",
        "  - Cross-entropy H(p,m) is an upper bound on the entropy H(p)\n",
        "    - Means we can use some simplified model m to help estimate the true entropy of a seq of symbols drawn according to probability p\n",
        "    - The more accurate m is, the closer the cross-entropy H(p,m) will be to the true entropy H(p)\n",
        "    - Thus, difference between H(pm,) and H(p) is a measure of how accurate a model is\n",
        "    - Between two models m1 and m2, the more accurate model will be the one with lower cross-entropy (cross-entropy can never be lower than true entropy, so model cannot err by underestimating the true entropy)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "- Probabilistic reasoning gives us framework for managing our beliefs and knowledge\n",
        "  - Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms)\n",
        "  - Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present)\n",
        "  - Model: Agent knows something about how the known variables relate to the unknown variables\n",
        "- Like logical assertions, probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is.\n",
        "- In probability theory, the possible worlds are called the sample space, and they are mutually exclusive and exhaustive.\n",
        "- Fully specified probability model associates a probability P(w) with each possible world w.\n",
        "- Random variable: some aspect of world about which we (may) have uncertainty\n",
        "- Axioms of probability (between 0 and 1 and sum of probs = 1)\n",
        "- Joint distribution specifies real # for each assignment (or outcome): size of distribution if n variables w/ domain sizes d (d^n)\n",
        "- Probabilistic model = joint distribution over set of RV\n",
        "  - RV with domains\n",
        "  - Assignments = outcomes\n",
        "  - Joint dist: say whether outcomes are likely\n",
        "  - Normalized: sum to 1\n",
        "  - Ideally only certain variables directly interact\n",
        "- Event: set of outcomes\n",
        "- Conditional distributions: probability distributions over some variables given fixed values of others\n",
        "- Probabilistic inference: compute desired probability from other known probabilities (i.e. conditional from joint)\n",
        "- Inference by enumeration:\n",
        "  - Select the entries consistent with the evidence\n",
        "  - Sum out H to get joint of Query and evidence\n",
        "  - Normalize\n",
        "- Product rule: P(x|y)P(y) = P(x,y)\n",
        "- Probabilistic language models: goal is to assign a probability to a sentence (related task: probability of upcoming word)\n",
        "  - Autocomplete for texting\n",
        "  - Machine translation\n",
        "  - Spelling correction\n",
        "  - Speech recognition\n",
        "- Markov assumption: only depends on previous k words, not whole context\n",
        "  - Unigram: no history; bigram: 1 word; trigram: 2 words; 4-gram: 3 words\n",
        "- N-grams: insufficient model of language bc language has long-distance dependencies\n",
        "- Problems for MLE:\n",
        "  - Out of vocab items (OOV): <unk> to deal with OOVs\n",
        "  - Fixed lexicon L of size V\n",
        "  - Normalize training data by replacing any word not in L with <unk>\n",
        "  - Avoid zeros with smoothing\n",
        "- Practical issues: do everything in log space to avoid underflow (also adding is faster than multiplying)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"zeros\" : \"grams that occur in the test set but not in the training set\",\n",
        "\"closed vocabulary system\": \"test set can only contain known words\",\n",
        "\"open vocabulary system\": \"model potential unknown words in test set using <unk>\"\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 4999
        },
        "cellView": "form",
        "outputId": "5bf63529-773b-4819-bac1-9df81982fa66"
      },
      "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 & 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 & Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models & Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies & Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies & Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- Problem-solving & logical agents handle uncertainty by keeping track of belief state and generate contingency plan that handles every possible eventuality that its sensors may report during execution\n\t- Belief state: representation of the set of all possible world states that it might be in\n\t- Drawbacks:\n\t\t- Agent must consider every possible explanation for its sensor observations, no matter how unlikely\n\t\t- Plan can grow very large and must consider arbitrarily unlikely contingencies\n\t\t- Sometimes there's no plan that's guaranteed to achieve the goal\n- Rational decision depends on both relative importance of various goals and the likelihood that they will be achieved\n- Summarizing uncertainty\n\t- Enumerating all possible logical rules (i.e. for medical diagnosis) might fail due to:\n    - Laziness (too much work to do this)\n    - Theoretical ignorance (there is no complete theory for the domain)\n    - Practical ignorance (even if we know all the rules, might still be uncertain)\n\t- Agent's knowledge can at best provide only degree of belief in relevant sentences => deal with it using probability theory\n\t\t- Ontological commitments of logic and probability theory are the same: world is composed of facts that do or don't hold in any particular case\n\t\t- Epistemological commitments: logical agent believes each sentence to be T/F or has no opinion; probabilistic agent may have a numerical degree of belief between 0 and 1\n\t- Theory of probability provides way of summarizing the uncertainty that comes from our laziness and ignorance\n\t- Probability statements are made wrt knowledge state, not real world\n- Uncertainty and rational decisions\n\t- Agent must have preferences among different possible outcomes of various plans\n\t\t- Use utility theory to represent preferences and reason quantitatively with them\n\t\t- Utility of a state: relative to an agent\n\t\t- No accounting for taste or preferences (can't think agent is irrational bc preferences is odd)\n\t- Decision theory = probability theory + utility theory\n\t\t- Fundamental idea: agent is rational iff it chooses the action that yields the highest expected utility, averaged over all possible outcomes of the action\n\t\t\t- Maximum expected utility (MEU)\n  - Decision-theoretic agent's belief state represents not just possibilities for world states but also their probabilities\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- What probabilities are about\n\t- Logical assertions: which possible worlds are strictly ruled out ==> probabilistic assertions: how probable the various worlds are\n\t- Sample space: set of all possible worlds (mutually exclusive & exhaustive)\n\t- Probability model: associates numerical probability with each possible world\n\t- Unconditional / prior probabilities: degrees of belief in propositions in the absence of any other information\n\t\t- Most of the time, we do have evidence (some information)\n\t- When making decisions, an agent needs to condition on all evidence it has observed\n- The language of propositions in probability assertions\n\t- Every random variable RV is a function that maps from domain of possible worlds to some range: set of possible values it can take on\n\t- Probabilities are unitless numbers whereas density functions are measured with a unit\n\t- Joint probability distribution (i.e. P(Weather,Cavity) = probabilities of all combos of values of Weather and Cavity)\n\t- Possible world defined to be an assignment of values to all of the RVs under consideration\n- Probability axioms and their reasonableness\n\t- Inclusion-exclusion principle: P(a or b) = P(a) + P(b) - P(a and b)\n\t- Finetti's argument for axioms of probability: if an agent has some degree of belief in a proposition a, then the agent should be able to state odds at which it is indifferent to a bet for or against a\n    - If agent1 expresses a set of degrees of belief that violate the axioms of probability theory, then there is a combo of bets by agent2 that guarantees agent1 will lose money every time\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- Probabilistic inference: computation of posterior probabilities for query propositions given observed evidence\n- Not used in practice because it requires input table of size O(2^n) in time and space\n\n\n## AIMA Chapter 12.4 Independence\n\n- If two events are independent:\n\t- P(a|b) = P(a)\n\t- P(b|a) = P(b)\n\t- P(a&b) = P(a)*P(b)\n- Independence assertions usually based on knowledge of domain\n\n\n## AIMA Chapter 12.5 Bayes’ Rule & Its Use\n\n- P(effect|cause): quantifies relationship in causal direction\n- P(cause|effect): quantifies in diagnostic direction\n- Conditional independence of two variables given a third: P(Cavity | toothache & catch) = P(toothache | Cavity)*P(catch | Cavity)*P(Cavity)\n\t- Conditional independence of two variables X and Y given a third variable Z: P(X,Y | Z) = P(X|Z)*P(Y|Z)\n- Conditional independence assertions can allow probabilistic systems to scale up; moreover, they are much more commonly available than absolute independence assertions\n- Decomposition of large probabilistic domains into weakly connected subsets through conditional independence is one of the most important developments in the recent history of AI\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- \"Naïve\" bc used in cases where \"effect\" of variables aren't strictly independent given the cause variable\n- For each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause; then normalize result\n\t- Runtime of calculation is linear in number of observed effects and doesn't depend on number of unobserved effects\n- Even though bc of assumption of conditional independence, model is overconfident in its predictions; however, even with these errors, the ranking of possible categories is often quite accurate\n\n\n## SLP Chapter 3.1 N-Grams\n\n- Get MLE estimate for the parameters of an n-gram model by getting counts from a corpus and normalizing the counts so they lie between 0 and 1\n  - Relative frequency: estimate n-gram probability by dividing the observed frequency of a particular sequence by the observed frequency of a prefix\n- Use log probabilities and not raw probabilities to keep numbers from getting too small\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- Extrinsic evaluation: best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves\n  - Only way to know if a particular improvement in a component is really going to help the task at hand\n  - Unfortunately, running big NLP systems end-to-end is very expensive\n- Intrinsic evaluation: measures quality of a model independent of any application\n- Training on test set introduces bias that makes probabilities all look too high and causes huge inaccuracies in perplexity\n- Perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words\n  - Higher the conditional probability of the word sequence, the lower the perplexity\n  - Minimizing perplexity = maximizing the test set probability according to LM\n- Since seq will cross many sentence boundaries => need to include begin- and end-sentence markers <s> and </s> in probability computation\n- Another way of thinking about perplexity: weighted average branching factor of a language\n  - Branching factor of language = # of possible next words that can follow any word\n- Perplexity used to compare different n-gram models: more info the n-gram gives us about the word seq, the lower the perplexity\n- In computing perplexities, n-gram model must be constructed without any knowledge of test set or any prior knowledge of the vocab of test set\n- Intrinsic improvement in perplexity does not guarantee an extrinsic improvement in performance of a language processing task\n- Model's improvement in perplexity should always be confirmed by an end-to-end evaluation of a real task before concluding the evaluation of the model\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n- N-gram model depends on training set => probabilities often encode specific facts about given training corpus and n-grams do a better and better job of modeling the training corpus as N increases\n- The longer the context on which we train the model, the more coherent the sentences\n  - Unigram sentences: no coherent relation between words or any sentence-final punctuation\n- What if training and test sets have no overlap? => no, must be similar genre and in appropriate dialect or variety of test set\n- Problem of sparsity: have cases of \"zero probability n-grams\" that should have non-zero probability\n- Problems of zeros:\n  - We underestimate the probability of all sorts of words that might occur\n  - If probability of any word in the test set = 0, entire probability of test set is 0\n- Out of vocabulary (OOV) words = unknown\n  - OOV rate: % of OOV words that appear in test set\n- To train probabilities of unknown:\n  - Turn problem back into closed vocab by choosing a fixed vocab in advance:\n    - Choose vocab that is fixed in advance\n    - Covert any word that's not in this set to <unk>\n    - Estimate probabilities for <unk> from its counts just like other regular words in the set\n  - If we don't have prior vocab in advance: create vocab implicitly, replacing words in the training data by <unk> based on their frequency\n- Exact choice of <unk> model affects metrics like perplexity: should only be compared across LMs with same vocabs\n\n\n## SLP Chapter 3.4 Generalization & Zeros\n\n- Laplace (add-one) smoothing: add one to all bigram counts before normalizing into probabilities\n  - Does not perform well enough to be used in modern n-gram models, but it usefully introduces many of the concepts in other smoothing algs, gives a useful baseline, and is practical for tasks like text classification\n- Relative discount d: ratio of discounted counts to original counts\n- Add-k smoothing: move a bit less of probability mass from seen to unseen events => instead of 1, add fractional count k (i.e. 0.5)\n  - k is hyperparam that needs tuning\n  - Still doesn't work great for language modeling\n- Sometimes using less context is good, helping to generalize more for contexts that the model hasn't learned much about\n  - Backoff: use trigram if evidence is sufficient, else bigram, else unigram\n  - Interpolation: always mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram and unigram counts\n    - Linear: Weight each with lambda such that sum of lambda = 1\n    - Other: each lambda weight is computed by conditioning on the context\n      - If we have particularly accurate counts for a particular bigram, can assume that counts of the trigrams based on this bigram will be more trustworth so we can make the lambdas for those trigrams higher and thus give that trigram more weight in the interpolation\n  - Lambdas are set and tuned using a held-out corpus: can use EM alg\n  - In backoff n-gram model, if the n-gram we need has zero counts, approximate it by backing off to the (N-1)-gram => keep backing off until reach a history that has some counts\n    - Have to discount the higher-order n-grams to save some probability mass for lower order n-grams\n    - Katz backoff: rely on discounted probability P* if we've seen n-gram before\n\n\n## SLP Chapter 3.5 Smoothing\n\n- Kneser-Ney has its roots in absolute discounting: subtract a fixed (absolute) discount d from each count\n- Idea was to look at a held-out corpus and just see what the count is for all those bigrams that had count 4 in training set\n- Kneser-Ney discounting augments absolute discounting with a more sophisticated way to handle the lower-order unigram distribution\n- Want to create unigram model PCONTINUATION that answers the question \"How likely is w to appear as a novel continuation?\"\n- Kneser-Ney intuition is to base our estimate of PCONTINUATION on the # of different contexts word w has appeared in (# of bigram types it completes)\n\n\n## SLP Chapter 3.7 Huge Language Models & Stupid Backoff\n\n- Entropy is a lower bound on # of bits it would take to encode a certain decision or piece of info in the optimal coding scheme\n- Entropy rate: entropy of seq divided by # of words\n- Stochastic process: stationary if probabilities it assigns to a seq are invariant wrt shifts in the time index\n  - Markov models (and hence n-grams) are stationary\n  - But natural language is not stationary: probability of upcoming words can be dependent on events that were arbitrarily distant and time dependent\n- By making some incorrect but convenient simplifying assumptions, can compute the entropy of some stochastic process by taking a very long sample of the output and computing its average log probability\n- Cross-entropy: useful when we don't know the actual probability distribution p that generated some data\n  - Draw sequences according to probability distribution p, but sum the log of their probabilities according to m (some model of p)\n  - Can estimate the cross-entropy of a model m on some distribution p by taking a single seq that is long enough instead of summing over all possible seq\n  - Cross-entropy H(p,m) is an upper bound on the entropy H(p)\n    - Means we can use some simplified model m to help estimate the true entropy of a seq of symbols drawn according to probability p\n    - The more accurate m is, the closer the cross-entropy H(p,m) will be to the true entropy H(p)\n    - Thus, difference between H(pm,) and H(p) is a measure of how accurate a model is\n    - Between two models m1 and m2, the more accurate model will be the one with lower cross-entropy (cross-entropy can never be lower than true entropy, so model cannot err by underestimating the true entropy)\n\n\n## Module 10 Lecture Notes\n\n- Probabilistic reasoning gives us framework for managing our beliefs and knowledge\n  - Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms)\n  - Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present)\n  - Model: Agent knows something about how the known variables relate to the unknown variables\n- Like logical assertions, probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is.\n- In probability theory, the possible worlds are called the sample space, and they are mutually exclusive and exhaustive.\n- Fully specified probability model associates a probability P(w) with each possible world w.\n- Random variable: some aspect of world about which we (may) have uncertainty\n- Axioms of probability (between 0 and 1 and sum of probs = 1)\n- Joint distribution specifies real # for each assignment (or outcome): size of distribution if n variables w/ domain sizes d (d^n)\n- Probabilistic model = joint distribution over set of RV\n  - RV with domains\n  - Assignments = outcomes\n  - Joint dist: say whether outcomes are likely\n  - Normalized: sum to 1\n  - Ideally only certain variables directly interact\n- Event: set of outcomes\n- Conditional distributions: probability distributions over some variables given fixed values of others\n- Probabilistic inference: compute desired probability from other known probabilities (i.e. conditional from joint)\n- Inference by enumeration:\n  - Select the entries consistent with the evidence\n  - Sum out H to get joint of Query and evidence\n  - Normalize\n- Product rule: P(x|y)P(y) = P(x,y)\n- Probabilistic language models: goal is to assign a probability to a sentence (related task: probability of upcoming word)\n  - Autocomplete for texting\n  - Machine translation\n  - Spelling correction\n  - Speech recognition\n- Markov assumption: only depends on previous k words, not whole context\n  - Unigram: no history; bigram: 1 word; trigram: 2 words; 4-gram: 3 words\n- N-grams: insufficient model of language bc language has long-distance dependencies\n- Problems for MLE:\n  - Out of vocab items (OOV): <unk> to deal with OOVs\n  - Fixed lexicon L of size V\n  - Normalize training data by replacing any word not in L with <unk>\n  - Avoid zeros with smoothing\n- Practical issues: do everything in log space to avoid underflow (also adding is faster than multiplying)\n\n\n## Module 10 Definitions\n* **Zeros** - grams that occur in the test set but not in the training set\n* **Closed vocabulary system** - test set can only contain known words\n* **Open vocabulary system** - model potential unknown words in test set using <unk>\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning & Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell & Norvig, Russell & Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "- Bayesian network is a directed acyclic graph in which each node is annotated with quantitative probability information\n",
        "\t- Each node corresponds to a random variable (discrete or continuous)\n",
        "\t- Directed links connect nodes. If X=>Y, means X is parent of Y. No cycles = DAG\n",
        "\t- Each node has associated probability of X given parents of X\n",
        "- Conditional probability tables (CPT): local probability info attached to each node\n",
        "\t- Each row contains conditional probability of each node value for a conditioning case (possible combo of values for parent nodes)\n",
        "\t- Table for Boolean variable with k Boolean parents contains 2k independently specifiable probabilities\n",
        "\t- Node with no parent has only one row, representing the prior probabilities of each possible value of the variable\n",
        "- Probabilities summarize a potentially infinite set of circumstances in which something might occur\n",
        "- Syntax of Bayes net: consists of DAG with some local probability info attached to each node\n",
        "- Semantics of Bayes net: defines how syntax corresponds to joint distribution over variables of network\n",
        "- When estimating vals for local cond dist => need to be actual cond probabilities for var given parents\n",
        "- Important property of Bayes nets: contain no redundant probability vals => no chance for inconsistency: can't create Bayes net that violates axioms of prob\n",
        "\"\"\"\n",
        "\n",
        "chapter13_2 = \"\"\"\n",
        "- Bayes net can be far more compact than full joint dist (sparse sys) => Local structure: linear growth in complexity\n",
        "- Specifying cond probability tables for fully connected net requires same amount of info as specifying joint dist in tabular form\n",
        "- Will get compact Bayes only if choose node ordering well\n",
        "- Stick to causal model, end up having to specify fewer #s & #s will often be easier to come up with\n",
        "- Cond independence relations: each var is cond independent of non-descendants given parents\n",
        "\t- Var cond independent of all other nodes in network, given parents, children & children's parents (given its Markov blanket)\n",
        "\t- Whether Z d-separates X & Y: whether set of nodes X is cond independent of another set Y given a third set Z\n",
        "\t\t- Consider just ancestral subgraph consisting of X, Y, Z & their ancestors\n",
        "\t\t- Add links between any unlinked pair of nodes that share common child (get moral graph)\n",
        "\t\t- Replace all directed w/ undirected links\n",
        "\t\t- If Z blocks all paths between X&Y in resulting graph, then Z d-separates X&Y ==> then X is cond independent of Y given Z\n",
        "\t\t- Otherwise, orig Bayes net doesn't require cond independence\n",
        "- Efficient Representation of Cond Dists\n",
        "\t- Even if max # of parents k is smallish, filling in CPT for node requires up to O(2^k) #s\n",
        "\t- Uncertain relationships can be characterized by noisy logical relationships\n",
        "\t\t- Noisy-OR relation (generalization of logical OR) - makes 2 assumps: all possible causes are listed & inhibition of each parent is independent of inhibition of any other parents\n",
        "\t\t- Noisy logical relationships where var depends on k parents can be described using O(k) params\n",
        "- Way to handle continuous vars: discretization (dividing into fixed set of intervals)\n",
        "- Can use standard families of pdfs (i.e. Gaussian)\n",
        "- Can use nonparametric rep to define cond dist implicitly w/ collection of instances, each containing specific vals of parent & child vars\n",
        "- Hybrid Bayes net: has both discrete & continuous => specify 2 new kinds of dists\n",
        "  - Cond dist for a continuous var given discrete or continuous parents\n",
        "    - Linear-Gaussian cond dist: child has Gaussian dist whose mean varies linearly w/ val of parent & std dev is fixed\n",
        "      - Network containing only continuous vars with linear-Gaussian dists has joint dist that's multivariate Gaussian dist over all vars\n",
        "      - Posterior dist given any evidence also has this property\n",
        "      - When discrete vars are added as parents of continuous vars, net defines cond Gaussian (CG) dist: given any assignment to discrete vars, dist over continous vars = multivariate Gaussian\n",
        "  - Cond dist for discrete var given continuous parents - like \"soft\" threshold fn (make by using integral of standard normal dist)\n",
        "    - Can use probit or expit/inverse logit models\n",
        "    - Probit often better fit to real situations\n",
        "    - Logit has longer tails & logistic fn sometimes easier to deal w/ mathematically\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "- Inference by enumeration\n",
        "  - Query can be answered using Bayes net by computing sums of products of conditional probabilities from network\n",
        "    - In worst case, where we have to sum out almost all variables, there will be O(2^n) terms in sum, each a product of O(n) probability values ==> O(n2^n)\n",
        "      - Can be reduced to O(2^n) by taking advantage of nested structure of computation\n",
        "  - Enumeration-ask alg evaluates expression trees using depth-first, left-to-right recursion\n",
        "    - Similar in structure to backtracking alg for solving CSPs and DPLL alg for satisfiability\n",
        "    - Space complexity: only linear in number of variables\n",
        "    - Time complexity: O(2^n) for network with n Boolean variables\n",
        "- Variable elimination algorithm\n",
        "  - Enumeration alg can be improved substantially by eliminating repeated calculations\n",
        "  - Idea: do calculation once and save results for later use (form of dynamic programming)\n",
        "  - One version of approach: variable elimination alg which works by evaluating expressions in right-to-left order\n",
        "    - Intermediate results are stored and summations over each variable are done only for those portions of expression that depend on variable\n",
        "  - Pointwise product of two factors f and g yields new factor h whose variables are union of vars in f and g and whose elements are given by product of corresponding elements in two factors\n",
        "  - Time and space requirements of variable elimination are dominated by the size of largest factor constructed during operation of algorithm\n",
        "    - Eliminate whichever variable minimizes the size of the next factor to be constructed\n",
        "    - Every variable that is not an ancestor of a query variable or evidence variable is irrelevant to the query\n",
        "- The complexity of exact inference\n",
        "  - Complexity of exact inference in Bayes nets depends strongly on structure of the network\n",
        "  - Singly connected networks / polytrees: networks that have at most one undirected path\n",
        "    - Time and space complexity of exact inference in polytrees is linear in the size of the network (size = # of CPT entires)\n",
        "  - Multiply connected networks: variable elimination can hav eexponential time and space complexity in the worst case, even when # of parents per node is bounded\n",
        "    - Bc it includes inference in propositional logic as special case, inference in Bayes nets is NP-hard\n",
        "- Clustering algorithms\n",
        "  - Variable elimination alg is simple and efficient for answering individual queries, but if we want to compute posterior probabilities for all variables in network, it can be less efficient\n",
        "    - Example: in polytree network, need to issue O(n) queries costing O(n) each for O(n^2) time ==> can use clustering to reduce time to O(n)\n",
        "      - Basic idea: join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "- Bayes net semantics: set of nodes (one per variable X), DAG, conditional distribution for each node\n",
        "- Bayes net = topology (graph) + local conditional probabilities\n",
        "- Bayes net implicitly encode joint distributions as product of local conditional distributions\n",
        "  - To see what probability a BN gives to full assignment, multiply all relevant conditionals together\n",
        "- Not every BN can represent every joint distribution\n",
        "- Only distributions whose variables are absolutely independent can be represented by a BN with no arcs\n",
        "- Size of Bayes net\n",
        "  - Size of joint distribution over N boolean variables: 2^N\n",
        "  - Size of N-node net if nodes have up to k parents: O(N * 2^(k+1))\n",
        "  - BNs: huge space savings\n",
        "  - Also easier to elicit local CPTs\n",
        "  - Also faster to answer queries\n",
        "- Causal chains: X => Y => Z\n",
        "  - One example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed\n",
        "  - Common cause: observing the cause blocks influence between effects\n",
        "  - Common effect:\n",
        "    - Are X and Y independent? Yes (still need to prove)\n",
        "    - Are X and Y independent given Z? No\n",
        "    - Backwards from other cases => observing an effect activates influence between possible causes\n",
        "- General question: in a given BN, are two variables independent (given evidence)? => Analyze graph\n",
        "  - Any complex example can be broken into repetitions of 3 canonical cases\n",
        "    - Reachability: shade evidence nodes, look for paths in resulting graph\n",
        "      - If 2 nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent\n",
        "- Active / Inactive Paths\n",
        "  - D-separation gives precise conditional independence guarantees from graph alone\n",
        "  - Are X and Y conditionally independent given evidence variables {Z}? => Yes, if X and Y \"d-separated\" by Z\n",
        "    - Consider all (undirected paths) from X to Y ==> no active paths = independence!\n",
        "  - Path is active if each triple is active:\n",
        "    - Causal chain A -> B -> C where B is unobserved (either direction)\n",
        "    - Common cause A <- B -> C where B is unobserved\n",
        "    - Common effect A -> B <- C where B or one of its descendants is observed\n",
        "  - All it takes to block a path is a single inactive segment\n",
        "- Given Bayes net structure: can run d-separation alg to build complete list of conditional independences that are necessarily true of the form [Xi independent of Xj | {Xk1,...,Xkn}]\n",
        "- Inference: calculating some useful quantity from a joint probability distribution\n",
        "- Inference by enumeration = very slow: joint up whole joint distribution before you sum out the hidden variables\n",
        "  - Advanced technique: variable elimination\n",
        "    - Interleave joining and marginalizing\n",
        "    - Still NP-hard, but usually much faster than inference by enumeration\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"deterministic node\" : \"val specified exactly by vals of its parents w/ no uncertainty and relationship can be logical or numerical\",\n",
        "\"context-specific independence (CSI)\":\"conditional dist exhibits CSI if a variable is conditionally independent of some of its parents given certain values of others\"\n",
        "}\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "Qc7ygr6Up1b4",
        "outputId": "198428e6-5347-428f-b9d1-778ee7f8e6ce"
      },
      "source": [
        "len(chapter13_3.split(\" \"))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "500"
            ]
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "maiqd8dXqdyy",
        "outputId": "75129ad0-3aff-4334-a851-d4f7fc4aba24"
      },
      "source": [
        "len(chapter13_3)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2817"
            ]
          },
          "metadata": {},
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2984
        },
        "cellView": "form",
        "outputId": "e6f4ce9d-ea3f-4362-a5bb-7afef021d76a"
      },
      "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 & Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning & Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n- Bayesian network is a directed acyclic graph in which each node is annotated with quantitative probability information\n\t- Each node corresponds to a random variable (discrete or continuous)\n\t- Directed links connect nodes. If X=>Y, means X is parent of Y. No cycles = DAG\n\t- Each node has associated probability of X given parents of X\n- Conditional probability tables (CPT): local probability info attached to each node\n\t- Each row contains conditional probability of each node value for a conditioning case (possible combo of values for parent nodes)\n\t- Table for Boolean variable with k Boolean parents contains 2k independently specifiable probabilities\n\t- Node with no parent has only one row, representing the prior probabilities of each possible value of the variable\n- Probabilities summarize a potentially infinite set of circumstances in which something might occur\n- Syntax of Bayes net: consists of DAG with some local probability info attached to each node\n- Semantics of Bayes net: defines how syntax corresponds to joint distribution over variables of network\n- When estimating vals for local cond dist => need to be actual cond probabilities for var given parents\n- Important property of Bayes nets: contain no redundant probability vals => no chance for inconsistency: can't create Bayes net that violates axioms of prob\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- Bayes net can be far more compact than full joint dist (sparse sys) => Local structure: linear growth in complexity\n- Specifying cond probability tables for fully connected net requires same amount of info as specifying joint dist in tabular form\n- Will get compact Bayes only if choose node ordering well\n- Stick to causal model, end up having to specify fewer #s & #s will often be easier to come up with\n- Cond independence relations: each var is cond independent of non-descendants given parents\n\t- Var cond independent of all other nodes in network, given parents, children & children's parents (given its Markov blanket)\n\t- Whether Z d-separates X & Y: whether set of nodes X is cond independent of another set Y given a third set Z\n\t\t- Consider just ancestral subgraph consisting of X, Y, Z & their ancestors\n\t\t- Add links between any unlinked pair of nodes that share common child (get moral graph)\n\t\t- Replace all directed w/ undirected links\n\t\t- If Z blocks all paths between X&Y in resulting graph, then Z d-separates X&Y ==> then X is cond independent of Y given Z\n\t\t- Otherwise, orig Bayes net doesn't require cond independence\n- Efficient Representation of Cond Dists\n\t- Even if max # of parents k is smallish, filling in CPT for node requires up to O(2^k) #s\n\t- Uncertain relationships can be characterized by noisy logical relationships\n\t\t- Noisy-OR relation (generalization of logical OR) - makes 2 assumps: all possible causes are listed & inhibition of each parent is independent of inhibition of any other parents\n\t\t- Noisy logical relationships where var depends on k parents can be described using O(k) params\n- Way to handle continuous vars: discretization (dividing into fixed set of intervals)\n- Can use standard families of pdfs (i.e. Gaussian)\n- Can use nonparametric rep to define cond dist implicitly w/ collection of instances, each containing specific vals of parent & child vars\n- Hybrid Bayes net: has both discrete & continuous => specify 2 new kinds of dists\n  - Cond dist for a continuous var given discrete or continuous parents\n    - Linear-Gaussian cond dist: child has Gaussian dist whose mean varies linearly w/ val of parent & std dev is fixed\n      - Network containing only continuous vars with linear-Gaussian dists has joint dist that's multivariate Gaussian dist over all vars\n      - Posterior dist given any evidence also has this property\n      - When discrete vars are added as parents of continuous vars, net defines cond Gaussian (CG) dist: given any assignment to discrete vars, dist over continous vars = multivariate Gaussian\n  - Cond dist for discrete var given continuous parents - like \"soft\" threshold fn (make by using integral of standard normal dist)\n    - Can use probit or expit/inverse logit models\n    - Probit often better fit to real situations\n    - Logit has longer tails & logistic fn sometimes easier to deal w/ mathematically\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- Inference by enumeration\n  - Query can be answered using Bayes net by computing sums of products of conditional probabilities from network\n    - In worst case, where we have to sum out almost all variables, there will be O(2^n) terms in sum, each a product of O(n) probability values ==> O(n2^n)\n      - Can be reduced to O(2^n) by taking advantage of nested structure of computation\n  - Enumeration-ask alg evaluates expression trees using depth-first, left-to-right recursion\n    - Similar in structure to backtracking alg for solving CSPs and DPLL alg for satisfiability\n    - Space complexity: only linear in number of variables\n    - Time complexity: O(2^n) for network with n Boolean variables\n- Variable elimination algorithm\n  - Enumeration alg can be improved substantially by eliminating repeated calculations\n  - Idea: do calculation once and save results for later use (form of dynamic programming)\n  - One version of approach: variable elimination alg which works by evaluating expressions in right-to-left order\n    - Intermediate results are stored and summations over each variable are done only for those portions of expression that depend on variable\n  - Pointwise product of two factors f and g yields new factor h whose variables are union of vars in f and g and whose elements are given by product of corresponding elements in two factors\n  - Time and space requirements of variable elimination are dominated by the size of largest factor constructed during operation of algorithm\n    - Eliminate whichever variable minimizes the size of the next factor to be constructed\n    - Every variable that is not an ancestor of a query variable or evidence variable is irrelevant to the query\n- The complexity of exact inference\n  - Complexity of exact inference in Bayes nets depends strongly on structure of the network\n  - Singly connected networks / polytrees: networks that have at most one undirected path\n    - Time and space complexity of exact inference in polytrees is linear in the size of the network (size = # of CPT entires)\n  - Multiply connected networks: variable elimination can hav eexponential time and space complexity in the worst case, even when # of parents per node is bounded\n    - Bc it includes inference in propositional logic as special case, inference in Bayes nets is NP-hard\n- Clustering algorithms\n  - Variable elimination alg is simple and efficient for answering individual queries, but if we want to compute posterior probabilities for all variables in network, it can be less efficient\n    - Example: in polytree network, need to issue O(n) queries costing O(n) each for O(n^2) time ==> can use clustering to reduce time to O(n)\n      - Basic idea: join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree\n\n\n## Module 11 Lecture Notes\n\n- Bayes net semantics: set of nodes (one per variable X), DAG, conditional distribution for each node\n- Bayes net = topology (graph) + local conditional probabilities\n- Bayes net implicitly encode joint distributions as product of local conditional distributions\n  - To see what probability a BN gives to full assignment, multiply all relevant conditionals together\n- Not every BN can represent every joint distribution\n- Only distributions whose variables are absolutely independent can be represented by a BN with no arcs\n- Size of Bayes net\n  - Size of joint distribution over N boolean variables: 2^N\n  - Size of N-node net if nodes have up to k parents: O(N * 2^(k+1))\n  - BNs: huge space savings\n  - Also easier to elicit local CPTs\n  - Also faster to answer queries\n- Causal chains: X => Y => Z\n  - One example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed\n  - Common cause: observing the cause blocks influence between effects\n  - Common effect:\n    - Are X and Y independent? Yes (still need to prove)\n    - Are X and Y independent given Z? No\n    - Backwards from other cases => observing an effect activates influence between possible causes\n- General question: in a given BN, are two variables independent (given evidence)? => Analyze graph\n  - Any complex example can be broken into repetitions of 3 canonical cases\n    - Reachability: shade evidence nodes, look for paths in resulting graph\n      - If 2 nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent\n- Active / Inactive Paths\n  - D-separation gives precise conditional independence guarantees from graph alone\n  - Are X and Y conditionally independent given evidence variables {Z}? => Yes, if X and Y \"d-separated\" by Z\n    - Consider all (undirected paths) from X to Y ==> no active paths = independence!\n  - Path is active if each triple is active:\n    - Causal chain A -> B -> C where B is unobserved (either direction)\n    - Common cause A <- B -> C where B is unobserved\n    - Common effect A -> B <- C where B or one of its descendants is observed\n  - All it takes to block a path is a single inactive segment\n- Given Bayes net structure: can run d-separation alg to build complete list of conditional independences that are necessarily true of the form [Xi independent of Xj | {Xk1,...,Xkn}]\n- Inference: calculating some useful quantity from a joint probability distribution\n- Inference by enumeration = very slow: joint up whole joint distribution before you sum out the hidden variables\n  - Advanced technique: variable elimination\n    - Interleave joining and marginalizing\n    - Still NP-hard, but usually much faster than inference by enumeration\n\n\n## Module 11 Definitions\n* **Deterministic node** - val specified exactly by vals of its parents w/ no uncertainty and relationship can be logical or numerical\n* **Context-specific independence (csi)** - conditional dist exhibits CSI if a variable is conditionally independent of some of its parents given certain values of others\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes & Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell & Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "- Any component of agent program can be improved by ML. Depends on:\n",
        "\t- Which component is to be improved\n",
        "\t- What prior knowledge the agent has (which influences the model it builds)\n",
        "\t- What data and feedback on that data is available\n",
        "- Components, each of which can be learned, include:\n",
        "\t- Direct mapping from conditions on current state to actions\n",
        "\t- Means to infer relevant properties of the world from the percept sequence\n",
        "\t- Information about the way the world evolves and about the results of possible actions the agent can take\n",
        "\t- Utility information indicating the desirability of world states\n",
        "\t- Action-value info indicating the desirability of actions\n",
        "\t- Goals that describe the most desirable states\n",
        "\t- Problem generator, critic and learning element that enable the system to improve\n",
        "- Transfer learning: knowledge from one domain is transferred to a new domain so that learning can proceed faster with less data\n",
        "- Induction: going from specific set of observations to general rule\n",
        "\t- Deductive conclusions are guaranteed to be correct of premises are correct; inductive conclusions may be incorrect\n",
        "- Three types of learning: supervised, unsupervised, reinforcement\n",
        "\"\"\"\n",
        "\n",
        "chapter19_2 = \"\"\"\n",
        "- How to choose hypothesis space: might have prior knowledge about the process that generated the data; if not, can perform EDA; otherwise can just try multiple hypothesis spaces and see what works best\n",
        "- How to choose good hypothesis from hypothesis space?\n",
        "  - Consistent hypothesis: any h such that each x in the training set has h(x) = y\n",
        "    - For continous, look for best-fit function where h(x) is close to y\n",
        "  - The function h that a learning alg discovers depends on the hypothesis space H it considers and on the training set it's given\n",
        "  - One way to analyze hypothesis space is by the bias they impose and the variance they produce\n",
        "    - Bias: tendency of a predictive hypothesis to deviate from expected value when averaged over different training sets\n",
        "      - Often results from restriction imposed by the hypothesis space\n",
        "    - Variance: amount of change in the hypothesis due to fluctuation in the training data\n",
        "  - Can choose hypothesis based on how probable it is\n",
        "- Tradeoff between expressiveness of hypothesis space and computational complexity of finding a good hypothesis within that space\n",
        "\"\"\"\n",
        "\n",
        "chapter19_3 = \"\"\"\n",
        "- Decision tree: representation of a function that maps a vector of attribute values to a single output value (a decision)\n",
        "- Can evaluate the performance of a learning alg with a learning curve\n",
        "- Entropy: measure of uncertainty of a random variable\n",
        "- Decision tree pruning combats overfitting\n",
        "  - How to detect if a node is testing an irrelevant attribute?: low information gain = good clue that attribute is irrelevant\n",
        "    - But how large a gain should be required in order to split on particular attribute?: significance test\n",
        "\t\t\t\t□ Null hypothesis is that attribute is irrelevant and that IG for infinitely large sample would be zero\n",
        "  - Chi-squared pruning (pg. 1225)\n",
        "- Problem with early stopping: stops us from recognizing situations where there is no one good attribute, but there are combinations of attributes that are informative\n",
        "- DTs are useful in handling\n",
        "  - Missing data\n",
        "  - Continuous/multivalued input attributes\n",
        "    - Split point test: inequality test on the value of an attribute for continuous values\n",
        "    - Information gain ratio: used for non-continuous attributes that do not have a meaningful ordering\n",
        "  - Continuous-valued output attribute (regression tree)\n",
        "- Pros: ease of understanding, scalability to large datasets, and versatility in handling discrete & continuous inputs as well as classification & regression\n",
        "- Cons: suboptimal accuracy, unstable, (if deep) prediction = expensive\n",
        "\"\"\"\n",
        "\n",
        "chapter19_4 = \"\"\"\n",
        "- Stationarity assumption: assumes that future examples will be like the past\n",
        "- For now: optimal fit is the hypothesis that minimizes the error rate (proportion of times that h(x) != y for an (x,y) exmaple\n",
        "- Hyperparameters: params of the model class, not of the individual model\n",
        "- Task of finding a good hypothesis as two subtasks:\n",
        "\t- Model selection chooses a good hypothesis space\n",
        "\t- Optimzation find the best hypothesis within that space\n",
        "- Model that exactly fits all the training data has interpolated the data\n",
        "\t- Models start to overfit as the capacity approaches the point of interpolation\n",
        "- Also necessary: minimize a loss function (rather than maximize a utility function)\n",
        "\t- No loss when you guess exactly right\n",
        "- Reasons why chosen hypothesis might different from true function f:\n",
        "\t- Learning problem is realizable if the hypothesis space H actually contains the true function f\n",
        "\t- Variance: learning alg will in general return different hypotheses for different sets of examples\n",
        "\t\t- If problem = realizable, variance decreases towards zero as # of training examples increase\n",
        "\t- f may be nondeterministic or noisy: may return different values of f(x) for same x\n",
        "\t- When H is a complicated function in a large hypothesis space == can be computationally intractable to systematically search all possibilities\n",
        "- 19.4.3 Regularization\n",
        "\t- Search for a hypothesis that directly minimizes the weighted sum of empirical loss and the complexity of the hypothesis\n",
        "\t- Regularization: explicitly penalizing complex hypotheses\n",
        "\t- Can simplify by reducing dimensionality (feature selection)\n",
        "- 19.4.4 Hyperparameter tuning\n",
        "\t- Hand-tuning: guess some parameter values based on past experience, train a model, measure its performance on the validation data, analyze results and use intuition to suggest new parameter values\n",
        "\t- Bayesian optimization: treats the task of choosing good hyperparamter values as a ML problem in itself\n",
        "    - Alternative: population-based training (PBT): uses random search to train (in parallel) a population of models, each with different hyperparams; then 2nd generation of models are trained but they choose hyperparams based on successful values from previous generation\n",
        "\"\"\"\n",
        "\n",
        "chapter19_5 = \"\"\"\n",
        "- Any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: must be probably approximately correct (PAC)\n",
        "- PAC learning algs: can provide bounds on performance of various learning algs\n",
        "\"\"\"\n",
        "chapter19_6 = \"\"\"\"\"\"\n",
        "\n",
        "# Speech & Language Processing Chapter 4 “Naive Bayes & Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "- NB is generative bc it states a kind of implicit assumption about how a document is generated: first a class is sampled from P(c) and then words are generated by sampling from P(d|c)\n",
        "- Make two simplifying assumptions:\n",
        "  - Bag of words assumption: position of words don't matter => only encode identity and not position\n",
        "  - NB assumption: conditional independence assumption that the probabilities P(fi|c) are independent given the class c\n",
        "- To apply NB to text: need to consider word positions by just walking an index through every word position in the document\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_2 = \"\"\"\n",
        "- Learn P(c) and P(fi|c) using maximum likelihood estimate\n",
        "  - For the class prior P(c): ask what % of documents in our training set are in each class c\n",
        "  - P(wi|c) = fraction of times the word wi appears among all words in all documents of topic c\n",
        "    - Vocab V = union of all word types in all classes, not just the words in one class c\n",
        "- NB ignores stopwords and unknown words\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_3 = \"\"\"\"\"\"\n",
        "\n",
        "slp_chapter4_4 = \"\"\"\n",
        "- For sentiment classification: whether a word occurs or not seems to matter more than its frequency\n",
        "  - Often improves performance to clip word counts in each document at 1\n",
        "    - Count will be higher if word appears in multiple documents\n",
        "  - Called binary multinomial naive Bayes or binary NB: for each doc, remove all duplicate words before concatenating them into the single big document\n",
        "- Also important: deal with negation\n",
        "  - During text normalization, prepend prefix NOT_ to every word after a token of logical negation (n't, not, no, never) until punctuation mark\n",
        "  - Newly formed words like NOT_like will occur more often in negative document and act as cues for negative sentiment while words like NOT_bored will acquire positive associations\n",
        "- If we have insufficient labeled training data, can derive positive and negative word features from sentiment lexicons:\n",
        "  - General Inquirer\n",
        "  - LIWC\n",
        "  - Opinion lexicon\n",
        "  - MPQA Subjectivity Lexicon\n",
        "- Common way to use lexicons in NB: add feature that is counted whenever a word from that lexicon occurs\n",
        "  - Might add feature called \"this word occurs in positive lexicon\" and treat all instances of words in the lexicon as counts for that one feature instead of counting each word separately\n",
        "- If we have lots of training data and if the test data matches the training data, using just two features won't work as well as using all the words\n",
        "- If training data is sparse or not representative of the test set, using dense lexicon features instead of sparse individual-word features may generalize better\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_5 = \"\"\"\n",
        "- NB doesn't require using all words in training data as features => features can express any property of the input text we want\n",
        "- Rather than using all words as individual features => predefine likely sets of words or phrases as features, combined with features that are not purely linguistic\n",
        "- For language id, most effective features are character or byte n-grams\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_6 = \"\"\"\n",
        "- NB can be viewed as a set of class-specific unigram language model in which the model for each class instantiates a unigram language model\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_7 = \"\"\"\n",
        "- Precision: measures % of items that the system detected as positive that are in fact positive\n",
        "- Recall: measures % of items actually present in the input that were correctly identified by the system\n",
        "- F-measure = ((B^2 + 1)P*R) / (PB^2 + R)\n",
        "  - When B > 1: favor recall\n",
        "  - When B < 1: favor precision\n",
        "  - When B = 1: balance precision and recall => F1 = 2PR / (P+R)\n",
        "- F-measure comes from weighted harmonic mean of precision and recall: used bc it's conservative => harmonic mean of two values is closer to the minimum of the two values than the arithmetic mean is\n",
        "- Macroaveraging: compute performance for each class and then average over the classes\n",
        "  - Better reflects the statistics of the smaller classes and so is more appropriate when performance on all the classes is equally important\n",
        "- Microaveraging: collect the decisions for all classes into a single confusion matrix and then compute precision and recall from the table\n",
        "  - Dominated by the more frequent class since the counts are pooled\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_8 = \"\"\"\"\"\"\n",
        "\n",
        "slp_chapter4_9 = \"\"\"\n",
        "- Effect size: the magnitude of difference between the score from one model and that of the other\n",
        "- To compute probability we need for p-value => usually use non-parametric tests based on sampling:\n",
        "  - Artificially create many versions of the experimental setup (i.e. having lots of test sets and measure model on all tests sets) => gives us a distribution\n",
        "  - Set a threshold and see if this distribution that 99% or more of the measures are smaller than the delta we observed\n",
        "  - If we see that our measure is greater than 99% of the measures we see => reject null hypothesis\n",
        "- Two common non-parametric tests used in NLP: approximate randomization & bootstrap test\n",
        "- Paired tests: compare two sets of observations that are aligned: each observation in one set can be paired with an observation in another\n",
        "- Bootstrap samples can create many virtual test sets from an observed test set by repeatedly sampling from it\n",
        "  - Only makes assumption that sample is representative of the population\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_10 = \"\"\"\n",
        "- Representational harms: harms caused by a system that demeans a social group\n",
        "- Toxicity detection: task of detecting hate speech, abuse, harassment, or other kinds of toxic language\n",
        "- Model card for each version of a model that documents a ML model with info like:\n",
        "  - Training algs and params\n",
        "  - Training data sources, motivation and preprocessing\n",
        "  - Evaluation data sources, motivation and preprocessing\n",
        "  - Intended use and users\n",
        "  - Model performance across different demographic or other groups and environmental situations\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "- Model-based classification:\n",
        "  - Build a model where both the label and features are RVs\n",
        "  - Instantiate any observed features\n",
        "  - Query for the distribution of the label conditioned on the features\n",
        "- Challenges:\n",
        "  - What structure should the Bayes net have?\n",
        "  - How should we learn its parameters?\n",
        "- General NB model: only have to specify how each feature depends on the class\n",
        "  - Total # of params is linear in # of features\n",
        "  - Model is very simplistic, but often works anyway\n",
        "- Inference for NB: goal is to compute posterior distribution over label variable Y\n",
        "  - Get joint probability of label and evidence for each label\n",
        "  - Sum to get probability of evidence\n",
        "  - Normalize by dividing step 1 by step 2\n",
        "- Parameter estimation: estimating the distribution of a RV\n",
        "  - Elicitation: ask a human (hard)\n",
        "  - Empirically: use training data (learning!)\n",
        "    - Relative frequencies are maximum likelihood estimates = count(x) / total samples\n",
        "- Laplace smoothing: k=strength of prior\n",
        "- Confidence of a probabilistic classifier: posterior over the top label => confidenc(x) = max[P(y|x)]\n",
        "  - Represents how sure the classifier is of the classification\n",
        "  - Any probabilistic model will have confidences\n",
        "  - No guarantee confidence is correct\n",
        "- Calibration\n",
        "  - Weak calibration: higher confidences mean higher accuracy\n",
        "  - Strong calibration: confidence predicts accuracy rate\n",
        "- Multiclass decision rule\n",
        "  - Weight vector for each class: wy\n",
        "  - Score (activation) of a class y: wy * f(x)\n",
        "  - Prediction highest score wins: y = argmax{y}[wy * f(x)]\n",
        "    - If correct: no change!\n",
        "    - If wrong: lower score of wrong answer, raise score of right answer\n",
        "- Properties of perceptrons\n",
        "  - Separability: true if some params get the training set perfectly correct\n",
        "  - Convergence: if the training is separable, perceptron will eventually converge (binary case)\n",
        "  - Mistake bound: the max # of mistakes (binary case) related to the margin or degree of separability [mistakes < (k / delta^2)]\n",
        "- Problems with perceptrons\n",
        "  - Noise: if data isn't separable, weights might thrash (averaging weight vectors over time can help, i.e. averaged perceptron)\n",
        "  - Mediocre generalization: finds a \"barely\" separating solution\n",
        "  - Overtraining: test/held-out accuracy usually rises, then falls\n",
        "- Fixing the perceptron: adjust weight update to mitigate these effects\n",
        "  - MIRA: Margin Infused Relaxed Algorithm\n",
        "  - MIRA*: choose an update size that fixes the current mistake but minimizes the change to w\n",
        "- Comparison\n",
        "  - NB\n",
        "    - Builds a model training data\n",
        "    - Gives prediction probabilities\n",
        "    - Strong assumptions about feature independence\n",
        "    - One pass through data (counting)\n",
        "  - Perceptrons / MIRA\n",
        "    - Makes less assumptions about data\n",
        "    - Mistake-driven learning\n",
        "    - Multiple passes through data (prediction)\n",
        "    - Often more accurate\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"bag-of-words\" : \"the frequency of each word in an unordered set of words, ignoring position\",\n",
        "\"sentiment lexicon\": \"list of words pre-annotated with positive or negative sentiment\",\n",
        "\"language ID\": \"a task in determining what language a text is written in\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 5264
        },
        "cellView": "form",
        "outputId": "9ea77d2e-cbc2-4bf8-a795-1a481a78b13e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 The Theory of Learning\", chapter19_5),\n",
        "  # (\"AIMA Chapter 19.6 Linear Regression and Classification\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets & 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 & Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes & Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n\n- Any component of agent program can be improved by ML. Depends on:\n\t- Which component is to be improved\n\t- What prior knowledge the agent has (which influences the model it builds)\n\t- What data and feedback on that data is available\n- Components, each of which can be learned, include:\n\t- Direct mapping from conditions on current state to actions\n\t- Means to infer relevant properties of the world from the percept sequence\n\t- Information about the way the world evolves and about the results of possible actions the agent can take\n\t- Utility information indicating the desirability of world states\n\t- Action-value info indicating the desirability of actions\n\t- Goals that describe the most desirable states\n\t- Problem generator, critic and learning element that enable the system to improve\n- Transfer learning: knowledge from one domain is transferred to a new domain so that learning can proceed faster with less data\n- Induction: going from specific set of observations to general rule\n\t- Deductive conclusions are guaranteed to be correct of premises are correct; inductive conclusions may be incorrect\n- Three types of learning: supervised, unsupervised, reinforcement\n\n\n## AIMA Chapter 19.2 Supervised Learning\n\n- How to choose hypothesis space: might have prior knowledge about the process that generated the data; if not, can perform EDA; otherwise can just try multiple hypothesis spaces and see what works best\n- How to choose good hypothesis from hypothesis space?\n  - Consistent hypothesis: any h such that each x in the training set has h(x) = y\n    - For continous, look for best-fit function where h(x) is close to y\n  - The function h that a learning alg discovers depends on the hypothesis space H it considers and on the training set it's given\n  - One way to analyze hypothesis space is by the bias they impose and the variance they produce\n    - Bias: tendency of a predictive hypothesis to deviate from expected value when averaged over different training sets\n      - Often results from restriction imposed by the hypothesis space\n    - Variance: amount of change in the hypothesis due to fluctuation in the training data\n  - Can choose hypothesis based on how probable it is\n- Tradeoff between expressiveness of hypothesis space and computational complexity of finding a good hypothesis within that space\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n\n- Decision tree: representation of a function that maps a vector of attribute values to a single output value (a decision)\n- Can evaluate the performance of a learning alg with a learning curve\n- Entropy: measure of uncertainty of a random variable\n- Decision tree pruning combats overfitting\n  - How to detect if a node is testing an irrelevant attribute?: low information gain = good clue that attribute is irrelevant\n    - But how large a gain should be required in order to split on particular attribute?: significance test\n\t\t\t\t□ Null hypothesis is that attribute is irrelevant and that IG for infinitely large sample would be zero\n  - Chi-squared pruning (pg. 1225)\n- Problem with early stopping: stops us from recognizing situations where there is no one good attribute, but there are combinations of attributes that are informative\n- DTs are useful in handling\n  - Missing data\n  - Continuous/multivalued input attributes\n    - Split point test: inequality test on the value of an attribute for continuous values\n    - Information gain ratio: used for non-continuous attributes that do not have a meaningful ordering\n  - Continuous-valued output attribute (regression tree)\n- Pros: ease of understanding, scalability to large datasets, and versatility in handling discrete & continuous inputs as well as classification & regression\n- Cons: suboptimal accuracy, unstable, (if deep) prediction = expensive\n\n\n## AIMA Chapter 19.4 Model Selection and Optimization\n\n- Stationarity assumption: assumes that future examples will be like the past\n- For now: optimal fit is the hypothesis that minimizes the error rate (proportion of times that h(x) != y for an (x,y) exmaple\n- Hyperparameters: params of the model class, not of the individual model\n- Task of finding a good hypothesis as two subtasks:\n\t- Model selection chooses a good hypothesis space\n\t- Optimzation find the best hypothesis within that space\n- Model that exactly fits all the training data has interpolated the data\n\t- Models start to overfit as the capacity approaches the point of interpolation\n- Also necessary: minimize a loss function (rather than maximize a utility function)\n\t- No loss when you guess exactly right\n- Reasons why chosen hypothesis might different from true function f:\n\t- Learning problem is realizable if the hypothesis space H actually contains the true function f\n\t- Variance: learning alg will in general return different hypotheses for different sets of examples\n\t\t- If problem = realizable, variance decreases towards zero as # of training examples increase\n\t- f may be nondeterministic or noisy: may return different values of f(x) for same x\n\t- When H is a complicated function in a large hypothesis space == can be computationally intractable to systematically search all possibilities\n- 19.4.3 Regularization\n\t- Search for a hypothesis that directly minimizes the weighted sum of empirical loss and the complexity of the hypothesis\n\t- Regularization: explicitly penalizing complex hypotheses\n\t- Can simplify by reducing dimensionality (feature selection)\n- 19.4.4 Hyperparameter tuning\n\t- Hand-tuning: guess some parameter values based on past experience, train a model, measure its performance on the validation data, analyze results and use intuition to suggest new parameter values\n\t- Bayesian optimization: treats the task of choosing good hyperparamter values as a ML problem in itself\n    - Alternative: population-based training (PBT): uses random search to train (in parallel) a population of models, each with different hyperparams; then 2nd generation of models are trained but they choose hyperparams based on successful values from previous generation\n\n\n## AIMA Chapter 19.5 The Theory of Learning\n\n- Any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: must be probably approximately correct (PAC)\n- PAC learning algs: can provide bounds on performance of various learning algs\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n- NB is generative bc it states a kind of implicit assumption about how a document is generated: first a class is sampled from P(c) and then words are generated by sampling from P(d|c)\n- Make two simplifying assumptions:\n  - Bag of words assumption: position of words don't matter => only encode identity and not position\n  - NB assumption: conditional independence assumption that the probabilities P(fi|c) are independent given the class c\n- To apply NB to text: need to consider word positions by just walking an index through every word position in the document\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n- Learn P(c) and P(fi|c) using maximum likelihood estimate\n  - For the class prior P(c): ask what % of documents in our training set are in each class c\n  - P(wi|c) = fraction of times the word wi appears among all words in all documents of topic c\n    - Vocab V = union of all word types in all classes, not just the words in one class c\n- NB ignores stopwords and unknown words\n\n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n- For sentiment classification: whether a word occurs or not seems to matter more than its frequency\n  - Often improves performance to clip word counts in each document at 1\n    - Count will be higher if word appears in multiple documents\n  - Called binary multinomial naive Bayes or binary NB: for each doc, remove all duplicate words before concatenating them into the single big document\n- Also important: deal with negation\n  - During text normalization, prepend prefix NOT_ to every word after a token of logical negation (n't, not, no, never) until punctuation mark\n  - Newly formed words like NOT_like will occur more often in negative document and act as cues for negative sentiment while words like NOT_bored will acquire positive associations\n- If we have insufficient labeled training data, can derive positive and negative word features from sentiment lexicons:\n  - General Inquirer\n  - LIWC\n  - Opinion lexicon\n  - MPQA Subjectivity Lexicon\n- Common way to use lexicons in NB: add feature that is counted whenever a word from that lexicon occurs\n  - Might add feature called \"this word occurs in positive lexicon\" and treat all instances of words in the lexicon as counts for that one feature instead of counting each word separately\n- If we have lots of training data and if the test data matches the training data, using just two features won't work as well as using all the words\n- If training data is sparse or not representative of the test set, using dense lexicon features instead of sparse individual-word features may generalize better\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n- NB doesn't require using all words in training data as features => features can express any property of the input text we want\n- Rather than using all words as individual features => predefine likely sets of words or phrases as features, combined with features that are not purely linguistic\n- For language id, most effective features are character or byte n-grams\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n- NB can be viewed as a set of class-specific unigram language model in which the model for each class instantiates a unigram language model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n- Precision: measures % of items that the system detected as positive that are in fact positive\n- Recall: measures % of items actually present in the input that were correctly identified by the system\n- F-measure = ((B^2 + 1)P*R) / (PB^2 + R)\n  - When B > 1: favor recall\n  - When B < 1: favor precision\n  - When B = 1: balance precision and recall => F1 = 2PR / (P+R)\n- F-measure comes from weighted harmonic mean of precision and recall: used bc it's conservative => harmonic mean of two values is closer to the minimum of the two values than the arithmetic mean is\n- Macroaveraging: compute performance for each class and then average over the classes\n  - Better reflects the statistics of the smaller classes and so is more appropriate when performance on all the classes is equally important\n- Microaveraging: collect the decisions for all classes into a single confusion matrix and then compute precision and recall from the table\n  - Dominated by the more frequent class since the counts are pooled\n\n\n## SLP Chapter 4.8 Test sets & Cross-validation\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n- Effect size: the magnitude of difference between the score from one model and that of the other\n- To compute probability we need for p-value => usually use non-parametric tests based on sampling:\n  - Artificially create many versions of the experimental setup (i.e. having lots of test sets and measure model on all tests sets) => gives us a distribution\n  - Set a threshold and see if this distribution that 99% or more of the measures are smaller than the delta we observed\n  - If we see that our measure is greater than 99% of the measures we see => reject null hypothesis\n- Two common non-parametric tests used in NLP: approximate randomization & bootstrap test\n- Paired tests: compare two sets of observations that are aligned: each observation in one set can be paired with an observation in another\n- Bootstrap samples can create many virtual test sets from an observed test set by repeatedly sampling from it\n  - Only makes assumption that sample is representative of the population\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n- Representational harms: harms caused by a system that demeans a social group\n- Toxicity detection: task of detecting hate speech, abuse, harassment, or other kinds of toxic language\n- Model card for each version of a model that documents a ML model with info like:\n  - Training algs and params\n  - Training data sources, motivation and preprocessing\n  - Evaluation data sources, motivation and preprocessing\n  - Intended use and users\n  - Model performance across different demographic or other groups and environmental situations\n\n\n## Module 12 Lecture Notes\n\n- Model-based classification:\n  - Build a model where both the label and features are RVs\n  - Instantiate any observed features\n  - Query for the distribution of the label conditioned on the features\n- Challenges:\n  - What structure should the Bayes net have?\n  - How should we learn its parameters?\n- General NB model: only have to specify how each feature depends on the class\n  - Total # of params is linear in # of features\n  - Model is very simplistic, but often works anyway\n- Inference for NB: goal is to compute posterior distribution over label variable Y\n  - Get joint probability of label and evidence for each label\n  - Sum to get probability of evidence\n  - Normalize by dividing step 1 by step 2\n- Parameter estimation: estimating the distribution of a RV\n  - Elicitation: ask a human (hard)\n  - Empirically: use training data (learning!)\n    - Relative frequencies are maximum likelihood estimates = count(x) / total samples\n- Laplace smoothing: k=strength of prior\n- Confidence of a probabilistic classifier: posterior over the top label => confidenc(x) = max[P(y|x)]\n  - Represents how sure the classifier is of the classification\n  - Any probabilistic model will have confidences\n  - No guarantee confidence is correct\n- Calibration\n  - Weak calibration: higher confidences mean higher accuracy\n  - Strong calibration: confidence predicts accuracy rate\n- Multiclass decision rule\n  - Weight vector for each class: wy\n  - Score (activation) of a class y: wy * f(x)\n  - Prediction highest score wins: y = argmax{y}[wy * f(x)]\n    - If correct: no change!\n    - If wrong: lower score of wrong answer, raise score of right answer\n- Properties of perceptrons\n  - Separability: true if some params get the training set perfectly correct\n  - Convergence: if the training is separable, perceptron will eventually converge (binary case)\n  - Mistake bound: the max # of mistakes (binary case) related to the margin or degree of separability [mistakes < (k / delta^2)]\n- Problems with perceptrons\n  - Noise: if data isn't separable, weights might thrash (averaging weight vectors over time can help, i.e. averaged perceptron)\n  - Mediocre generalization: finds a \"barely\" separating solution\n  - Overtraining: test/held-out accuracy usually rises, then falls\n- Fixing the perceptron: adjust weight update to mitigate these effects\n  - MIRA: Margin Infused Relaxed Algorithm\n  - MIRA*: choose an update size that fixes the current mistake but minimizes the change to w\n- Comparison\n  - NB\n    - Builds a model training data\n    - Gives prediction probabilities\n    - Strong assumptions about feature independence\n    - One pass through data (counting)\n  - Perceptrons / MIRA\n    - Makes less assumptions about data\n    - Mistake-driven learning\n    - Multiple passes through data (prediction)\n    - Often more accurate\n\n\n## Module 12 Definitions\n* **Bag-of-words** - the frequency of each word in an unordered set of words, ignoring position\n* **Sentiment lexicon** - list of words pre-annotated with positive or negative sentiment\n* **Language id** - a task in determining what language a text is written in\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky & Martin, Speech & Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"\n",
        "- LR learns from a training set a vector of weights and a bias term\n",
        "  - Each weight represents how important that input feature is to the classification decision\n",
        "- To create a probability, we'll pass z=w*x + b through sigmoid function\n",
        "- To classify, 0.5 is the decision boundary\n",
        "- Designing features usually done by examining the training set with an eye to linguistic intuitions and linguistic literature on the domain\n",
        "- Large number of features are usually created automatically via feature templates (abstract specifications of features)\n",
        "- Representation learning: ways to learn features automatically in an unsupervised way from the input\n",
        "- LR vs NB: LR is more robust to correlated features; generally works better on larger documents\n",
        "  - NB has overly strong conditional independence assumptions, but can work very well on small datasets or small documents; also easy to implement and very fast to train\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_2 = \"\"\"\n",
        "- Want to learn parameters (meaning w and b) that make y_hat for each training observation as close as possible to the true y\n",
        "- Metric for how far current label is from true gold label: loss / cost function\n",
        "- Need optimization algorithm for iteratively updating the weights in order to minimize loss function: (stochastic) gradient descent\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_3 = \"\"\"\n",
        "- Conditional maximum likelihood estimation: choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x\n",
        "\t- Learn weights that maximize probability of correct label p(y|x)\n",
        "- Negative log of this probability = convenient loss metric since it goes from 0 to infinity\n",
        "- Loss function also ensures that as the probability of the correct answer is maximized, probability of incorrect answer is also minimized\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_4 = \"\"\"\n",
        "- Goal: find set of weights which minimizes the loss function, averaged over all examples\n",
        "- Gradient descent: method that finds a minimum of a function by figuring out in which direction the function's slope is rising the most steeply and moving in the opposite direction\n",
        "- For LR: loss function = convex -- GD guaranteed to find a minimum\n",
        "- Gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function\n",
        "- Magnitude of the amount to move in GD = value of slope weighted by a learning rate\n",
        "- Gradient expresses directional components of the sharpest slope along each of N dimensions\n",
        "\t- Slope = partial derivative of the loss function\n",
        "- SGD: online alg that minimizes loss function by computing its gradient after each training example\n",
        "\t- Learning rate needs to be adjusted: if too high, learner will take steps that are too large; if too low, it'll take too long to get to minimum\n",
        "- Batch training: computer gradient over entire dataset\n",
        "- Mini-batch training: train a group of m examples that is less than the whole dataset\n",
        "- Allows us to process all examples in one mini-batch in parallel and then accumulate the loss\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_5 = \"\"\"\n",
        "- If a feature is perfectly predictive of outcome bc it happens to only occur in one class == assigned very high weight\n",
        "- To avoid, add regularization to objective function which will penalize large weights\n",
        "\t- L2: quadratic function of weight values == same as Euclidean distance of vector from origin\n",
        "\t\t- Easier to optimize bc of simple derivative\n",
        "\t\t- Prefers weight vectors with many small weights\n",
        "\t- L1: linear function of weight values == sum of absolute values of the weights (Manhattan distance)\n",
        "    - Prefers sparse solutions with some larger weights but many more weights set to zero\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_6 = \"\"\"\n",
        "- Generalization of sigmoid = softmax function p(y= c|x)\n",
        "- Like sigmoid, but now need separate weight vectors (and bias) for each of K classes\n",
        "- Each feature can be evidence for or against each individual class\n",
        "- One-hot vector: one value=1 and the rest=0\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky & Martin, Chapter 7 “Neural Networks & Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\n",
        "- Building block of NN: single computational unit (weighted sum of its inputs and a bias term)\n",
        "- Neural units apply a non-linear function f to z (z=w*x+b)\n",
        "\t- Output of this function = activation value for the unit\n",
        "- Tanh: variant of sigmoid that ranges from -1 to +1\n",
        "\t- Pros: Smoothly differentiable and mapping outlier values toward the mean\n",
        "\t- Cons: zero derivatives = vanishing gradient problem (also for sigmoid)\n",
        "- ReLU: same as x when x is positive, otherwise 0\n",
        "  - Pros: very close to linear\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_2 = \"\"\"\n",
        "- Perceptron: simple neural unit that has a binary output and doesn't have a non-linear activation function\n",
        "- XOR: not linearly separable\n",
        "- Cannot be calculated by single perceptron, but can be calculated by layered network of units\n",
        "- Weights for NNs are learned automatically using the error backpropagation alg (hidden layers will learn to form useful representations\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_3 = \"\"\"\n",
        "- FFN: multilayer network in which the units are connected with no cycles; outputs from units in each layer are passed to units in the next higher layer and no outputs are passed back to lower layers (those with cycles = RNNs)\n",
        "- Sometimes called multi-layer perceptrons (MLPs) but is a misnomer since units in multilayer networks aren't perceptrons which are purely linear\n",
        "- Three kinds of nodes:\n",
        "\t- Input units: scalar values\n",
        "\t\t- Input lyaer = layer 0\n",
        "\t- Hidden units: neural unit, taking a weighted sum of its inputs and then applying a non-linearity\n",
        "\t\t- Standard architecture: each layer is fully-connected - each unit in each layer takes as input the outputs from all the units in previous layer and there is a link between every pair of units from two adjacent layers\n",
        "\t\t- Each hidden unit sums over all input units\n",
        "\t\t- Advantage of using single matrix W for the weights of the entire layer is that now the hidden layer computation for a FFN can be done very efficiently with simple matrix operations\n",
        "\t\t\t- Computation only has 3 steps: multiplying the weight matrix by the input vector x, adding the bias vector b, and applying the activation function g\n",
        "\t\t- Forms a representation of the input == output layer takes this representation and computes a final output\n",
        "\t- Output units\n",
        "\t\t- Use softmax to get output of classifier\n",
        "- When counting layers, don't count input layer but do count output\n",
        "- Activation functions are generally different at the final layer\n",
        "- Replacing the bias unit\n",
        "  - Add a dummy node to each layer whose value will always be 1: still has an associated weight and that weight represents the bias value b\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_4 = \"\"\"\n",
        "- How do we partial out the loss over all intermediate layers?: backpropagation\n",
        "- If NN is being used as binary classifier with sigmoid at final layer == loss function is exactly the same as we saw with logistic regression\n",
        "- Backprop makes use of chain rule\n",
        "- Optimization in NN is a non-convex optimization problem\n",
        "- Need to initialize the weights with small random numbers\n",
        "- Helpful to normalize the input values\n",
        "- To help with overfitting: dropout, tuning of hyperparams (i.e. learning rate, mini-batch size, model architecture)\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_5 = \"\"\"\n",
        "- NN language models are strikingly slower to train than traditional language models\n",
        "- Prior context is represented by embeddings of previous words == allows neural language models to generalize to unseen data much better than n-gram language models\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_6 = \"\"\"\"\"\"\n",
        "slp_chapter7_7 = \"\"\"\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "- Machine learning classifiers require a training corpus of M observations input/output pairs (xi,yi)\n",
        "  - Feature representation of input: vector of features [x1,x2,...,xn]\n",
        "  - Classification function: computes the estimated class y_hat via p(y|x)\n",
        "  - Objective function: used for learning, usually involving minimizing error on training examples\n",
        "  - Algorithm for optimizing the objective function\n",
        "- Learning in logistic regression\n",
        "  - Must learn weights & bias via learning => 2 components\n",
        "    - Objective / loss fn: tells us distance between the system output and the gold output (will use cross-entropy loss)\n",
        "    - Alg for optimizing objective fn: SGD to minimize loss fn\n",
        "- Conditional maximum likelihood estimation: choose params w,b that maximize the (log) probabilities of the true labels in the training data\n",
        "  - Resulting loss function = negative log likelihood loss => cross entropy loss\n",
        "  - p(y|x) = y_hat^y * (1-y_hat)^(1-y)\n",
        "    - Change to logs: y*log(y_hat) + (1-y)*log(1-y_hat)\n",
        "      - Negative of this: cross-entropy loss\n",
        "- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the params theta) the fn's slope is rising the most steeply and moving in the opposite direction\n",
        "- FFN\n",
        "  - Multiply weight matrix by input vector x\n",
        "  - Add bias vector b\n",
        "  - Apply activation fn g (such as sigmoid)\n",
        "- Equations\n",
        "  - h = sig(Wx + b)\n",
        "  - z = U*h\n",
        "  - y = softmax(z)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {    \n",
        "}\n"
      ],
      "execution_count": 21,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3027
        },
        "cellView": "form",
        "outputId": "d6ffefbd-64f6-41a7-bc45-799fae5c1083"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  # (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  # (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n- LR learns from a training set a vector of weights and a bias term\n  - Each weight represents how important that input feature is to the classification decision\n- To create a probability, we'll pass z=w*x + b through sigmoid function\n- To classify, 0.5 is the decision boundary\n- Designing features usually done by examining the training set with an eye to linguistic intuitions and linguistic literature on the domain\n- Large number of features are usually created automatically via feature templates (abstract specifications of features)\n- Representation learning: ways to learn features automatically in an unsupervised way from the input\n- LR vs NB: LR is more robust to correlated features; generally works better on larger documents\n  - NB has overly strong conditional independence assumptions, but can work very well on small datasets or small documents; also easy to implement and very fast to train\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n- Want to learn parameters (meaning w and b) that make y_hat for each training observation as close as possible to the true y\n- Metric for how far current label is from true gold label: loss / cost function\n- Need optimization algorithm for iteratively updating the weights in order to minimize loss function: (stochastic) gradient descent\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n- Conditional maximum likelihood estimation: choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x\n\t- Learn weights that maximize probability of correct label p(y|x)\n- Negative log of this probability = convenient loss metric since it goes from 0 to infinity\n- Loss function also ensures that as the probability of the correct answer is maximized, probability of incorrect answer is also minimized\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n- Goal: find set of weights which minimizes the loss function, averaged over all examples\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction the function's slope is rising the most steeply and moving in the opposite direction\n- For LR: loss function = convex -- GD guaranteed to find a minimum\n- Gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function\n- Magnitude of the amount to move in GD = value of slope weighted by a learning rate\n- Gradient expresses directional components of the sharpest slope along each of N dimensions\n\t- Slope = partial derivative of the loss function\n- SGD: online alg that minimizes loss function by computing its gradient after each training example\n\t- Learning rate needs to be adjusted: if too high, learner will take steps that are too large; if too low, it'll take too long to get to minimum\n- Batch training: computer gradient over entire dataset\n- Mini-batch training: train a group of m examples that is less than the whole dataset\n- Allows us to process all examples in one mini-batch in parallel and then accumulate the loss\n\n\n## SLP Chapter 5.5 Regularization\n\n- If a feature is perfectly predictive of outcome bc it happens to only occur in one class == assigned very high weight\n- To avoid, add regularization to objective function which will penalize large weights\n\t- L2: quadratic function of weight values == same as Euclidean distance of vector from origin\n\t\t- Easier to optimize bc of simple derivative\n\t\t- Prefers weight vectors with many small weights\n\t- L1: linear function of weight values == sum of absolute values of the weights (Manhattan distance)\n    - Prefers sparse solutions with some larger weights but many more weights set to zero\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n- Generalization of sigmoid = softmax function p(y= c|x)\n- Like sigmoid, but now need separate weight vectors (and bias) for each of K classes\n- Each feature can be evidence for or against each individual class\n- One-hot vector: one value=1 and the rest=0\n\n\n## SLP Chapter 7.1 Units\n\n- Building block of NN: single computational unit (weighted sum of its inputs and a bias term)\n- Neural units apply a non-linear function f to z (z=w*x+b)\n\t- Output of this function = activation value for the unit\n- Tanh: variant of sigmoid that ranges from -1 to +1\n\t- Pros: Smoothly differentiable and mapping outlier values toward the mean\n\t- Cons: zero derivatives = vanishing gradient problem (also for sigmoid)\n- ReLU: same as x when x is positive, otherwise 0\n  - Pros: very close to linear\n\n\n## SLP Chapter 7.2 The XOR problem\n\n- Perceptron: simple neural unit that has a binary output and doesn't have a non-linear activation function\n- XOR: not linearly separable\n- Cannot be calculated by single perceptron, but can be calculated by layered network of units\n- Weights for NNs are learned automatically using the error backpropagation alg (hidden layers will learn to form useful representations\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n- FFN: multilayer network in which the units are connected with no cycles; outputs from units in each layer are passed to units in the next higher layer and no outputs are passed back to lower layers (those with cycles = RNNs)\n- Sometimes called multi-layer perceptrons (MLPs) but is a misnomer since units in multilayer networks aren't perceptrons which are purely linear\n- Three kinds of nodes:\n\t- Input units: scalar values\n\t\t- Input lyaer = layer 0\n\t- Hidden units: neural unit, taking a weighted sum of its inputs and then applying a non-linearity\n\t\t- Standard architecture: each layer is fully-connected - each unit in each layer takes as input the outputs from all the units in previous layer and there is a link between every pair of units from two adjacent layers\n\t\t- Each hidden unit sums over all input units\n\t\t- Advantage of using single matrix W for the weights of the entire layer is that now the hidden layer computation for a FFN can be done very efficiently with simple matrix operations\n\t\t\t- Computation only has 3 steps: multiplying the weight matrix by the input vector x, adding the bias vector b, and applying the activation function g\n\t\t- Forms a representation of the input == output layer takes this representation and computes a final output\n\t- Output units\n\t\t- Use softmax to get output of classifier\n- When counting layers, don't count input layer but do count output\n- Activation functions are generally different at the final layer\n- Replacing the bias unit\n  - Add a dummy node to each layer whose value will always be 1: still has an associated weight and that weight represents the bias value b\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n- How do we partial out the loss over all intermediate layers?: backpropagation\n- If NN is being used as binary classifier with sigmoid at final layer == loss function is exactly the same as we saw with logistic regression\n- Backprop makes use of chain rule\n- Optimization in NN is a non-convex optimization problem\n- Need to initialize the weights with small random numbers\n- Helpful to normalize the input values\n- To help with overfitting: dropout, tuning of hyperparams (i.e. learning rate, mini-batch size, model architecture)\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n- NN language models are strikingly slower to train than traditional language models\n- Prior context is represented by embeddings of previous words == allows neural language models to generalize to unseen data much better than n-gram language models\n\n\n## Module 13 Lecture Notes\n\n- Machine learning classifiers require a training corpus of M observations input/output pairs (xi,yi)\n  - Feature representation of input: vector of features [x1,x2,...,xn]\n  - Classification function: computes the estimated class y_hat via p(y|x)\n  - Objective function: used for learning, usually involving minimizing error on training examples\n  - Algorithm for optimizing the objective function\n- Learning in logistic regression\n  - Must learn weights & bias via learning => 2 components\n    - Objective / loss fn: tells us distance between the system output and the gold output (will use cross-entropy loss)\n    - Alg for optimizing objective fn: SGD to minimize loss fn\n- Conditional maximum likelihood estimation: choose params w,b that maximize the (log) probabilities of the true labels in the training data\n  - Resulting loss function = negative log likelihood loss => cross entropy loss\n  - p(y|x) = y_hat^y * (1-y_hat)^(1-y)\n    - Change to logs: y*log(y_hat) + (1-y)*log(1-y_hat)\n      - Negative of this: cross-entropy loss\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the params theta) the fn's slope is rising the most steeply and moving in the opposite direction\n- FFN\n  - Multiply weight matrix by input vector x\n  - Add bias vector b\n  - Apply activation fn g (such as sigmoid)\n- Equations\n  - h = sig(Wx + b)\n  - z = U*h\n  - y = softmax(z)\n\n\n## Module 13 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky & Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\"\n",
        "- Language models give us the ability to assign a conditional probability to every possible next word, giving us a distribution over the entire vocabulary\n",
        "- Evaluate language models by examining how well they predict unseen text ==> good models are those that assign higher probabilities to unseen data (are less surprised when encountering the new words)\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter9_2 = \"\"\"\n",
        "- RNN is any network that contains a cycle within its network connections (can be dependent on its own earlier outputs as an input)\n",
        "- Key difference from FFN lies in recurrent link that augments the input to the computation at the hidden layer with the value of the hidden layer from the preceding point in time\n",
        "- Hidden layer from previous time step provides a form of memory (context) that encodes earlier processing and informs the decisions to be made at later points in time\n",
        "\t- This approach does not impose a fixed-length limit on this prior context; the context embodied in the previous hidden layer can include information extending back to the beginning of the sequence\n",
        "- Most significant change between FFN and RNN is in new set of weights that connect the hidden layer from the previous time step to the current hidden layer\n",
        "- Have 3 sets of weights to update -- weights from the:\n",
        "\t- input layer to the hidden layer (W)\n",
        "\t- previous hidden layer to the current hidden layer (U)\n",
        "\t- hidden layer to output layer (V)\n",
        "- Two considerations we didn't have to worry about with backprop in FFN:\n",
        "\t- To compute loss function for output at time t, we need the hidden layer from time t-1\n",
        "\t- The hidden layer at time t influences both the output at time t and the hidden layer at time t+1\n",
        "- To assess the error accruing to ht, we'll need to know it\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter9_3 = \"\"\"\n",
        "- Teacher forcing: always give the model the correct history sequence to predict the next word, rather than feeding the model its best case from the previous time step\n",
        "- Weight typing: method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers (redundancy in that the input word embedding matrix and final layer matrix are very similar => E=V)\n",
        "\t- Set dimensionality of final hidden layer to be the same as size of hidden layer and use the same matrix for both layers\n",
        "  - Provides improved perplexity results and also significantly reduces the # of params required for the model\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky & Martin, Chapter 6 “Vector Semantics & Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\"\n",
        "- A model of word meaning should allow us to draw inferences to address meaning-related tasks like question-answering or dialogue\n",
        "- Lemma = citation form\n",
        "  - Infinitive form = lemma for verb\n",
        "  - Wordforms: like sung, carpets, sing or duermes\n",
        "  - Each lemma can have multiple meanings (i.e. mouse = animal or controller? == called a word sense)\n",
        "    - Multiple word senses = polysemous\n",
        "- Word sense disambiguation: task of determining which sense of a word is being used in a particular context\n",
        "- Same propositional meaning if can swap out to synonymous words with no change in truth conditions\n",
        "- Principle of contrast: states that a difference in linguistic form is always associated with some difference in meaning\n",
        "- Knowing how similar two words are can help in computing how similar the meaning of two phrases or sentences are\n",
        "- Instead of similarity, can also use word relatedness (i.e. coffee and cup = associated by co-participating in an everyday event)\n",
        "- Semantic frame: set of words that denote perspectives or participants in a particular type of event (event can be encoded lexically)\n",
        "- Connotation: aspects of a word's meaning that are related to a writer or reader's emotions, sentiment, opinions or evaluations\n",
        "- Sentiment: positive or negative evaluation language\n",
        "- Words vary along three important dimensions of affective meaning:\n",
        "  - Valence: pleasantness of the stimulus\n",
        "  - Arousal: intensity of emotion provoked by the stimulus\n",
        "  - Dominance: degree of control exerted by the stimulus\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_2 = \"\"\"\n",
        "- Define meaning of a word by its distribution in language use, meaning its neighboring words or grammatical env\n",
        "- Two words that occur in very similar distributions (whose neighboring words are similar) have similar meanings\n",
        "- Idea of vector semantics is to represent a word as a point in a multidimensional semantic space that's derived from the distributions of word neighbors\n",
        "- Word embeddings: use \"embeddings\" in mathematical sense as a mapping from one space or structure to another\n",
        "- By representing words as embeddings, classifiers can assign sentiment as long as it sees some words with similar meanings\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_3 = \"\"\"\n",
        "- Vector or distributional models of meaning are generally based on a co-occurrence matrix (way of representing how often words co-occur)\n",
        "- In a term-document matrix: each row represents a word in the vocabulary and each column represents a document from some collection of documents\n",
        "  - Each cell represents the # of times a particular word occurs in a particular document\n",
        "  - First defined as part of the vector space model of information retrieval: a document is represented as a count vector\n",
        "  - Originally defined as means of finding similar documents for the task of document information retrieval: docs that are similar will tend to have similar words (thus, column vectors will be similar)\n",
        "  - Has V rows (one for each word type in vocab) and D columns (one for each document in collection)\n",
        "- Information retrieval (IR): task of finding the document d from the D documents in some collection that best matches a query q (query also represented by vector of length V)\n",
        "- Vector semantics can also be used to represent the meaning of words: associate row vector rather than column vector\n",
        "  - Similar words have similar vectors bc they tend to occur in similar documents\n",
        "- Term-term matrix (or word-word or term-context): columns are labeled by words rather than documents (VxV dimensionality)\n",
        "  - Each cell records # of times the row (target) word and the column (context) word co-occur in some context of size window in some training corpus\n",
        "  - Sparse vectors\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_4 = \"\"\"\n",
        "- Cosine of angle between vectors: based on dot product operator which acts as a similarity metric bc it will tend to be high just when the two vectors have large values in the same dimensions\n",
        "  - If vectors have zeros in different dimensions (orthogonal vectors): dot product will be 0, representing strong dissimilarity\n",
        "  - However, favors long vectors: must use normalized dot product which is the same as the cosine of the angle between the two vectors\n",
        "  - Can pre-normalize vectors by dividing it by its length: unit vector of length 1\n",
        "    - For unit vectors: dot product = cosine\n",
        "- Cosine value ranges from 1 for those pointing in same direction through 0 for orthogonal vectors and -1 for vectors pointing in opposite directions\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_8 = \"\"\"\n",
        "- Embeddings: short, dense vectors\n",
        "  - Short: Dimensions range from 50-1000 instead of vocab size or # of documents\n",
        "  - Dense: values will be real-valued numbers that can be negative\n",
        "- Works better in every NLP task than sparse vectors\n",
        "  - Model learns far fewer weights\n",
        "  - Small param space possibly helps with generalization\n",
        "  - Also better at capturing synonymy\n",
        "- One method for computing embeddings: skip-gram with negative sampling (word2vec)\n",
        "  - Fast, efficient to train and easily available online with code and pretrained embeddings\n",
        "  - Static embeddings: the method learns one fixed embedding for each word in the vocabulary\n",
        "- Embeddings answer the question: \"Is word w likely to show up near 'apricot'?\"\n",
        "  - Can just use running text as implicitly supervised training data\n",
        "    - Self-supervision: avoids need for any sort of hand-labeled supervision signal\n",
        "- Word2vec is much simpler than neural nets:\n",
        "  - Simplifies task by making it binary classification instead of word prediction\n",
        "  - Simplifies architecture by using logistic regression instead of multi-layer NN\n",
        "- Intuition of skip-gram:\n",
        "  - Treat target word and a neighboring context word as positive examples\n",
        "  - Randomly sample other words in the lexicon to get negative samples\n",
        "  - Use logistic regression to train a classifier to distinguish those two cases\n",
        "  - Use learned weights as embeddings\n",
        "- How does classifier compute probability P(+ | w,c)?\n",
        "  - Skip-gram model bases probability on embedding similarity: word is likely to occur near the target if its embedding is similar to the target embedding\n",
        "  - Take dot product of word and context and pass through sigmoid to get probability\n",
        "  - Makes simplifying assumption that all context words are independent, so can multiply probabilities\n",
        "- Skip-gram learns embeddings by starting with random embedding vectors and then iteratively shifting the embedding of each word w to be more like the embeddings of words that occur nearby in texts and less like the embeddings of words that don't occur nearby\n",
        "- Need to generate k negative samples for each positive example (tune k) using noise words: random word from lexicon constrained not to be the target word w\n",
        "- Other static embedding: fasttext deals with unknown words and sparsity in languages with rich morphology by using subword models\n",
        "- GloVe is based on ratios of probabilities from the word-word co-occurrence matrix, combining the intuitions of count-based models like PPMI while also capturing the linear structures using methods like word2vec\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_10 = \"\"\"\n",
        "- One param of vector semantic models: size of context window (generally bc 1 and 10 words on each side of target word)\n",
        "  - Choice depends on goals of preresentation\n",
        "    - Shorter context windows tend to lead to representations that are more syntactic, since info is coming from immediately nearby words\n",
        "      - Most similar words to a target word w tend to be semantically similar words with the same parts of speech\n",
        "    - Longer context sindows: highest cosine words to a target word w tend to be words that are topically related but not similar\n",
        "- Distinguish two kinds of similarity of association between words\n",
        "  - Two words have first-order co-occurrence (syntagmatic association) if they are typically nearby each other (i.e. for wrote: book or poem)\n",
        "  - Two words have second-order co-occurrence (paradigmatic association) if they have similar neighbors (i.e. for wrote: said or remarked)\n",
        "- Another semantic property of embeddings: ability to capture relational meanings\n",
        "  - Parallelogram method: generally too simple to model the human cognitive process of forming analogies of this kind\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_11 = \"\"\"\n",
        "- Embeddings can also reproduce the implicit biases and stereotypes that were latent in the text\n",
        "- Allocational harm: when a system allocates resources unfairly to different groups\n",
        "- Amplify bias: gendered terms become more gendered in embedding space than they were in the input text statistics\n",
        "- Also encode implicit associations that are a property of human reasoning\n",
        "- Representational harm: when a system demeans or even ignores some social groups\n",
        "- Can fix by developing a transformation of the embedding space that removes gender stereotypes but preserves definitional gender or changing training procedure\n",
        "- Debiasing may reduce bias in embeddings, they do not eliminate\n",
        "- Also can evaluate biases in historical texts\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_12 = \"\"\"\n",
        "- Most important eval metric: extrinsic evaluation\n",
        "- Still useful to have intrinsic evaluations\n",
        "  - Most common metric is to test their performance on similarity: computing the correlation between an alg's word similarity scores and word similarity ratings assigned by humans\n",
        "- All embedding algs suffer from inherent variability\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "- Neural language models have several advantages over n-gram LMs:\n",
        "  - They don't need smoothing\n",
        "  - They can handle much longer histories\n",
        "  - They can generalize over contexts of similar words\n",
        "  - Neural LMs tend to have much higher predictive accuracy than n-grams LMs\n",
        "- Disadvantage: slower to train than traditional n-gram LMs\n",
        "- Neural LMs\n",
        "  - Associate each word in the vocab with a vector-representation, thereby creating a notion of similarity between words\n",
        "  - Express the joint probability fn of a word sequence in terms of the word vectors for the words in that sequence\n",
        "  - Simultaneously learn the word vectors and the parameters of the function\n",
        "- Input to NN is a k-gram of words w1:k\n",
        "- Output: probability distribution over the next word\n",
        "- k context words: treated as word window\n",
        "  - Each word is associated with an embedding vector\n",
        "  - Input vector x just concatenates v(w) for each of k words\n",
        "- Training examples: word k-grams from the corpus\n",
        "- Advantages of NN LMs\n",
        "  - Better results: achieve better perplexity scores than SOTA n-gram LMs\n",
        "  - Larger N: NN LMs can scale to much larger orders of n. This is achievable bc params are associated only with individual words and not with n-grams\n",
        "  - They generalize across contexts\n",
        "- By-product of training are word embeddings\n",
        "- LM Goal: learn a function that returns the joint probability\n",
        "  - Primary difficulty\n",
        "    - Too many params to accurately estimate (curse of dimensionality)\n",
        "    - In n-gram-based models, we fail to generalize to related words / word sequences that we have observed\n",
        "- Unseen sequences: basically want to stitch together short sequences of observed words\n",
        "  - Back-off\n",
        "  - Smoothing / interpolation\n",
        "- TF-IDF: term frequency - inverse document frequency\n",
        "  - Term frequency: how often a word occurred in a document\n",
        "  - Inverse document frequency: 1 / # of documents that it occurred in\n",
        "- To get dense vectors:\n",
        "  - Treat target word and neighboring context word as positive examples\n",
        "  - Randomly sample other words in the lexicon to get negative samples\n",
        "  - Use logistic regression to train a classifier to distinguish those two cases\n",
        "  - Use the weights as the embeddings\n",
        "- Choosing noise words\n",
        "  - Can pick according to their unigram frequency P(w)\n",
        "  - More common to choose accord to p\n",
        "- Evaluating embeddings\n",
        "  - Compare to human scores on word similarity-type tasks:\n",
        "    - WordSim-353 (Finkelstein et al., 2002)\n",
        "    - SimLex-999 (Hill et al., 2015)\n",
        "    - Stanford Contextual Word Similarity (SCWS) dataset (Huang et al., 2012)\n",
        "    - TOEFL dataset: “levied” is closest in meaning to: (a) imposed, (b) believed, (c) requested, (d) correlated \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"lexical semantics\" : \"linguistic study of word meaning\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 4602
        },
        "cellView": "form",
        "outputId": "7b04b75f-bf67-48f0-eceb-1666bede11ed"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words & 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 & 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))"
      ],
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n- Language models give us the ability to assign a conditional probability to every possible next word, giving us a distribution over the entire vocabulary\n- Evaluate language models by examining how well they predict unseen text ==> good models are those that assign higher probabilities to unseen data (are less surprised when encountering the new words)\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n- RNN is any network that contains a cycle within its network connections (can be dependent on its own earlier outputs as an input)\n- Key difference from FFN lies in recurrent link that augments the input to the computation at the hidden layer with the value of the hidden layer from the preceding point in time\n- Hidden layer from previous time step provides a form of memory (context) that encodes earlier processing and informs the decisions to be made at later points in time\n\t- This approach does not impose a fixed-length limit on this prior context; the context embodied in the previous hidden layer can include information extending back to the beginning of the sequence\n- Most significant change between FFN and RNN is in new set of weights that connect the hidden layer from the previous time step to the current hidden layer\n- Have 3 sets of weights to update -- weights from the:\n\t- input layer to the hidden layer (W)\n\t- previous hidden layer to the current hidden layer (U)\n\t- hidden layer to output layer (V)\n- Two considerations we didn't have to worry about with backprop in FFN:\n\t- To compute loss function for output at time t, we need the hidden layer from time t-1\n\t- The hidden layer at time t influences both the output at time t and the hidden layer at time t+1\n- To assess the error accruing to ht, we'll need to know it\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n- Teacher forcing: always give the model the correct history sequence to predict the next word, rather than feeding the model its best case from the previous time step\n- Weight typing: method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers (redundancy in that the input word embedding matrix and final layer matrix are very similar => E=V)\n\t- Set dimensionality of final hidden layer to be the same as size of hidden layer and use the same matrix for both layers\n  - Provides improved perplexity results and also significantly reduces the # of params required for the model\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n- A model of word meaning should allow us to draw inferences to address meaning-related tasks like question-answering or dialogue\n- Lemma = citation form\n  - Infinitive form = lemma for verb\n  - Wordforms: like sung, carpets, sing or duermes\n  - Each lemma can have multiple meanings (i.e. mouse = animal or controller? == called a word sense)\n    - Multiple word senses = polysemous\n- Word sense disambiguation: task of determining which sense of a word is being used in a particular context\n- Same propositional meaning if can swap out to synonymous words with no change in truth conditions\n- Principle of contrast: states that a difference in linguistic form is always associated with some difference in meaning\n- Knowing how similar two words are can help in computing how similar the meaning of two phrases or sentences are\n- Instead of similarity, can also use word relatedness (i.e. coffee and cup = associated by co-participating in an everyday event)\n- Semantic frame: set of words that denote perspectives or participants in a particular type of event (event can be encoded lexically)\n- Connotation: aspects of a word's meaning that are related to a writer or reader's emotions, sentiment, opinions or evaluations\n- Sentiment: positive or negative evaluation language\n- Words vary along three important dimensions of affective meaning:\n  - Valence: pleasantness of the stimulus\n  - Arousal: intensity of emotion provoked by the stimulus\n  - Dominance: degree of control exerted by the stimulus\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n- Define meaning of a word by its distribution in language use, meaning its neighboring words or grammatical env\n- Two words that occur in very similar distributions (whose neighboring words are similar) have similar meanings\n- Idea of vector semantics is to represent a word as a point in a multidimensional semantic space that's derived from the distributions of word neighbors\n- Word embeddings: use \"embeddings\" in mathematical sense as a mapping from one space or structure to another\n- By representing words as embeddings, classifiers can assign sentiment as long as it sees some words with similar meanings\n\n\n## SLP Chapter 6.3 Words & Vectors\n\n- Vector or distributional models of meaning are generally based on a co-occurrence matrix (way of representing how often words co-occur)\n- In a term-document matrix: each row represents a word in the vocabulary and each column represents a document from some collection of documents\n  - Each cell represents the # of times a particular word occurs in a particular document\n  - First defined as part of the vector space model of information retrieval: a document is represented as a count vector\n  - Originally defined as means of finding similar documents for the task of document information retrieval: docs that are similar will tend to have similar words (thus, column vectors will be similar)\n  - Has V rows (one for each word type in vocab) and D columns (one for each document in collection)\n- Information retrieval (IR): task of finding the document d from the D documents in some collection that best matches a query q (query also represented by vector of length V)\n- Vector semantics can also be used to represent the meaning of words: associate row vector rather than column vector\n  - Similar words have similar vectors bc they tend to occur in similar documents\n- Term-term matrix (or word-word or term-context): columns are labeled by words rather than documents (VxV dimensionality)\n  - Each cell records # of times the row (target) word and the column (context) word co-occur in some context of size window in some training corpus\n  - Sparse vectors\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n- Cosine of angle between vectors: based on dot product operator which acts as a similarity metric bc it will tend to be high just when the two vectors have large values in the same dimensions\n  - If vectors have zeros in different dimensions (orthogonal vectors): dot product will be 0, representing strong dissimilarity\n  - However, favors long vectors: must use normalized dot product which is the same as the cosine of the angle between the two vectors\n  - Can pre-normalize vectors by dividing it by its length: unit vector of length 1\n    - For unit vectors: dot product = cosine\n- Cosine value ranges from 1 for those pointing in same direction through 0 for orthogonal vectors and -1 for vectors pointing in opposite directions\n\n\n## SLP Chapter 6.8 Word2vec\n\n- Embeddings: short, dense vectors\n  - Short: Dimensions range from 50-1000 instead of vocab size or # of documents\n  - Dense: values will be real-valued numbers that can be negative\n- Works better in every NLP task than sparse vectors\n  - Model learns far fewer weights\n  - Small param space possibly helps with generalization\n  - Also better at capturing synonymy\n- One method for computing embeddings: skip-gram with negative sampling (word2vec)\n  - Fast, efficient to train and easily available online with code and pretrained embeddings\n  - Static embeddings: the method learns one fixed embedding for each word in the vocabulary\n- Embeddings answer the question: \"Is word w likely to show up near 'apricot'?\"\n  - Can just use running text as implicitly supervised training data\n    - Self-supervision: avoids need for any sort of hand-labeled supervision signal\n- Word2vec is much simpler than neural nets:\n  - Simplifies task by making it binary classification instead of word prediction\n  - Simplifies architecture by using logistic regression instead of multi-layer NN\n- Intuition of skip-gram:\n  - Treat target word and a neighboring context word as positive examples\n  - Randomly sample other words in the lexicon to get negative samples\n  - Use logistic regression to train a classifier to distinguish those two cases\n  - Use learned weights as embeddings\n- How does classifier compute probability P(+ | w,c)?\n  - Skip-gram model bases probability on embedding similarity: word is likely to occur near the target if its embedding is similar to the target embedding\n  - Take dot product of word and context and pass through sigmoid to get probability\n  - Makes simplifying assumption that all context words are independent, so can multiply probabilities\n- Skip-gram learns embeddings by starting with random embedding vectors and then iteratively shifting the embedding of each word w to be more like the embeddings of words that occur nearby in texts and less like the embeddings of words that don't occur nearby\n- Need to generate k negative samples for each positive example (tune k) using noise words: random word from lexicon constrained not to be the target word w\n- Other static embedding: fasttext deals with unknown words and sparsity in languages with rich morphology by using subword models\n- GloVe is based on ratios of probabilities from the word-word co-occurrence matrix, combining the intuitions of count-based models like PPMI while also capturing the linear structures using methods like word2vec\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n- One param of vector semantic models: size of context window (generally bc 1 and 10 words on each side of target word)\n  - Choice depends on goals of preresentation\n    - Shorter context windows tend to lead to representations that are more syntactic, since info is coming from immediately nearby words\n      - Most similar words to a target word w tend to be semantically similar words with the same parts of speech\n    - Longer context sindows: highest cosine words to a target word w tend to be words that are topically related but not similar\n- Distinguish two kinds of similarity of association between words\n  - Two words have first-order co-occurrence (syntagmatic association) if they are typically nearby each other (i.e. for wrote: book or poem)\n  - Two words have second-order co-occurrence (paradigmatic association) if they have similar neighbors (i.e. for wrote: said or remarked)\n- Another semantic property of embeddings: ability to capture relational meanings\n  - Parallelogram method: generally too simple to model the human cognitive process of forming analogies of this kind\n\n\n## SLP Chapter 6.11 Bias & Embeddings\n\n- Embeddings can also reproduce the implicit biases and stereotypes that were latent in the text\n- Allocational harm: when a system allocates resources unfairly to different groups\n- Amplify bias: gendered terms become more gendered in embedding space than they were in the input text statistics\n- Also encode implicit associations that are a property of human reasoning\n- Representational harm: when a system demeans or even ignores some social groups\n- Can fix by developing a transformation of the embedding space that removes gender stereotypes but preserves definitional gender or changing training procedure\n- Debiasing may reduce bias in embeddings, they do not eliminate\n- Also can evaluate biases in historical texts\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n- Most important eval metric: extrinsic evaluation\n- Still useful to have intrinsic evaluations\n  - Most common metric is to test their performance on similarity: computing the correlation between an alg's word similarity scores and word similarity ratings assigned by humans\n- All embedding algs suffer from inherent variability\n\n\n## Module 14 Lecture Notes\n\n- Neural language models have several advantages over n-gram LMs:\n  - They don't need smoothing\n  - They can handle much longer histories\n  - They can generalize over contexts of similar words\n  - Neural LMs tend to have much higher predictive accuracy than n-grams LMs\n- Disadvantage: slower to train than traditional n-gram LMs\n- Neural LMs\n  - Associate each word in the vocab with a vector-representation, thereby creating a notion of similarity between words\n  - Express the joint probability fn of a word sequence in terms of the word vectors for the words in that sequence\n  - Simultaneously learn the word vectors and the parameters of the function\n- Input to NN is a k-gram of words w1:k\n- Output: probability distribution over the next word\n- k context words: treated as word window\n  - Each word is associated with an embedding vector\n  - Input vector x just concatenates v(w) for each of k words\n- Training examples: word k-grams from the corpus\n- Advantages of NN LMs\n  - Better results: achieve better perplexity scores than SOTA n-gram LMs\n  - Larger N: NN LMs can scale to much larger orders of n. This is achievable bc params are associated only with individual words and not with n-grams\n  - They generalize across contexts\n- By-product of training are word embeddings\n- LM Goal: learn a function that returns the joint probability\n  - Primary difficulty\n    - Too many params to accurately estimate (curse of dimensionality)\n    - In n-gram-based models, we fail to generalize to related words / word sequences that we have observed\n- Unseen sequences: basically want to stitch together short sequences of observed words\n  - Back-off\n  - Smoothing / interpolation\n- TF-IDF: term frequency - inverse document frequency\n  - Term frequency: how often a word occurred in a document\n  - Inverse document frequency: 1 / # of documents that it occurred in\n- To get dense vectors:\n  - Treat target word and neighboring context word as positive examples\n  - Randomly sample other words in the lexicon to get negative samples\n  - Use logistic regression to train a classifier to distinguish those two cases\n  - Use the weights as the embeddings\n- Choosing noise words\n  - Can pick according to their unigram frequency P(w)\n  - More common to choose accord to p\n- Evaluating embeddings\n  - Compare to human scores on word similarity-type tasks:\n    - WordSim-353 (Finkelstein et al., 2002)\n    - SimLex-999 (Hill et al., 2015)\n    - Stanford Contextual Word Similarity (SCWS) dataset (Huang et al., 2012)\n    - TOEFL dataset: “levied” is closest in meaning to: (a) imposed, (b) believed, (c) requested, (d) correlated \n\n\n## Module 14 Definitions\n* **Lexical semantics** - linguistic study of word meaning\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from L&scape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 31438
        },
        "id": "T3cm1WV542_a",
        "outputId": "a3c1fd36-172d-4a63-a6f1-44d79321566e"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs & Desires under Uncertainty\n\n- Agent assigns probability P(s) to each possible current state s\n- Transition model: given by P(s' | s,a), the probability that action a in state s reaches state s'\n- P(Result(a) = s') = sum(P(s) * P(s'|s,a))\n- Utility function U(s): agent's preferences captured in a single number to express desirability of a state\n- Expected utility of an action given evidence EU(a): average utility value of the outcomes weighted by the probability that the outcome occurs\n- Principle of maximum expected utility (MEU): rational agent should choose action that maximizes agent's expected utility\n  - Maximizing utility doesn't mean the problem is solved by the definition: formalizes that agent should 'do the right thing' but doesn't operationalize that advice\n- If an agent acts to maximize a utility function that correctly reflects the performance measure, then agent will achieve the highest possible performance score (averaged over all possible environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- Constraints on rational preferences\n\t- Can think of set of outcomes for each action as a lottery; each action = ticket\n\t- Primary issue for utility theory: underst& how preferences between complex lotteries are related to preferences between the underlying state in those lotteries\n\t\t- Axioms of utility theory: 6 constraints that we require any reasonable preference relation to obey:\n\t\t\t- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable; cannot avoid deciding\n\t\t\t- Transitivity: Given any three lotteries, if an agent prefers A to B & prefers B to C, then the agent must prefer A to C\n\t\t\t- Continuity: If some lottery B is between A & C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure & the lottery that yields A with probability p & C with probability 1-p\n\t\t\t- Substitutability: If an agent is indifferent between two lotteries A & B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n\t\t\t- Monotonicity: Suppose two lotteries have the same two possible outcomes, A & B. If agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A\n\t\t\t- Decomposability:  Compound lotteries can be reduced to simpler ones using the laws of probability\n- 16.2.2 Rational preferences lead to utility\n\t- From axioms of utility, can derive the following:\n    - Existence of utility function: if agent's preferences obey the axioms of utility, then there exists a function U such that U(A)>U(B) iff A is preferred to B & U(A)=U(B) iff agent is indifferent between A & B\n    - Expected utility of a lottery: utility of lottery = sum[probability of each outcome * utility of that outcome]\n  - Once the probabilities & utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined\n\t- In a deterministic environment, an agent needs only a preference ranking on states (numbers don't matter)\n\t\t- Called a value function or ordinal utility function\n  - Existence of utility function that describes agent's preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- Preference elicitation: process to work out what a human's utility function is by presenting choices to them & using observed preferences to pin down the underlying utility function\n- Useful to establish some scale on which utilities can be recorded & compared for any particular problem by fixing the utilities of any two particular outcomes (best vs worst possible)\n\t- Normalized utilities: scale between 0 & 1\n- Utility of money almost exactly proportional to log of the amount\n  - Most people have a utility function that is concave for positive wealth\n  - Agent with linear curve: risk-neutral\n- Expected utility & post-decision disappointment\n\t- Rational way to choose best action: maximize expected utility\n\t- Model usually oversimplifies real situation: either because we don't know enough or because the computation of the true expected utility is too difficult\n\t\t- Therefore working with estimates of true expected utility\n\t\t- Assume estimates are unbiased: expected value of error is zero\n- Real outcome will usually be significantly worse than we estimated, even though estimate was unbiased\n\t- Optimizer's curse: tendency for the estimated expected utility of the best choice to be too high\n\t\t- Can avoid with Bayesian approach that uses an explicit probability model P(EU_hat | EU) of the error in the utility estimates\n- Decision theory = normative theory: describes how a rational agent should act\n- Descriptive theory: describes how actual agents really do act\n- Certainty effect: people are strongly attracted to gains that are certain --> explanation for apparently irrational preferences\n\t- People may prefer to reduce their computational burden (don't have to calculate probabilities)\n\t- People may distrust the legitimacy of the stated probabilities\n\t- People may be accounting for their emotional state as well as their financial state (avoid feeling like an idiot if you lose)\n- Ambiguity aversion: people elect the known probability rather than unknown unknowns\n- Framing effect: exact wording of a decision problem can have a big impact on agent's choices\n- Anchoring effect: people feel more comfortable making relative utility judgments rather than absolute ones\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- Bc decision prob=sequential, utility fn will depend on seq of states & actions (environment history) rather than on single state\n- MDP: sequential decision prob for fully observable, stochastic env w/ Markovian transition model & additive rewards\n\t- Consists of set of states & actions in each state, transition model, reward function\n- Solving MDPs => dynamic programming: simplifying prob by recursively breaking into smaller pieces & remember optimal solns to the pieces\n- Policy: soln that specifies what agent should do for any state that agent might reach\n\t- No matter outcome of action, resulting state will be in policy & agent will know what to do next\n\t- Quality of policy measured by exp utility of possible env histories generated by that policy (bc stochastic nature of env may lead to different env history)\n\t- Optimal policy: yields highest exp utility (π*)\n- Balance of risk & reward changes depending on value of r=R(s,a,s') for transitions between nonterminal states\n- Finite horizon (nonstationary policy): fixed time N after which nothing matters (game is over) => optimal action in given state may depend on how much time left\n- Infinite horizon (stationary policy): no fixed deadline (simpler to solve)\n- How to calc utility of state seq: additive disc. rewards\n\t- Discount factor describes pref of agent for current rewards over future rewards\n\t\t-  Close to 0: rewards in distant future viewed as insig\n\t\t-  Close to 1: agent more willing to wait for long-term rewards\n\t\t-  Exactly 1: disc. rewards reduce to special case of purely additive rewards\n- If env not contain terminal state or if agent never reaches one=> all env histories will be infinitely long & utilities w/ additive undiscounted rewards will generally be infinite\n\t- Solns: w/ disc. rewards, utility of infinite seq is finite\n- If env contains terminal states & if agent guaranteed to get to one eventually, then never need to compare infinite seqs\n\t- Proper policy: guaranteed to reach terminal state\n- Infinite seqs can be compared in terms of avg reward obtained per time step\n- Utility of given history: sum of disc. rewards => compare policies by comparing exp utilities obtained when executing them\n- Consequence of using disc. utilities w/ infinite horizons => optimal policy is independent of starting state\n- True utility of state: expected sum of disc. rewards if agent executes optimal policy\n- Direct relationship between utility of state & utility of its neighbors\n\t- Bellman equation: utility of state = expected reward for next transition plus disc. utility of next state assuming that agent chooses optimal action\n- Action-utility fn (Q-fn): Q(s,a)=expected utility of taking given action in given state\n- Scale of utilities is arbitrary: affine transformation leaves optimal decision unchanged\n\t- Similar transformation of rewards will leave optimal policy unchanged in MDP\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- 4 alg for solving MDPs: Generate exact solns offline (value/policy iteration,linear programming) & fam of online approx alg (Monte Carlo planning)\n- Value iter: If there are n possible states, then there are n Bellman eqs, one for each state (n eqns contain n unknowns (util of states))\n\t- Problem: eqns are nonlinear (max operator = not linear) => Can try solve using iterative approach (refer to module notes)\n\t- Value iter: propagates information through state space by means of local updates\n\t- Convergence of value iteration (exponentially fast): Contraction=fn of 1 argument that, when applied to 2 different inputs in turn, produces 2 output val that're \"closer together\" by at least some constant factor than orig inputs (i.e. divide by two)\n\t\t- Two important properties: Only has 1 fixed point (unchanged by application of fn) // When fn applied to any argument, val must get closer to fixed point\n\t\t- Bellman update=contraction by factor of gamma on space of util vectors => valiter always converges to unique soln of Bellman equations whenever gamma < 1\n\t\t- Can use contraction to analyze rate of convergence to soln\n- Policy iter\n\t- Possible to get optimal policy even when util fn estimate=inaccurate\n\t- Eqns=linear bc max operator has been removed\n\t- For state spaces: Small[policy eval using exact soln methods most efficient] // Large[O(n3) might be prohibitive]\n\t\t- Soln: don't need to do exact policy eval => can perform some # of simplified valiter steps (simplified bc policy is fixed) to give reasonably good approx of util\n\t- Asynchronous policyiter: on each iter, pick any subset of states & apply either kind of updating (policy improve or simplified valueiter) to that subset\n\t\t- Given certain conditions on init policy & init util fn => guaranteed to converge to optimal policy\n- Linear programming: general approach for forumlating constrained optimization problems\n\t- Basic idea: consider as vars in LP util of each state, noting that util for optimal policy are highest util attainable that are consistent with Bellman eqs\n- Offline alg: value & policy iter => generate optimal soln for prob when can then be executed by simple agent\n\t- For sufficiently large MDPs => exact offline soln not possible\n- Most straightforward: simplification of Expectminimax\n- Real-time dynamic programming (RTDP) (effective in moderate-sized domains)\n\t- In larger domains, issues: State space such that any manageable set of explored states contains very few repeated states (so might as well use expectimax tree) // Simple heuristic for frontier nodes may not be enough to guide agent, particularly if rewards are sparse\n\t- Potential fixes: Apply RL to generate more accurate heuristic // Look further ahead in MDP using Monte Carlo approach\n\n\n## Module 8 Lecture Notes\n\n- Transitions are Markovian: the probability of arriving in s' only depends on s & not the history of earlier states\n- We will specify a utility or reward function for the agent => the 'rewards' can be + or - but are bounded by some maximum value\n- Because the decision process is sequential, we must specify the utility function on a sequence of states & actions\n- Instead of only giving a reward at the goal states, the agent can receive a reward at each time step, based on its transition from s to s’ via action a\n- MDP is a sequential decision problem for a fully observable environment with a stochastic transition model that has additive rewards\n- Expectimax node: outcome is uncertain. In expectimax search, we calculate their expected utilities.\n- MDPs: non-deterministic search problems. One way of solving them is via expectimax search.\n- Solution to MDP is a policy\n- Performance of agent in MDP = sum of rewards for the transitions it takes\n- Discounting: prefer rewards now to rewards later => values of rewards decay exponentially\n- Stationary preferences: two ways to define utilities => additive & discounted\n- Problem: what if game lasts forever?? Solutions:\n  - Finite horizon (like depth-limited search): terminate after fixed T steps & gives nonstationary policies\n  - Discounting\n  - Absorbing state: guarantee that for every policy, a terminal state will eventually be reached\n- Optimal quantities\n  - Value of state s V*(s) = expected utility starting in s & acting optimally\n  - Value of q-state Q*(s,a) = expected utility starting out having taken action a from state s & (thereafter) acting optimally\n  - Optimal policy: optimal action from state s\n- Value Iteration => complexity of each iteration: O(S^2*A)\n  - Start with V0(s) = 0: no time steps left means an expected reward sum of zero\n  - Given vector of Vk(s) values: do (refer to written notes)\n  - Repeat until convergence\n- Theorem: will converge to unique optimal values ==> Basic idea: approximations get refined towards optimal values; policy may converge long before values do\n- How do we know the Vk vectors are going to converge?\n  - Case 1: If the tree has maximum depth M, then VM holds the actual untruncated values\n  - Case 2: If the discount is less than 1\n    - Sketch: For any state Vk & Vk+1 can be viewed as depth k+1 expectimax results in nearly identical search trees\n    - The difference is that on the bottom layer, Vk+1 has actual rewards while Vk has zeros\n    - That last layer is at best all RMAX; at worst RMIN\n    - But everything is discounted by γk that far out\n    - So Vk & Vk+1 are at most γk max|R| different\n    - So as k increases, the values converge\n- Bellman equations: definition of \"optimal utility\" via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values\n- Problems with Value Iteration: repeats Bellman updates\n  - It's slow O(S^2 * A) per iteration\n  - The max at each state rarely changes\n  - The policy often converges long before the values\n- Policy iteration: optimal & converges faster\n  - Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n  - Policy improvement: update policy using one-step look-ahead with resulting converged (but not optimal!) utilities as future values\n  - Repeat steps until policy converges\n- Comparison: both value & policy iteration compute the same thing (all optimal values) // both are dynamic programs for solving MDPs\n  - In value, every iteration updates both the values & (implicitly) the policy; we don't track the policy, but taking the max over actions implicitly recomputes it\n  - In policy, we do several passes that update utilities with fixed policy (each pass is fast bc we consider only one action, not all of them)\n    - After policy is evaluated, a new policy is chosen (slow like a value iteration pass)\n    - The new policy will be better (or we're done)\n- If you want to:\n  - Compute optimal values: use value iteration or policy iteration\n  - Compute values for a particular policy: use policy evaluation\n  - Turn your values into a policy: use policy extraction (one-step lookahead)\n- Above differ only in whether we plug in a fixed policy or max over actions\n- Principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes its expected utility, given its knowledge\n- Utilities => agent must have preferences among choices\n  - Preference: A > B\n  - Indifference A ~ B\n- Rational preferences imply behavior describable as maximization of expected utility\n- Utility scales: normalized; micromorts; QALYs (quality-adjusted life years)\n  - With deterministic prizes only (no lottery choices), only ordinal utility can be determined\n\n\n## Module 8 Definitions\n* **** - \n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- Ubiquitous tradeoff between:\n\t- Exploitation of the current best action to obtain rewards\n\t- Exploration of previously unknown states & actions to gain info\n- Definitions of bandit problems (Overall bandit problem is MDP)\n\t- Each arm is a Markov reward process (MRP), an MDP with only one possible action\n- Key property: arms are independent, coupled only by fact that agent can work on only one arm at a time\n- Optimal strategy is to run arm M up to time T & then switches to Mλ the rest of the time (where λ is the discount factor)\n- Gittins index of M: Provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins indices\n- Calculating the Gittins index\n\t- To calculate the Gittins index for a general arm M & current state s, we simply make the following observation: at the tipping point where an optimal policy is indifferent between choosing arm M & choosing the fixed arm Mλ, the value of choosing M is the same as the value of choosing an infinite sequence of λ-rewards\n\t- Restart MDP\n- Bernoulli bandit\n\t- Each arm Mi produces reward of 0 or 1 with fixed but unknown probability µi\n\t- The state of arm Mi is defined by si & fi the counts of successes (1s) & failures (0s) so far for that arm\n\t- Transition probability predicts the next outcome to be 1 with probability si / (si + fi) & 0 with probability fi / (si + fi)\n\t- Assign exploration bonus associated with arms that have only been tried a few times\n- Approximately optimal bandit policies\n\t- Calculating Gittins indices for more realistic problems is rarely easy, but can create \"nearly as good\" policies\n\t- Upper confidence bound (UCB) heuristic: use the samples from each arm to establish CI for value of the arm, that is, range within which value can be estimated to lie w/ high confidence; then choose arm w/ highest upper bound on its CI\n\t- Thompson sampling: chooses arm randomly according to probability that the arm is in fact optimal, given the samples so far\n- Non-indexable variants\n\t- Selection problem: there's fixed cost for each test, but don't have to minimize test failures; just try to make good decision asap\n\t\t- No index function exists for selection problems\n\t- Bandit superprocess (BSP): generalization of bandit process in which each arm is a full MDP in its own right, rather than being MRP w/ only one possible action\n\t- How to solve BSPs\n\t\t- Impractical but optimal: convert into global MDP on Cartesian-product state space\n\t\t- Take advantage of loose nature of interaction between arms\n\t\t\t- Interaction arises only from agent's limited ability to attend to arms simultaneously\n\t\t\t\t- Interaction can be modeled by notion of opportunity cost: how much utility is given up per time step by not devoting that time step to another arm\n\t\t\t- Dominating policy?\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- Reinforcement learning (RL): agent interacts with world & periodically receives rewards (reinforcements) that reflect how well it's doing\n\t- Goal is the same as MDPs: maximize expected sum of rewards\n\t- Differs from MDP bc agent is not given the MDP to solve; it's IN the MDP (may not know transition model or reward function so has to act to learn more)\n- Providing reward signal is usually much easier than providing labeled examples of how to behave\n\t- Very concise & easy to specify\n\t- Don't have to be experts capable of supplying the correct action in any situation (but a little expertise goes a long way)\n\t\t- Sparse rewards: in vast majority of states, agent is given no informative reward signal at all\n\t\t- Intermediate rewards make learning easier\n- Different RL algorithms:\n\t- Model-based RL: agent uses transition model of environment to help interpret the reward signals & to make decisions about how to act\n\t\t- Model may be initially unknown (so agent learns from observing effects of its actions) or known\n\t\t- In partially observable environments: transition model is also useful for state estimation\n\t\t- Utility function = sum of rewards from state s onwards\n\t- Model-free RL: agent neither knows nor learns a transition model for environment; it learns a more direct representation of how to behave\n\t\t- Action-utility learning: agent choose what to do in s by finding action with highest q-value (Q(s,a) = sum of rewards from state s onward if action a is taken)\n\t\t- Policy search: agent learns a policy that maps directly from states to actions (reflex agent)\n- Passive RL: agent's policy is fixed & the task is to learn the utilities of states\n  - Passive learning agent: agent trying to learn utility function Uπ(s) (the expected total discounted reward if policy π is executed beginning in state s)\n  - Passive learning task similar to policy eval task => Difference: PL agent doesn't know T or R\n  - PL agent executes a set of trials in environment using its policy π\n\t- Percepts supply both current state & reward received for the transition that just occurred to reach that state\n\t- Each transition annotated with both action taken & reward received at next state\n\t- Agent will use info about rewards to learn expected utility associated with each nonterminal state s\n\t\t- Utility: expected sum of (discounted) rewards obtained if policy π is followed\n- Active RL: agent must also figure out what to do\n\t- Will need to learn complete T w/ outcome probabilities for all actions instead of just model for fixed policy\n\t- Has choice of actions => needs to learn utilities defined by optimal policy\n- Main issue is exploration: agent must experience as much as possible of its environment in order to learn how to behave in it (can use inductive learning to learn much faster)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n- Direct utility est: util of state defined as exp total reward from that state onward that each trial provides sample of this quantity for each state visited\n\t- RL => standard supervised learning prob => each example = (state, reward-to-go)\n\t\t- Constraint: util of state determined by reward & exp util of successor states (util values obey Bellman for fixed policy)\n\t\t\t- Ignoring connections between states: DUE misses opps for learning\n\t- Can view DUE as searching for U in hypothesis space that's much larger than needed (includes many functions that violate Bellman)\n- Adaptive dynamic programming (ADP): agent takes advantage of constraints among utils of states by learning T that connects them & solving corresponding MDP using DP\n\t- Take PL agent, plug in T & observed R to calc utils of states\n\t- Alsocan take approach of modified policyiter: using simplified valiter to update util estimates after each change to learned model\n\t\t- Since model usu only changes slightly w/ each obs, valueiter can use prev util esimates as init vals & converge very quickly\n\t- Learning T=easy bc env is fully observable\n\t- How quickly val ests improve=> ADP agent limited only by ability to learn T (intractable for large state spaces)\n- TD learning: Can use observed transitions to adj utils of observed states so that they agree w/ constraint eqns\n\t- New update rule uses diff in utils between successive states/times (TD eqn)\n\t\t- TD term = error signal (update is intended to reduce error)\n\t- All TD methods work by adj util ests toward ideal equilib that holds locally when util ests=correct\n\t- TD agent learns slower than ADP agent & shows higher variability, but much simpler & requires much less computation per obs\n\t\t- TD doesn't need T to perform updates: env itself supplies connection between neighboring states in form of observed transitions\n\t- ADP & TD approaches both try to make local adj to util estimates to make each state \"agree\" w/ its successors. Diffs:\n\t\t- TD adj state to agree w/ its observed successor; ADP adj to agree w/ all of successors that might occur, weighted by their probabilities\n\t\t\t- Diff disappears when effects of TD adj are averaged over large # of transitions (freq of each successor in set of transitions approx. proportional to its probability)\n\t\t- TD makes single adj per observed transition; ADP makes as many as needed to restore consistency between util ests U & transition model P\n\t\t\t- TD=crude but efficient first approx to ADP\n\t- From TD POV, each adj made by ADP = result of pseudoexperience generated by simulating current T\n\t\t- TD agent can generate large # of imaginary transitions for each observed transition => resulting util ests will approx more closely those of ADP\n\t- Can generate more efficient versions of ADP by directly approxing algs for value/policyiter\n\t\t- Can generate good answers quickly by bounding # of adj made after each observed transition\n\t- Approx ADP algs can learn roughly as fast as full ADP but can be much more efficient\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- Greedy agent: always take constant believed optimal action: can lead to suboptimal results => learned model =/= true env\n\t- Overlooks: actions provide rewards AND info\n\t- GLIE: try each action in each state unbounded # of times to avoid having finite probability that optimal action is missed\n\t\t- Choose random action at time step t with probability 1/t otherwise follow greedy policy (will slowly converge)\n\t\t- Give weight to less-tried actions but avoiding possible low util\n- Exploration fn f(u,n): determines how greed (pref for high values of util u) traded off against curiosity (pref for actions not tried often, low count n) => increasing u & decreasing n\n\n- Worst case: agent enters absorbing state bc model unknown (actively explore in bad direction) or incorrect (don't know given action is disastrous)\n- Better: choose okay policy that works for range of models that have chance of being true model, even if policy suboptimal for maximum-likelihood model (Bayesian RL)\n\t- Robust control theory: allows for set of possible models H w/o assigning probabilities to them & defines optimal robust policy = gives best outcome in worst case over H (too conservative)\n\t\t- H = set of models that exceed some likelihood threshold on posterior P(h|e) (Bayesian & robust are related)\n- Human knowledge can help keep sys safe: record actions by expert so sys acts reasonably from start or write down constraints on sys & have prog outside of RL sys enforce\n\n- Active TD learning agent: have to learn T to choose action based on U(s) via one-step look-ahead\n- Model acq prob still identical to ADP agent & TD update rule remains unchanged\n- Q-learn method: learns action-utility Q(s,a) not utility U(s) => act optimally (choose argmax)\n\t- TD Q-learn agent doesn't need T for learning or action selection\n\t- Cons: q-learn agent no way look into future=> may have difficulty when rewards=sparse & long action seq must be constructed to reach them\n- Like Q-learn: SARSA (state, action, reward, state', action')\n\t- Update rule like Q-learn except SARSA updates w/ q-value of action a' actually taken\n\t- Q-learn backs up q-value from best action in s' ==> SARSA waits until action taken & backs up q-value for that action\n\t\t- If agent=greedy & always takes action w/ best q-value: two algs are identical\n\t\t- If explore happening: if yields negative reward, SARSA penalizes action; Q-learning doesn't\n- Q-learn = off-policy: learns q-values that answer: \"what would action be worth in state, assuming that I switch to policy that chooses best action?\"\n- SARSA = on-policy: learns q-values that answers: \"what would action be worth in state, assuming that I stick w/ my policy?\"\n- Q-learn more flexible: can learn how to behave well when under control of wide variety of exploration policies\n- SARSA appropriate if overall policy is even partly controlled by other agents or progs\n- Both learn optimal pol=> much slower than ADP agent (local updates don't enforce consistency among all q-values via model)\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n- Function approx with look-ahead search ==> produce more accurate decisions\n\t- Effective behavior can result from much simpler util fn approximator that's learnable from fewer experiences\n  - Makes it practical to represent util (or Q) fns for large spaces\n  - Allows for inductive generalization: can generalize from states visited to states not yet visited\n  - Approximating DUE: learn faster if use fn approximator if hypothesis space not too large & includes some fn that're reasonably good fit to true util fn\n- Approximating TD learning: adj params to reduce TD between successive states\n\t- For passive TD learning, update rule can converge to closest possible approx to true fn when fn approximator is linear in features\n\t- For active learning & nonlinear functions (neural nets): params can go to infinity w/ these update rules even if good solutions in hypothesis space\n\t- Catastrophic forgetting: if agent learns too well (flat value fn, so quadratic features get zero weight, but then nonzero weight on linear features cause abrupt change)\n\t\t- Solution: experience replay (ensures agent relives youthful bad behavior at intervals to ensure value fn still accurate for parts of state space no longer visits)\n- Deep RL system: RL system that uses deep network as fn approximator\n\t- 2 reasons why we need to go beyond linear fn approximators:\n\t\t- May be no good linear fn that comes close to approximating util fn or Q-function\n\t\t- May not be able to invent necessary features, particularly in new domains\n\t- Deep NN discovers useful features for itself: final layer linear => can see what features network used to build own linear fn approximator\n\t- Deep NN = fn parameterized by theta except fn much more complicated => params are all weights in layers of network (but gradient same as in supervised learning)\n- Reward shaping\n\t- Prob of credit assignment: other than going through process a million times before rewards propagate back to actions responsible for it\n\t- Reward shaping: supplying agent with additional rewards for \"making progress\" (pseudorewards)\n\t\t- Risk that agent will learn to maximize pseudorewards rather than true rewards\n- Hierarchical reinforcement learning: break up very long action seqs into few smaller pieces, then break those into smaller pieces still, and so on until action sequences are short enough to make learning easy\n\t- Partial program: outlines hierarchical structure for agent's behavior\n\t- HRL includes ordinary RL as a special case\n\t- Choose operator allows agent to choose any element of specified set\n\t- Learning process converts partial agent program into a complete program by learning how each choice should be made\n\t- Can be effective method for learning complex behaviors\n  - Important characteristic: lower-level skills are not fixed subroutines ==> their choices are sensitive to entire internal state of agent program so they behave differently depending on where they are invoked within that program and what is going on at the time\n\n\n## AIMA Chapter 22.5 Policy Search\n\n- Idea is to keep twiddling the policy as long as performance improves, then stop\n- Interested primarily in parameterized representations of π that have far fewer parameters than there are states in the state space\n- If policy is represented by Q-functions ==> policy search results in process that learns Q-functions\n\t- Not the same as Q-learning!\n\t\t- Q-learning: finds value of theta to approximate Q*\n\t\t- Policy search: finds value of theta that results in good performance (may be far from estimating true utility function)\n- Policy = discontinuous function of parameters when actions are discrete\n\t- Will be values of theta such that the smallest change will cause the policy to switch from one action to another\n\t- Will use a stochastic policy representation which specifies probability of select action a in state s (i.e. softmax)\n\t\t- β > 0 modulates softness of softmax\n\t\t- If large: approaches hard max\n    - If close to 0: approaches uniform random choice among actions\n\n\n## Module 9 Lecture Notes\n\n- Solving MDPs = offline planning\n  - Determine all quantities through computation\n  - Need to know the details of the MDP\n  - Do not actually play the game\n- Regret: even if you learn intelligently, you make mistakes\n- Sampling: bc of chance, you have to try things repeatedly\n- Difficulty: learning can be much harder than solving a known MDP\n- RL basic idea:\n  - Receive feedback in the form of rewards\n  - Agent's utility is defined by the reward function\n  - Must (learn to) act so as to maximize expected rewards\n  - All learning is based on observed samples of outcomes\n- Still assume MDP: set of states, set of actions, transition model, reward function => still looking for a policy\n  - New twist: don't know the transition model or reward function: must actually try actions & states out to learn\n- Model-based learning: estimate T & R & plug in\n  - Learn an approximate model based on experiences & solve for values as if the learned model were correct\n  - Step 1: learn empirical MDP model\n    - Count outcomes s' for each s,a\n    - Normalize to give an estimate of T(s,a,s')\n    - Discover each R(s,a,s') when we experience (s,a,s')\n  - Step 2: solve the learned MDP (i.e. use value iteration)\n- Model-free learning: don't build explicit transition model\n  - Take action, compare results to what we thought was going to happen to what actually happens\n  - When something deviates from expectation, take values & adjust them up or down\n  - Track values of being in certain states, don't track transition or reward values\n- Passive RL: instead of us picking the policy, let someone else choose & we'll try it out\n  - Don't figure out how to act optimally, instead see how good this policy is\n  - Simplified task: policy evaluation where input=fixed policy, but don't know T or R ==> goal: learn state values\n  - Learner is \"along for the ride\" & has no choice about what actions to take => just execute the policy & learn from experience\n- Direct evaluation: goal is to compute values for each state under policy\n  - Idea: average together observed sample values\n    - Act according to policy\n    - Every time you visit a state, write down what the sum of discounted rewards turned out to be\n    - Average those samples\n  - Pros: easy to understand, doesn't require knowledge of T or R, eventually computes the correct avg values using just sample transitions\n  - Cons: wastes info about state connections, each state must be learned separately => takes a long time to learn\n- Temporal Difference Learning: solution to policy eval since we don't know T or R\n  - Want to improve our estimate of V by computing these averages by taking samples of outcomes s' (by doing the action!) & average, but we can't rewind time to get sample after sample from state s\n- TD learning: learn from every experience => Update V(s) each time we experience a transition (s,a,s',r) => Likely outcomes s' will contribute updates more often\n  - Policy still fixed, still doing evaluation\n  - Move values toward value of whatever successor occurs: running average\n  - Exponential moving average: makes recent samples more important & forgets about the past (distant past values were wrong anyway)\n    - Decreasing learning rate (alpha) can give converging averages\n  - Problems with TD value learning: model-free way to do policy eval, mimicking Bellman updates with running sample averages; however, if we want to turn values into a (new) policy, we're sunk\n    - Idea: learn Q-values, not values\n    - Makes action selection model-free too\n- Active RL: don't know T or R but we choose the actions now => learn the optimal policy/values\n  - Learner makes choices => fundamental tradeoff between exploration vs exploitation\n  - Q-learning: sample-based Q-value iteration (refer to written notes)\n    - Off-policy learning: Q-learning converges to optimal policy even if you're acting suboptimally\n    - Caveats: have to explore enough, have to eventually make the learning rate small enough (but don't decrease it too quickly) => but in the limit, doesn't matter how you select actions\n- Exploration vs Exploitation\n  - Problem with epsilon greedy: eventually explore the space, but keep thrashing around once learning is done (soln: lower epsilon over time OR exploration functions (explore areas whose badness is not yet established))\n    - Exploration function: refer to written notes\n  - Basic Q-learning keeps a table of all q-values: not realistic! => too many states to visit them all in training & to hold q-tables in memory\n    - Want to generalize: learn about some small # of training states from experience => generalize that experience to new, similar situations\n    - Approximate Q-learning: adjust weights of active features as positive or negative\n\n\n## Module 9 Definitions\n* **Prioritized sweeping heuristic** - make adj to states whose likely successors have just undergone a large adjustment in their own utility estimates\n* **Absorbing state** - state where no actions have any effect & no rewards are received\n* **Glie** - greedy in limit of infinite exploration\n* **Evaluation function** - measure of desirability for potentially vast state spaces (approximate utility function)\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n\n\n# Module 10: Probabilies & Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- Problem-solving & logical agents handle uncertainty by keeping track of belief state and generate contingency plan that handles every possible eventuality that its sensors may report during execution\n\t- Belief state: representation of the set of all possible world states that it might be in\n\t- Drawbacks:\n\t\t- Agent must consider every possible explanation for its sensor observations, no matter how unlikely\n\t\t- Plan can grow very large and must consider arbitrarily unlikely contingencies\n\t\t- Sometimes there's no plan that's guaranteed to achieve the goal\n- Rational decision depends on both relative importance of various goals and the likelihood that they will be achieved\n- Summarizing uncertainty\n\t- Enumerating all possible logical rules (i.e. for medical diagnosis) might fail due to:\n    - Laziness (too much work to do this)\n    - Theoretical ignorance (there is no complete theory for the domain)\n    - Practical ignorance (even if we know all the rules, might still be uncertain)\n\t- Agent's knowledge can at best provide only degree of belief in relevant sentences => deal with it using probability theory\n\t\t- Ontological commitments of logic and probability theory are the same: world is composed of facts that do or don't hold in any particular case\n\t\t- Epistemological commitments: logical agent believes each sentence to be T/F or has no opinion; probabilistic agent may have a numerical degree of belief between 0 and 1\n\t- Theory of probability provides way of summarizing the uncertainty that comes from our laziness and ignorance\n\t- Probability statements are made wrt knowledge state, not real world\n- Uncertainty and rational decisions\n\t- Agent must have preferences among different possible outcomes of various plans\n\t\t- Use utility theory to represent preferences and reason quantitatively with them\n\t\t- Utility of a state: relative to an agent\n\t\t- No accounting for taste or preferences (can't think agent is irrational bc preferences is odd)\n\t- Decision theory = probability theory + utility theory\n\t\t- Fundamental idea: agent is rational iff it chooses the action that yields the highest expected utility, averaged over all possible outcomes of the action\n\t\t\t- Maximum expected utility (MEU)\n  - Decision-theoretic agent's belief state represents not just possibilities for world states but also their probabilities\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- What probabilities are about\n\t- Logical assertions: which possible worlds are strictly ruled out ==> probabilistic assertions: how probable the various worlds are\n\t- Sample space: set of all possible worlds (mutually exclusive & exhaustive)\n\t- Probability model: associates numerical probability with each possible world\n\t- Unconditional / prior probabilities: degrees of belief in propositions in the absence of any other information\n\t\t- Most of the time, we do have evidence (some information)\n\t- When making decisions, an agent needs to condition on all evidence it has observed\n- The language of propositions in probability assertions\n\t- Every random variable RV is a function that maps from domain of possible worlds to some range: set of possible values it can take on\n\t- Probabilities are unitless numbers whereas density functions are measured with a unit\n\t- Joint probability distribution (i.e. P(Weather,Cavity) = probabilities of all combos of values of Weather and Cavity)\n\t- Possible world defined to be an assignment of values to all of the RVs under consideration\n- Probability axioms and their reasonableness\n\t- Inclusion-exclusion principle: P(a or b) = P(a) + P(b) - P(a and b)\n\t- Finetti's argument for axioms of probability: if an agent has some degree of belief in a proposition a, then the agent should be able to state odds at which it is indifferent to a bet for or against a\n    - If agent1 expresses a set of degrees of belief that violate the axioms of probability theory, then there is a combo of bets by agent2 that guarantees agent1 will lose money every time\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- Probabilistic inference: computation of posterior probabilities for query propositions given observed evidence\n- Not used in practice because it requires input table of size O(2^n) in time and space\n\n\n## AIMA Chapter 12.4 Independence\n\n- If two events are independent:\n\t- P(a|b) = P(a)\n\t- P(b|a) = P(b)\n\t- P(a&b) = P(a)*P(b)\n- Independence assertions usually based on knowledge of domain\n\n\n## AIMA Chapter 12.5 Bayes’ Rule & Its Use\n\n- P(effect|cause): quantifies relationship in causal direction\n- P(cause|effect): quantifies in diagnostic direction\n- Conditional independence of two variables given a third: P(Cavity | toothache & catch) = P(toothache | Cavity)*P(catch | Cavity)*P(Cavity)\n\t- Conditional independence of two variables X and Y given a third variable Z: P(X,Y | Z) = P(X|Z)*P(Y|Z)\n- Conditional independence assertions can allow probabilistic systems to scale up; moreover, they are much more commonly available than absolute independence assertions\n- Decomposition of large probabilistic domains into weakly connected subsets through conditional independence is one of the most important developments in the recent history of AI\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- \"Naïve\" bc used in cases where \"effect\" of variables aren't strictly independent given the cause variable\n- For each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause; then normalize result\n\t- Runtime of calculation is linear in number of observed effects and doesn't depend on number of unobserved effects\n- Even though bc of assumption of conditional independence, model is overconfident in its predictions; however, even with these errors, the ranking of possible categories is often quite accurate\n\n\n## SLP Chapter 3.1 N-Grams\n\n- Get MLE estimate for the parameters of an n-gram model by getting counts from a corpus and normalizing the counts so they lie between 0 and 1\n  - Relative frequency: estimate n-gram probability by dividing the observed frequency of a particular sequence by the observed frequency of a prefix\n- Use log probabilities and not raw probabilities to keep numbers from getting too small\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- Extrinsic evaluation: best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves\n  - Only way to know if a particular improvement in a component is really going to help the task at hand\n  - Unfortunately, running big NLP systems end-to-end is very expensive\n- Intrinsic evaluation: measures quality of a model independent of any application\n- Training on test set introduces bias that makes probabilities all look too high and causes huge inaccuracies in perplexity\n- Perplexity of a language model on a test set is the inverse probability of the test set, normalized by the number of words\n  - Higher the conditional probability of the word sequence, the lower the perplexity\n  - Minimizing perplexity = maximizing the test set probability according to LM\n- Since seq will cross many sentence boundaries => need to include begin- and end-sentence markers <s> and </s> in probability computation\n- Another way of thinking about perplexity: weighted average branching factor of a language\n  - Branching factor of language = # of possible next words that can follow any word\n- Perplexity used to compare different n-gram models: more info the n-gram gives us about the word seq, the lower the perplexity\n- In computing perplexities, n-gram model must be constructed without any knowledge of test set or any prior knowledge of the vocab of test set\n- Intrinsic improvement in perplexity does not guarantee an extrinsic improvement in performance of a language processing task\n- Model's improvement in perplexity should always be confirmed by an end-to-end evaluation of a real task before concluding the evaluation of the model\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n- N-gram model depends on training set => probabilities often encode specific facts about given training corpus and n-grams do a better and better job of modeling the training corpus as N increases\n- The longer the context on which we train the model, the more coherent the sentences\n  - Unigram sentences: no coherent relation between words or any sentence-final punctuation\n- What if training and test sets have no overlap? => no, must be similar genre and in appropriate dialect or variety of test set\n- Problem of sparsity: have cases of \"zero probability n-grams\" that should have non-zero probability\n- Problems of zeros:\n  - We underestimate the probability of all sorts of words that might occur\n  - If probability of any word in the test set = 0, entire probability of test set is 0\n- Out of vocabulary (OOV) words = unknown\n  - OOV rate: % of OOV words that appear in test set\n- To train probabilities of unknown:\n  - Turn problem back into closed vocab by choosing a fixed vocab in advance:\n    - Choose vocab that is fixed in advance\n    - Covert any word that's not in this set to <unk>\n    - Estimate probabilities for <unk> from its counts just like other regular words in the set\n  - If we don't have prior vocab in advance: create vocab implicitly, replacing words in the training data by <unk> based on their frequency\n- Exact choice of <unk> model affects metrics like perplexity: should only be compared across LMs with same vocabs\n\n\n## SLP Chapter 3.4 Generalization & Zeros\n\n- Laplace (add-one) smoothing: add one to all bigram counts before normalizing into probabilities\n  - Does not perform well enough to be used in modern n-gram models, but it usefully introduces many of the concepts in other smoothing algs, gives a useful baseline, and is practical for tasks like text classification\n- Relative discount d: ratio of discounted counts to original counts\n- Add-k smoothing: move a bit less of probability mass from seen to unseen events => instead of 1, add fractional count k (i.e. 0.5)\n  - k is hyperparam that needs tuning\n  - Still doesn't work great for language modeling\n- Sometimes using less context is good, helping to generalize more for contexts that the model hasn't learned much about\n  - Backoff: use trigram if evidence is sufficient, else bigram, else unigram\n  - Interpolation: always mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram and unigram counts\n    - Linear: Weight each with lambda such that sum of lambda = 1\n    - Other: each lambda weight is computed by conditioning on the context\n      - If we have particularly accurate counts for a particular bigram, can assume that counts of the trigrams based on this bigram will be more trustworth so we can make the lambdas for those trigrams higher and thus give that trigram more weight in the interpolation\n  - Lambdas are set and tuned using a held-out corpus: can use EM alg\n  - In backoff n-gram model, if the n-gram we need has zero counts, approximate it by backing off to the (N-1)-gram => keep backing off until reach a history that has some counts\n    - Have to discount the higher-order n-grams to save some probability mass for lower order n-grams\n    - Katz backoff: rely on discounted probability P* if we've seen n-gram before\n\n\n## SLP Chapter 3.5 Smoothing\n\n- Kneser-Ney has its roots in absolute discounting: subtract a fixed (absolute) discount d from each count\n- Idea was to look at a held-out corpus and just see what the count is for all those bigrams that had count 4 in training set\n- Kneser-Ney discounting augments absolute discounting with a more sophisticated way to handle the lower-order unigram distribution\n- Want to create unigram model PCONTINUATION that answers the question \"How likely is w to appear as a novel continuation?\"\n- Kneser-Ney intuition is to base our estimate of PCONTINUATION on the # of different contexts word w has appeared in (# of bigram types it completes)\n\n\n## SLP Chapter 3.7 Huge Language Models & Stupid Backoff\n\n- Entropy is a lower bound on # of bits it would take to encode a certain decision or piece of info in the optimal coding scheme\n- Entropy rate: entropy of seq divided by # of words\n- Stochastic process: stationary if probabilities it assigns to a seq are invariant wrt shifts in the time index\n  - Markov models (and hence n-grams) are stationary\n  - But natural language is not stationary: probability of upcoming words can be dependent on events that were arbitrarily distant and time dependent\n- By making some incorrect but convenient simplifying assumptions, can compute the entropy of some stochastic process by taking a very long sample of the output and computing its average log probability\n- Cross-entropy: useful when we don't know the actual probability distribution p that generated some data\n  - Draw sequences according to probability distribution p, but sum the log of their probabilities according to m (some model of p)\n  - Can estimate the cross-entropy of a model m on some distribution p by taking a single seq that is long enough instead of summing over all possible seq\n  - Cross-entropy H(p,m) is an upper bound on the entropy H(p)\n    - Means we can use some simplified model m to help estimate the true entropy of a seq of symbols drawn according to probability p\n    - The more accurate m is, the closer the cross-entropy H(p,m) will be to the true entropy H(p)\n    - Thus, difference between H(pm,) and H(p) is a measure of how accurate a model is\n    - Between two models m1 and m2, the more accurate model will be the one with lower cross-entropy (cross-entropy can never be lower than true entropy, so model cannot err by underestimating the true entropy)\n\n\n## Module 10 Lecture Notes\n\n- Probabilistic reasoning gives us framework for managing our beliefs and knowledge\n  - Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms)\n  - Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present)\n  - Model: Agent knows something about how the known variables relate to the unknown variables\n- Like logical assertions, probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is.\n- In probability theory, the possible worlds are called the sample space, and they are mutually exclusive and exhaustive.\n- Fully specified probability model associates a probability P(w) with each possible world w.\n- Random variable: some aspect of world about which we (may) have uncertainty\n- Axioms of probability (between 0 and 1 and sum of probs = 1)\n- Joint distribution specifies real # for each assignment (or outcome): size of distribution if n variables w/ domain sizes d (d^n)\n- Probabilistic model = joint distribution over set of RV\n  - RV with domains\n  - Assignments = outcomes\n  - Joint dist: say whether outcomes are likely\n  - Normalized: sum to 1\n  - Ideally only certain variables directly interact\n- Event: set of outcomes\n- Conditional distributions: probability distributions over some variables given fixed values of others\n- Probabilistic inference: compute desired probability from other known probabilities (i.e. conditional from joint)\n- Inference by enumeration:\n  - Select the entries consistent with the evidence\n  - Sum out H to get joint of Query and evidence\n  - Normalize\n- Product rule: P(x|y)P(y) = P(x,y)\n- Probabilistic language models: goal is to assign a probability to a sentence (related task: probability of upcoming word)\n  - Autocomplete for texting\n  - Machine translation\n  - Spelling correction\n  - Speech recognition\n- Markov assumption: only depends on previous k words, not whole context\n  - Unigram: no history; bigram: 1 word; trigram: 2 words; 4-gram: 3 words\n- N-grams: insufficient model of language bc language has long-distance dependencies\n- Problems for MLE:\n  - Out of vocab items (OOV): <unk> to deal with OOVs\n  - Fixed lexicon L of size V\n  - Normalize training data by replacing any word not in L with <unk>\n  - Avoid zeros with smoothing\n- Practical issues: do everything in log space to avoid underflow (also adding is faster than multiplying)\n\n\n## Module 10 Definitions\n* **Zeros** - grams that occur in the test set but not in the training set\n* **Closed vocabulary system** - test set can only contain known words\n* **Open vocabulary system** - model potential unknown words in test set using <unk>\n\n\n# Module 11: Probabilistic Reasoning & Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n- Bayesian network is a directed acyclic graph in which each node is annotated with quantitative probability information\n\t- Each node corresponds to a random variable (discrete or continuous)\n\t- Directed links connect nodes. If X=>Y, means X is parent of Y. No cycles = DAG\n\t- Each node has associated probability of X given parents of X\n- Conditional probability tables (CPT): local probability info attached to each node\n\t- Each row contains conditional probability of each node value for a conditioning case (possible combo of values for parent nodes)\n\t- Table for Boolean variable with k Boolean parents contains 2k independently specifiable probabilities\n\t- Node with no parent has only one row, representing the prior probabilities of each possible value of the variable\n- Probabilities summarize a potentially infinite set of circumstances in which something might occur\n- Syntax of Bayes net: consists of DAG with some local probability info attached to each node\n- Semantics of Bayes net: defines how syntax corresponds to joint distribution over variables of network\n- When estimating vals for local cond dist => need to be actual cond probabilities for var given parents\n- Important property of Bayes nets: contain no redundant probability vals => no chance for inconsistency: can't create Bayes net that violates axioms of prob\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- Bayes net can be far more compact than full joint dist (sparse sys) => Local structure: linear growth in complexity\n- Specifying cond probability tables for fully connected net requires same amount of info as specifying joint dist in tabular form\n- Will get compact Bayes only if choose node ordering well\n- Stick to causal model, end up having to specify fewer #s & #s will often be easier to come up with\n- Cond independence relations: each var is cond independent of non-descendants given parents\n\t- Var cond independent of all other nodes in network, given parents, children & children's parents (given its Markov blanket)\n\t- Whether Z d-separates X & Y: whether set of nodes X is cond independent of another set Y given a third set Z\n\t\t- Consider just ancestral subgraph consisting of X, Y, Z & their ancestors\n\t\t- Add links between any unlinked pair of nodes that share common child (get moral graph)\n\t\t- Replace all directed w/ undirected links\n\t\t- If Z blocks all paths between X&Y in resulting graph, then Z d-separates X&Y ==> then X is cond independent of Y given Z\n\t\t- Otherwise, orig Bayes net doesn't require cond independence\n- Efficient Representation of Cond Dists\n\t- Even if max # of parents k is smallish, filling in CPT for node requires up to O(2^k) #s\n\t- Uncertain relationships can be characterized by noisy logical relationships\n\t\t- Noisy-OR relation (generalization of logical OR) - makes 2 assumps: all possible causes are listed & inhibition of each parent is independent of inhibition of any other parents\n\t\t- Noisy logical relationships where var depends on k parents can be described using O(k) params\n- Way to handle continuous vars: discretization (dividing into fixed set of intervals)\n- Can use standard families of pdfs (i.e. Gaussian)\n- Can use nonparametric rep to define cond dist implicitly w/ collection of instances, each containing specific vals of parent & child vars\n- Hybrid Bayes net: has both discrete & continuous => specify 2 new kinds of dists\n  - Cond dist for a continuous var given discrete or continuous parents\n    - Linear-Gaussian cond dist: child has Gaussian dist whose mean varies linearly w/ val of parent & std dev is fixed\n      - Network containing only continuous vars with linear-Gaussian dists has joint dist that's multivariate Gaussian dist over all vars\n      - Posterior dist given any evidence also has this property\n      - When discrete vars are added as parents of continuous vars, net defines cond Gaussian (CG) dist: given any assignment to discrete vars, dist over continous vars = multivariate Gaussian\n  - Cond dist for discrete var given continuous parents - like \"soft\" threshold fn (make by using integral of standard normal dist)\n    - Can use probit or expit/inverse logit models\n    - Probit often better fit to real situations\n    - Logit has longer tails & logistic fn sometimes easier to deal w/ mathematically\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- Inference by enumeration\n  - Query can be answered using Bayes net by computing sums of products of conditional probabilities from network\n    - In worst case, where we have to sum out almost all variables, there will be O(2^n) terms in sum, each a product of O(n) probability values ==> O(n2^n)\n      - Can be reduced to O(2^n) by taking advantage of nested structure of computation\n  - Enumeration-ask alg evaluates expression trees using depth-first, left-to-right recursion\n    - Similar in structure to backtracking alg for solving CSPs and DPLL alg for satisfiability\n    - Space complexity: only linear in number of variables\n    - Time complexity: O(2^n) for network with n Boolean variables\n- Variable elimination algorithm\n  - Enumeration alg can be improved substantially by eliminating repeated calculations\n  - Idea: do calculation once and save results for later use (form of dynamic programming)\n  - One version of approach: variable elimination alg which works by evaluating expressions in right-to-left order\n    - Intermediate results are stored and summations over each variable are done only for those portions of expression that depend on variable\n  - Pointwise product of two factors f and g yields new factor h whose variables are union of vars in f and g and whose elements are given by product of corresponding elements in two factors\n  - Time and space requirements of variable elimination are dominated by the size of largest factor constructed during operation of algorithm\n    - Eliminate whichever variable minimizes the size of the next factor to be constructed\n    - Every variable that is not an ancestor of a query variable or evidence variable is irrelevant to the query\n- The complexity of exact inference\n  - Complexity of exact inference in Bayes nets depends strongly on structure of the network\n  - Singly connected networks / polytrees: networks that have at most one undirected path\n    - Time and space complexity of exact inference in polytrees is linear in the size of the network (size = # of CPT entires)\n  - Multiply connected networks: variable elimination can hav eexponential time and space complexity in the worst case, even when # of parents per node is bounded\n    - Bc it includes inference in propositional logic as special case, inference in Bayes nets is NP-hard\n- Clustering algorithms\n  - Variable elimination alg is simple and efficient for answering individual queries, but if we want to compute posterior probabilities for all variables in network, it can be less efficient\n    - Example: in polytree network, need to issue O(n) queries costing O(n) each for O(n^2) time ==> can use clustering to reduce time to O(n)\n      - Basic idea: join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree\n\n\n## Module 11 Lecture Notes\n\n- Bayes net semantics: set of nodes (one per variable X), DAG, conditional distribution for each node\n- Bayes net = topology (graph) + local conditional probabilities\n- Bayes net implicitly encode joint distributions as product of local conditional distributions\n  - To see what probability a BN gives to full assignment, multiply all relevant conditionals together\n- Not every BN can represent every joint distribution\n- Only distributions whose variables are absolutely independent can be represented by a BN with no arcs\n- Size of Bayes net\n  - Size of joint distribution over N boolean variables: 2^N\n  - Size of N-node net if nodes have up to k parents: O(N * 2^(k+1))\n  - BNs: huge space savings\n  - Also easier to elicit local CPTs\n  - Also faster to answer queries\n- Causal chains: X => Y => Z\n  - One example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed\n  - Common cause: observing the cause blocks influence between effects\n  - Common effect:\n    - Are X and Y independent? Yes (still need to prove)\n    - Are X and Y independent given Z? No\n    - Backwards from other cases => observing an effect activates influence between possible causes\n- General question: in a given BN, are two variables independent (given evidence)? => Analyze graph\n  - Any complex example can be broken into repetitions of 3 canonical cases\n    - Reachability: shade evidence nodes, look for paths in resulting graph\n      - If 2 nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent\n- Active / Inactive Paths\n  - D-separation gives precise conditional independence guarantees from graph alone\n  - Are X and Y conditionally independent given evidence variables {Z}? => Yes, if X and Y \"d-separated\" by Z\n    - Consider all (undirected paths) from X to Y ==> no active paths = independence!\n  - Path is active if each triple is active:\n    - Causal chain A -> B -> C where B is unobserved (either direction)\n    - Common cause A <- B -> C where B is unobserved\n    - Common effect A -> B <- C where B or one of its descendants is observed\n  - All it takes to block a path is a single inactive segment\n- Given Bayes net structure: can run d-separation alg to build complete list of conditional independences that are necessarily true of the form [Xi independent of Xj | {Xk1,...,Xkn}]\n- Inference: calculating some useful quantity from a joint probability distribution\n- Inference by enumeration = very slow: joint up whole joint distribution before you sum out the hidden variables\n  - Advanced technique: variable elimination\n    - Interleave joining and marginalizing\n    - Still NP-hard, but usually much faster than inference by enumeration\n\n\n## Module 11 Definitions\n* **Deterministic node** - val specified exactly by vals of its parents w/ no uncertainty and relationship can be logical or numerical\n* **Context-specific independence (csi)** - conditional dist exhibits CSI if a variable is conditionally independent of some of its parents given certain values of others\n\n\n# Module 12: Naive Bayes & Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n\n- Any component of agent program can be improved by ML. Depends on:\n\t- Which component is to be improved\n\t- What prior knowledge the agent has (which influences the model it builds)\n\t- What data and feedback on that data is available\n- Components, each of which can be learned, include:\n\t- Direct mapping from conditions on current state to actions\n\t- Means to infer relevant properties of the world from the percept sequence\n\t- Information about the way the world evolves and about the results of possible actions the agent can take\n\t- Utility information indicating the desirability of world states\n\t- Action-value info indicating the desirability of actions\n\t- Goals that describe the most desirable states\n\t- Problem generator, critic and learning element that enable the system to improve\n- Transfer learning: knowledge from one domain is transferred to a new domain so that learning can proceed faster with less data\n- Induction: going from specific set of observations to general rule\n\t- Deductive conclusions are guaranteed to be correct of premises are correct; inductive conclusions may be incorrect\n- Three types of learning: supervised, unsupervised, reinforcement\n\n\n## AIMA Chapter 19.2 Supervised Learning\n\n- How to choose hypothesis space: might have prior knowledge about the process that generated the data; if not, can perform EDA; otherwise can just try multiple hypothesis spaces and see what works best\n- How to choose good hypothesis from hypothesis space?\n  - Consistent hypothesis: any h such that each x in the training set has h(x) = y\n    - For continous, look for best-fit function where h(x) is close to y\n  - The function h that a learning alg discovers depends on the hypothesis space H it considers and on the training set it's given\n  - One way to analyze hypothesis space is by the bias they impose and the variance they produce\n    - Bias: tendency of a predictive hypothesis to deviate from expected value when averaged over different training sets\n      - Often results from restriction imposed by the hypothesis space\n    - Variance: amount of change in the hypothesis due to fluctuation in the training data\n  - Can choose hypothesis based on how probable it is\n- Tradeoff between expressiveness of hypothesis space and computational complexity of finding a good hypothesis within that space\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n\n- Decision tree: representation of a function that maps a vector of attribute values to a single output value (a decision)\n- Can evaluate the performance of a learning alg with a learning curve\n- Entropy: measure of uncertainty of a random variable\n- Decision tree pruning combats overfitting\n  - How to detect if a node is testing an irrelevant attribute?: low information gain = good clue that attribute is irrelevant\n    - But how large a gain should be required in order to split on particular attribute?: significance test\n\t\t\t\t□ Null hypothesis is that attribute is irrelevant and that IG for infinitely large sample would be zero\n  - Chi-squared pruning (pg. 1225)\n- Problem with early stopping: stops us from recognizing situations where there is no one good attribute, but there are combinations of attributes that are informative\n- DTs are useful in handling\n  - Missing data\n  - Continuous/multivalued input attributes\n    - Split point test: inequality test on the value of an attribute for continuous values\n    - Information gain ratio: used for non-continuous attributes that do not have a meaningful ordering\n  - Continuous-valued output attribute (regression tree)\n- Pros: ease of understanding, scalability to large datasets, and versatility in handling discrete & continuous inputs as well as classification & regression\n- Cons: suboptimal accuracy, unstable, (if deep) prediction = expensive\n\n\n## AIMA Chapter 19.4 Model Selection and Optimization\n\n- Stationarity assumption: assumes that future examples will be like the past\n- For now: optimal fit is the hypothesis that minimizes the error rate (proportion of times that h(x) != y for an (x,y) exmaple\n- Hyperparameters: params of the model class, not of the individual model\n- Task of finding a good hypothesis as two subtasks:\n\t- Model selection chooses a good hypothesis space\n\t- Optimzation find the best hypothesis within that space\n- Model that exactly fits all the training data has interpolated the data\n\t- Models start to overfit as the capacity approaches the point of interpolation\n- Also necessary: minimize a loss function (rather than maximize a utility function)\n\t- No loss when you guess exactly right\n- Reasons why chosen hypothesis might different from true function f:\n\t- Learning problem is realizable if the hypothesis space H actually contains the true function f\n\t- Variance: learning alg will in general return different hypotheses for different sets of examples\n\t\t- If problem = realizable, variance decreases towards zero as # of training examples increase\n\t- f may be nondeterministic or noisy: may return different values of f(x) for same x\n\t- When H is a complicated function in a large hypothesis space == can be computationally intractable to systematically search all possibilities\n- 19.4.3 Regularization\n\t- Search for a hypothesis that directly minimizes the weighted sum of empirical loss and the complexity of the hypothesis\n\t- Regularization: explicitly penalizing complex hypotheses\n\t- Can simplify by reducing dimensionality (feature selection)\n- 19.4.4 Hyperparameter tuning\n\t- Hand-tuning: guess some parameter values based on past experience, train a model, measure its performance on the validation data, analyze results and use intuition to suggest new parameter values\n\t- Bayesian optimization: treats the task of choosing good hyperparamter values as a ML problem in itself\n    - Alternative: population-based training (PBT): uses random search to train (in parallel) a population of models, each with different hyperparams; then 2nd generation of models are trained but they choose hyperparams based on successful values from previous generation\n\n\n## AIMA Chapter 19.5 The Theory of Learning\n\n- Any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: must be probably approximately correct (PAC)\n- PAC learning algs: can provide bounds on performance of various learning algs\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n- NB is generative bc it states a kind of implicit assumption about how a document is generated: first a class is sampled from P(c) and then words are generated by sampling from P(d|c)\n- Make two simplifying assumptions:\n  - Bag of words assumption: position of words don't matter => only encode identity and not position\n  - NB assumption: conditional independence assumption that the probabilities P(fi|c) are independent given the class c\n- To apply NB to text: need to consider word positions by just walking an index through every word position in the document\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n- Learn P(c) and P(fi|c) using maximum likelihood estimate\n  - For the class prior P(c): ask what % of documents in our training set are in each class c\n  - P(wi|c) = fraction of times the word wi appears among all words in all documents of topic c\n    - Vocab V = union of all word types in all classes, not just the words in one class c\n- NB ignores stopwords and unknown words\n\n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n- For sentiment classification: whether a word occurs or not seems to matter more than its frequency\n  - Often improves performance to clip word counts in each document at 1\n    - Count will be higher if word appears in multiple documents\n  - Called binary multinomial naive Bayes or binary NB: for each doc, remove all duplicate words before concatenating them into the single big document\n- Also important: deal with negation\n  - During text normalization, prepend prefix NOT_ to every word after a token of logical negation (n't, not, no, never) until punctuation mark\n  - Newly formed words like NOT_like will occur more often in negative document and act as cues for negative sentiment while words like NOT_bored will acquire positive associations\n- If we have insufficient labeled training data, can derive positive and negative word features from sentiment lexicons:\n  - General Inquirer\n  - LIWC\n  - Opinion lexicon\n  - MPQA Subjectivity Lexicon\n- Common way to use lexicons in NB: add feature that is counted whenever a word from that lexicon occurs\n  - Might add feature called \"this word occurs in positive lexicon\" and treat all instances of words in the lexicon as counts for that one feature instead of counting each word separately\n- If we have lots of training data and if the test data matches the training data, using just two features won't work as well as using all the words\n- If training data is sparse or not representative of the test set, using dense lexicon features instead of sparse individual-word features may generalize better\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n- NB doesn't require using all words in training data as features => features can express any property of the input text we want\n- Rather than using all words as individual features => predefine likely sets of words or phrases as features, combined with features that are not purely linguistic\n- For language id, most effective features are character or byte n-grams\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n- NB can be viewed as a set of class-specific unigram language model in which the model for each class instantiates a unigram language model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n- Precision: measures % of items that the system detected as positive that are in fact positive\n- Recall: measures % of items actually present in the input that were correctly identified by the system\n- F-measure = ((B^2 + 1)P*R) / (PB^2 + R)\n  - When B > 1: favor recall\n  - When B < 1: favor precision\n  - When B = 1: balance precision and recall => F1 = 2PR / (P+R)\n- F-measure comes from weighted harmonic mean of precision and recall: used bc it's conservative => harmonic mean of two values is closer to the minimum of the two values than the arithmetic mean is\n- Macroaveraging: compute performance for each class and then average over the classes\n  - Better reflects the statistics of the smaller classes and so is more appropriate when performance on all the classes is equally important\n- Microaveraging: collect the decisions for all classes into a single confusion matrix and then compute precision and recall from the table\n  - Dominated by the more frequent class since the counts are pooled\n\n\n## SLP Chapter 4.8 Test sets & Cross-validation\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n- Effect size: the magnitude of difference between the score from one model and that of the other\n- To compute probability we need for p-value => usually use non-parametric tests based on sampling:\n  - Artificially create many versions of the experimental setup (i.e. having lots of test sets and measure model on all tests sets) => gives us a distribution\n  - Set a threshold and see if this distribution that 99% or more of the measures are smaller than the delta we observed\n  - If we see that our measure is greater than 99% of the measures we see => reject null hypothesis\n- Two common non-parametric tests used in NLP: approximate randomization & bootstrap test\n- Paired tests: compare two sets of observations that are aligned: each observation in one set can be paired with an observation in another\n- Bootstrap samples can create many virtual test sets from an observed test set by repeatedly sampling from it\n  - Only makes assumption that sample is representative of the population\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n- Representational harms: harms caused by a system that demeans a social group\n- Toxicity detection: task of detecting hate speech, abuse, harassment, or other kinds of toxic language\n- Model card for each version of a model that documents a ML model with info like:\n  - Training algs and params\n  - Training data sources, motivation and preprocessing\n  - Evaluation data sources, motivation and preprocessing\n  - Intended use and users\n  - Model performance across different demographic or other groups and environmental situations\n\n\n## Module 12 Lecture Notes\n\n- Model-based classification:\n  - Build a model where both the label and features are RVs\n  - Instantiate any observed features\n  - Query for the distribution of the label conditioned on the features\n- Challenges:\n  - What structure should the Bayes net have?\n  - How should we learn its parameters?\n- General NB model: only have to specify how each feature depends on the class\n  - Total # of params is linear in # of features\n  - Model is very simplistic, but often works anyway\n- Inference for NB: goal is to compute posterior distribution over label variable Y\n  - Get joint probability of label and evidence for each label\n  - Sum to get probability of evidence\n  - Normalize by dividing step 1 by step 2\n- Parameter estimation: estimating the distribution of a RV\n  - Elicitation: ask a human (hard)\n  - Empirically: use training data (learning!)\n    - Relative frequencies are maximum likelihood estimates = count(x) / total samples\n- Laplace smoothing: k=strength of prior\n- Confidence of a probabilistic classifier: posterior over the top label => confidenc(x) = max[P(y|x)]\n  - Represents how sure the classifier is of the classification\n  - Any probabilistic model will have confidences\n  - No guarantee confidence is correct\n- Calibration\n  - Weak calibration: higher confidences mean higher accuracy\n  - Strong calibration: confidence predicts accuracy rate\n- Multiclass decision rule\n  - Weight vector for each class: wy\n  - Score (activation) of a class y: wy * f(x)\n  - Prediction highest score wins: y = argmax{y}[wy * f(x)]\n    - If correct: no change!\n    - If wrong: lower score of wrong answer, raise score of right answer\n- Properties of perceptrons\n  - Separability: true if some params get the training set perfectly correct\n  - Convergence: if the training is separable, perceptron will eventually converge (binary case)\n  - Mistake bound: the max # of mistakes (binary case) related to the margin or degree of separability [mistakes < (k / delta^2)]\n- Problems with perceptrons\n  - Noise: if data isn't separable, weights might thrash (averaging weight vectors over time can help, i.e. averaged perceptron)\n  - Mediocre generalization: finds a \"barely\" separating solution\n  - Overtraining: test/held-out accuracy usually rises, then falls\n- Fixing the perceptron: adjust weight update to mitigate these effects\n  - MIRA: Margin Infused Relaxed Algorithm\n  - MIRA*: choose an update size that fixes the current mistake but minimizes the change to w\n- Comparison\n  - NB\n    - Builds a model training data\n    - Gives prediction probabilities\n    - Strong assumptions about feature independence\n    - One pass through data (counting)\n  - Perceptrons / MIRA\n    - Makes less assumptions about data\n    - Mistake-driven learning\n    - Multiple passes through data (prediction)\n    - Often more accurate\n\n\n## Module 12 Definitions\n* **Bag-of-words** - the frequency of each word in an unordered set of words, ignoring position\n* **Sentiment lexicon** - list of words pre-annotated with positive or negative sentiment\n* **Language id** - a task in determining what language a text is written in\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n- LR learns from a training set a vector of weights and a bias term\n  - Each weight represents how important that input feature is to the classification decision\n- To create a probability, we'll pass z=w*x + b through sigmoid function\n- To classify, 0.5 is the decision boundary\n- Designing features usually done by examining the training set with an eye to linguistic intuitions and linguistic literature on the domain\n- Large number of features are usually created automatically via feature templates (abstract specifications of features)\n- Representation learning: ways to learn features automatically in an unsupervised way from the input\n- LR vs NB: LR is more robust to correlated features; generally works better on larger documents\n  - NB has overly strong conditional independence assumptions, but can work very well on small datasets or small documents; also easy to implement and very fast to train\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n- Want to learn parameters (meaning w and b) that make y_hat for each training observation as close as possible to the true y\n- Metric for how far current label is from true gold label: loss / cost function\n- Need optimization algorithm for iteratively updating the weights in order to minimize loss function: (stochastic) gradient descent\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n- Conditional maximum likelihood estimation: choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x\n\t- Learn weights that maximize probability of correct label p(y|x)\n- Negative log of this probability = convenient loss metric since it goes from 0 to infinity\n- Loss function also ensures that as the probability of the correct answer is maximized, probability of incorrect answer is also minimized\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n- Goal: find set of weights which minimizes the loss function, averaged over all examples\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction the function's slope is rising the most steeply and moving in the opposite direction\n- For LR: loss function = convex -- GD guaranteed to find a minimum\n- Gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function\n- Magnitude of the amount to move in GD = value of slope weighted by a learning rate\n- Gradient expresses directional components of the sharpest slope along each of N dimensions\n\t- Slope = partial derivative of the loss function\n- SGD: online alg that minimizes loss function by computing its gradient after each training example\n\t- Learning rate needs to be adjusted: if too high, learner will take steps that are too large; if too low, it'll take too long to get to minimum\n- Batch training: computer gradient over entire dataset\n- Mini-batch training: train a group of m examples that is less than the whole dataset\n- Allows us to process all examples in one mini-batch in parallel and then accumulate the loss\n\n\n## SLP Chapter 5.5 Regularization\n\n- If a feature is perfectly predictive of outcome bc it happens to only occur in one class == assigned very high weight\n- To avoid, add regularization to objective function which will penalize large weights\n\t- L2: quadratic function of weight values == same as Euclidean distance of vector from origin\n\t\t- Easier to optimize bc of simple derivative\n\t\t- Prefers weight vectors with many small weights\n\t- L1: linear function of weight values == sum of absolute values of the weights (Manhattan distance)\n    - Prefers sparse solutions with some larger weights but many more weights set to zero\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n- Generalization of sigmoid = softmax function p(y= c|x)\n- Like sigmoid, but now need separate weight vectors (and bias) for each of K classes\n- Each feature can be evidence for or against each individual class\n- One-hot vector: one value=1 and the rest=0\n\n\n## SLP Chapter 7.1 Units\n\n- Building block of NN: single computational unit (weighted sum of its inputs and a bias term)\n- Neural units apply a non-linear function f to z (z=w*x+b)\n\t- Output of this function = activation value for the unit\n- Tanh: variant of sigmoid that ranges from -1 to +1\n\t- Pros: Smoothly differentiable and mapping outlier values toward the mean\n\t- Cons: zero derivatives = vanishing gradient problem (also for sigmoid)\n- ReLU: same as x when x is positive, otherwise 0\n  - Pros: very close to linear\n\n\n## SLP Chapter 7.2 The XOR problem\n\n- Perceptron: simple neural unit that has a binary output and doesn't have a non-linear activation function\n- XOR: not linearly separable\n- Cannot be calculated by single perceptron, but can be calculated by layered network of units\n- Weights for NNs are learned automatically using the error backpropagation alg (hidden layers will learn to form useful representations\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n- FFN: multilayer network in which the units are connected with no cycles; outputs from units in each layer are passed to units in the next higher layer and no outputs are passed back to lower layers (those with cycles = RNNs)\n- Sometimes called multi-layer perceptrons (MLPs) but is a misnomer since units in multilayer networks aren't perceptrons which are purely linear\n- Three kinds of nodes:\n\t- Input units: scalar values\n\t\t- Input lyaer = layer 0\n\t- Hidden units: neural unit, taking a weighted sum of its inputs and then applying a non-linearity\n\t\t- Standard architecture: each layer is fully-connected - each unit in each layer takes as input the outputs from all the units in previous layer and there is a link between every pair of units from two adjacent layers\n\t\t- Each hidden unit sums over all input units\n\t\t- Advantage of using single matrix W for the weights of the entire layer is that now the hidden layer computation for a FFN can be done very efficiently with simple matrix operations\n\t\t\t- Computation only has 3 steps: multiplying the weight matrix by the input vector x, adding the bias vector b, and applying the activation function g\n\t\t- Forms a representation of the input == output layer takes this representation and computes a final output\n\t- Output units\n\t\t- Use softmax to get output of classifier\n- When counting layers, don't count input layer but do count output\n- Activation functions are generally different at the final layer\n- Replacing the bias unit\n  - Add a dummy node to each layer whose value will always be 1: still has an associated weight and that weight represents the bias value b\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n- How do we partial out the loss over all intermediate layers?: backpropagation\n- If NN is being used as binary classifier with sigmoid at final layer == loss function is exactly the same as we saw with logistic regression\n- Backprop makes use of chain rule\n- Optimization in NN is a non-convex optimization problem\n- Need to initialize the weights with small random numbers\n- Helpful to normalize the input values\n- To help with overfitting: dropout, tuning of hyperparams (i.e. learning rate, mini-batch size, model architecture)\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n- NN language models are strikingly slower to train than traditional language models\n- Prior context is represented by embeddings of previous words == allows neural language models to generalize to unseen data much better than n-gram language models\n\n\n## Module 13 Lecture Notes\n\n- Machine learning classifiers require a training corpus of M observations input/output pairs (xi,yi)\n  - Feature representation of input: vector of features [x1,x2,...,xn]\n  - Classification function: computes the estimated class y_hat via p(y|x)\n  - Objective function: used for learning, usually involving minimizing error on training examples\n  - Algorithm for optimizing the objective function\n- Learning in logistic regression\n  - Must learn weights & bias via learning => 2 components\n    - Objective / loss fn: tells us distance between the system output and the gold output (will use cross-entropy loss)\n    - Alg for optimizing objective fn: SGD to minimize loss fn\n- Conditional maximum likelihood estimation: choose params w,b that maximize the (log) probabilities of the true labels in the training data\n  - Resulting loss function = negative log likelihood loss => cross entropy loss\n  - p(y|x) = y_hat^y * (1-y_hat)^(1-y)\n    - Change to logs: y*log(y_hat) + (1-y)*log(1-y_hat)\n      - Negative of this: cross-entropy loss\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the params theta) the fn's slope is rising the most steeply and moving in the opposite direction\n- FFN\n  - Multiply weight matrix by input vector x\n  - Add bias vector b\n  - Apply activation fn g (such as sigmoid)\n- Equations\n  - h = sig(Wx + b)\n  - z = U*h\n  - y = softmax(z)\n\n\n## Module 13 Definitions\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n- Language models give us the ability to assign a conditional probability to every possible next word, giving us a distribution over the entire vocabulary\n- Evaluate language models by examining how well they predict unseen text ==> good models are those that assign higher probabilities to unseen data (are less surprised when encountering the new words)\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n- RNN is any network that contains a cycle within its network connections (can be dependent on its own earlier outputs as an input)\n- Key difference from FFN lies in recurrent link that augments the input to the computation at the hidden layer with the value of the hidden layer from the preceding point in time\n- Hidden layer from previous time step provides a form of memory (context) that encodes earlier processing and informs the decisions to be made at later points in time\n\t- This approach does not impose a fixed-length limit on this prior context; the context embodied in the previous hidden layer can include information extending back to the beginning of the sequence\n- Most significant change between FFN and RNN is in new set of weights that connect the hidden layer from the previous time step to the current hidden layer\n- Have 3 sets of weights to update -- weights from the:\n\t- input layer to the hidden layer (W)\n\t- previous hidden layer to the current hidden layer (U)\n\t- hidden layer to output layer (V)\n- Two considerations we didn't have to worry about with backprop in FFN:\n\t- To compute loss function for output at time t, we need the hidden layer from time t-1\n\t- The hidden layer at time t influences both the output at time t and the hidden layer at time t+1\n- To assess the error accruing to ht, we'll need to know it\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n- Teacher forcing: always give the model the correct history sequence to predict the next word, rather than feeding the model its best case from the previous time step\n- Weight typing: method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers (redundancy in that the input word embedding matrix and final layer matrix are very similar => E=V)\n\t- Set dimensionality of final hidden layer to be the same as size of hidden layer and use the same matrix for both layers\n  - Provides improved perplexity results and also significantly reduces the # of params required for the model\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n- A model of word meaning should allow us to draw inferences to address meaning-related tasks like question-answering or dialogue\n- Lemma = citation form\n  - Infinitive form = lemma for verb\n  - Wordforms: like sung, carpets, sing or duermes\n  - Each lemma can have multiple meanings (i.e. mouse = animal or controller? == called a word sense)\n    - Multiple word senses = polysemous\n- Word sense disambiguation: task of determining which sense of a word is being used in a particular context\n- Same propositional meaning if can swap out to synonymous words with no change in truth conditions\n- Principle of contrast: states that a difference in linguistic form is always associated with some difference in meaning\n- Knowing how similar two words are can help in computing how similar the meaning of two phrases or sentences are\n- Instead of similarity, can also use word relatedness (i.e. coffee and cup = associated by co-participating in an everyday event)\n- Semantic frame: set of words that denote perspectives or participants in a particular type of event (event can be encoded lexically)\n- Connotation: aspects of a word's meaning that are related to a writer or reader's emotions, sentiment, opinions or evaluations\n- Sentiment: positive or negative evaluation language\n- Words vary along three important dimensions of affective meaning:\n  - Valence: pleasantness of the stimulus\n  - Arousal: intensity of emotion provoked by the stimulus\n  - Dominance: degree of control exerted by the stimulus\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n- Define meaning of a word by its distribution in language use, meaning its neighboring words or grammatical env\n- Two words that occur in very similar distributions (whose neighboring words are similar) have similar meanings\n- Idea of vector semantics is to represent a word as a point in a multidimensional semantic space that's derived from the distributions of word neighbors\n- Word embeddings: use \"embeddings\" in mathematical sense as a mapping from one space or structure to another\n- By representing words as embeddings, classifiers can assign sentiment as long as it sees some words with similar meanings\n\n\n## SLP Chapter 6.3 Words & Vectors\n\n- Vector or distributional models of meaning are generally based on a co-occurrence matrix (way of representing how often words co-occur)\n- In a term-document matrix: each row represents a word in the vocabulary and each column represents a document from some collection of documents\n  - Each cell represents the # of times a particular word occurs in a particular document\n  - First defined as part of the vector space model of information retrieval: a document is represented as a count vector\n  - Originally defined as means of finding similar documents for the task of document information retrieval: docs that are similar will tend to have similar words (thus, column vectors will be similar)\n  - Has V rows (one for each word type in vocab) and D columns (one for each document in collection)\n- Information retrieval (IR): task of finding the document d from the D documents in some collection that best matches a query q (query also represented by vector of length V)\n- Vector semantics can also be used to represent the meaning of words: associate row vector rather than column vector\n  - Similar words have similar vectors bc they tend to occur in similar documents\n- Term-term matrix (or word-word or term-context): columns are labeled by words rather than documents (VxV dimensionality)\n  - Each cell records # of times the row (target) word and the column (context) word co-occur in some context of size window in some training corpus\n  - Sparse vectors\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n- Cosine of angle between vectors: based on dot product operator which acts as a similarity metric bc it will tend to be high just when the two vectors have large values in the same dimensions\n  - If vectors have zeros in different dimensions (orthogonal vectors): dot product will be 0, representing strong dissimilarity\n  - However, favors long vectors: must use normalized dot product which is the same as the cosine of the angle between the two vectors\n  - Can pre-normalize vectors by dividing it by its length: unit vector of length 1\n    - For unit vectors: dot product = cosine\n- Cosine value ranges from 1 for those pointing in same direction through 0 for orthogonal vectors and -1 for vectors pointing in opposite directions\n\n\n## SLP Chapter 6.8 Word2vec\n\n- Embeddings: short, dense vectors\n  - Short: Dimensions range from 50-1000 instead of vocab size or # of documents\n  - Dense: values will be real-valued numbers that can be negative\n- Works better in every NLP task than sparse vectors\n  - Model learns far fewer weights\n  - Small param space possibly helps with generalization\n  - Also better at capturing synonymy\n- One method for computing embeddings: skip-gram with negative sampling (word2vec)\n  - Fast, efficient to train and easily available online with code and pretrained embeddings\n  - Static embeddings: the method learns one fixed embedding for each word in the vocabulary\n- Embeddings answer the question: \"Is word w likely to show up near 'apricot'?\"\n  - Can just use running text as implicitly supervised training data\n    - Self-supervision: avoids need for any sort of hand-labeled supervision signal\n- Word2vec is much simpler than neural nets:\n  - Simplifies task by making it binary classification instead of word prediction\n  - Simplifies architecture by using logistic regression instead of multi-layer NN\n- Intuition of skip-gram:\n  - Treat target word and a neighboring context word as positive examples\n  - Randomly sample other words in the lexicon to get negative samples\n  - Use logistic regression to train a classifier to distinguish those two cases\n  - Use learned weights as embeddings\n- How does classifier compute probability P(+ | w,c)?\n  - Skip-gram model bases probability on embedding similarity: word is likely to occur near the target if its embedding is similar to the target embedding\n  - Take dot product of word and context and pass through sigmoid to get probability\n  - Makes simplifying assumption that all context words are independent, so can multiply probabilities\n- Skip-gram learns embeddings by starting with random embedding vectors and then iteratively shifting the embedding of each word w to be more like the embeddings of words that occur nearby in texts and less like the embeddings of words that don't occur nearby\n- Need to generate k negative samples for each positive example (tune k) using noise words: random word from lexicon constrained not to be the target word w\n- Other static embedding: fasttext deals with unknown words and sparsity in languages with rich morphology by using subword models\n- GloVe is based on ratios of probabilities from the word-word co-occurrence matrix, combining the intuitions of count-based models like PPMI while also capturing the linear structures using methods like word2vec\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n- One param of vector semantic models: size of context window (generally bc 1 and 10 words on each side of target word)\n  - Choice depends on goals of preresentation\n    - Shorter context windows tend to lead to representations that are more syntactic, since info is coming from immediately nearby words\n      - Most similar words to a target word w tend to be semantically similar words with the same parts of speech\n    - Longer context sindows: highest cosine words to a target word w tend to be words that are topically related but not similar\n- Distinguish two kinds of similarity of association between words\n  - Two words have first-order co-occurrence (syntagmatic association) if they are typically nearby each other (i.e. for wrote: book or poem)\n  - Two words have second-order co-occurrence (paradigmatic association) if they have similar neighbors (i.e. for wrote: said or remarked)\n- Another semantic property of embeddings: ability to capture relational meanings\n  - Parallelogram method: generally too simple to model the human cognitive process of forming analogies of this kind\n\n\n## SLP Chapter 6.11 Bias & Embeddings\n\n- Embeddings can also reproduce the implicit biases and stereotypes that were latent in the text\n- Allocational harm: when a system allocates resources unfairly to different groups\n- Amplify bias: gendered terms become more gendered in embedding space than they were in the input text statistics\n- Also encode implicit associations that are a property of human reasoning\n- Representational harm: when a system demeans or even ignores some social groups\n- Can fix by developing a transformation of the embedding space that removes gender stereotypes but preserves definitional gender or changing training procedure\n- Debiasing may reduce bias in embeddings, they do not eliminate\n- Also can evaluate biases in historical texts\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n- Most important eval metric: extrinsic evaluation\n- Still useful to have intrinsic evaluations\n  - Most common metric is to test their performance on similarity: computing the correlation between an alg's word similarity scores and word similarity ratings assigned by humans\n- All embedding algs suffer from inherent variability\n\n\n## Module 14 Lecture Notes\n\n- Neural language models have several advantages over n-gram LMs:\n  - They don't need smoothing\n  - They can handle much longer histories\n  - They can generalize over contexts of similar words\n  - Neural LMs tend to have much higher predictive accuracy than n-grams LMs\n- Disadvantage: slower to train than traditional n-gram LMs\n- Neural LMs\n  - Associate each word in the vocab with a vector-representation, thereby creating a notion of similarity between words\n  - Express the joint probability fn of a word sequence in terms of the word vectors for the words in that sequence\n  - Simultaneously learn the word vectors and the parameters of the function\n- Input to NN is a k-gram of words w1:k\n- Output: probability distribution over the next word\n- k context words: treated as word window\n  - Each word is associated with an embedding vector\n  - Input vector x just concatenates v(w) for each of k words\n- Training examples: word k-grams from the corpus\n- Advantages of NN LMs\n  - Better results: achieve better perplexity scores than SOTA n-gram LMs\n  - Larger N: NN LMs can scale to much larger orders of n. This is achievable bc params are associated only with individual words and not with n-grams\n  - They generalize across contexts\n- By-product of training are word embeddings\n- LM Goal: learn a function that returns the joint probability\n  - Primary difficulty\n    - Too many params to accurately estimate (curse of dimensionality)\n    - In n-gram-based models, we fail to generalize to related words / word sequences that we have observed\n- Unseen sequences: basically want to stitch together short sequences of observed words\n  - Back-off\n  - Smoothing / interpolation\n- TF-IDF: term frequency - inverse document frequency\n  - Term frequency: how often a word occurred in a document\n  - Inverse document frequency: 1 / # of documents that it occurred in\n- To get dense vectors:\n  - Treat target word and neighboring context word as positive examples\n  - Randomly sample other words in the lexicon to get negative samples\n  - Use logistic regression to train a classifier to distinguish those two cases\n  - Use the weights as the embeddings\n- Choosing noise words\n  - Can pick according to their unigram frequency P(w)\n  - More common to choose accord to p\n- Evaluating embeddings\n  - Compare to human scores on word similarity-type tasks:\n    - WordSim-353 (Finkelstein et al., 2002)\n    - SimLex-999 (Hill et al., 2015)\n    - Stanford Contextual Word Similarity (SCWS) dataset (Huang et al., 2012)\n    - TOEFL dataset: “levied” is closest in meaning to: (a) imposed, (b) believed, (c) requested, (d) correlated \n\n\n## Module 14 Definitions\n* **Lexical semantics** - linguistic study of word meaning\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}