{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521 Midterm II Notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b4e1be13-8943-4c63-dc12-3d24ffdb488c"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5ad6f325-8412-4509-e330-aabd3d038937"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "Begin with an agent that nees to make a decision.\n",
        "- Agent has actions a\n",
        "- Agent assigns probability P(s) to each state s\n",
        "- May be uncertainty about action outcomes\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') = ∑_s P(s)P(s′|s,a)\n",
        "Decision theory deals with choosing among actions based on the desirability of their immediate outcomes\n",
        "(the environment is assumed to be __episodic__).\n",
        "Agent's preferences are catured by a __utility function__ U(s).\n",
        "The expected utility EU(a) is the average utility value of the outcomes weighted by the probability that\n",
        "the outcome occurs: EU(a) = ∑_s'P(RESULT(a)=s′)U(s′).\n",
        "MEU prinicple formalizes the general notion that an intelligent agent should \"do the right thing\" but\n",
        "does not tell us how -> estimating the probability distribution P(s) over possible states\n",
        "requires perception, learning, knowledge representation, and inference.\n",
        "\"\"\"\n",
        "chapter16_2 =  \"\"\"\n",
        "Why is maximizing average utility so special? What's wrong with an agent that tries to minimize the worst possible loss?\n",
        "- A ≻ B the agent prefers A over B.\n",
        "- A ∼ B the agent is indifferent between A and B.\n",
        "- A ≻∼ B the agent prefers A over B or is indifferent between them.\n",
        "- What sorts of things are A and B? --> could be states of the world, but there is often uncertainty.\n",
        "- The set of outcomes for each action is a lottery L with outcomes S_1, ... ,S_n that occur with probabilities p_1,...,p_n\n",
        "is written L = [p1,S1; p2,S2; ... pn,Sn].\n",
        "  - Each outcome S_i can be an atomic state or another lottery\n",
        "  - Primary issue for utility theory is how to understand preferences between complex lotteries, so we list six constraints\n",
        "  (called the __axioms of utility theory__) that we require any reasonable preference relation to obey:\n",
        "    - __Orderability__: Exactly one of (A≻B),(B≻A),or(A∼B)holds.\n",
        "    - __Transitivity__: (A≻B)∧(B≻C) ⇒ (A≻C).\n",
        "    - __Continuity__: If some lottery B is between A and C in preference, then there is some probability p \n",
        "    for which teh rational agent will be indifferent between getting B for sure and the lottery \n",
        "    that yields A with p and C with 1-p. A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B.\n",
        "    - __Substitutability__: A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]. Also holds if we substitute ≻ for ∼\n",
        "    - __Monotonicity__: A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]).\n",
        "    - __Decomposability__: Compound lotteries can be reduced to simpler ones using laws of\n",
        "    probability. [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C].\n",
        "- We can derive from the axioms of utility theory the following consequences:\n",
        "  - __Existence of Utility Function__: There exists a function U such that U(A)>U(B) ⇔ A≻B and U(A)=U(B) ⇔ A∼B.\n",
        "  - __Expected Utility of a Lottery__: The utility of a lottery is the sum of the probability of each outcome: U([p1,S1;...;pn,Sn])=∑_ipiU(Si).\n",
        "- An agent's behavior would not change if utility function U(S) were transformed according to U′(S)=aU(S)+b, where a and b are constants and a > 0;\n",
        "  a positive affine transformation\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "Utility functions map from lotteries to real numbers.\n",
        "- __preference elicitation__: presenting choices to the human an using the observed preferences to pin down the underlying utility function\n",
        "- We fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible catastrophe” at U (S) = u⊥ \n",
        "- __Normalized utilities__: use a scale with u⊥ = 0 and u⊤ = 1\n",
        "- We can assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery [ p, u⊤ ; (1 − p), u⊥ ]\n",
        "  - The probability p is adjusted until the agent is indifferent between S and the standard lottery\n",
        "- __micromort__: a one in a million chance of death, used in medical and safety analysis\n",
        "  - in the UK, driving in a car for 230 miles incurs a risk of one micromort\n",
        "Example: You win 1,000,000 prize and you can gamble it with the flip of a coin: heads you get nothing, tails you get 2,500,000.\n",
        "- The __expected monetary value (EMV)__ is 1/2 (0) + 1/2 (2,500,000) = 1,250,000 which is more than the original 1,000,000\n",
        "- Utility is not directly proportional to monetary value\n",
        "- Found that the utility of money was almost exactly proportional to the logarithm of the amount\n",
        "- Agents with utility curves with decreasing slopes are __risk-averse__\n",
        "- The difference between the EMV of a lottery and its certainty equivalent is called the __insurance premium__\n",
        "- Agents with linear curve is said to be __risk-neutral__\n",
        "- Rational way to choose the best action, a* is to maximize expected utility: a* = argmax EU(a)\n",
        "  - We are usually estimating EU though, but we are assuming that the estimates are __unbiased__, meaning the expected\n",
        "  value of the error E(EU(a)−EU(a)) is zero\n",
        "  - The real outcome will usually be significantly worse than we estimated --> tendenceny for the estimated expected utility\n",
        "  to be too high is called the __optimizer's curse__\n",
        "  - Calculate the distribution of the maximum of k estimates (this calc is a special case of computing an __order statistic__, the\n",
        "  distribution of any particular ranked element of a sample)\n",
        "\n",
        "- Decision theory is a __normative theory__: it describes how a rational agent SHOULD act\n",
        "- __Descriptive theory__ describes how actual agents (i.e. humans) really do act\n",
        "- __Certainty effect__ people are strongly attracted to gains that are certain\n",
        "- __Ambiguity aversion__: Most people elect the known probability rather than the unknown unknowns\n",
        "- __Framing effect__: Exact wording of a decision problem can have a big impact on the agent's choices\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "- Transition model with stochastic outcome is written as P(s'|s,a) for the probability reaching state s' if action a is done in state s,\n",
        "also written as T(s,a,s')\n",
        "- __Markovian__: the probability of reaching s' from s depends only on s and not on the history of earlier states\n",
        "- Since the decision problem is sequential, the utility function will depend on a sequence of states and actions, an __environment history__\n",
        "- Agent receives a __reward__ R(s,a,s') for every transition from s to s' via a\n",
        "- Methods for solving Markov Decision Problems usually involve dynamic programming\n",
        "- A solution to the problem:\n",
        "  - Must specify what the agent should do for any state that the agent might reach, a __policy__ π, where π(s) is the recommended\n",
        "  policy for state s\n",
        "  - The quality of a policy is measured by the expected utility of the possible environment histories generated by that policy\n",
        "  - __optimal policy__ π* yields the highest expected utility\n",
        "- __finite horizon__: there is a fixed time N after which nothing matters, a policy that depends on the time is called __nonstationary__\n",
        "- __discount factor__ γ is a number between 0 and 1, describes the preference of an agent for current rewards over future rewards\n",
        "  - γ close to 0 means rewards in the distance future are viewed as insignificant\n",
        "  - γ close to 1 means an agent is more willing to wait for long-term rewards\n",
        "- __proper policy__: a policy that is guaranteed to reach a terminal state\n",
        "- The true utility of a state is U^π∗ (s), the expected sum of discounted rewards if the agent executes an optimal policy\n",
        "Utility of a state is __the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses\n",
        "the optimal action__: \n",
        "  - U(s)= max ∑_s'P(s′|s,a)[R(s,a,s′)+γU(s′)].\n",
        "- __Q-function__: Q(s,a) is the expected utility of taking a given action in a given state. U(s) = max Q(s, a)\n",
        "  - The optimal policy can be extracted from Q as follows: π∗(s) = argmax_a Q(s,a)\n",
        "  - Bellman equation for Q: \n",
        "    - Q(s,a) = ∑P(s′ |s,a)[R(s,a,s′)+γ U(s′)]\n",
        "    - Q(s,a) = ∑P(s′ |s,a)[R(s,a,s′)+γ maxQ(s′,a′)]\n",
        "\n",
        "- R′(s,a,s′)=mR(s,a,s′)+b transformation leaves the optimal policy unchanged in an MDP\n",
        "  - Let Φ(s) be any function of the state s, then according to __shaping theorem__, the following transformation\n",
        "  leaves the optimal policy unchanged: R′(s,a,s′) = R(s,a,s′)+γΦ(s′)−Φ(s)\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "Four different algorithms for solving MDPs: __value iteration, policy iteration, linear programming__ (exact solutions), and __Monte Carlo planning__ \n",
        "(approximate algorithms).\n",
        "- __Value Iteration__: if there are n possible states, then there are n Bellman equations\n",
        "```\n",
        "function VALUE-ITERATION(mdp, ǫ) returns a utility function\n",
        "  repeat\n",
        "    U←U′; δ←0\n",
        "    for each state s in S do\n",
        "      U′[s]←maxa∈A(s) Q-VALUE(mdp,s,a,U)\n",
        "      if |U′[s] − U[s]| > δ then δ←|U′[s] − U[s]| \n",
        "    until δ ≤ ǫ(1−γ)/γ\n",
        "    return U\n",
        "```\n",
        "  - Iteration step, called a __Bellman update__: Ui+1(s)← max ∑P(s′|s,a)[R(s,a,s′)+γUi(s′)]\n",
        "  - Guaranteed to reach an equilibrium\n",
        "  - After i iterations of value iteration, the agent has an estimate U_i of the true utility U and obtains the MEU policy\n",
        "  based on one-step look-ahead using U_i\n",
        "- __Policy interation__: if one action is clearly better than all others, then the exact utilities on the states need not be precise, policy\n",
        "iteration alternates the following two steps:\n",
        "  - __Policy evaluation__: given π_i, calculate U_i=U^π_i, the utility of each state if π_i were to be executed\n",
        "  - __Policy improvement__: Calculate a new MEU policy π_i+1, using one-step look-ahead based on Ui\n",
        "```\n",
        "function POLICY-ITERATION(mdp) returns a policy\n",
        "repeat\n",
        "  U ← POLICY-EVALUATION(π, U, mdp) unchanged?←true\n",
        "  for each state s in S do\n",
        "    a∗ ← argmax_a∈A(s) Q-VALUE(mdp, s, a, U) \n",
        "    if Q-VALUE(mdp,s,a∗,U) > Q-VALUE(mdp,s,π[s],U)then π[s]←a∗; \n",
        "      unchanged?←false\n",
        "  until unchanged? \n",
        "  return π\n",
        "```\n",
        "  - Implementing policy iteration is easier than standard Bellman:\n",
        "    - Ui+1(s) ← ∑P(s′ |s,πi(s))[R(s,πi(s),s′)+γUi(s′)]\n",
        "- __Linear programming__: consider as variables in the LP the utilities U(s) of each state s, noting that the utilities\n",
        "for an optimal policy are the highest utilities attainable\n",
        "  - Seek to minimize U(s) for all s: U(s) ≥ ∑P(s′ |s,a)[R(s,a,s′)+γU(s′)] for every state s and every action a\n",
        "- __Real-time dynamic programming (RTDP): can work well with moderate-size to larger domains (Tetris)\n",
        "\n",
        "\"\"\"\n",
        "  \n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "- __Markovian__ transition: probability of arriving in s' depends only on s and not the history of earlier states\n",
        "Markov Decision Problem (MDP):\n",
        "- sequential decision problem\n",
        "- fully observable environment\n",
        "- stohcastic transition model\n",
        "- additive rewards\n",
        "- one way to solve in expectimax search\n",
        "- the solution to an MDP is a policy\n",
        "- performance = sum of rewards\n",
        "To find a solution to an MDP, you need to define the following things:\n",
        "- A set of states s in S\n",
        "- A set of actions a in A\n",
        "- A transition function T(s,a,s')\n",
        "  - This probability is called __the model__\n",
        "- A reward function R(s,a,s')\n",
        "- An initial state s_0\n",
        "- Optionally, one or more __terminal states__\n",
        "The __discount__ is how much we are willing to postpone immediate gratification\n",
        "To make a game not last forever:\n",
        "- discounting\n",
        "- __finite horizon__: terminate after a fixed T steps\n",
        "- __absorbing state__: guarantee that with each policy, a terminal state will be reached\n",
        "Optimal Quantities:\n",
        "- V*(s) = value (utility) of a state s, expected utility of starting in s and acting optimally\n",
        "- Q*(s,a) = value (utility) of a q-state (s,a), expected utility of starting out having taken action a from state s and acting optimally\n",
        "\n",
        "V*(s) = max_a Q*(s,a) --> taking the max over all possible actions from s\n",
        "Q*(s,a) = ∑_s' T(s,a,s')[R(s,a,s') + γV*(s')]\n",
        "V*(s) = max_a ∑_s' T(s,a,s')[R(s,a,s') + γV*(s')]\n",
        "\n",
        "__Value Iteration Algorithm__\n",
        "- Start with V_0(s) = 0\n",
        "- Given a vector fo V_k(s) values, do one ply of expectimax from each state:\n",
        "  - V_k+1 (s) = max_a ∑_s' T(s,a,s')[R(s,a,s') + γV_k(s')]\n",
        "- Repeat until convergence\n",
        "- Complexity is O(S^2A)\n",
        "- Theorem: will converge to unique optimal values\n",
        "__Policy Evaluation__\n",
        "- Expectimax trees max over all actions to compute the optimal values --> if we fixed some policy π(s), then the tree would be simpler -\n",
        "only one action per state\n",
        "- Steps:\n",
        "  - Turn recursive Bellman equations into updates (like value iteration)\n",
        "    - V_0^π(s) = 0\n",
        "    - V_k+1^π(s) = ∑_s' T(s,π(s),s')[R(s,π(s),s') + γV^π_k(s')]\n",
        "- Without the maxes, the Bellman equations are just a linear system\n",
        "- O(S^2) per iteration\n",
        "- __Policy extraction__: a mini-expectimax (one step): π^*(s) = argmax_a ∑_s' T(s,a,s')[R(s,a,s') + γV*_k(s')]\n",
        "- If we have the optimal q-values, then policy improvement: π^*(s) = argmax_a Q*(s,a)\n",
        "Comparison of value iteration and policy iteration:\n",
        "- Value iteration:\n",
        "  - Every iteration updates both values and implictly the policy\n",
        "  - We don't track the policy, but taking the max over actions implicitly recomptues it\n",
        "- Policy iteration\n",
        "  - Several passes that update utilities with fixed policy\n",
        "  - After the policy is evaluated, a new policy is chosen\n",
        "  - The new policy will be better (or we're done)\n",
        "\n",
        "__Utilities__ are functions from outcomes (states of the world) to real numbers that describe an agent's preferences\n",
        "- An agent must have preferences among:\n",
        "  - Prizes: A, B, etc\n",
        "  - Lotteries: situations with uncertain prizes: L = [p, A; (1-p), B]\n",
        "- __Maximum expected utility (MEU) principle__:\n",
        "  - Choose the action that maximizes expected utility\n",
        "\n",
        "__Markov property__: Given the present state, the future and past are independent.\n",
        "Which of the following is unnecessary to construct a dynamic Bayesian model (DBN)?: Multiple state and evidence variables\n",
        "(The sensor model, transition model, and prior distribution over the state variables are necessary)\n",
        "  \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"agent's preferences\",\n",
        "\"expected utility\" : \"EU(a), average utility value of the outcomes\",\n",
        "\"maximum expected utility (MEU)\": \"rational agent should choose the action that maximizes agent's EU\",\n",
        "\"sequential decision problems\": \"agent's utility depends on a sequence of decisions\",\n",
        "\"dynamic decision networks (DDNs)\": \"factored representations to represents MDPs by extending dynamic Bayesian networks\",\n",
        "\"contraction\": \"basic concept used to show that value iteration converges\",\n",
        "\"online algorithm\": \"agent does a significant amount of computation at each decision point\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "784038ce-84e4-400b-8371-7e90753a5288"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nBegin with an agent that nees to make a decision.\n- Agent has actions a\n- Agent assigns probability P(s) to each state s\n- May be uncertainty about action outcomes\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') = ∑_s P(s)P(s′|s,a)\nDecision theory deals with choosing among actions based on the desirability of their immediate outcomes\n(the environment is assumed to be __episodic__).\nAgent's preferences are catured by a __utility function__ U(s).\nThe expected utility EU(a) is the average utility value of the outcomes weighted by the probability that\nthe outcome occurs: EU(a) = ∑_s'P(RESULT(a)=s′)U(s′).\nMEU prinicple formalizes the general notion that an intelligent agent should \"do the right thing\" but\ndoes not tell us how -> estimating the probability distribution P(s) over possible states\nrequires perception, learning, knowledge representation, and inference.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nWhy is maximizing average utility so special? What's wrong with an agent that tries to minimize the worst possible loss?\n- A ≻ B the agent prefers A over B.\n- A ∼ B the agent is indifferent between A and B.\n- A ≻∼ B the agent prefers A over B or is indifferent between them.\n- What sorts of things are A and B? --> could be states of the world, but there is often uncertainty.\n- The set of outcomes for each action is a lottery L with outcomes S_1, ... ,S_n that occur with probabilities p_1,...,p_n\nis written L = [p1,S1; p2,S2; ... pn,Sn].\n  - Each outcome S_i can be an atomic state or another lottery\n  - Primary issue for utility theory is how to understand preferences between complex lotteries, so we list six constraints\n  (called the __axioms of utility theory__) that we require any reasonable preference relation to obey:\n    - __Orderability__: Exactly one of (A≻B),(B≻A),or(A∼B)holds.\n    - __Transitivity__: (A≻B)∧(B≻C) ⇒ (A≻C).\n    - __Continuity__: If some lottery B is between A and C in preference, then there is some probability p \n    for which teh rational agent will be indifferent between getting B for sure and the lottery \n    that yields A with p and C with 1-p. A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B.\n    - __Substitutability__: A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]. Also holds if we substitute ≻ for ∼\n    - __Monotonicity__: A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]).\n    - __Decomposability__: Compound lotteries can be reduced to simpler ones using laws of\n    probability. [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C].\n- We can derive from the axioms of utility theory the following consequences:\n  - __Existence of Utility Function__: There exists a function U such that U(A)>U(B) ⇔ A≻B and U(A)=U(B) ⇔ A∼B.\n  - __Expected Utility of a Lottery__: The utility of a lottery is the sum of the probability of each outcome: U([p1,S1;...;pn,Sn])=∑_ipiU(Si).\n- An agent's behavior would not change if utility function U(S) were transformed according to U′(S)=aU(S)+b, where a and b are constants and a > 0;\n  a positive affine transformation\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n\nUtility functions map from lotteries to real numbers.\n- __preference elicitation__: presenting choices to the human an using the observed preferences to pin down the underlying utility function\n- We fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible catastrophe” at U (S) = u⊥ \n- __Normalized utilities__: use a scale with u⊥ = 0 and u⊤ = 1\n- We can assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery [ p, u⊤ ; (1 − p), u⊥ ]\n  - The probability p is adjusted until the agent is indifferent between S and the standard lottery\n- __micromort__: a one in a million chance of death, used in medical and safety analysis\n  - in the UK, driving in a car for 230 miles incurs a risk of one micromort\nExample: You win 1,000,000 prize and you can gamble it with the flip of a coin: heads you get nothing, tails you get 2,500,000.\n- The __expected monetary value (EMV)__ is 1/2 (0) + 1/2 (2,500,000) = 1,250,000 which is more than the original 1,000,000\n- Utility is not directly proportional to monetary value\n- Found that the utility of money was almost exactly proportional to the logarithm of the amount\n- Agents with utility curves with decreasing slopes are __risk-averse__\n- The difference between the EMV of a lottery and its certainty equivalent is called the __insurance premium__\n- Agents with linear curve is said to be __risk-neutral__\n- Rational way to choose the best action, a* is to maximize expected utility: a* = argmax EU(a)\n  - We are usually estimating EU though, but we are assuming that the estimates are __unbiased__, meaning the expected\n  value of the error E(EU(a)−EU(a)) is zero\n  - The real outcome will usually be significantly worse than we estimated --> tendenceny for the estimated expected utility\n  to be too high is called the __optimizer's curse__\n  - Calculate the distribution of the maximum of k estimates (this calc is a special case of computing an __order statistic__, the\n  distribution of any particular ranked element of a sample)\n\n- Decision theory is a __normative theory__: it describes how a rational agent SHOULD act\n- __Descriptive theory__ describes how actual agents (i.e. humans) really do act\n- __Certainty effect__ people are strongly attracted to gains that are certain\n- __Ambiguity aversion__: Most people elect the known probability rather than the unknown unknowns\n- __Framing effect__: Exact wording of a decision problem can have a big impact on the agent's choices\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- Transition model with stochastic outcome is written as P(s'|s,a) for the probability reaching state s' if action a is done in state s,\nalso written as T(s,a,s')\n- __Markovian__: the probability of reaching s' from s depends only on s and not on the history of earlier states\n- Since the decision problem is sequential, the utility function will depend on a sequence of states and actions, an __environment history__\n- Agent receives a __reward__ R(s,a,s') for every transition from s to s' via a\n- Methods for solving Markov Decision Problems usually involve dynamic programming\n- A solution to the problem:\n  - Must specify what the agent should do for any state that the agent might reach, a __policy__ π, where π(s) is the recommended\n  policy for state s\n  - The quality of a policy is measured by the expected utility of the possible environment histories generated by that policy\n  - __optimal policy__ π* yields the highest expected utility\n- __finite horizon__: there is a fixed time N after which nothing matters, a policy that depends on the time is called __nonstationary__\n- __discount factor__ γ is a number between 0 and 1, describes the preference of an agent for current rewards over future rewards\n  - γ close to 0 means rewards in the distance future are viewed as insignificant\n  - γ close to 1 means an agent is more willing to wait for long-term rewards\n- __proper policy__: a policy that is guaranteed to reach a terminal state\n- The true utility of a state is U^π∗ (s), the expected sum of discounted rewards if the agent executes an optimal policy\nUtility of a state is __the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses\nthe optimal action__: \n  - U(s)= max ∑_s'P(s′|s,a)[R(s,a,s′)+γU(s′)].\n- __Q-function__: Q(s,a) is the expected utility of taking a given action in a given state. U(s) = max Q(s, a)\n  - The optimal policy can be extracted from Q as follows: π∗(s) = argmax_a Q(s,a)\n  - Bellman equation for Q: \n    - Q(s,a) = ∑P(s′ |s,a)[R(s,a,s′)+γ U(s′)]\n    - Q(s,a) = ∑P(s′ |s,a)[R(s,a,s′)+γ maxQ(s′,a′)]\n\n- R′(s,a,s′)=mR(s,a,s′)+b transformation leaves the optimal policy unchanged in an MDP\n  - Let Φ(s) be any function of the state s, then according to __shaping theorem__, the following transformation\n  leaves the optimal policy unchanged: R′(s,a,s′) = R(s,a,s′)+γΦ(s′)−Φ(s)\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nFour different algorithms for solving MDPs: __value iteration, policy iteration, linear programming__ (exact solutions), and __Monte Carlo planning__ \n(approximate algorithms).\n- __Value Iteration__: if there are n possible states, then there are n Bellman equations\n```\nfunction VALUE-ITERATION(mdp, ǫ) returns a utility function\n  repeat\n    U←U′; δ←0\n    for each state s in S do\n      U′[s]←maxa∈A(s) Q-VALUE(mdp,s,a,U)\n      if |U′[s] − U[s]| > δ then δ←|U′[s] − U[s]| \n    until δ ≤ ǫ(1−γ)/γ\n    return U\n```\n  - Iteration step, called a __Bellman update__: Ui+1(s)← max ∑P(s′|s,a)[R(s,a,s′)+γUi(s′)]\n  - Guaranteed to reach an equilibrium\n  - After i iterations of value iteration, the agent has an estimate U_i of the true utility U and obtains the MEU policy\n  based on one-step look-ahead using U_i\n- __Policy interation__: if one action is clearly better than all others, then the exact utilities on the states need not be precise, policy\niteration alternates the following two steps:\n  - __Policy evaluation__: given π_i, calculate U_i=U^π_i, the utility of each state if π_i were to be executed\n  - __Policy improvement__: Calculate a new MEU policy π_i+1, using one-step look-ahead based on Ui\n```\nfunction POLICY-ITERATION(mdp) returns a policy\nrepeat\n  U ← POLICY-EVALUATION(π, U, mdp) unchanged?←true\n  for each state s in S do\n    a∗ ← argmax_a∈A(s) Q-VALUE(mdp, s, a, U) \n    if Q-VALUE(mdp,s,a∗,U) > Q-VALUE(mdp,s,π[s],U)then π[s]←a∗; \n      unchanged?←false\n  until unchanged? \n  return π\n```\n  - Implementing policy iteration is easier than standard Bellman:\n    - Ui+1(s) ← ∑P(s′ |s,πi(s))[R(s,πi(s),s′)+γUi(s′)]\n- __Linear programming__: consider as variables in the LP the utilities U(s) of each state s, noting that the utilities\nfor an optimal policy are the highest utilities attainable\n  - Seek to minimize U(s) for all s: U(s) ≥ ∑P(s′ |s,a)[R(s,a,s′)+γU(s′)] for every state s and every action a\n- __Real-time dynamic programming (RTDP): can work well with moderate-size to larger domains (Tetris)\n\n\n\n## Module 8 Lecture Notes\n\n- __Markovian__ transition: probability of arriving in s' depends only on s and not the history of earlier states\nMarkov Decision Problem (MDP):\n- sequential decision problem\n- fully observable environment\n- stohcastic transition model\n- additive rewards\n- one way to solve in expectimax search\n- the solution to an MDP is a policy\n- performance = sum of rewards\nTo find a solution to an MDP, you need to define the following things:\n- A set of states s in S\n- A set of actions a in A\n- A transition function T(s,a,s')\n  - This probability is called __the model__\n- A reward function R(s,a,s')\n- An initial state s_0\n- Optionally, one or more __terminal states__\nThe __discount__ is how much we are willing to postpone immediate gratification\nTo make a game not last forever:\n- discounting\n- __finite horizon__: terminate after a fixed T steps\n- __absorbing state__: guarantee that with each policy, a terminal state will be reached\nOptimal Quantities:\n- V*(s) = value (utility) of a state s, expected utility of starting in s and acting optimally\n- Q*(s,a) = value (utility) of a q-state (s,a), expected utility of starting out having taken action a from state s and acting optimally\n\nV*(s) = max_a Q*(s,a) --> taking the max over all possible actions from s\nQ*(s,a) = ∑_s' T(s,a,s')[R(s,a,s') + γV*(s')]\nV*(s) = max_a ∑_s' T(s,a,s')[R(s,a,s') + γV*(s')]\n\n__Value Iteration Algorithm__\n- Start with V_0(s) = 0\n- Given a vector fo V_k(s) values, do one ply of expectimax from each state:\n  - V_k+1 (s) = max_a ∑_s' T(s,a,s')[R(s,a,s') + γV_k(s')]\n- Repeat until convergence\n- Complexity is O(S^2A)\n- Theorem: will converge to unique optimal values\n__Policy Evaluation__\n- Expectimax trees max over all actions to compute the optimal values --> if we fixed some policy π(s), then the tree would be simpler -\nonly one action per state\n- Steps:\n  - Turn recursive Bellman equations into updates (like value iteration)\n    - V_0^π(s) = 0\n    - V_k+1^π(s) = ∑_s' T(s,π(s),s')[R(s,π(s),s') + γV^π_k(s')]\n- Without the maxes, the Bellman equations are just a linear system\n- O(S^2) per iteration\n- __Policy extraction__: a mini-expectimax (one step): π^*(s) = argmax_a ∑_s' T(s,a,s')[R(s,a,s') + γV*_k(s')]\n- If we have the optimal q-values, then policy improvement: π^*(s) = argmax_a Q*(s,a)\nComparison of value iteration and policy iteration:\n- Value iteration:\n  - Every iteration updates both values and implictly the policy\n  - We don't track the policy, but taking the max over actions implicitly recomptues it\n- Policy iteration\n  - Several passes that update utilities with fixed policy\n  - After the policy is evaluated, a new policy is chosen\n  - The new policy will be better (or we're done)\n\n__Utilities__ are functions from outcomes (states of the world) to real numbers that describe an agent's preferences\n- An agent must have preferences among:\n  - Prizes: A, B, etc\n  - Lotteries: situations with uncertain prizes: L = [p, A; (1-p), B]\n- __Maximum expected utility (MEU) principle__:\n  - Choose the action that maximizes expected utility\n\n__Markov property__: Given the present state, the future and past are independent.\nWhich of the following is unnecessary to construct a dynamic Bayesian model (DBN)?: Multiple state and evidence variables\n(The sensor model, transition model, and prior distribution over the state variables are necessary)\n  \n \n\n## Module 8 Definitions\n* **Utility function** - agent's preferences\n* **Expected utility** - EU(a), average utility value of the outcomes\n* **Maximum expected utility (meu)** - rational agent should choose the action that maximizes agent's EU\n* **Sequential decision problems** - agent's utility depends on a sequence of decisions\n* **Dynamic decision networks (ddns)** - factored representations to represents MDPs by extending dynamic Bayesian networks\n* **Contraction** - basic concept used to show that value iteration converges\n* **Online algorithm** - agent does a significant amount of computation at each decision point\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" \n",
        "- one-armed bandit = slot machine\n",
        "- __n-armed bandit__ has n levers\n",
        "  - which of n possible new treatments to try to cure a disease, which of n possible investments to put part of your savings into\n",
        "- tradeoff between __exploitation__ and __exploration__\n",
        "- __bandit problems__:\n",
        "  - each arm M_i is a __Markov reward process__ or MRP (an MDP with only one possible action a_i)\n",
        "  - has states S_i, transition model P_i(s'|s,a), reward R_i(s,a_i,s')\n",
        "  - arms are independent\n",
        "- __Bernoulli bandit__: each arm M_i produces a reward of 0 or 1 with a fixed but unknown probability μ_i\n",
        "  - The state of arm Mi is defined by s_i and f_i, the counts of successes (1s) and failures (0s) so far for that arm; the transition probability predicts the next \n",
        "  outcome to be 1 with probability (s_i)/(s_i + f_i) and 0 with probability (f_i)/(s_i + f_i)\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "__Reinforcement learning__: agent interacts with the world and periodically receives __rewards__\n",
        "- Want to maximize the expected sum of rewards\n",
        "- Differs from \"just solving an MDP\" because the agent is not given the MDP, the agent is IN the MDP\n",
        "  - May not know the transition model or the reward function\n",
        "- Win/loss rewards for chess are __sparse__ because for the vast majority of states, this is not an informative signal at all\n",
        "-\n",
        "Variety of approaches to reinforcement learning:\n",
        "- __Model-based reinforcement learning__: agent uses transition model, model may be initially unknown, often learn a __utility function__ U(s) as\n",
        "defined in Chapter 17 as sum of rewards from state s onward\n",
        "- __Model-free reinforcement learning__: Agent neither knows nor learns a transition model, instead, it learns a more direct representation of how to behave:\n",
        "  - __Action-utility learning__: Agent learns a __q-function__ denoting the sum of rewards from state s onward if action a is taken\n",
        "  - __Policy search__: The agent learns a policy π(s) that maps directly from states to actions. This is a __reflex agent__\n",
        " \"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "Start with simple case offully observable environment with a small number of actions and states, in which an agent already has a \n",
        "fixed policy π(s) that determines its actions. The agent is trying to learn the utility function U^π(s), the expected total discounted\n",
        "reward if policy π is executed beginning in state s. This is called a __passive learning agent__.\n",
        "- Passive learning task is similar to __policy evaluation__ from 17.2.2. But now the passive learning agent does not know the transition model P(s'|s,a)\n",
        "- __Direct utility estimation__: the utility of a state is defined as the expected total reward from that state onward (called the expected __reward-to-go__)\n",
        "  - Each example is a (state, reward-to-go) pair --> the utility of a state is determined by the reward and the expected utility of the successor states\n",
        "  - Utility values obey the Bellman equations for a fixed policy:  U_i(s) = ∑_s'P(s′|s,πi(s))[R(s,πi(s),s′)+γUi(s′)].\n",
        "- __Adaptive dynamic programming__: takes advantage of the constraints among the utilities of states by learning the transition model that connects them\n",
        "and solving the corresponding Markov decision process using DP\n",
        "  - We adopt a __modified policy iteration__ using a simplified value iteration process to update the utility estimates after each change to the learned model\n",
        "- __Temporal-difference learning__: Uπ(s)←Uπ(s)+α[R(s,π(s),s′)+γUπ(s′)−Uπ(s)]\n",
        "  - Adjust the utility estimates toward the ideal equilibrium that holds locally when the utility estimates are correct\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "A passive learning agent has a fixed policy that determines its behavior. An __active learning agent__ gets to decide what actions to take.\n",
        "- Needs to learn a complete transition model with outcome probabilities for all actions, rather than just the model for the fixed policy\n",
        "- The utilities it needs to learn are those defined by the _optimal policy_; they obey the Bellman equations\n",
        "- The agent does not learn the true utilities or the true optimal policy!\n",
        "- Agent must make a tradeoff between exploitation of the current best action to maximize its short-term reward and exploration of previously\n",
        "unknown states to gain information that can lead to a change in policy (and to greater rewards in the future)\n",
        "- A __GLIE__ scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed\n",
        "  - One simple GLIE scheme is to have the agent choose a random action at time step t with probability 1/t and to follow the \n",
        "  greedy policy otherwise\n",
        "- Real-world we can't just choose to randomly explore\n",
        "  - hoose a policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, \n",
        "  even if the policy happens to be suboptimal for the maximum-likelihood model. Approaches:\n",
        "    - __Bayesian reinforcement learning__: assumes a prior probability P(h) over hypotheses h about what the true model is; the posterior probability P(h|e) \n",
        "    is obtained in the usual way by Bayes’ rule given the observations to date\n",
        "      - π∗ = argmax ∑_h P(h|e) U_h^π \n",
        "    - __Robust control theory__: allows for a set of possible models H without assigning probabilities to them, \n",
        "    and defines an optimal robust policy as one that gives the best outcome in the worst case over H\n",
        "      - π∗ = argmax(min U_h^π) \n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "Solving MDPs is __offline planning__:\n",
        "- Determine all quantities through computation\n",
        "- Need to know the details of the MDP\n",
        "- Do not need to actually play the game!\n",
        "__Online planning__ is when we do NOT know the probabilities! Still an MDP, just can't solve through computation.\n",
        "- This is __reinforcement learning__:\n",
        "  - __Exploration__:  you have to try unknown actions to get information\n",
        "  - __Exploitation__: eventually, you have to use what you know\n",
        "  - __Regret__: even if you learn intelligently, you make mistakes\n",
        "  - __Sampling__ : because of chance, you have to try things repeatedly\n",
        "  - __Difficulty__: learning can be much harder than solving a known MDP\n",
        "- Since reinforcement learning is still a MDP:\n",
        "  - A set of states s ∈ S\n",
        "  - A set of actions (per state) A\n",
        "  - A model T(s,a,s’)\n",
        "  - A reward function R(s,a,s’)\n",
        "  - Still looking for a policy π(s)\n",
        "  - Twist: We do not know T or R, we need to try actions and states to learn\n",
        "__Model-Based Learning__: Learn an approximate model based on experiences, and 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 and 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\n",
        "    - For example, use value iteration, as before\n",
        "__Model-Free Learning__: Compare results of an action to what we thought was going to happen to what did happen. When something deviates, we adjust values up and down.\n",
        "We just keep track of values of states.\n",
        "- __Passive Reinforcement Learning__\n",
        "  - Simplified task: policy evaluation\n",
        "  - Input: a fixed policy π(s)\n",
        "  - You don’t know the transitions T(s,a,s’)\n",
        "  - You don’t know the rewards R(s,a,s’)\n",
        "  - Goal: learn the state values. Note: this is NOT offline planning since we actually take actions in the world\n",
        "  - __Direct evaluation__: Compute values for each state under π\n",
        "    - Idea: Average together observed sample values (Act according to π. Every time you visit a state, write down what the sum of discounted \n",
        "     rewards turned out to be. Average those samples)\n",
        "      - REMEMBER: The value of being in a state is from that point TO THE END\n",
        "    - Pros of direct evaluation:\n",
        "      - It’s easy to understand\n",
        "      - It doesn’t require any knowledge of T, R\n",
        "      - It eventually computes the correct average values, using just sample transitions\n",
        "    - Cons of direct evaluation:\n",
        "      - It wastes information about state connections\n",
        "      - Each state must be learned separately\n",
        "      - So, it takes a long time to learn\n",
        "    - So can we use __policy evaluation__? We would need T and R!\n",
        "    - What about __sample-based policy evaluation__?\n",
        "      - We want to improve our estimate of V by computing these averages:\n",
        "        - V^π_(k+1)(s) = ∑_s' T(s, π(s), s')[R(s, π(s), s') + γV^π_k(s')]\n",
        "      - We do this by taking samples of outcomes s' and average\n",
        "        - sample_1 = R(s,π(s),s_1')+ γV^π_k(s_1')\n",
        "        - V^π_(k+1)(s) = 1/n ∑_i sample_i\n",
        "  - __Temporal Difference Learning__: learn from every experience (instead of waiting for the end)!\n",
        "    - Update V(s) each time we experience a transition (s, a, s’, r)\n",
        "    - 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",
        "    - Sample of V(s): sample = R(s,π(s),s')+ γV^π_k(s')\n",
        "    - Update to V(s): V^π(s) = (1-a)V^π(s)+ (a)sample\n",
        "      - a (alpha) is a value we get to set, it tells us how much our sample should update the value\n",
        "      - This is the same as V^π(s) = V^π(s)+ a(sample - V^π(s))\n",
        "    - __Exponential moving average__\n",
        "      - The running interpolation update: (bar on top) x_n = (1-a)x_(n-1)+ax_n\n",
        "      - Makes recent samples more important!\n",
        "      - Forgets about the past (distant past values were wrong anyway)\n",
        "    - Problems with temporal difference value learning:\n",
        "      - TD value leaning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages\n",
        "      - However, if we want to turn values into a (new) policy, we’re sunk\n",
        "        - π(s) = argmax_s Q(s,a)\n",
        "      - Idea: learn Q-values, not values!\n",
        "- __Active Reinforcement Learning (Q-Learning)__: full reinforcement learning: optimal policies (like value iteration)\n",
        "  - We can choose the actions now\n",
        "  - Goal: learn the optimal policy/values\n",
        "  - Learner makees the choices!\n",
        "  - Fundamental tradeoff: exploration vs. exploitation\n",
        "  - NOT offline planning: we take actions in the world and find out what happens\n",
        "  - __Q-Value Iteration__:\n",
        "    - For value iteration: start with V_0(s) = 0, which we know is right and calculate V_(k+1)(s) = max_a  ∑_s' T(s, a, s')[R(s, a, s') + γV_k(s')]\n",
        "    - For Q-value iteration: Start with Q_0(s,a) = 0, which we know is right\n",
        "      - Given Q)k, calculate the depth k+1 q-values for all q-states: Q_(k+1)(s,a) = ∑_s' T(s, a, s')[R(s, a, s') + γmax_a' Q_k(s',a')]\n",
        "  - __Q-Learning__: instead of Q-value iteration, we're going to do it based on SAMPLEs that we learn\n",
        "    - Learn Q(s,a) values as you go\n",
        "      - Samples (s,a,s',r)\n",
        "      - Consider old estimate: Q(s,a)\n",
        "      - Consider new sample estimate: sample = R(s,a,s')+γmax_a' Q_k(s',a')\n",
        "      - Incorporate the new estimate into a running average: Q(s,a) = (1-a)Q(s,a) + a[sample]\n",
        "      - Amazing result: __Q-learning converges to optimal policy__, even if you're acting suboptimally!\n",
        "      - This is called __off-policy learning__\n",
        "      - Caveats: \n",
        "        - You have to explore enough\n",
        "        - You have to eventually make the learning rate small enough, but not decrease it too quickly\n",
        "        - Basically, in the limit, it doesn’t matter how you select actions (!)\n",
        "- How do we explore? We have several schemes for forcing exploration\n",
        "  - Simplest: __random actions (ε-greedy):\n",
        "    - With (small) probability ε, act randomly\n",
        "    - With (large) probability 1-ε, act on current policy\n",
        "    - Problems: We do eventually explore the space, but keep thrashing (pick things repeatedly that are bad) around once learning is done\n",
        "      - One solution: lower ε over time\n",
        "      - Another solution: exploration fucntions\n",
        "  - __Exploration function__: Takes a value estimate u (current utility estimate) and a visit count n (# of times we've visited that state), \n",
        "  and returns an optimistic utility, e.g f(u,n) = u + k/n, k is a bonus for exploring a state\n",
        "    - Modified Q-update: Q(s,a) = R(s,a,s')+γmax_a'f(Q(s',a'), N(s',a'))\n",
        "__Regret__ is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n",
        "- __Approximate Q-Learning__: In realistic situations, we cannot possibly learn about every single state! Too many states to visit all, too many states to hold q-tables in memory\n",
        "  - Instead, we want to generalize: learn about some small number of training states from experience\n",
        "  - Flashback: __evaluation functions__ score non-terminals in depth-limited search\n",
        "    - Ideal function: returns the actual minimax value of the position\n",
        "    - In practice: typically weighted linear sum of features:\n",
        "      - Eval(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)\n",
        "        e.g. f_1(s) = (num white queens - num black queens)\n",
        "  - __Linear value functions__: Using a feature representation, we can write a q function (or value function) for any state using a few weights\n",
        "    - V(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)\n",
        "    - Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a) + ... + w_nf_n(s,a)\n",
        "    - Advantage: our experience is summed up in a few powerful numbers\n",
        "    - Disadvantage: states may share features but actually be very different in value!\n",
        "  - EQUATION for Approximate Q-Learning: Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a) + ... + w_nf_n(s,a)\n",
        "  - Given a transition (s,a,r,s'), what is the difference = [r+γmax_a' Q(s',a')]-Q(s,a)\n",
        "    - Q(s,a) = Q(s,a) + a[difference] is Exact Q's\n",
        "    - w_i = w_i + a[difference]f_i(s,a) is Approximate Q's\n",
        "      - So APPROXIMATE Q-learning is us updating the WEIGHTs\n",
        "    - Intuitive interpretation: Adjust weights of active features. e.g., if something unexpectedly bad happens, blame the features that were on:\n",
        "    disprefer all states with that state’s features\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Gittins index\" : \"provides simple optimal policy for any bandit problem\",\n",
        "\"Thompson sampling\": \"chooses an arm randomly according to the prob. that the arm is optimal given the samples so far\",\n",
        "\"bandit superprocess (BSP)\": \"each arm is a full Markov decision process rather than being a Markov reward process (w/ only one action)\",\n",
        "\"dominating policy\": \"by addings actions to states, we can always create a relaxed version of an MDP\",\n",
        "\"prioritized sweeping heuristic\": \"ranks possible adjustments in TD learning to prefer adjustments to states whose likely successors have just undergone a large adjustment in their utility estimates\",\n",
        "\"greedy agent\": \"greedily takes the action that it currently believes to be optimal at each step\",\n",
        "\"GLIE\": \"Greedy in the limit of infinite exploration\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1909f353-7245-434c-ec07-32ec5e774527"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \n- one-armed bandit = slot machine\n- __n-armed bandit__ has n levers\n  - which of n possible new treatments to try to cure a disease, which of n possible investments to put part of your savings into\n- tradeoff between __exploitation__ and __exploration__\n- __bandit problems__:\n  - each arm M_i is a __Markov reward process__ or MRP (an MDP with only one possible action a_i)\n  - has states S_i, transition model P_i(s'|s,a), reward R_i(s,a_i,s')\n  - arms are independent\n- __Bernoulli bandit__: each arm M_i produces a reward of 0 or 1 with a fixed but unknown probability μ_i\n  - The state of arm Mi is defined by s_i and f_i, the counts of successes (1s) and failures (0s) so far for that arm; the transition probability predicts the next \n  outcome to be 1 with probability (s_i)/(s_i + f_i) and 0 with probability (f_i)/(s_i + f_i)\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n__Reinforcement learning__: agent interacts with the world and periodically receives __rewards__\n- Want to maximize the expected sum of rewards\n- Differs from \"just solving an MDP\" because the agent is not given the MDP, the agent is IN the MDP\n  - May not know the transition model or the reward function\n- Win/loss rewards for chess are __sparse__ because for the vast majority of states, this is not an informative signal at all\n-\nVariety of approaches to reinforcement learning:\n- __Model-based reinforcement learning__: agent uses transition model, model may be initially unknown, often learn a __utility function__ U(s) as\ndefined in Chapter 17 as sum of rewards from state s onward\n- __Model-free reinforcement learning__: Agent neither knows nor learns a transition model, instead, it learns a more direct representation of how to behave:\n  - __Action-utility learning__: Agent learns a __q-function__ denoting the sum of rewards from state s onward if action a is taken\n  - __Policy search__: The agent learns a policy π(s) that maps directly from states to actions. This is a __reflex agent__\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nStart with simple case offully observable environment with a small number of actions and states, in which an agent already has a \nfixed policy π(s) that determines its actions. The agent is trying to learn the utility function U^π(s), the expected total discounted\nreward if policy π is executed beginning in state s. This is called a __passive learning agent__.\n- Passive learning task is similar to __policy evaluation__ from 17.2.2. But now the passive learning agent does not know the transition model P(s'|s,a)\n- __Direct utility estimation__: the utility of a state is defined as the expected total reward from that state onward (called the expected __reward-to-go__)\n  - Each example is a (state, reward-to-go) pair --> the utility of a state is determined by the reward and the expected utility of the successor states\n  - Utility values obey the Bellman equations for a fixed policy:  U_i(s) = ∑_s'P(s′|s,πi(s))[R(s,πi(s),s′)+γUi(s′)].\n- __Adaptive dynamic programming__: takes advantage of the constraints among the utilities of states by learning the transition model that connects them\nand solving the corresponding Markov decision process using DP\n  - We adopt a __modified policy iteration__ using a simplified value iteration process to update the utility estimates after each change to the learned model\n- __Temporal-difference learning__: Uπ(s)←Uπ(s)+α[R(s,π(s),s′)+γUπ(s′)−Uπ(s)]\n  - Adjust the utility estimates toward the ideal equilibrium that holds locally when the utility estimates are correct\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nA passive learning agent has a fixed policy that determines its behavior. An __active learning agent__ gets to decide what actions to take.\n- Needs to learn a complete transition model with outcome probabilities for all actions, rather than just the model for the fixed policy\n- The utilities it needs to learn are those defined by the _optimal policy_; they obey the Bellman equations\n- The agent does not learn the true utilities or the true optimal policy!\n- Agent must make a tradeoff between exploitation of the current best action to maximize its short-term reward and exploration of previously\nunknown states to gain information that can lead to a change in policy (and to greater rewards in the future)\n- A __GLIE__ scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed\n  - One simple GLIE scheme is to have the agent choose a random action at time step t with probability 1/t and to follow the \n  greedy policy otherwise\n- Real-world we can't just choose to randomly explore\n  - hoose a policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, \n  even if the policy happens to be suboptimal for the maximum-likelihood model. Approaches:\n    - __Bayesian reinforcement learning__: assumes a prior probability P(h) over hypotheses h about what the true model is; the posterior probability P(h|e) \n    is obtained in the usual way by Bayes’ rule given the observations to date\n      - π∗ = argmax ∑_h P(h|e) U_h^π \n    - __Robust control theory__: allows for a set of possible models H without assigning probabilities to them, \n    and defines an optimal robust policy as one that gives the best outcome in the worst case over H\n      - π∗ = argmax(min U_h^π) \n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\nSolving MDPs is __offline planning__:\n- Determine all quantities through computation\n- Need to know the details of the MDP\n- Do not need to actually play the game!\n__Online planning__ is when we do NOT know the probabilities! Still an MDP, just can't solve through computation.\n- This is __reinforcement learning__:\n  - __Exploration__:  you have to try unknown actions to get information\n  - __Exploitation__: eventually, you have to use what you know\n  - __Regret__: even if you learn intelligently, you make mistakes\n  - __Sampling__ : because of chance, you have to try things repeatedly\n  - __Difficulty__: learning can be much harder than solving a known MDP\n- Since reinforcement learning is still a MDP:\n  - A set of states s ∈ S\n  - A set of actions (per state) A\n  - A model T(s,a,s’)\n  - A reward function R(s,a,s’)\n  - Still looking for a policy π(s)\n  - Twist: We do not know T or R, we need to try actions and states to learn\n__Model-Based Learning__: Learn an approximate model based on experiences, and 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 and 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\n    - For example, use value iteration, as before\n__Model-Free Learning__: Compare results of an action to what we thought was going to happen to what did happen. When something deviates, we adjust values up and down.\nWe just keep track of values of states.\n- __Passive Reinforcement Learning__\n  - Simplified task: policy evaluation\n  - Input: a fixed policy π(s)\n  - You don’t know the transitions T(s,a,s’)\n  - You don’t know the rewards R(s,a,s’)\n  - Goal: learn the state values. Note: this is NOT offline planning since we actually take actions in the world\n  - __Direct evaluation__: Compute values for each state under π\n    - Idea: Average together observed sample values (Act according to π. Every time you visit a state, write down what the sum of discounted \n     rewards turned out to be. Average those samples)\n      - REMEMBER: The value of being in a state is from that point TO THE END\n    - Pros of direct evaluation:\n      - It’s easy to understand\n      - It doesn’t require any knowledge of T, R\n      - It eventually computes the correct average values, using just sample transitions\n    - Cons of direct evaluation:\n      - It wastes information about state connections\n      - Each state must be learned separately\n      - So, it takes a long time to learn\n    - So can we use __policy evaluation__? We would need T and R!\n    - What about __sample-based policy evaluation__?\n      - We want to improve our estimate of V by computing these averages:\n        - V^π_(k+1)(s) = ∑_s' T(s, π(s), s')[R(s, π(s), s') + γV^π_k(s')]\n      - We do this by taking samples of outcomes s' and average\n        - sample_1 = R(s,π(s),s_1')+ γV^π_k(s_1')\n        - V^π_(k+1)(s) = 1/n ∑_i sample_i\n  - __Temporal Difference Learning__: learn from every experience (instead of waiting for the end)!\n    - Update V(s) each time we experience a transition (s, a, s’, r)\n    - 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    - Sample of V(s): sample = R(s,π(s),s')+ γV^π_k(s')\n    - Update to V(s): V^π(s) = (1-a)V^π(s)+ (a)sample\n      - a (alpha) is a value we get to set, it tells us how much our sample should update the value\n      - This is the same as V^π(s) = V^π(s)+ a(sample - V^π(s))\n    - __Exponential moving average__\n      - The running interpolation update: (bar on top) x_n = (1-a)x_(n-1)+ax_n\n      - Makes recent samples more important!\n      - Forgets about the past (distant past values were wrong anyway)\n    - Problems with temporal difference value learning:\n      - TD value leaning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages\n      - However, if we want to turn values into a (new) policy, we’re sunk\n        - π(s) = argmax_s Q(s,a)\n      - Idea: learn Q-values, not values!\n- __Active Reinforcement Learning (Q-Learning)__: full reinforcement learning: optimal policies (like value iteration)\n  - We can choose the actions now\n  - Goal: learn the optimal policy/values\n  - Learner makees the choices!\n  - Fundamental tradeoff: exploration vs. exploitation\n  - NOT offline planning: we take actions in the world and find out what happens\n  - __Q-Value Iteration__:\n    - For value iteration: start with V_0(s) = 0, which we know is right and calculate V_(k+1)(s) = max_a  ∑_s' T(s, a, s')[R(s, a, s') + γV_k(s')]\n    - For Q-value iteration: Start with Q_0(s,a) = 0, which we know is right\n      - Given Q)k, calculate the depth k+1 q-values for all q-states: Q_(k+1)(s,a) = ∑_s' T(s, a, s')[R(s, a, s') + γmax_a' Q_k(s',a')]\n  - __Q-Learning__: instead of Q-value iteration, we're going to do it based on SAMPLEs that we learn\n    - Learn Q(s,a) values as you go\n      - Samples (s,a,s',r)\n      - Consider old estimate: Q(s,a)\n      - Consider new sample estimate: sample = R(s,a,s')+γmax_a' Q_k(s',a')\n      - Incorporate the new estimate into a running average: Q(s,a) = (1-a)Q(s,a) + a[sample]\n      - Amazing result: __Q-learning converges to optimal policy__, even if you're acting suboptimally!\n      - This is called __off-policy learning__\n      - Caveats: \n        - You have to explore enough\n        - You have to eventually make the learning rate small enough, but not decrease it too quickly\n        - Basically, in the limit, it doesn’t matter how you select actions (!)\n- How do we explore? We have several schemes for forcing exploration\n  - Simplest: __random actions (ε-greedy):\n    - With (small) probability ε, act randomly\n    - With (large) probability 1-ε, act on current policy\n    - Problems: We do eventually explore the space, but keep thrashing (pick things repeatedly that are bad) around once learning is done\n      - One solution: lower ε over time\n      - Another solution: exploration fucntions\n  - __Exploration function__: Takes a value estimate u (current utility estimate) and a visit count n (# of times we've visited that state), \n  and returns an optimistic utility, e.g f(u,n) = u + k/n, k is a bonus for exploring a state\n    - Modified Q-update: Q(s,a) = R(s,a,s')+γmax_a'f(Q(s',a'), N(s',a'))\n__Regret__ is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n- __Approximate Q-Learning__: In realistic situations, we cannot possibly learn about every single state! Too many states to visit all, too many states to hold q-tables in memory\n  - Instead, we want to generalize: learn about some small number of training states from experience\n  - Flashback: __evaluation functions__ score non-terminals in depth-limited search\n    - Ideal function: returns the actual minimax value of the position\n    - In practice: typically weighted linear sum of features:\n      - Eval(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)\n        e.g. f_1(s) = (num white queens - num black queens)\n  - __Linear value functions__: Using a feature representation, we can write a q function (or value function) for any state using a few weights\n    - V(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)\n    - Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a) + ... + w_nf_n(s,a)\n    - Advantage: our experience is summed up in a few powerful numbers\n    - Disadvantage: states may share features but actually be very different in value!\n  - EQUATION for Approximate Q-Learning: Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a) + ... + w_nf_n(s,a)\n  - Given a transition (s,a,r,s'), what is the difference = [r+γmax_a' Q(s',a')]-Q(s,a)\n    - Q(s,a) = Q(s,a) + a[difference] is Exact Q's\n    - w_i = w_i + a[difference]f_i(s,a) is Approximate Q's\n      - So APPROXIMATE Q-learning is us updating the WEIGHTs\n    - Intuitive interpretation: Adjust weights of active features. e.g., if something unexpectedly bad happens, blame the features that were on:\n    disprefer all states with that state’s features\n \n\n## Module 9 Definitions\n* **Gittins index** - provides simple optimal policy for any bandit problem\n* **Thompson sampling** - chooses an arm randomly according to the prob. that the arm is optimal given the samples so far\n* **Bandit superprocess (bsp)** - each arm is a full Markov decision process rather than being a Markov reward process (w/ only one action)\n* **Dominating policy** - by addings actions to states, we can always create a relaxed version of an MDP\n* **Prioritized sweeping heuristic** - ranks possible adjustments in TD learning to prefer adjustments to states whose likely successors have just undergone a large adjustment in their utility estimates\n* **Greedy agent** - greedily takes the action that it currently believes to be optimal at each step\n* **Glie** - Greedy in the limit of infinite exploration\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"\n",
        "- To make choices, an agent must first have preferences among the different possible outcomes of the various plans.\n",
        "- We use utility theory to represent preferences and reason quantitatively with them\n",
        "- __Decision theory__: Decision theory = probability theory + utility theory\n",
        "- Principle of __maximum expected utility (MEU)__: _an agent is rational if and only if it chooses the action that yields the highest \n",
        "expected utility, averaged over all the possible outcomes of the action_\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "- Conditional probability: P(a|b) = P(a∧b)/P(b) OR  P(a∧b) = P(a|b)P(b) .\n",
        "- __Probability density functions__ (sometimes called pdfs) differ in meaning from discrete distributions\n",
        "  - Saying that the probability density is uniform from 18C to 26C means that there is a 100% chance that the temperature \n",
        "  will fall somewhere in that 8C-wide region and a 50% chance that it will fall in any 4C-wide sub-region, and so on\n",
        "- __Joint probability distribution__: distributions on multiple variables\n",
        "- __inclusion–exclusion principle__: P(a∨b) = P(a)+P(b)−P(a∧b)\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "- __marginalization__: P(Y) = ∑_z P(Y,Z=z),\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\"\n",
        "- __independence__: P(X |Y)=P(X) or P(Y |X)=P(Y) or P(X,Y)=P(X)P(Y)\n",
        " \"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "- __Bayes' rule__: P(Y|X)= P(X|Y)P(Y) / P(X)\n",
        "- __Conditional independence__: P(X,Y|Z) = P(X|Z)P(Y|Z)\n",
        "  - P(X|Y,Z)=P(X|Z) and P(Y|X,Z)=P(Y|Z)\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "- Commonly occurring pattern in which a single cause directly \n",
        "influences a number of effects, all of which are conditionally independent, given the cause. The full joint distribution can be written as\n",
        "  - P(Cause,Effect_1,...,Effect_n) = P(Cause)∏P(Effect_i|Cause)\n",
        "- This probability distribution is called a __naive Bayes__ model\n",
        "  - Sometimes called a __Bayesian classifier__\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\"\n",
        "Let’s begin with the task of computing P(w|h), the probability of a word w given\n",
        "some history h.\n",
        "Now how can we compute probabilities of entire sequences like P(w1,w2,...,wn)?\n",
        "One thing we can do is decompose this probability using the chain rule of probability:\n",
        "- P(X1...Xn) = P(X1)P(X2|X1)P(X3|X1:2)...P(Xn|X1:n−1) \n",
        "The bigram model, for example, approximates the probability of a word given\n",
        "all the previous words P(wn|w1:n−1) by using only the conditional probability of the\n",
        "preceding word P(wn|wn−1) --> this is a __Markov__ assumption\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "The best way to evaluate the performance of a language model is to embed it in\n",
        "an application and measure how much the application improves. Such end-to-end\n",
        "evaluation is called __extrinsic evaluation__. An __intrinsic evaluation__ metric is one that measures \n",
        "the quality of a model independent of any application. \n",
        "- __perplexity__ can be thought of as the __weighted average branching factor of a language__.\n",
        " \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "To keep a language model from assigning\n",
        "zero probability to these unseen events, we’ll have to shave off a bit of probability\n",
        "mass from some more frequent events and give it to the events we’ve never seen.\n",
        "__smoothing__. This modification is called __smoothing__ or __discounting__.\n",
        "The simplest way to do smoothing is to add one to all the n-gram counts, before\n",
        "we normalize them into probabilities. All the counts that used to be zero will now\n",
        "have a count of 1, the counts of 1 will be 2, and so on. This algorithm is called\n",
        "__Laplace smoothing__. \n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "__Uncertainty__:\n",
        "- __Observed variables (evidence)__: Agent knows certain things about the state of the world (e.g.,\n",
        "sensor readings or symptoms)\n",
        "- __Unobserved variables (states)__: Agent needs to reason about other aspects (e.g. where an object\n",
        "is or what disease is present)\n",
        "- __Model__: Agent knows something about how the known variables relate to the unknown variables\n",
        "__Axioms of Probability__:\n",
        "- 0 <= P(w) <= 1 for every w\n",
        "- ∑_(w in Omega) P(w) = 1\n",
        "__Joint Distributions__:\n",
        "- A joint distribution over a set of random variables: X_1, X_2,...,X_n specifies a real number for each assignment (or outcome): \n",
        "- A probabilistic model is a joint distribution over a set of random variables\n",
        "- Joint distributions: say whether assignments (outcomes) are likely\n",
        "__Events__: an event is a set E of outcomes\n",
        "__Marginal Distributions__: Marginal distributions are sub-tables which eliminate variables\n",
        "- Marginalization (summing out): Combine collapsed rows by adding\n",
        "  - P(t) = ∑_s P(t,s)\n",
        "__Conditional Distributions__:\n",
        "- Conditional distributions are probability distributions over some variables given fixed values of others (i.e. P(W|T=hot))\n",
        "__Probabilistic inference__: compute a desired probability from other known probabilities (e.g. conditional from joint)\n",
        "- Probabilities change with new evidence\n",
        "- Inference by enumeration, general case, we split our random variables into 3 sets of things:\n",
        "  - Evidence variables E_1...E_k = e_1...e_k\n",
        "  - Query* variable: Q (things we care about)\n",
        "  - Hidden variables H_1...H_r (things that occur in our big joint probability, not things we've observed or are actively reasoning about)\n",
        "  - We want: P(Q|e_1...e_k)\n",
        "  - Step 1: Select the entries consistent with the evidence\n",
        "  - Step 2: Sum out H to get joint of query and evidence\n",
        "    - If we had a,b,c, we would have ∑_b P(a,b,c) = P(a,c) (if b is the hidden variable)\n",
        "  - Step 3: Normalize (x 1/Z)\n",
        "- __Product Rule__: P(y)P(x|y) = P(x,y)\n",
        "  - More generally, __chain rule__: P(x_1,x_2,...,x_n) = product from i to n of (P(x_i| x_1...x_i-1))\n",
        "- __Bayes' Rule__: P(x|y) = P(y|x)P(x)/P(y)\n",
        "__Probabilistic Language Models__\n",
        "- Assign a probability to a sentence (autocomplete for texting, machine translation, spelling correction, speech recognition)\n",
        "  - Goal: Compute probability of a sequence of words: P(W) = P(w_1,w_2,...,w_n)\n",
        "  - Related task: compute probability of an upcoming word: P(w_5|w_1,w_2,w_3,w_4)\n",
        "  - Example: P(\"the underdog Philadelphia Eagles won\") = P(the) x P(underdog|the) x P(Philadelphia| the underdog) x P(Eagles| the underdog Philadelphia) x P(won|the underdog Philadelphia Eagles)\n",
        "  - How to estimate these probabilities? __Maximum likelihood estimation (MLE)__\n",
        "    - P(won|the underdog team) = Count(the underdog team won) / Count(the underdog team)\n",
        "    - Problem: some sentences never appear in the sample, so we're limited by data constraints\n",
        "  - So we use a simplifying assupmtion: __Markov Assumption__! The probability of moving to next state only depends on the current state\n",
        "    - So we're saying that P(won|the underdog team) approx equals P(won|team)\n",
        "    - Only depends on previous k words, not the whole context (example above is k=1)\n",
        "    - unigram = no history, bigram = 1 word as history, trigram = 2 words as history, 4-gram = 3 words as history\n",
        "    - __Bigram model__: Condition on the previous word: P(w_i|w_1w_2...w_i-1) approx equals P(w_i|w_i-1)\n",
        "      - Maximum likelihood estimate: P(w_i|w_i-1) = count(w_i-1, w_i)/count(w_i-1)\n",
        "\n",
        "How many ways are there to apply the chain rule to a joint distribution with NN random variables? N!\n",
        "\n",
        "How are n-gram language models typically evaluated? (Perplexity on a test set)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"belief state\" : \"a representation of the set of all possible world states that an agent might be in\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "aa539d21-5e8f-4266-da6d-3b553764019e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- To make choices, an agent must first have preferences among the different possible outcomes of the various plans.\n- We use utility theory to represent preferences and reason quantitatively with them\n- __Decision theory__: Decision theory = probability theory + utility theory\n- Principle of __maximum expected utility (MEU)__: _an agent is rational if and only if it chooses the action that yields the highest \nexpected utility, averaged over all the possible outcomes of the action_\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- Conditional probability: P(a|b) = P(a∧b)/P(b) OR  P(a∧b) = P(a|b)P(b) .\n- __Probability density functions__ (sometimes called pdfs) differ in meaning from discrete distributions\n  - Saying that the probability density is uniform from 18C to 26C means that there is a 100% chance that the temperature \n  will fall somewhere in that 8C-wide region and a 50% chance that it will fall in any 4C-wide sub-region, and so on\n- __Joint probability distribution__: distributions on multiple variables\n- __inclusion–exclusion principle__: P(a∨b) = P(a)+P(b)−P(a∧b)\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- __marginalization__: P(Y) = ∑_z P(Y,Z=z),\n\n\n## AIMA Chapter 12.4 Independence\n\n- __independence__: P(X |Y)=P(X) or P(Y |X)=P(Y) or P(X,Y)=P(X)P(Y)\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n- __Bayes' rule__: P(Y|X)= P(X|Y)P(Y) / P(X)\n- __Conditional independence__: P(X,Y|Z) = P(X|Z)P(Y|Z)\n  - P(X|Y,Z)=P(X|Z) and P(Y|X,Z)=P(Y|Z)\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- Commonly occurring pattern in which a single cause directly \ninfluences a number of effects, all of which are conditionally independent, given the cause. The full joint distribution can be written as\n  - P(Cause,Effect_1,...,Effect_n) = P(Cause)∏P(Effect_i|Cause)\n- This probability distribution is called a __naive Bayes__ model\n  - Sometimes called a __Bayesian classifier__\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n\nLet’s begin with the task of computing P(w|h), the probability of a word w given\nsome history h.\nNow how can we compute probabilities of entire sequences like P(w1,w2,...,wn)?\nOne thing we can do is decompose this probability using the chain rule of probability:\n- P(X1...Xn) = P(X1)P(X2|X1)P(X3|X1:2)...P(Xn|X1:n−1) \nThe bigram model, for example, approximates the probability of a word given\nall the previous words P(wn|w1:n−1) by using only the conditional probability of the\npreceding word P(wn|wn−1) --> this is a __Markov__ assumption\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nThe best way to evaluate the performance of a language model is to embed it in\nan application and measure how much the application improves. Such end-to-end\nevaluation is called __extrinsic evaluation__. An __intrinsic evaluation__ metric is one that measures \nthe quality of a model independent of any application. \n- __perplexity__ can be thought of as the __weighted average branching factor of a language__.\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n\nTo keep a language model from assigning\nzero probability to these unseen events, we’ll have to shave off a bit of probability\nmass from some more frequent events and give it to the events we’ve never seen.\n__smoothing__. This modification is called __smoothing__ or __discounting__.\nThe simplest way to do smoothing is to add one to all the n-gram counts, before\nwe normalize them into probabilities. All the counts that used to be zero will now\nhave a count of 1, the counts of 1 will be 2, and so on. This algorithm is called\n__Laplace smoothing__. \n\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n__Uncertainty__:\n- __Observed variables (evidence)__: Agent knows certain things about the state of the world (e.g.,\nsensor readings or symptoms)\n- __Unobserved variables (states)__: Agent needs to reason about other aspects (e.g. where an object\nis or what disease is present)\n- __Model__: Agent knows something about how the known variables relate to the unknown variables\n__Axioms of Probability__:\n- 0 <= P(w) <= 1 for every w\n- ∑_(w in Omega) P(w) = 1\n__Joint Distributions__:\n- A joint distribution over a set of random variables: X_1, X_2,...,X_n specifies a real number for each assignment (or outcome): \n- A probabilistic model is a joint distribution over a set of random variables\n- Joint distributions: say whether assignments (outcomes) are likely\n__Events__: an event is a set E of outcomes\n__Marginal Distributions__: Marginal distributions are sub-tables which eliminate variables\n- Marginalization (summing out): Combine collapsed rows by adding\n  - P(t) = ∑_s P(t,s)\n__Conditional Distributions__:\n- Conditional distributions are probability distributions over some variables given fixed values of others (i.e. P(W|T=hot))\n__Probabilistic inference__: compute a desired probability from other known probabilities (e.g. conditional from joint)\n- Probabilities change with new evidence\n- Inference by enumeration, general case, we split our random variables into 3 sets of things:\n  - Evidence variables E_1...E_k = e_1...e_k\n  - Query* variable: Q (things we care about)\n  - Hidden variables H_1...H_r (things that occur in our big joint probability, not things we've observed or are actively reasoning about)\n  - We want: P(Q|e_1...e_k)\n  - Step 1: Select the entries consistent with the evidence\n  - Step 2: Sum out H to get joint of query and evidence\n    - If we had a,b,c, we would have ∑_b P(a,b,c) = P(a,c) (if b is the hidden variable)\n  - Step 3: Normalize (x 1/Z)\n- __Product Rule__: P(y)P(x|y) = P(x,y)\n  - More generally, __chain rule__: P(x_1,x_2,...,x_n) = product from i to n of (P(x_i| x_1...x_i-1))\n- __Bayes' Rule__: P(x|y) = P(y|x)P(x)/P(y)\n__Probabilistic Language Models__\n- Assign a probability to a sentence (autocomplete for texting, machine translation, spelling correction, speech recognition)\n  - Goal: Compute probability of a sequence of words: P(W) = P(w_1,w_2,...,w_n)\n  - Related task: compute probability of an upcoming word: P(w_5|w_1,w_2,w_3,w_4)\n  - Example: P(\"the underdog Philadelphia Eagles won\") = P(the) x P(underdog|the) x P(Philadelphia| the underdog) x P(Eagles| the underdog Philadelphia) x P(won|the underdog Philadelphia Eagles)\n  - How to estimate these probabilities? __Maximum likelihood estimation (MLE)__\n    - P(won|the underdog team) = Count(the underdog team won) / Count(the underdog team)\n    - Problem: some sentences never appear in the sample, so we're limited by data constraints\n  - So we use a simplifying assupmtion: __Markov Assumption__! The probability of moving to next state only depends on the current state\n    - So we're saying that P(won|the underdog team) approx equals P(won|team)\n    - Only depends on previous k words, not the whole context (example above is k=1)\n    - unigram = no history, bigram = 1 word as history, trigram = 2 words as history, 4-gram = 3 words as history\n    - __Bigram model__: Condition on the previous word: P(w_i|w_1w_2...w_i-1) approx equals P(w_i|w_i-1)\n      - Maximum likelihood estimate: P(w_i|w_i-1) = count(w_i-1, w_i)/count(w_i-1)\n\nHow many ways are there to apply the chain rule to a joint distribution with NN random variables? N!\n\nHow are n-gram language models typically evaluated? (Perplexity on a test set)\n\n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states that an agent might be in\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "A Bayesian network is a directed graph in which each node is annotated with quantitative probability information. \n",
        "1. Each node corresponds to a random variable, which may be discrete or continuous.\n",
        "2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to node Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a DAG.\n",
        "3. Each node Xi has associated probability information θ(Xi |Parents(Xi)) that quantifies the effect of the parents on the node using a finite number of __parameters__.\n",
        "The topology of the network (sets of nodes and links) specifies the conditional independence relationships that hold.\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "The __syntax__ of a Bayes net consists of a directed acyclic graph with some local \n",
        "probability information attached to each node. The __semantics__ defines how the syntax corresponds to a \n",
        "joint distribution over the variables of the network. Assume that the Bayes net contains n variables, X1,...,Xn. \n",
        "A generic entry in the joint distribution is then P(X1=x1 ∧...∧Xn=xn), or P(x1,...,xn).\n",
        "Bayes nets defines each entry in the joint distribution as follows:\n",
        "P(x1,...,xn) = ∏^n_(i=1)θ(x_i | parents(X_i))\n",
        "- __Chain rule__: P(x1,...,xn) = P(xn |xn−1,...,x1)P(xn−1 |xn−2,...,x1) ··· P(x2 |x1)P(x1) = ∏^n_(i=1) P(xi|xi−1,...,x1).\n",
        "- Compactness of Bayesian networks is an example of a general proprety of __locally structured (sparse)__ systems\n",
        "- A variable is conditionally independent of all other nodes in the network, given its parents,\n",
        "children, and children’s parents-that is, given its __Markov blanket__.\n",
        "\n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "- __variable elimination algorithm__: works by evaluating expressions in right-to-left order\n",
        "- __singly connected networks or polytrees__: have a particularly nice property:  the time and space complexity of exact inference in \n",
        "polytrees is linear in the size of the network\n",
        "- __multiply connected networks__: variable elimination can have exponential time and space complexity in the worst case, even\n",
        "when the number of parents per node is bounded\n",
        "  - inference in Bayes nets is NP-hard\n",
        "- Using __clustering__ algorithms can help us bring O(n^2) to O(n)\n",
        "  - Idea is to 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",
        "X and Y are independent if for all x, y P(x,y) = P(x)P(y)\\n\n",
        "X and Y are __conditionally indpendent__ given Z if P(x,y|z) = P(x|z)P(y|z)\\n\n",
        "\n",
        "__Common cause__: Y points to X and Y points to Z\n",
        "- P(x,y,z) = P(y)P(x|y)P(z|y)\\n\n",
        "__Common effect__: X and Y point to Z\\n\n",
        "Given a Bayes net, are two variables independent (given some evidence)? I.e. Are X and Y conditionally independent given evidence variables {Z}?\n",
        "- Yes, if X and Y \"d-separated\" by Z\n",
        "- Consider all (undirected) paths from X to Y\n",
        "- No active paths = independence!\\n\n",
        "\n",
        "A path is active if each triple is active:\n",
        "- Causal chain A -> B -> C where B is unobserved (either direction)\n",
        "- Common cause A <- B -> C where B is unobserved\n",
        "- Common effect (aka v-structure) A -> B <- C where B or one of its descendents is observed\\n\n",
        "\n",
        "__D-separation algorithm__\n",
        "- Check all (UNDIRECTED) paths between X_i and X_j\n",
        "  - If one or more active, then independence is NOT guaranteed\n",
        "  - If ALL paths inactive, then independence is guaranteed\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"leak-node\" : \"covers 'miscellaneous causes'\", \n",
        "\"discretization\": \"dividing up the possible values into a fixed set of intervals\",\n",
        "\"nonparametric representation\": \"define the conditional probability implicitly with a collection of instances\",\n",
        "\"hybrid Bayesian network\": \"a network with both discrete and continuous variables\",\n",
        "\"conditional Gaussian\": \"when discrete variables are added as parents (not as children) of continuous variables\",\n",
        "\"expit/inverse logit model\": \"uses the logistic function 1//(1+e^-x) to produce a soft threshold\",\n",
        "\"hidden variables\": \"neither input nor output variables, but essential for structuring the network so it's reasonably sparse\"\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "80d64461-512d-4005-edbe-aaff4f98feeb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\nA Bayesian network is a directed graph in which each node is annotated with quantitative probability information. \n1. Each node corresponds to a random variable, which may be discrete or continuous.\n2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to node Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a DAG.\n3. Each node Xi has associated probability information θ(Xi |Parents(Xi)) that quantifies the effect of the parents on the node using a finite number of __parameters__.\nThe topology of the network (sets of nodes and links) specifies the conditional independence relationships that hold.\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nThe __syntax__ of a Bayes net consists of a directed acyclic graph with some local \nprobability information attached to each node. The __semantics__ defines how the syntax corresponds to a \njoint distribution over the variables of the network. Assume that the Bayes net contains n variables, X1,...,Xn. \nA generic entry in the joint distribution is then P(X1=x1 ∧...∧Xn=xn), or P(x1,...,xn).\nBayes nets defines each entry in the joint distribution as follows:\nP(x1,...,xn) = ∏^n_(i=1)θ(x_i | parents(X_i))\n- __Chain rule__: P(x1,...,xn) = P(xn |xn−1,...,x1)P(xn−1 |xn−2,...,x1) ··· P(x2 |x1)P(x1) = ∏^n_(i=1) P(xi|xi−1,...,x1).\n- Compactness of Bayesian networks is an example of a general proprety of __locally structured (sparse)__ systems\n- A variable is conditionally independent of all other nodes in the network, given its parents,\nchildren, and children’s parents-that is, given its __Markov blanket__.\n\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- __variable elimination algorithm__: works by evaluating expressions in right-to-left order\n- __singly connected networks or polytrees__: have a particularly nice property:  the time and space complexity of exact inference in \npolytrees is linear in the size of the network\n- __multiply connected networks__: variable elimination can have exponential time and space complexity in the worst case, even\nwhen the number of parents per node is bounded\n  - inference in Bayes nets is NP-hard\n- Using __clustering__ algorithms can help us bring O(n^2) to O(n)\n  - Idea is to 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 \nX and Y are independent if for all x, y P(x,y) = P(x)P(y)\n\nX and Y are __conditionally indpendent__ given Z if P(x,y|z) = P(x|z)P(y|z)\n\n\n__Common cause__: Y points to X and Y points to Z\n- P(x,y,z) = P(y)P(x|y)P(z|y)\n\n__Common effect__: X and Y point to Z\n\nGiven a Bayes net, are two variables independent (given some evidence)? I.e. Are X and Y conditionally independent given evidence variables {Z}?\n- Yes, if X and Y \"d-separated\" by Z\n- Consider all (undirected) paths from X to Y\n- No active paths = independence!\n\n\nA path is active if each triple is active:\n- Causal chain A -> B -> C where B is unobserved (either direction)\n- Common cause A <- B -> C where B is unobserved\n- Common effect (aka v-structure) A -> B <- C where B or one of its descendents is observed\n\n\n__D-separation algorithm__\n- Check all (UNDIRECTED) paths between X_i and X_j\n  - If one or more active, then independence is NOT guaranteed\n  - If ALL paths inactive, then independence is guaranteed\n\n\n## Module 11 Definitions\n* **Leak-node** - covers 'miscellaneous causes'\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Nonparametric representation** - define the conditional probability implicitly with a collection of instances\n* **Hybrid bayesian network** - a network with both discrete and continuous variables\n* **Conditional gaussian** - when discrete variables are added as parents (not as children) of continuous variables\n* **Expit/inverse logit model** - uses the logistic function 1//(1+e^-x) to produce a soft threshold\n* **Hidden variables** - neither input nor output variables, but essential for structuring the network so it's reasonably sparse\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "The components of agents include:\n",
        "1. A direct mapping from conditions on the current state to actions.\n",
        "2. A means to infer relevant properties of the world from the percept sequence.\n",
        "3. Information about the way the world evolves and about the results of possible actions\n",
        "4. Utility information indicating the desirability of world states.\n",
        "5. Action-value information indicating the desirability of actions.\n",
        "6. Goals that describe the most desirable states.\n",
        "7. A problem generator, critic, and learning element that enable the system to improve.\n",
        "Three types of __feedback__ that can accompany inputs and determine the three main types of learning:\n",
        "- In __supervised learning__ the agent observes input-output pairs and learns a function that maps from input to output. \n",
        "For example, the inputs could be camera images, each one accompanied by an output saying “bus” or “pedestrian,” etc. \n",
        "An output like this is called a __label__. The agent learns a function that, when given a new image, predicts the appropriate label. \n",
        "In the case of braking actions (component 1 above), an input is the current state (speed and direction of the car, road condition),\n",
        "and an output is the distance it took to stop. In this case a set of output values can be obtained by the agent from its own percepts (after the fact); \n",
        "the environment is the teacher, and the agent learns a function that maps states to stopping distance.\n",
        "- In __unsupervised learning__ the agent learns patterns in the input without any explicit feedback. \n",
        "The most common unsupervised learning task is clustering: detecting poten- tially useful clusters of input examples. \n",
        "For example, when shown millions of images taken from the Internet, a computer vision system can identify a large cluster of \n",
        "similar images which an English speaker would call “cats.”\n",
        "- In __reinforcement learning__ the agent learns from a series of reinforcements: rewards and punishments. \n",
        "For example, at the end of a chess game the agent is told that it has won (a reward) or lost (a punishment). \n",
        "It is up to the agent to decide which of the actions prior to the reinforcement were most responsible for it, \n",
        "and to alter its actions to aim towards more rewards in the future.\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\"\n",
        "The task of __supervised learning__ is: Given a training set of N example input–output pairs (x_1,y_1),(x_2,y_2),...(x_N,y_N),\n",
        "where each pair was generated by an unknown function y=f(x), discover a function h that approximates the true function f.\n",
        "- The function h is called a __hypothesis__ about the world\n",
        "- h is a __model__ of the data, drawn from a model class H, or we can say a function drawn from a function class\n",
        "We call the output y_i the ground truth-the true answer we are asking our model to predict\n",
        "- __exploratory data analysis__: examining the data with statistical tests and visualizations—histograms, \n",
        "scatter plots, box plots—to get a feel for the data, and some insight into what hypothesis space might be appropriate\n",
        "- __consistent hypothesis__: an h such that each x in the training set has h(x ) = y \n",
        "- By __bias__ we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets\n",
        "- a hypothesis is __underfitting__ when it fails to find a pattern in the data\n",
        "Often there is a bias–variance tradeoff: a choice between more complex, low-bias hy- potheses that fit the training data well and simpler, \n",
        "low-variance hypotheses that may gen- eralize better\n",
        "\"\"\"\n",
        " \n",
        "chapter19_3 = \"\"\"\n",
        "A __decision tree__ is a representation of a function that maps a vector of attribute values to a single output value; a “decision.”\n",
        "- A decision tree reaches its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached\n",
        "- The decision tree learning algorithm chooses the attribute with the highest IMPORTANCE\n",
        "  - Importance is measured in terms of __entropy__, the fundamental quantity in information theory\n",
        "    - __Entropy__ = measure of uncertainy of a random variable. More information = less entropy\n",
        "    - Entropy: H(V) = ∑_kP(vk)lg P(vk) = −∑_kP(vk)lg P(vk)\n",
        "    - Rolling die = 2 bits of entropy, flipping a fair coin = 1 bit of entropy\n",
        "- For decision trees, a technique called __decision tree pruning__ combats overfitting \n",
        "  - Start with a full tree\n",
        "  - Look at test node that has only leaf nodes as descendants\n",
        "  - If the test seems irrelevant (detecting only noise), then we eliminate the test, replacing it with a leaf node\n",
        "- Statistical __significance test__: __null hypothesis__ (assume no underlying pattern)\n",
        "Decision trees can be made more widely useful by handling the following complications:\n",
        "- __Missing data__\n",
        "- __Continuous and multivalued input attributes__: better way to deal with this is a __split point__ test, an equality\n",
        "test on the value of an attribute (like Weight > 160)\n",
        "- __Continuous-valued output attribute__: trying to predict a numerical output requires a __regression tree__ rather than a classification\n",
        "tree\n",
        "Decision trees are also __unstable__ in that adding just one new example can change the test at the root, which changes the entire tree\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\"\n",
        "Our goal in machine learning is to select a hypothesis that will optimally fit future examples. To make that precise we need to define “future example” and “optimal fit.”\n",
        "__stationarity assumption__: we assume that each example E_j has the same prior probability distribution: P(E_j) = P(E_j+1)=P(E_j+2)=...\n",
        "and is independent of the previous examples: P(E_j) = P(E_j|E_j-1 E_j-2)\n",
        "- Examples that satisfy these equations are independent and identically distributed or i.i.d.\n",
        "__optimal fit__: the hypothesis that minimizes the __error rate__: the proportion of times that h(x) is not equal to y for an (x,y)\n",
        "example\n",
        "Need three data sets:\n",
        "1. A __training set__ to train candidate models.\n",
        "2. A __validation set__, also known as a __development set__ or dev set, to evaluate the candidate\n",
        "models and choose the best one.\n",
        "3. A __test set__ to do a final unbiased evaluation of the best model.\n",
        "What if we don’t have enough data to make all three of these data sets? We can squeeze more out of the data using a technique called __k-fold cross-validation__.\n",
        "- Each sample serves double duty: as training data and validation data\n",
        "- First split the data into k equal subsets\n",
        "- Then perform k rounds of learning, on each round 1/k of the data are held out as validation set and the remaining are used as training set\n",
        "The extreme is k = n, also known as __leave-one-out cross-validation or LOOCV__.\n",
        "We can think of the task of finding a good hypothesis as two subtasks: __model selection__ chooses a good hypothesis \n",
        "space, and __optimization__ (also called training) finds the best hypothesis within that space\n",
        "__Model selection__:  It takes as argument a learn- ing algorithm, Learner\n",
        "__Bayesian optimization__ treats the task of choosing good hyperparameter values as a machine learning problem in itself.\n",
        "An alternative to __Bayesian optimization__ is __population-based training (PBT)__. PBT starts by using random search to train (in parallel) a population of models, each with different hyperparameter values. Then a second generation of models are trained, \n",
        "but they can choose hyperparameter values based on the successful values from the previous generation, as well as by random mutation, as in genetic algorithms\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\"\n",
        "We now show how to apply PAC learning to a new hypothesis space: __decision lists__. A decision list consists of a series of tests, each of which is a conjunction of literals.\n",
        "If a test succeeds when applied to an example description, the __decision list__ specifies the value to be returned. \n",
        "If the test fails, processing continues with the next test in the list. Decision lists resemble decision trees, but their overall structure is simpler: they branch only in one direction.\n",
        "\"\"\"\n",
        "\n",
        "chapter19_6 = \"\"\"\n",
        "A __univariate linear function__ (a straight line) with input x and output y has the form y=w_1x+ w_0, where w_0 and w_1 are real-valued coefficients to be learned.\n",
        "put y has the form y=w1x+ w0, where w0 and w1 are real-valued coefficients to be learned. \n",
        "We use the letter w because we think of the coefficients as weights; the value of y is changed by changing the relative weight of one term or another.\n",
        "We’ll define w to be the vector ⟨w0,w1⟩, and define the linear function with those weights as h_w(x)=w_1x+w_0.\n",
        "The task of finding the h_w that best fits these data is called __linear regression__.\n",
        "As discussed in Section 4.2 (page 119) we can search through a continuous weight space by incrementally modifying the parameters. \n",
        "There we called the algorithm __hill climbing__, but here we are __minimizing loss, not maximizing gain__, so we will use the term __gradient descent__.\n",
        " \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "In this chapter, we intrdouce the naive Bayes algorithm and apply it to __text categorization__, the task of assigning a label or category to an entire text or document.\n",
        "We focus on one common text categorization task, __sentiment analysis__, the extraction of sentiment.\n",
        "__Spam detection__ is another important commercial application, the binary classification task of assigning an email to one of the two classes spam or not-spam\n",
        "__Multinomial naive Bayes classifier__: a Bayesian classifier that makes a simplifying (naive) assumptino about how the features interact.\n",
        "__Naive bayes assumption__: conditional independence assumption that the probabilities P(f_i|c) are independent given teh class c and can be \n",
        "naively multiplied as follows: P(f_1,f_2,...,f_n|c) = P(f_1|c) x P(f_2|c) x ... x P(f_n|c)\n",
        " \"\"\"\n",
        "slp_chapter4_2 = \"\"\"\n",
        "P(w_i|c) = count(w_i,c)/sum of w in V (count(w,c)) (look in lecture notes!)\n",
        " \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "Classification: given inputs x, predict labels y\n",
        "Examples:\n",
        "- Spam detection (input: document,\n",
        "classes: spam / ham)\n",
        "-  OCR (input: images, classes: characters)\n",
        "- Medical diagnosis (input: symptoms,\n",
        "classes: diseases)\n",
        "-  Automatic essay grading (input: document,\n",
        "classes: grades)\n",
        "- Fraud detection (input: account activity,\n",
        "classes: fraud / no fraud)\n",
        "- Customer service email routing\\n\n",
        "Classification is an important commercial technology/n\n",
        "\n",
        "__Inference for Naive Bayes__:\\n\n",
        "Goal: compute posterior distribution over label variable Y\n",
        "1. Get joint probability of label and evidence for each label\\n\n",
        "  P(Y, f_1...f_n = [P(y_1,f_1...f_n); P(y_2,f_1...f_n); ... ; P(y_k,f_1...f_n)])\n",
        "2. Sum to get probability of evidence\n",
        "3. Normalize by dividing Step 1 by Step 2\\n\n",
        "\n",
        "__General Naive Bayes__\n",
        "What do we need in order to use Naïve Bayes?\n",
        "- Inference method (we just saw this part)\n",
        "  - Start with a bunch of probabilities: P(Y) and the P(Fi\n",
        "|Y) tables\n",
        "  - Use standard inference to compute P(Y|F1…Fn)\n",
        "  - Nothing new here\n",
        "- Estimates of local conditional probability tables\n",
        "  - P(Y), the prior over labels\n",
        "  - P(Fi|Y) for each feature (evidence variable)\n",
        "  - These probabilities are collectively called the parameters of the model and denoted by q\n",
        "  - Up until now, we assumed these appeared by magic, but…\n",
        "  - ... they typically come from training data counts: we’ll look at this soon\\n\n",
        "\n",
        "__Naive Bayes for Text__\n",
        "P(Y, W_1...W_n) = P(Y)Pi_i P(W_i|Y)\n",
        "\n",
        "__Generalization and Overfitting__\n",
        "Relative frequency parameters will overfit the training data!\n",
        "- Just because we never saw a 3 with pixel (15,15) on during training doesn’t mean we won’t\n",
        "see it at test time\n",
        "- Unlikely that every occurrence of “minute” is 100% spam\n",
        "- Unlikely that every occurrence of “seriously” is 100% ham\n",
        "- What about all the words that don’t occur in the training set at all?\n",
        "- In general, we can’t go around giving unseen events zero probability\n",
        "As an extreme case, imagine using the entire email as the only feature\n",
        "- Would get the training data perfect (if deterministic labeling)\n",
        "- Wouldn’t generalize at all\n",
        "- Just making the bag-of-words assumption gives us some generalization, but isn’t enough\n",
        "To generalize better: we need to smooth or regularize the estimates\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"trasnfer learning\" : \"knowledge from one domain is transferred to a new domain\",\n",
        "\"factored representation\": \"a vector of attribute values\",\n",
        "\"classification\": \"when the output is one of a finite set of values\",\n",
        "\"underfitting\": \"when a hypothesis fails to find a pattern in the data\",\n",
        "\"variance\": \"the amount of change in the hypothesis due to fluctuation in the training data\",\n",
        "\"overfitting\": \"paying too much attention to the particular data set it is trained on, causing it to perform poorly on unseen data\",\n",
        "\"bias-variance tradeoff\": \"a choice between more complex, low bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may generalize better\",\n",
        "\"Ockham’s razor\": \"simplest hypothesis should be chosen\",\n",
        "\"early stopping\": \"having the decision tree algo stop generating nodes when there is no good attribute to split on\",\n",
        "\"CART\": \"Classification and Regression Trees\",\n",
        "\"hyperparameters\": \"parameters of the model class, not the individual model\",\n",
        "\"regularization\": \"looking for functions that are more regular\",\n",
        "\"computational learning theory\": \"any hypothesis that is seriously wrong will almost certainly be “found out” with high probability after a small number of examples\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9edb18c7-7d38-43b6-bac2-fea770779e63"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\nThe components of agents include:\n1. A direct mapping from conditions on the current state to actions.\n2. A means to infer relevant properties of the world from the percept sequence.\n3. Information about the way the world evolves and about the results of possible actions\n4. Utility information indicating the desirability of world states.\n5. Action-value information indicating the desirability of actions.\n6. Goals that describe the most desirable states.\n7. A problem generator, critic, and learning element that enable the system to improve.\nThree types of __feedback__ that can accompany inputs and determine the three main types of learning:\n- In __supervised learning__ the agent observes input-output pairs and learns a function that maps from input to output. \nFor example, the inputs could be camera images, each one accompanied by an output saying “bus” or “pedestrian,” etc. \nAn output like this is called a __label__. The agent learns a function that, when given a new image, predicts the appropriate label. \nIn the case of braking actions (component 1 above), an input is the current state (speed and direction of the car, road condition),\nand an output is the distance it took to stop. In this case a set of output values can be obtained by the agent from its own percepts (after the fact); \nthe environment is the teacher, and the agent learns a function that maps states to stopping distance.\n- In __unsupervised learning__ the agent learns patterns in the input without any explicit feedback. \nThe most common unsupervised learning task is clustering: detecting poten- tially useful clusters of input examples. \nFor example, when shown millions of images taken from the Internet, a computer vision system can identify a large cluster of \nsimilar images which an English speaker would call “cats.”\n- In __reinforcement learning__ the agent learns from a series of reinforcements: rewards and punishments. \nFor example, at the end of a chess game the agent is told that it has won (a reward) or lost (a punishment). \nIt is up to the agent to decide which of the actions prior to the reinforcement were most responsible for it, \nand to alter its actions to aim towards more rewards in the future.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nThe task of __supervised learning__ is: Given a training set of N example input–output pairs (x_1,y_1),(x_2,y_2),...(x_N,y_N),\nwhere each pair was generated by an unknown function y=f(x), discover a function h that approximates the true function f.\n- The function h is called a __hypothesis__ about the world\n- h is a __model__ of the data, drawn from a model class H, or we can say a function drawn from a function class\nWe call the output y_i the ground truth-the true answer we are asking our model to predict\n- __exploratory data analysis__: examining the data with statistical tests and visualizations—histograms, \nscatter plots, box plots—to get a feel for the data, and some insight into what hypothesis space might be appropriate\n- __consistent hypothesis__: an h such that each x in the training set has h(x ) = y \n- By __bias__ we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets\n- a hypothesis is __underfitting__ when it fails to find a pattern in the data\nOften there is a bias–variance tradeoff: a choice between more complex, low-bias hy- potheses that fit the training data well and simpler, \nlow-variance hypotheses that may gen- eralize better\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nA __decision tree__ is a representation of a function that maps a vector of attribute values to a single output value; a “decision.”\n- A decision tree reaches its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached\n- The decision tree learning algorithm chooses the attribute with the highest IMPORTANCE\n  - Importance is measured in terms of __entropy__, the fundamental quantity in information theory\n    - __Entropy__ = measure of uncertainy of a random variable. More information = less entropy\n    - Entropy: H(V) = ∑_kP(vk)lg P(vk) = −∑_kP(vk)lg P(vk)\n    - Rolling die = 2 bits of entropy, flipping a fair coin = 1 bit of entropy\n- For decision trees, a technique called __decision tree pruning__ combats overfitting \n  - Start with a full tree\n  - Look at test node that has only leaf nodes as descendants\n  - If the test seems irrelevant (detecting only noise), then we eliminate the test, replacing it with a leaf node\n- Statistical __significance test__: __null hypothesis__ (assume no underlying pattern)\nDecision trees can be made more widely useful by handling the following complications:\n- __Missing data__\n- __Continuous and multivalued input attributes__: better way to deal with this is a __split point__ test, an equality\ntest on the value of an attribute (like Weight > 160)\n- __Continuous-valued output attribute__: trying to predict a numerical output requires a __regression tree__ rather than a classification\ntree\nDecision trees are also __unstable__ in that adding just one new example can change the test at the root, which changes the entire tree\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nOur goal in machine learning is to select a hypothesis that will optimally fit future examples. To make that precise we need to define “future example” and “optimal fit.”\n__stationarity assumption__: we assume that each example E_j has the same prior probability distribution: P(E_j) = P(E_j+1)=P(E_j+2)=...\nand is independent of the previous examples: P(E_j) = P(E_j|E_j-1 E_j-2)\n- Examples that satisfy these equations are independent and identically distributed or i.i.d.\n__optimal fit__: the hypothesis that minimizes the __error rate__: the proportion of times that h(x) is not equal to y for an (x,y)\nexample\nNeed three data sets:\n1. A __training set__ to train candidate models.\n2. A __validation set__, also known as a __development set__ or dev set, to evaluate the candidate\nmodels and choose the best one.\n3. A __test set__ to do a final unbiased evaluation of the best model.\nWhat if we don’t have enough data to make all three of these data sets? We can squeeze more out of the data using a technique called __k-fold cross-validation__.\n- Each sample serves double duty: as training data and validation data\n- First split the data into k equal subsets\n- Then perform k rounds of learning, on each round 1/k of the data are held out as validation set and the remaining are used as training set\nThe extreme is k = n, also known as __leave-one-out cross-validation or LOOCV__.\nWe can think of the task of finding a good hypothesis as two subtasks: __model selection__ chooses a good hypothesis \nspace, and __optimization__ (also called training) finds the best hypothesis within that space\n__Model selection__:  It takes as argument a learn- ing algorithm, Learner\n__Bayesian optimization__ treats the task of choosing good hyperparameter values as a machine learning problem in itself.\nAn alternative to __Bayesian optimization__ is __population-based training (PBT)__. PBT starts by using random search to train (in parallel) a population of models, each with different hyperparameter values. Then a second generation of models are trained, \nbut they can choose hyperparameter values based on the successful values from the previous generation, as well as by random mutation, as in genetic algorithms\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nWe now show how to apply PAC learning to a new hypothesis space: __decision lists__. A decision list consists of a series of tests, each of which is a conjunction of literals.\nIf a test succeeds when applied to an example description, the __decision list__ specifies the value to be returned. \nIf the test fails, processing continues with the next test in the list. Decision lists resemble decision trees, but their overall structure is simpler: they branch only in one direction.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nA __univariate linear function__ (a straight line) with input x and output y has the form y=w_1x+ w_0, where w_0 and w_1 are real-valued coefficients to be learned.\nput y has the form y=w1x+ w0, where w0 and w1 are real-valued coefficients to be learned. \nWe use the letter w because we think of the coefficients as weights; the value of y is changed by changing the relative weight of one term or another.\nWe’ll define w to be the vector ⟨w0,w1⟩, and define the linear function with those weights as h_w(x)=w_1x+w_0.\nThe task of finding the h_w that best fits these data is called __linear regression__.\nAs discussed in Section 4.2 (page 119) we can search through a continuous weight space by incrementally modifying the parameters. \nThere we called the algorithm __hill climbing__, but here we are __minimizing loss, not maximizing gain__, so we will use the term __gradient descent__.\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\nIn this chapter, we intrdouce the naive Bayes algorithm and apply it to __text categorization__, the task of assigning a label or category to an entire text or document.\nWe focus on one common text categorization task, __sentiment analysis__, the extraction of sentiment.\n__Spam detection__ is another important commercial application, the binary classification task of assigning an email to one of the two classes spam or not-spam\n__Multinomial naive Bayes classifier__: a Bayesian classifier that makes a simplifying (naive) assumptino about how the features interact.\n__Naive bayes assumption__: conditional independence assumption that the probabilities P(f_i|c) are independent given teh class c and can be \nnaively multiplied as follows: P(f_1,f_2,...,f_n|c) = P(f_1|c) x P(f_2|c) x ... x P(f_n|c)\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\nP(w_i|c) = count(w_i,c)/sum of w in V (count(w,c)) (look in lecture notes!)\n \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\nClassification: given inputs x, predict labels y\nExamples:\n- Spam detection (input: document,\nclasses: spam / ham)\n-  OCR (input: images, classes: characters)\n- Medical diagnosis (input: symptoms,\nclasses: diseases)\n-  Automatic essay grading (input: document,\nclasses: grades)\n- Fraud detection (input: account activity,\nclasses: fraud / no fraud)\n- Customer service email routing\n\nClassification is an important commercial technology/n\n\n__Inference for Naive Bayes__:\n\nGoal: compute posterior distribution over label variable Y\n1. Get joint probability of label and evidence for each label\n\n  P(Y, f_1...f_n = [P(y_1,f_1...f_n); P(y_2,f_1...f_n); ... ; P(y_k,f_1...f_n)])\n2. Sum to get probability of evidence\n3. Normalize by dividing Step 1 by Step 2\n\n\n__General Naive Bayes__\nWhat do we need in order to use Naïve Bayes?\n- Inference method (we just saw this part)\n  - Start with a bunch of probabilities: P(Y) and the P(Fi\n|Y) tables\n  - Use standard inference to compute P(Y|F1…Fn)\n  - Nothing new here\n- Estimates of local conditional probability tables\n  - P(Y), the prior over labels\n  - P(Fi|Y) for each feature (evidence variable)\n  - These probabilities are collectively called the parameters of the model and denoted by q\n  - Up until now, we assumed these appeared by magic, but…\n  - ... they typically come from training data counts: we’ll look at this soon\n\n\n__Naive Bayes for Text__\nP(Y, W_1...W_n) = P(Y)Pi_i P(W_i|Y)\n\n__Generalization and Overfitting__\nRelative frequency parameters will overfit the training data!\n- Just because we never saw a 3 with pixel (15,15) on during training doesn’t mean we won’t\nsee it at test time\n- Unlikely that every occurrence of “minute” is 100% spam\n- Unlikely that every occurrence of “seriously” is 100% ham\n- What about all the words that don’t occur in the training set at all?\n- In general, we can’t go around giving unseen events zero probability\nAs an extreme case, imagine using the entire email as the only feature\n- Would get the training data perfect (if deterministic labeling)\n- Wouldn’t generalize at all\n- Just making the bag-of-words assumption gives us some generalization, but isn’t enough\nTo generalize better: we need to smooth or regularize the estimates\n\n\n## Module 12 Definitions\n* **Trasnfer learning** - knowledge from one domain is transferred to a new domain\n* **Factored representation** - a vector of attribute values\n* **Classification** - when the output is one of a finite set of values\n* **Underfitting** - when a hypothesis fails to find a pattern in the data\n* **Variance** - the amount of change in the hypothesis due to fluctuation in the training data\n* **Overfitting** - paying too much attention to the particular data set it is trained on, causing it to perform poorly on unseen data\n* **Bias-variance tradeoff** - a choice between more complex, low bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may generalize better\n* **Ockham’s razor** - simplest hypothesis should be chosen\n* **Early stopping** - having the decision tree algo stop generating nodes when there is no good attribute to split on\n* **Cart** - Classification and Regression Trees\n* **Hyperparameters** - parameters of the model class, not the individual model\n* **Regularization** - looking for functions that are more regular\n* **Computational learning theory** - any hypothesis that is seriously wrong will almost certainly be “found out” with high probability after a small number of examples\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"\n",
        "The most important difference between naive Bayes and logistic regression is that logistic regression is a \n",
        "__discriminative__ classifier while naive Bayes is a __generative__ classifier.\n",
        "Consider a visual\n",
        "metaphor: imagine we’re trying to distinguish dog\n",
        "images from cat images. A generative model would\n",
        "have the goal of understanding what dogs look like\n",
        "and what cats look like. A discriminative model, by contrast, is only trying to learn to distinguish the classes.\n",
        "__Components of a probabilistic machine learning classifier__: Like naive Bayes,\n",
        "logistic regression is a probabilistic classifier that makes use of supervised machine\n",
        "learning. Machine learning classifiers require a training corpus of m input/output\n",
        "pairs (x^i, y^i). \n",
        "1. A __feature representation__ of the input\n",
        "2. A classification function that computes y hat, the estimated class, via p(y|x)\n",
        "3. An objective function (__cross-entropy loss function__)\n",
        "4. Al algorithm for optimizing the objective function (__stochastic gradient descent))\n",
        "\n",
        "Logistic regression has two phases:\\n\n",
        "__training__: we train the system (specifically the weights w and b) using stochastic\n",
        "gradient descent and the cross-entropy loss.\\n\n",
        "__test__: Given a test example x we compute p(y|x) and return the higher probability\n",
        "label y = 1 or y = 0.\\n\\n\n",
        "The goal of __binary logistic regression__ is to train a classifier that can make a binary\n",
        "decision about the class of a new input observation. Here we introduce the sigmoid\n",
        "classifier that will help us make this decision.\\n\n",
        "\"positive sentiment\" vs \"negative sentiment\".\\n\n",
        "To create a probability, we’ll pass z through the __sigmoid function, σ(z)__.\n",
        "Consider the task of __period disambiguation__: deciding\n",
        "if a period is the end of a sentence or part of a word, by classifying each period\n",
        "into one of two classes EOS (end-of-sentence) and not-EOS\\n\n",
        "Logistic regression has a number of advantages over naive\n",
        "Bayes. Naive Bayes has overly strong conditional independence assumptions\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" \n",
        "We need a loss function that expresses, for an observation x, how close the classifier\n",
        "output __(y hat = σ(w· x+b))__ is to the correct output (y, which is 0 or 1)\\n\n",
        "We do this via a loss function that prefers the correct class labels of the training examples to be more likely. This is called __conditional maximum likelihood\n",
        "estimation__: we choose the parameters w,b that maximize the log probability of\n",
        "the true y labels in the training data given the observations x. The resulting loss function is called __cross-entropy loss__.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "For logistic regression, this loss function is conveniently __convex__. A convex function has just one minimum; there are no local minima to get stuck in, so gradient\n",
        "descent starting from any point is guaranteed to find the minimum.\n",
        "The magnitude of the amount to move in gradient descent is the value of the\n",
        "slope d/dw learning rate L(f(x;w), y) weighted by a learning rate η.\\n\n",
        "higher (faster) learning rate means that we should move w more on each step\\n\n",
        "Stochastic gradient descent is an online algorithm that minimizes the loss function\n",
        "by computing its gradient after each training example, and nudging θ in the right\n",
        "direction (the opposite direction of the gradient). (an “online algorithm” is one that\n",
        "processes its input example by example, rather than waiting until it sees the entire\n",
        "input).\\n\n",
        "The __learning rate η is a hyperparameter__ that must be adjusted. If it’s too high,\n",
        "the learner will take steps that are too large, overshooting the minimum of the loss\n",
        "function. If it’s too low, the learner will take steps that are too small, and take too\n",
        "long to get to the minimum. It is common to start with a higher learning rate and then\n",
        "slowly decrease it, so that it is a function of the iteration k of training; the notation\n",
        "ηk can be used to mean the value of the learning rate at iteration k\\n\n",
        "Stochastic gradient descent is called stochastic because it chooses a single random\n",
        "example at a time, moving the weights so as to improve performance on that single\n",
        "example. That can result in very choppy movements, so it’s common to compute the\n",
        "gradient over batches of training instances rather than a single instance.\\n\n",
        "For example in __batch training__ we compute the gradient over the entire dataset.\n",
        "By seeing so many examples, batch training offers a superb estimate of which direction to move the weights, at the cost of spending a lot of time processing every\n",
        "single example in the training set to compute this perfect direction.\n",
        "A compromise is __mini-batch training__: we train on a group of m examples (perhaps 512, or 1024) that is less than the whole dataset.\n",
        "\"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "There is a problem with learning weights that make the model perfectly match the\n",
        "training data. If a feature is perfectly predictive of the outcome because it happens\n",
        "to only occur in one class, it will be assigned a very high weight. The weights for\n",
        "features will attempt to perfectly fit details of the training set, in fact too perfectly,\n",
        "modeling noisy factors that just accidentally correlate with the class. This problem is called __overfitting__.\n",
        "A good model should be able to __generalize__ well from the training data to the unseen test set, but a model that overfits will have poor generalization.\n",
        "__L2 regularization__ is a quadratic function of the weight values, named because it uses the (square of the) L2 norm of the weight\n",
        "values. The L2 norm, ||θ||_2, is the same as the Euclidean distance of the vector θ from the origin.\\n\n",
        "__L1 regularization__ is a linear function of the weight values, named after the L1 norm L1\n",
        "regularization ||W||1, the sum of the absolute values of the weights, or Manhattan distance.\n",
        " \"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "Sometimes we need more than two classes. Perhaps we might want to do 3-way\n",
        "sentiment classification (positive, negative, or neutral). Or we could be assigning\n",
        "some of the labels we will introduce in Chapter 8, like the part of speech of a word\n",
        "(choosing from 10, 30, or even 50 different parts of speech), or the named entity\n",
        "type of a phrase (choosing from tags like person, location, organization).\\n\n",
        "In such cases we use __multinomal logistic regression__, also called __softmax regression__.\n",
        "The multinomial logistic classifier uses a generalization of the sigmoid, called\n",
        "softmax the softmax function, to compute the probability p(y = c|x).\\n\n",
        "Recall cross-entropy loss for binary:\\n\n",
        "LCE(yˆ, y) = −log p(y|x) = −[y log ˆy+ (1−y)log(1−yˆ)]\\n\n",
        "Because only one class (let’s call it i) is the correct one, the vector y takes the value\n",
        "1 only for this value of k, i.e., has yi = 1 and yj = 0 ∀ j 6= i. A vector like this,\n",
        "with one value=1 and the rest 0, is called a __one-hot vector__.\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\n",
        "The architecture we\n",
        "feedforward introduce is called a __feedforward network__ because the computation proceeds iteratively from one layer of units to the next.\n",
        " \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "__Classifier components__\n",
        "Machine learning classifiers require a training corpus of M observations\n",
        "input/output pairs (x^(i),y^(i)).\n",
        "1. A __feature representation__ of the input. For each input observation\n",
        "x(i), this will be a vector of features [x1,x2,...,xn].\n",
        "2. A __classification function__ that computes the estimated class y hat! viap(y|x).\n",
        "3. An __objective function__ for learning, usually involving minimizing error on training examples.\n",
        "4. An algorithm for __optimizing__ the objective function.\\n\n",
        "\n",
        "__Sentiment classification__: z = w . x + b\n",
        "\n",
        "__Sigmoid function__: y = 1/(1+e^-z)\n",
        "- P(y=1) = sigma(wx +b) = 1/(1+e^-(wx+b))\\n\n",
        "\n",
        "__Learning in logistic regression__\n",
        "How do we get the weights of the model? We learn the parameters\n",
        "(weights + bias) via learning. This requires 2 components:\n",
        "1. An objective function or __loss function__ that tells us distance between\n",
        "the system output and the gold output. We will use __cross-entropy loss__.\n",
        "2. An algorithm for optimizing the objective function. We will use\n",
        "stochastic gradient descent to __minimize the loss function__.\\n\n",
        "\n",
        "For one observation x, let’s maximize the probability of the correct label p(y|x).\n",
        "- P(y|x) = y hat^y (1-y hat)^(1-y)\n",
        "\n",
        "If y = 1, then p(y|x) = yhat\n",
        "If y = 0, then p(y|x) = 1- yhat\\n\n",
        "\n",
        "__Change to logs and then negate, and we get cross-entropy loss, and we want to minimze:\n",
        "- L_CE(yhat, y) = -logp(y|x)=-[ylog yhat + (1-y)log(1-yhat)]\n",
        "- Plug in sigmoid function for p(y|x)\\n\n",
        "\n",
        "Why does minimizing this negative log probability do what we want? We\n",
        "want the loss to be smaller if the model’s estimate is close to correct,\n",
        "and we want the loss to be bigger if it is confused.\\n\n",
        "\n",
        "__Gradient descent__ is a method that finds a minimum of a function by figuring out in\n",
        "which direction (in the space of the parameters θ) the function’s slope is rising the most\n",
        "steeply, and moving in the opposite direction.\\n\n",
        "For logistic regression, this loss function is conveniently __convex__.\n",
        "A convex function has just one minimum, so there are no local minima\n",
        "to get stuck in\\n\n",
        "\n",
        "__Stochastic gradient descent__ chooses a single random example at a time and updates\n",
        "its weights on that example. As a result the updates can fluctuate.\n",
        "An alternate is __batch training__, which computes the gradient over the entire dataset.\n",
        "This gives a much better estimate of which direction to move the weights but takes a\n",
        "long time to compute.\n",
        "A commonly used compromise is __mini-batch training__, where we train on a small\n",
        "batch. The batch size can be 512 or 1024, often selected based on computational\n",
        "resources, so that all examples in the mini-batch can be processed in parallel. The loss\n",
        "is then accumulated.\\n\n",
        "\n",
        "__Overfitting__ is a problem with many machine learning models. Overfitting results in\n",
        "poor generalization and poor performance on unseen test set.\n",
        "In logistic regression, if a feature only occurs in one class then it will get a high weight.\n",
        "Sometimes we are just modelling noisy factors that just accidentally correlate with the\n",
        "class.\n",
        "__Regularization__ is a way to penalize large weights. A regularization term is added to\n",
        "the loss function.\n",
        "Lasso regression uses L1 regularization\n",
        "Ridge regression uses L2 regularization\\n\n",
        "\n",
        "__Multinomal logistic regression__\n",
        "Instead of binary classification, we often want more than two classes. For sentiment\n",
        "classification we might extend the class labels to be positive, negative, and neutral.\n",
        "We want to know the probability of y for each class c ∈ C, p(y = c|x).\n",
        "To get a proper probability, we will use a generalization of the sigmoid function\n",
        "called the __softmax function__.\\n\n",
        "\n",
        "__Sigmoid neurons__\n",
        "Problem: a small change in the weights or bias of any single perceptron in the network\n",
        "can causes the output to completely flip from 0 to 1.\n",
        "Solution: sigmoid neuron\\n\n",
        "\n",
        "__Activation functions__\n",
        "Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units\n",
        "apply a non-linear function f to z.\n",
        "The output of this function is called the activation value for the unit, represented by\n",
        "the variable a. The output of a neural network is called y, so if the activation of a node\n",
        "is the final output of a network then. y = a = f(z)\\n\\n\n",
        "\n",
        "The simplest kind of NN is the __Feed-Forward Neural Network__\n",
        "Multilayer network, all units are usually fully-connected, and no cycles.\n",
        "The outputs from each layer are passed to units in the next higher layer, and no\n",
        "outputs are passed back to lower layers. \n",
        "A single hidden unit has parameters w (the weight vector) and b (the bias scalar).\n",
        "We represent the parameters for the __entire hidden layer__ by combining the weight\n",
        "vector wi and bias bi for each unit i into a single weight matrix W and a single bias\n",
        "vector b for the whole layer.\\n\n",
        "The advantage of using a single matrix W for the weights of the entire layer is the\n",
        "hidden layer computation can be done efficiently with simple matrix operations.\n",
        "The computation has three steps:\n",
        "1. multiplying the weight matrix by the input vector x,\n",
        "2. adding the bias vector b, and\n",
        "3. applying the activation function g (such as Sigmoid)\n",
        "The output of the hidden layer, the vector h, is thus the following, using the sigmoid\n",
        "function σ:\n",
        "- h=σ(wx+b)\n",
        "\\n\\n\n",
        "__Training Neural Nets__\\n\n",
        "Like logistic regression, we want to learn the best parameters for the neural net to\n",
        "make its predictions yhat as close to possible as the gold standard labels in our training\n",
        "data y.\n",
        "What do we need?\n",
        "- A loss function – cross-entropy loss\n",
        "- An optimization algorithm – gradient descent\n",
        "- A way of computing the gradient of the loss function – error propagation \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "289a88cd-483f-419f-d34a-434a7cdba538"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\nThe most important difference between naive Bayes and logistic regression is that logistic regression is a \n__discriminative__ classifier while naive Bayes is a __generative__ classifier.\nConsider a visual\nmetaphor: imagine we’re trying to distinguish dog\nimages from cat images. A generative model would\nhave the goal of understanding what dogs look like\nand what cats look like. A discriminative model, by contrast, is only trying to learn to distinguish the classes.\n__Components of a probabilistic machine learning classifier__: Like naive Bayes,\nlogistic regression is a probabilistic classifier that makes use of supervised machine\nlearning. Machine learning classifiers require a training corpus of m input/output\npairs (x^i, y^i). \n1. A __feature representation__ of the input\n2. A classification function that computes y hat, the estimated class, via p(y|x)\n3. An objective function (__cross-entropy loss function__)\n4. Al algorithm for optimizing the objective function (__stochastic gradient descent))\n\nLogistic regression has two phases:\n\n__training__: we train the system (specifically the weights w and b) using stochastic\ngradient descent and the cross-entropy loss.\n\n__test__: Given a test example x we compute p(y|x) and return the higher probability\nlabel y = 1 or y = 0.\n\n\nThe goal of __binary logistic regression__ is to train a classifier that can make a binary\ndecision about the class of a new input observation. Here we introduce the sigmoid\nclassifier that will help us make this decision.\n\n\"positive sentiment\" vs \"negative sentiment\".\n\nTo create a probability, we’ll pass z through the __sigmoid function, σ(z)__.\nConsider the task of __period disambiguation__: deciding\nif a period is the end of a sentence or part of a word, by classifying each period\ninto one of two classes EOS (end-of-sentence) and not-EOS\n\nLogistic regression has a number of advantages over naive\nBayes. Naive Bayes has overly strong conditional independence assumptions\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \nWe need a loss function that expresses, for an observation x, how close the classifier\noutput __(y hat = σ(w· x+b))__ is to the correct output (y, which is 0 or 1)\n\nWe do this via a loss function that prefers the correct class labels of the training examples to be more likely. This is called __conditional maximum likelihood\nestimation__: we choose the parameters w,b that maximize the log probability of\nthe true y labels in the training data given the observations x. The resulting loss function is called __cross-entropy loss__.\n\n\n\n## SLP Chapter 5.4 Gradient Descent\n\nFor logistic regression, this loss function is conveniently __convex__. A convex function has just one minimum; there are no local minima to get stuck in, so gradient\ndescent starting from any point is guaranteed to find the minimum.\nThe magnitude of the amount to move in gradient descent is the value of the\nslope d/dw learning rate L(f(x;w), y) weighted by a learning rate η.\n\nhigher (faster) learning rate means that we should move w more on each step\n\nStochastic gradient descent is an online algorithm that minimizes the loss function\nby computing its gradient after each training example, and nudging θ in the right\ndirection (the opposite direction of the gradient). (an “online algorithm” is one that\nprocesses its input example by example, rather than waiting until it sees the entire\ninput).\n\nThe __learning rate η is a hyperparameter__ that must be adjusted. If it’s too high,\nthe learner will take steps that are too large, overshooting the minimum of the loss\nfunction. If it’s too low, the learner will take steps that are too small, and take too\nlong to get to the minimum. It is common to start with a higher learning rate and then\nslowly decrease it, so that it is a function of the iteration k of training; the notation\nηk can be used to mean the value of the learning rate at iteration k\n\nStochastic gradient descent is called stochastic because it chooses a single random\nexample at a time, moving the weights so as to improve performance on that single\nexample. That can result in very choppy movements, so it’s common to compute the\ngradient over batches of training instances rather than a single instance.\n\nFor example in __batch training__ we compute the gradient over the entire dataset.\nBy seeing so many examples, batch training offers a superb estimate of which direction to move the weights, at the cost of spending a lot of time processing every\nsingle example in the training set to compute this perfect direction.\nA compromise is __mini-batch training__: we train on a group of m examples (perhaps 512, or 1024) that is less than the whole dataset.\n\n\n## SLP Chapter 5.5 Regularization\n\nThere is a problem with learning weights that make the model perfectly match the\ntraining data. If a feature is perfectly predictive of the outcome because it happens\nto only occur in one class, it will be assigned a very high weight. The weights for\nfeatures will attempt to perfectly fit details of the training set, in fact too perfectly,\nmodeling noisy factors that just accidentally correlate with the class. This problem is called __overfitting__.\nA good model should be able to __generalize__ well from the training data to the unseen test set, but a model that overfits will have poor generalization.\n__L2 regularization__ is a quadratic function of the weight values, named because it uses the (square of the) L2 norm of the weight\nvalues. The L2 norm, ||θ||_2, is the same as the Euclidean distance of the vector θ from the origin.\n\n__L1 regularization__ is a linear function of the weight values, named after the L1 norm L1\nregularization ||W||1, the sum of the absolute values of the weights, or Manhattan distance.\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n\nSometimes we need more than two classes. Perhaps we might want to do 3-way\nsentiment classification (positive, negative, or neutral). Or we could be assigning\nsome of the labels we will introduce in Chapter 8, like the part of speech of a word\n(choosing from 10, 30, or even 50 different parts of speech), or the named entity\ntype of a phrase (choosing from tags like person, location, organization).\n\nIn such cases we use __multinomal logistic regression__, also called __softmax regression__.\nThe multinomial logistic classifier uses a generalization of the sigmoid, called\nsoftmax the softmax function, to compute the probability p(y = c|x).\n\nRecall cross-entropy loss for binary:\n\nLCE(yˆ, y) = −log p(y|x) = −[y log ˆy+ (1−y)log(1−yˆ)]\n\nBecause only one class (let’s call it i) is the correct one, the vector y takes the value\n1 only for this value of k, i.e., has yi = 1 and yj = 0 ∀ j 6= i. A vector like this,\nwith one value=1 and the rest 0, is called a __one-hot vector__.\n\n\n## SLP Chapter 7.1 Units\n\nThe architecture we\nfeedforward introduce is called a __feedforward network__ because the computation proceeds iteratively from one layer of units to the next.\n \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n__Classifier components__\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x^(i),y^(i)).\n1. A __feature representation__ of the input. For each input observation\nx(i), this will be a vector of features [x1,x2,...,xn].\n2. A __classification function__ that computes the estimated class y hat! viap(y|x).\n3. An __objective function__ for learning, usually involving minimizing error on training examples.\n4. An algorithm for __optimizing__ the objective function.\n\n\n__Sentiment classification__: z = w . x + b\n\n__Sigmoid function__: y = 1/(1+e^-z)\n- P(y=1) = sigma(wx +b) = 1/(1+e^-(wx+b))\n\n\n__Learning in logistic regression__\nHow do we get the weights of the model? We learn the parameters\n(weights + bias) via learning. This requires 2 components:\n1. An objective function or __loss function__ that tells us distance between\nthe system output and the gold output. We will use __cross-entropy loss__.\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to __minimize the loss function__.\n\n\nFor one observation x, let’s maximize the probability of the correct label p(y|x).\n- P(y|x) = y hat^y (1-y hat)^(1-y)\n\nIf y = 1, then p(y|x) = yhat\nIf y = 0, then p(y|x) = 1- yhat\n\n\n__Change to logs and then negate, and we get cross-entropy loss, and we want to minimze:\n- L_CE(yhat, y) = -logp(y|x)=-[ylog yhat + (1-y)log(1-yhat)]\n- Plug in sigmoid function for p(y|x)\n\n\nWhy does minimizing this negative log probability do what we want? We\nwant the loss to be smaller if the model’s estimate is close to correct,\nand we want the loss to be bigger if it is confused.\n\n\n__Gradient descent__ is a method that finds a minimum of a function by figuring out in\nwhich direction (in the space of the parameters θ) the function’s slope is rising the most\nsteeply, and moving in the opposite direction.\n\nFor logistic regression, this loss function is conveniently __convex__.\nA convex function has just one minimum, so there are no local minima\nto get stuck in\n\n\n__Stochastic gradient descent__ chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\nAn alternate is __batch training__, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\nA commonly used compromise is __mini-batch training__, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n\n__Overfitting__ is a problem with many machine learning models. Overfitting results in\npoor generalization and poor performance on unseen test set.\nIn logistic regression, if a feature only occurs in one class then it will get a high weight.\nSometimes we are just modelling noisy factors that just accidentally correlate with the\nclass.\n__Regularization__ is a way to penalize large weights. A regularization term is added to\nthe loss function.\nLasso regression uses L1 regularization\nRidge regression uses L2 regularization\n\n\n__Multinomal logistic regression__\nInstead of binary classification, we often want more than two classes. For sentiment\nclassification we might extend the class labels to be positive, negative, and neutral.\nWe want to know the probability of y for each class c ∈ C, p(y = c|x).\nTo get a proper probability, we will use a generalization of the sigmoid function\ncalled the __softmax function__.\n\n\n__Sigmoid neurons__\nProblem: a small change in the weights or bias of any single perceptron in the network\ncan causes the output to completely flip from 0 to 1.\nSolution: sigmoid neuron\n\n\n__Activation functions__\nInstead of directly outputting z = w·x+b, which is a linear function of x, neuron units\napply a non-linear function f to z.\nThe output of this function is called the activation value for the unit, represented by\nthe variable a. The output of a neural network is called y, so if the activation of a node\nis the final output of a network then. y = a = f(z)\n\n\n\nThe simplest kind of NN is the __Feed-Forward Neural Network__\nMultilayer network, all units are usually fully-connected, and no cycles.\nThe outputs from each layer are passed to units in the next higher layer, and no\noutputs are passed back to lower layers. \nA single hidden unit has parameters w (the weight vector) and b (the bias scalar).\nWe represent the parameters for the __entire hidden layer__ by combining the weight\nvector wi and bias bi for each unit i into a single weight matrix W and a single bias\nvector b for the whole layer.\n\nThe advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\nThe computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\nThe output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ:\n- h=σ(wx+b)\n\n\n\n__Training Neural Nets__\n\nLike logistic regression, we want to learn the best parameters for the neural net to\nmake its predictions yhat as close to possible as the gold standard labels in our training\ndata y.\nWhat do we need?\n- A loss function – cross-entropy loss\n- An optimization algorithm – gradient descent\n- A way of computing the gradient of the loss function – error propagation \n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" \"\"\"\n",
        "slp_chapter9_2 = \"\"\"\n",
        "A __recurrent neural network (RNN)__ is any network that contains a cycle within its\n",
        "network connections, meaning that the value of some unit is directly, or indirectly,\n",
        "dependent on its own earlier outputs as an input.\\n\n",
        "__Forward inference__ (mapping a sequence of inputs to a sequence of outputs) in an\n",
        "RNN is nearly identical to what we’ve already seen with feedforward networks.\n",
        "```\n",
        "function FORWARDRNN(x, network) returns output sequence y\n",
        "  ^0←0\n",
        "  for i←1 to LENGTH(x) do\n",
        "  h_i←g(Uh_i−1 + W_x_i)\n",
        "  y_i← f(V_h_i)\n",
        "  return y\n",
        "```\n",
        "As with feedforward networks, __we’ll use a training set, a loss function, \n",
        "and backpropagation__ to obtain the gradients needed to adjust the weights in these recurrent\n",
        "networks.\\n\n",
        "Tailoring the backpropagation algorithm to this situation leads to a two-pass algorithm for training the weights in RNNs. In the first pass, we perform forward\n",
        "inference, computing ht, yt, accumulating the loss at each step in time, saving the\n",
        "value of the hidden layer at each step for use at the next time step. In the second\n",
        "phase, we process the sequence in reverse, computing the required gradients as we\n",
        "go, computing and saving the error term for use in the hidden layer for each step\n",
        "backward in time.\n",
        "\"\"\"\n",
        "slp_chapter9_3 = \"\"\"\n",
        "RNN language models process the input sequence one word at a time, attempting to predict the next word from the current word and \n",
        "the previous hidden state.\n",
        "To train an RNN as a language model, we use a corpus of text as training material,\n",
        "having the model predict the next word at each time step t. We train the model to\n",
        "minimize the error in predicting the true next word in the training sequence, using\n",
        "cross-entropy as the loss function. Recall that the cross-entropy loss measures the\n",
        "difference between a predicted probability distribution and the correct distribution.\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\"\n",
        "This link between similarity in how words are distributed and similarity\n",
        "in what they mean is called the __distributional hypothesis__.\\n\n",
        "__Vector semantics__: instantiates this linguistic hypothesis by learning representations of the meaning of words, called embeddings,\n",
        "directly from their distributions in texts.\\n\n",
        "One of the fundamental tenets of semantics, called the __principle of contrast__ states that a difference \n",
        "in linguistic form is always associated with some difference in meaning.\\n\n",
        "One common kind of relatedness between words is if they belong to the same\n",
        "__semantic field__. A semantic field is a set of words which cover a particular semantic\n",
        "domain and bear structured relations with each other. For example, words might be\n",
        "related by being in the semantic field of hospitals (surgeon, scalpel, nurse, anesthetic, hospital), restaurants (waiter, menu, plate, food, chef).\\n\n",
        "Finally, words have affective meanings or __connotations__.\n",
        " \"\"\"\n",
        "slp_chapter6_2 = \"\"\" \n",
        "__Vector semantics__ is the standard way to represent word meaning in NLP, helping us model many of the aspects of word meaning.\\n\n",
        "Vectors for representing words are called __embeddings__ (although\n",
        "the term is sometimes more strictly applied only to dense vectors like word2vec rather than sparse tf-idf or PPMI vectors).\n",
        "\"\"\"\n",
        "slp_chapter6_3 = \"\"\"\n",
        "In a __term-document matrix__, each row represents a word in the vocabulary and each term-document\n",
        "matrix column represents a document from some collection of documents. This was first defined as part of the \n",
        "__vector space model__ of information retrieval (a document represented as a count vector).\n",
        "Term-document matrices were originally defined as a means of finding similar\n",
        "documents for the task of document __information retrieval__. Information retrieval (IR) is the task of finding the document d from the D\n",
        "documents in some collection that best matches a query q.\\n\n",
        "An alternative to using the __term-document matrix__ to represent words as vectors of\n",
        "document counts, is to use the __term-term matrix__, also called the __word-word matrix__ or the __term-context matrix__.\n",
        " \"\"\"\n",
        "slp_chapter6_4 = \"\"\"\n",
        "To measure similarity between two target words v and w, we need a metric that\n",
        "takes two vectors (of the same dimensionality, either both with words as dimensions,\n",
        "hence of length |V|, or both with documents as dimensions as documents, of length\n",
        "|D|) and gives a measure of their similarity. By far the most common similarity\n",
        "metric is the __cosine of the angle between the vectors__.\\n\n",
        "As we will see, most metrics for similarity between vectors are based on the dot\n",
        "product. The dot product acts as a similarity metric because it will tend to be high\n",
        "just when the two vectors have large values in the same dimensions.\\n\n",
        "The dot product is higher if a vector is longer, with higher values in each dimension.\n",
        "More frequent words have longer vectors, since they tend to co-occur with more\n",
        "words and have higher co-occurrence values with each of them. The raw dot product\n",
        "thus will be higher for frequent words. But this is a problem; we’d like a similarity\n",
        "metric that tells us how similar two words are regardless of their frequency.\\n\n",
        "We modify the dot product to normalize for the vector length by dividing the\n",
        "dot product by the lengths of each of the two vectors. This __normalized dot product__\n",
        "turns out to be the same as the cosine of the angle between the two vectors, following\n",
        "from the definition of the dot product between two vectors a and b:\n",
        " \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "__Word Meaning__\n",
        "How should we represent the meaning of a word?\n",
        "In N-gram LMs we represented words as a string of letters or as an index in a\n",
        "vocabulary list.\n",
        "Ideally, we want a meaning representation to encode:\n",
        "1. Synonyms – words that have similar meanings\n",
        "2. Antonyms – words that have opposite meanings\n",
        "3. Connotations – words that are positive or negative\n",
        "4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\n",
        "purchasing event\n",
        "5. Support for entailment\n",
        "\\n\\n\n",
        "\n",
        "__Term-Document Matrix__:\n",
        "- Each column vector represents a document\n",
        "- Each row vector represents a Term (a word)\n",
        "- The value in a cell is based on how often that term occurred in that document\n",
        "- The length of the document vectors is the size of the vocabulary\n",
        "- Document vectors can be sparse (most values are 0)\n",
        "- We can measure how similar two documents are by comparing their column vectors\n",
        "- Two rows can show us how similar two words are\\n\\n\n",
        "\n",
        "__Term-Term matrix/term-context matrix__:\n",
        "- Terms on the rows and column headers\n",
        "- Length of the row vector is now |V| instead of number of documents\n",
        "- The value in a cell indicates how often a word appears in a context window surrounding the word\n",
        "  - __Context windows__: w-2, w-1, target_word, w+1, w+2\n",
        "\\n\n",
        "__Alternates to counts__\\n\n",
        "Raw word frequency is not a great measure of association between words. It’s very\n",
        "skewed “the” and “of” are very frequent, but maybe not the most discriminative\n",
        "We’d rather have a measure that asks whether a context word is particularly\n",
        "informative about the target word.\n",
        "Instead of raw counts, it’s common to transform vectors using TF-IDF or PPM\n",
        "\\n\\n\n",
        "__TF-IDF__:\n",
        "- term frequency (how often a word occurred in a document) * inverse document frequency (1 over the number of documents that it occurred in)\n",
        "\\n\\n\n",
        "\n",
        "__Sparse v. Dense Vectors__\n",
        "Co-occurrence matrix (weighted by TF-IDF or mutual information)\n",
        "- Long (length |V| = 50,000+)\n",
        "- Sparse (most elements are zeros)\n",
        "Alternative: learn vectors that are\n",
        "- Short (length 200-1000)\n",
        "- Dense (most elements are non-zero)\n",
        "\\n\\n\n",
        "Chain rule\n",
        "In LMs we user chain rule to get the conditional probability of the next\n",
        "word in the sequence given all of the previous words:\n",
        "- P(w1w2...wt) = Pi_(t=1)^TP(wt|w1...w_(t-1))\n",
        "What assumption do we make in n-gram LMs to simplify this?\n",
        "The probability of the next word only depends on the previous n-1\n",
        "words.\n",
        "A small n makes it easier for us to get an estimate of the probability from data.\n",
        "\\n\\n\n",
        "Unseen sequences\n",
        "What happens when we have a new (unseen) combination of n words?\n",
        "__1. Back-off\n",
        "2. Smoothing / interpolation__\n",
        "We are basically just stitching together short sequences of observed\n",
        "words.\\n\\n\n",
        "\n",
        "__Alternate idea: Generalizing__\\n\n",
        "Taking a sentence like \"The cat is walking in the bedroom\" and use it when we assign probabilities to similar sentences like\n",
        "\"The dog is running around the room\".\\n\\n\n",
        "\n",
        "__Neural Language Models__\\n\n",
        "Neural Language models have several advantages over n-gram LMs:\n",
        "1. They don’t need smoothing\n",
        "2. They can handle much longer histories.\n",
        "3. They can generalize over contexts of similar words.\n",
        "4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
        "Disadvantage: slower to train than traditional n-gram LMs\\n\\n\n",
        "\n",
        "__The input__ to the neural network is a k-gram of words w1:k.\n",
        "__The output__ is a probability distribution over the next word.\n",
        "The k context words are treated as a word window. Each word is associated with an\n",
        "__embedding__ vector: x = [v(w1);v(w2);...;v(wk)]\n",
        "\\n\\n\n",
        "__Training__\\n\n",
        "The training examples are simply word k-grams from the corpus\n",
        "The identities of the first k-1 words are used as features, and the last word is used as\n",
        "the target label for the classification.\n",
        "Conceptually, the model is trained using cross-entropy loss\\n\\n\n",
        "\n",
        "__Advantages of NN LMs__\\n\n",
        "Better results. They achieve better preplexity scores than SOTA n-gram LMs.\n",
        "Larger N. NN LMs can scale to much larger orders of n. This is achievable because\n",
        "parameters are associated only with individual words, and not with n-grams.\n",
        "They generalize across contexts. For example, by observing that the words blue,\n",
        "green, red, black, etc. appear in similar contexts, the model will be able to assign a\n",
        "reasonable score to the green car even though it never observed in training, because it\n",
        "did observe blue car and red car.\n",
        "A by-product of training are word embeddings\n",
        "\\n\\n\n",
        "__Word2vec__\\n\n",
        "- Instead of counting how often each word w occurs near \"apricot\"\n",
        "- Train a classifier on a binary prediction task:\n",
        "  - Is w likely to show up near \"apricot\"?\n",
        "- We don’t actually care about this task\n",
        "- But we'll take the learned classifier weights as the word embeddings\n",
        "\\n\\n\n",
        "__Skip-gram algorithm__\n",
        "1. Treat the target word and a neighboring context\n",
        "word as positive examples.\n",
        "2. Randomly sample other words in the lexicon to get\n",
        "negative samples\n",
        "3. Use logistic regression to train a classifier to\n",
        "distinguish those two cases\n",
        "4. Use the weights as the embeddings\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "dfdf56e9-f0aa-4ba7-8606-ed89fea86209"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\nA __recurrent neural network (RNN)__ is any network that contains a cycle within its\nnetwork connections, meaning that the value of some unit is directly, or indirectly,\ndependent on its own earlier outputs as an input.\n\n__Forward inference__ (mapping a sequence of inputs to a sequence of outputs) in an\nRNN is nearly identical to what we’ve already seen with feedforward networks.\n```\nfunction FORWARDRNN(x, network) returns output sequence y\n  ^0←0\n  for i←1 to LENGTH(x) do\n  h_i←g(Uh_i−1 + W_x_i)\n  y_i← f(V_h_i)\n  return y\n```\nAs with feedforward networks, __we’ll use a training set, a loss function, \nand backpropagation__ to obtain the gradients needed to adjust the weights in these recurrent\nnetworks.\n\nTailoring the backpropagation algorithm to this situation leads to a two-pass algorithm for training the weights in RNNs. In the first pass, we perform forward\ninference, computing ht, yt, accumulating the loss at each step in time, saving the\nvalue of the hidden layer at each step for use at the next time step. In the second\nphase, we process the sequence in reverse, computing the required gradients as we\ngo, computing and saving the error term for use in the hidden layer for each step\nbackward in time.\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\nRNN language models process the input sequence one word at a time, attempting to predict the next word from the current word and \nthe previous hidden state.\nTo train an RNN as a language model, we use a corpus of text as training material,\nhaving the model predict the next word at each time step t. We train the model to\nminimize the error in predicting the true next word in the training sequence, using\ncross-entropy as the loss function. Recall that the cross-entropy loss measures the\ndifference between a predicted probability distribution and the correct distribution.\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\nThis link between similarity in how words are distributed and similarity\nin what they mean is called the __distributional hypothesis__.\n\n__Vector semantics__: instantiates this linguistic hypothesis by learning representations of the meaning of words, called embeddings,\ndirectly from their distributions in texts.\n\nOne of the fundamental tenets of semantics, called the __principle of contrast__ states that a difference \nin linguistic form is always associated with some difference in meaning.\n\nOne common kind of relatedness between words is if they belong to the same\n__semantic field__. A semantic field is a set of words which cover a particular semantic\ndomain and bear structured relations with each other. For example, words might be\nrelated by being in the semantic field of hospitals (surgeon, scalpel, nurse, anesthetic, hospital), restaurants (waiter, menu, plate, food, chef).\n\nFinally, words have affective meanings or __connotations__.\n \n\n## SLP Chapter 6.2 Vector Semantics\n \n__Vector semantics__ is the standard way to represent word meaning in NLP, helping us model many of the aspects of word meaning.\n\nVectors for representing words are called __embeddings__ (although\nthe term is sometimes more strictly applied only to dense vectors like word2vec rather than sparse tf-idf or PPMI vectors).\n\n\n## SLP Chapter 6.3 Words and Vectors\n\nIn a __term-document matrix__, each row represents a word in the vocabulary and each term-document\nmatrix column represents a document from some collection of documents. This was first defined as part of the \n__vector space model__ of information retrieval (a document represented as a count vector).\nTerm-document matrices were originally defined as a means of finding similar\ndocuments for the task of document __information retrieval__. Information retrieval (IR) is the task of finding the document d from the D\ndocuments in some collection that best matches a query q.\n\nAn alternative to using the __term-document matrix__ to represent words as vectors of\ndocument counts, is to use the __term-term matrix__, also called the __word-word matrix__ or the __term-context matrix__.\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\nTo measure similarity between two target words v and w, we need a metric that\ntakes two vectors (of the same dimensionality, either both with words as dimensions,\nhence of length |V|, or both with documents as dimensions as documents, of length\n|D|) and gives a measure of their similarity. By far the most common similarity\nmetric is the __cosine of the angle between the vectors__.\n\nAs we will see, most metrics for similarity between vectors are based on the dot\nproduct. The dot product acts as a similarity metric because it will tend to be high\njust when the two vectors have large values in the same dimensions.\n\nThe dot product is higher if a vector is longer, with higher values in each dimension.\nMore frequent words have longer vectors, since they tend to co-occur with more\nwords and have higher co-occurrence values with each of them. The raw dot product\nthus will be higher for frequent words. But this is a problem; we’d like a similarity\nmetric that tells us how similar two words are regardless of their frequency.\n\nWe modify the dot product to normalize for the vector length by dividing the\ndot product by the lengths of each of the two vectors. This __normalized dot product__\nturns out to be the same as the cosine of the angle between the two vectors, following\nfrom the definition of the dot product between two vectors a and b:\n \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n__Word Meaning__\nHow should we represent the meaning of a word?\nIn N-gram LMs we represented words as a string of letters or as an index in a\nvocabulary list.\nIdeally, we want a meaning representation to encode:\n1. Synonyms – words that have similar meanings\n2. Antonyms – words that have opposite meanings\n3. Connotations – words that are positive or negative\n4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\npurchasing event\n5. Support for entailment\n\n\n\n\n__Term-Document Matrix__:\n- Each column vector represents a document\n- Each row vector represents a Term (a word)\n- The value in a cell is based on how often that term occurred in that document\n- The length of the document vectors is the size of the vocabulary\n- Document vectors can be sparse (most values are 0)\n- We can measure how similar two documents are by comparing their column vectors\n- Two rows can show us how similar two words are\n\n\n\n__Term-Term matrix/term-context matrix__:\n- Terms on the rows and column headers\n- Length of the row vector is now |V| instead of number of documents\n- The value in a cell indicates how often a word appears in a context window surrounding the word\n  - __Context windows__: w-2, w-1, target_word, w+1, w+2\n\n\n__Alternates to counts__\n\nRaw word frequency is not a great measure of association between words. It’s very\nskewed “the” and “of” are very frequent, but maybe not the most discriminative\nWe’d rather have a measure that asks whether a context word is particularly\ninformative about the target word.\nInstead of raw counts, it’s common to transform vectors using TF-IDF or PPM\n\n\n\n__TF-IDF__:\n- term frequency (how often a word occurred in a document) * inverse document frequency (1 over the number of documents that it occurred in)\n\n\n\n\n__Sparse v. Dense Vectors__\nCo-occurrence matrix (weighted by TF-IDF or mutual information)\n- Long (length |V| = 50,000+)\n- Sparse (most elements are zeros)\nAlternative: learn vectors that are\n- Short (length 200-1000)\n- Dense (most elements are non-zero)\n\n\n\nChain rule\nIn LMs we user chain rule to get the conditional probability of the next\nword in the sequence given all of the previous words:\n- P(w1w2...wt) = Pi_(t=1)^TP(wt|w1...w_(t-1))\nWhat assumption do we make in n-gram LMs to simplify this?\nThe probability of the next word only depends on the previous n-1\nwords.\nA small n makes it easier for us to get an estimate of the probability from data.\n\n\n\nUnseen sequences\nWhat happens when we have a new (unseen) combination of n words?\n__1. Back-off\n2. Smoothing / interpolation__\nWe are basically just stitching together short sequences of observed\nwords.\n\n\n\n__Alternate idea: Generalizing__\n\nTaking a sentence like \"The cat is walking in the bedroom\" and use it when we assign probabilities to similar sentences like\n\"The dog is running around the room\".\n\n\n\n__Neural Language Models__\n\nNeural Language models have several advantages over n-gram LMs:\n1. They don’t need smoothing\n2. They can handle much longer histories.\n3. They can generalize over contexts of similar words.\n4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\nDisadvantage: slower to train than traditional n-gram LMs\n\n\n\n__The input__ to the neural network is a k-gram of words w1:k.\n__The output__ is a probability distribution over the next word.\nThe k context words are treated as a word window. Each word is associated with an\n__embedding__ vector: x = [v(w1);v(w2);...;v(wk)]\n\n\n\n__Training__\n\nThe training examples are simply word k-grams from the corpus\nThe identities of the first k-1 words are used as features, and the last word is used as\nthe target label for the classification.\nConceptually, the model is trained using cross-entropy loss\n\n\n\n__Advantages of NN LMs__\n\nBetter results. They achieve better preplexity scores than SOTA n-gram LMs.\nLarger N. NN LMs can scale to much larger orders of n. This is achievable because\nparameters are associated only with individual words, and not with n-grams.\nThey generalize across contexts. For example, by observing that the words blue,\ngreen, red, black, etc. appear in similar contexts, the model will be able to assign a\nreasonable score to the green car even though it never observed in training, because it\ndid observe blue car and red car.\nA by-product of training are word embeddings\n\n\n\n__Word2vec__\n\n- Instead of counting how often each word w occurs near \"apricot\"\n- Train a classifier on a binary prediction task:\n  - Is w likely to show up near \"apricot\"?\n- We don’t actually care about this task\n- But we'll take the learned classifier weights as the word embeddings\n\n\n\n__Skip-gram algorithm__\n1. Treat the target word and a neighboring context\nword as positive examples.\n2. Randomly sample other words in the lexicon to get\nnegative samples\n3. Use logistic regression to train a classifier to\ndistinguish those two cases\n4. Use the weights as the embeddings\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "edd97757-b2f4-4a69-ee3d-ef409191e274"
      },
      "source": [
        "\n",
        "# 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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nBegin with an agent that nees to make a decision.\n- Agent has actions a\n- Agent assigns probability P(s) to each state s\n- May be uncertainty about action outcomes\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') = ∑_s P(s)P(s′|s,a)\nDecision theory deals with choosing among actions based on the desirability of their immediate outcomes\n(the environment is assumed to be __episodic__).\nAgent's preferences are catured by a __utility function__ U(s).\nThe expected utility EU(a) is the average utility value of the outcomes weighted by the probability that\nthe outcome occurs: EU(a) = ∑_s'P(RESULT(a)=s′)U(s′).\nMEU prinicple formalizes the general notion that an intelligent agent should \"do the right thing\" but\ndoes not tell us how -> estimating the probability distribution P(s) over possible states\nrequires perception, learning, knowledge representation, and inference.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nWhy is maximizing average utility so special? What's wrong with an agent that tries to minimize the worst possible loss?\n- A ≻ B the agent prefers A over B.\n- A ∼ B the agent is indifferent between A and B.\n- A ≻∼ B the agent prefers A over B or is indifferent between them.\n- What sorts of things are A and B? --> could be states of the world, but there is often uncertainty.\n- The set of outcomes for each action is a lottery L with outcomes S_1, ... ,S_n that occur with probabilities p_1,...,p_n\nis written L = [p1,S1; p2,S2; ... pn,Sn].\n  - Each outcome S_i can be an atomic state or another lottery\n  - Primary issue for utility theory is how to understand preferences between complex lotteries, so we list six constraints\n  (called the __axioms of utility theory__) that we require any reasonable preference relation to obey:\n    - __Orderability__: Exactly one of (A≻B),(B≻A),or(A∼B)holds.\n    - __Transitivity__: (A≻B)∧(B≻C) ⇒ (A≻C).\n    - __Continuity__: If some lottery B is between A and C in preference, then there is some probability p \n    for which teh rational agent will be indifferent between getting B for sure and the lottery \n    that yields A with p and C with 1-p. A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B.\n    - __Substitutability__: A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]. Also holds if we substitute ≻ for ∼\n    - __Monotonicity__: A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]).\n    - __Decomposability__: Compound lotteries can be reduced to simpler ones using laws of\n    probability. [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C].\n- We can derive from the axioms of utility theory the following consequences:\n  - __Existence of Utility Function__: There exists a function U such that U(A)>U(B) ⇔ A≻B and U(A)=U(B) ⇔ A∼B.\n  - __Expected Utility of a Lottery__: The utility of a lottery is the sum of the probability of each outcome: U([p1,S1;...;pn,Sn])=∑_ipiU(Si).\n- An agent's behavior would not change if utility function U(S) were transformed according to U′(S)=aU(S)+b, where a and b are constants and a > 0;\n  a positive affine transformation\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n\nUtility functions map from lotteries to real numbers.\n- __preference elicitation__: presenting choices to the human an using the observed preferences to pin down the underlying utility function\n- We fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible catastrophe” at U (S) = u⊥ \n- __Normalized utilities__: use a scale with u⊥ = 0 and u⊤ = 1\n- We can assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery [ p, u⊤ ; (1 − p), u⊥ ]\n  - The probability p is adjusted until the agent is indifferent between S and the standard lottery\n- __micromort__: a one in a million chance of death, used in medical and safety analysis\n  - in the UK, driving in a car for 230 miles incurs a risk of one micromort\nExample: You win 1,000,000 prize and you can gamble it with the flip of a coin: heads you get nothing, tails you get 2,500,000.\n- The __expected monetary value (EMV)__ is 1/2 (0) + 1/2 (2,500,000) = 1,250,000 which is more than the original 1,000,000\n- Utility is not directly proportional to monetary value\n- Found that the utility of money was almost exactly proportional to the logarithm of the amount\n- Agents with utility curves with decreasing slopes are __risk-averse__\n- The difference between the EMV of a lottery and its certainty equivalent is called the __insurance premium__\n- Agents with linear curve is said to be __risk-neutral__\n- Rational way to choose the best action, a* is to maximize expected utility: a* = argmax EU(a)\n  - We are usually estimating EU though, but we are assuming that the estimates are __unbiased__, meaning the expected\n  value of the error E(EU(a)−EU(a)) is zero\n  - The real outcome will usually be significantly worse than we estimated --> tendenceny for the estimated expected utility\n  to be too high is called the __optimizer's curse__\n  - Calculate the distribution of the maximum of k estimates (this calc is a special case of computing an __order statistic__, the\n  distribution of any particular ranked element of a sample)\n\n- Decision theory is a __normative theory__: it describes how a rational agent SHOULD act\n- __Descriptive theory__ describes how actual agents (i.e. humans) really do act\n- __Certainty effect__ people are strongly attracted to gains that are certain\n- __Ambiguity aversion__: Most people elect the known probability rather than the unknown unknowns\n- __Framing effect__: Exact wording of a decision problem can have a big impact on the agent's choices\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- Transition model with stochastic outcome is written as P(s'|s,a) for the probability reaching state s' if action a is done in state s,\nalso written as T(s,a,s')\n- __Markovian__: the probability of reaching s' from s depends only on s and not on the history of earlier states\n- Since the decision problem is sequential, the utility function will depend on a sequence of states and actions, an __environment history__\n- Agent receives a __reward__ R(s,a,s') for every transition from s to s' via a\n- Methods for solving Markov Decision Problems usually involve dynamic programming\n- A solution to the problem:\n  - Must specify what the agent should do for any state that the agent might reach, a __policy__ π, where π(s) is the recommended\n  policy for state s\n  - The quality of a policy is measured by the expected utility of the possible environment histories generated by that policy\n  - __optimal policy__ π* yields the highest expected utility\n- __finite horizon__: there is a fixed time N after which nothing matters, a policy that depends on the time is called __nonstationary__\n- __discount factor__ γ is a number between 0 and 1, describes the preference of an agent for current rewards over future rewards\n  - γ close to 0 means rewards in the distance future are viewed as insignificant\n  - γ close to 1 means an agent is more willing to wait for long-term rewards\n- __proper policy__: a policy that is guaranteed to reach a terminal state\n- The true utility of a state is U^π∗ (s), the expected sum of discounted rewards if the agent executes an optimal policy\nUtility of a state is __the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses\nthe optimal action__: \n  - U(s)= max ∑_s'P(s′|s,a)[R(s,a,s′)+γU(s′)].\n- __Q-function__: Q(s,a) is the expected utility of taking a given action in a given state. U(s) = max Q(s, a)\n  - The optimal policy can be extracted from Q as follows: π∗(s) = argmax_a Q(s,a)\n  - Bellman equation for Q: \n    - Q(s,a) = ∑P(s′ |s,a)[R(s,a,s′)+γ U(s′)]\n    - Q(s,a) = ∑P(s′ |s,a)[R(s,a,s′)+γ maxQ(s′,a′)]\n\n- R′(s,a,s′)=mR(s,a,s′)+b transformation leaves the optimal policy unchanged in an MDP\n  - Let Φ(s) be any function of the state s, then according to __shaping theorem__, the following transformation\n  leaves the optimal policy unchanged: R′(s,a,s′) = R(s,a,s′)+γΦ(s′)−Φ(s)\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nFour different algorithms for solving MDPs: __value iteration, policy iteration, linear programming__ (exact solutions), and __Monte Carlo planning__ \n(approximate algorithms).\n- __Value Iteration__: if there are n possible states, then there are n Bellman equations\n```\nfunction VALUE-ITERATION(mdp, ǫ) returns a utility function\n  repeat\n    U←U′; δ←0\n    for each state s in S do\n      U′[s]←maxa∈A(s) Q-VALUE(mdp,s,a,U)\n      if |U′[s] − U[s]| > δ then δ←|U′[s] − U[s]| \n    until δ ≤ ǫ(1−γ)/γ\n    return U\n```\n  - Iteration step, called a __Bellman update__: Ui+1(s)← max ∑P(s′|s,a)[R(s,a,s′)+γUi(s′)]\n  - Guaranteed to reach an equilibrium\n  - After i iterations of value iteration, the agent has an estimate U_i of the true utility U and obtains the MEU policy\n  based on one-step look-ahead using U_i\n- __Policy interation__: if one action is clearly better than all others, then the exact utilities on the states need not be precise, policy\niteration alternates the following two steps:\n  - __Policy evaluation__: given π_i, calculate U_i=U^π_i, the utility of each state if π_i were to be executed\n  - __Policy improvement__: Calculate a new MEU policy π_i+1, using one-step look-ahead based on Ui\n```\nfunction POLICY-ITERATION(mdp) returns a policy\nrepeat\n  U ← POLICY-EVALUATION(π, U, mdp) unchanged?←true\n  for each state s in S do\n    a∗ ← argmax_a∈A(s) Q-VALUE(mdp, s, a, U) \n    if Q-VALUE(mdp,s,a∗,U) > Q-VALUE(mdp,s,π[s],U)then π[s]←a∗; \n      unchanged?←false\n  until unchanged? \n  return π\n```\n  - Implementing policy iteration is easier than standard Bellman:\n    - Ui+1(s) ← ∑P(s′ |s,πi(s))[R(s,πi(s),s′)+γUi(s′)]\n- __Linear programming__: consider as variables in the LP the utilities U(s) of each state s, noting that the utilities\nfor an optimal policy are the highest utilities attainable\n  - Seek to minimize U(s) for all s: U(s) ≥ ∑P(s′ |s,a)[R(s,a,s′)+γU(s′)] for every state s and every action a\n- __Real-time dynamic programming (RTDP): can work well with moderate-size to larger domains (Tetris)\n\n\n\n## Module 8 Lecture Notes\n\n- __Markovian__ transition: probability of arriving in s' depends only on s and not the history of earlier states\nMarkov Decision Problem (MDP):\n- sequential decision problem\n- fully observable environment\n- stohcastic transition model\n- additive rewards\n- one way to solve in expectimax search\n- the solution to an MDP is a policy\n- performance = sum of rewards\nTo find a solution to an MDP, you need to define the following things:\n- A set of states s in S\n- A set of actions a in A\n- A transition function T(s,a,s')\n  - This probability is called __the model__\n- A reward function R(s,a,s')\n- An initial state s_0\n- Optionally, one or more __terminal states__\nThe __discount__ is how much we are willing to postpone immediate gratification\nTo make a game not last forever:\n- discounting\n- __finite horizon__: terminate after a fixed T steps\n- __absorbing state__: guarantee that with each policy, a terminal state will be reached\nOptimal Quantities:\n- V*(s) = value (utility) of a state s, expected utility of starting in s and acting optimally\n- Q*(s,a) = value (utility) of a q-state (s,a), expected utility of starting out having taken action a from state s and acting optimally\n\nV*(s) = max_a Q*(s,a) --> taking the max over all possible actions from s\nQ*(s,a) = ∑_s' T(s,a,s')[R(s,a,s') + γV*(s')]\nV*(s) = max_a ∑_s' T(s,a,s')[R(s,a,s') + γV*(s')]\n\n__Value Iteration Algorithm__\n- Start with V_0(s) = 0\n- Given a vector fo V_k(s) values, do one ply of expectimax from each state:\n  - V_k+1 (s) = max_a ∑_s' T(s,a,s')[R(s,a,s') + γV_k(s')]\n- Repeat until convergence\n- Complexity is O(S^2A)\n- Theorem: will converge to unique optimal values\n__Policy Evaluation__\n- Expectimax trees max over all actions to compute the optimal values --> if we fixed some policy π(s), then the tree would be simpler -\nonly one action per state\n- Steps:\n  - Turn recursive Bellman equations into updates (like value iteration)\n    - V_0^π(s) = 0\n    - V_k+1^π(s) = ∑_s' T(s,π(s),s')[R(s,π(s),s') + γV^π_k(s')]\n- Without the maxes, the Bellman equations are just a linear system\n- O(S^2) per iteration\n- __Policy extraction__: a mini-expectimax (one step): π^*(s) = argmax_a ∑_s' T(s,a,s')[R(s,a,s') + γV*_k(s')]\n- If we have the optimal q-values, then policy improvement: π^*(s) = argmax_a Q*(s,a)\nComparison of value iteration and policy iteration:\n- Value iteration:\n  - Every iteration updates both values and implictly the policy\n  - We don't track the policy, but taking the max over actions implicitly recomptues it\n- Policy iteration\n  - Several passes that update utilities with fixed policy\n  - After the policy is evaluated, a new policy is chosen\n  - The new policy will be better (or we're done)\n\n__Utilities__ are functions from outcomes (states of the world) to real numbers that describe an agent's preferences\n- An agent must have preferences among:\n  - Prizes: A, B, etc\n  - Lotteries: situations with uncertain prizes: L = [p, A; (1-p), B]\n- __Maximum expected utility (MEU) principle__:\n  - Choose the action that maximizes expected utility\n\n__Markov property__: Given the present state, the future and past are independent.\nWhich of the following is unnecessary to construct a dynamic Bayesian model (DBN)?: Multiple state and evidence variables\n(The sensor model, transition model, and prior distribution over the state variables are necessary)\n  \n \n\n## Module 8 Definitions\n* **Utility function** - agent's preferences\n* **Expected utility** - EU(a), average utility value of the outcomes\n* **Maximum expected utility (meu)** - rational agent should choose the action that maximizes agent's EU\n* **Sequential decision problems** - agent's utility depends on a sequence of decisions\n* **Dynamic decision networks (ddns)** - factored representations to represents MDPs by extending dynamic Bayesian networks\n* **Contraction** - basic concept used to show that value iteration converges\n* **Online algorithm** - agent does a significant amount of computation at each decision point\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \n- one-armed bandit = slot machine\n- __n-armed bandit__ has n levers\n  - which of n possible new treatments to try to cure a disease, which of n possible investments to put part of your savings into\n- tradeoff between __exploitation__ and __exploration__\n- __bandit problems__:\n  - each arm M_i is a __Markov reward process__ or MRP (an MDP with only one possible action a_i)\n  - has states S_i, transition model P_i(s'|s,a), reward R_i(s,a_i,s')\n  - arms are independent\n- __Bernoulli bandit__: each arm M_i produces a reward of 0 or 1 with a fixed but unknown probability μ_i\n  - The state of arm Mi is defined by s_i and f_i, the counts of successes (1s) and failures (0s) so far for that arm; the transition probability predicts the next \n  outcome to be 1 with probability (s_i)/(s_i + f_i) and 0 with probability (f_i)/(s_i + f_i)\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n__Reinforcement learning__: agent interacts with the world and periodically receives __rewards__\n- Want to maximize the expected sum of rewards\n- Differs from \"just solving an MDP\" because the agent is not given the MDP, the agent is IN the MDP\n  - May not know the transition model or the reward function\n- Win/loss rewards for chess are __sparse__ because for the vast majority of states, this is not an informative signal at all\n-\nVariety of approaches to reinforcement learning:\n- __Model-based reinforcement learning__: agent uses transition model, model may be initially unknown, often learn a __utility function__ U(s) as\ndefined in Chapter 17 as sum of rewards from state s onward\n- __Model-free reinforcement learning__: Agent neither knows nor learns a transition model, instead, it learns a more direct representation of how to behave:\n  - __Action-utility learning__: Agent learns a __q-function__ denoting the sum of rewards from state s onward if action a is taken\n  - __Policy search__: The agent learns a policy π(s) that maps directly from states to actions. This is a __reflex agent__\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nStart with simple case offully observable environment with a small number of actions and states, in which an agent already has a \nfixed policy π(s) that determines its actions. The agent is trying to learn the utility function U^π(s), the expected total discounted\nreward if policy π is executed beginning in state s. This is called a __passive learning agent__.\n- Passive learning task is similar to __policy evaluation__ from 17.2.2. But now the passive learning agent does not know the transition model P(s'|s,a)\n- __Direct utility estimation__: the utility of a state is defined as the expected total reward from that state onward (called the expected __reward-to-go__)\n  - Each example is a (state, reward-to-go) pair --> the utility of a state is determined by the reward and the expected utility of the successor states\n  - Utility values obey the Bellman equations for a fixed policy:  U_i(s) = ∑_s'P(s′|s,πi(s))[R(s,πi(s),s′)+γUi(s′)].\n- __Adaptive dynamic programming__: takes advantage of the constraints among the utilities of states by learning the transition model that connects them\nand solving the corresponding Markov decision process using DP\n  - We adopt a __modified policy iteration__ using a simplified value iteration process to update the utility estimates after each change to the learned model\n- __Temporal-difference learning__: Uπ(s)←Uπ(s)+α[R(s,π(s),s′)+γUπ(s′)−Uπ(s)]\n  - Adjust the utility estimates toward the ideal equilibrium that holds locally when the utility estimates are correct\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nA passive learning agent has a fixed policy that determines its behavior. An __active learning agent__ gets to decide what actions to take.\n- Needs to learn a complete transition model with outcome probabilities for all actions, rather than just the model for the fixed policy\n- The utilities it needs to learn are those defined by the _optimal policy_; they obey the Bellman equations\n- The agent does not learn the true utilities or the true optimal policy!\n- Agent must make a tradeoff between exploitation of the current best action to maximize its short-term reward and exploration of previously\nunknown states to gain information that can lead to a change in policy (and to greater rewards in the future)\n- A __GLIE__ scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed\n  - One simple GLIE scheme is to have the agent choose a random action at time step t with probability 1/t and to follow the \n  greedy policy otherwise\n- Real-world we can't just choose to randomly explore\n  - hoose a policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, \n  even if the policy happens to be suboptimal for the maximum-likelihood model. Approaches:\n    - __Bayesian reinforcement learning__: assumes a prior probability P(h) over hypotheses h about what the true model is; the posterior probability P(h|e) \n    is obtained in the usual way by Bayes’ rule given the observations to date\n      - π∗ = argmax ∑_h P(h|e) U_h^π \n    - __Robust control theory__: allows for a set of possible models H without assigning probabilities to them, \n    and defines an optimal robust policy as one that gives the best outcome in the worst case over H\n      - π∗ = argmax(min U_h^π) \n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\nSolving MDPs is __offline planning__:\n- Determine all quantities through computation\n- Need to know the details of the MDP\n- Do not need to actually play the game!\n__Online planning__ is when we do NOT know the probabilities! Still an MDP, just can't solve through computation.\n- This is __reinforcement learning__:\n  - __Exploration__:  you have to try unknown actions to get information\n  - __Exploitation__: eventually, you have to use what you know\n  - __Regret__: even if you learn intelligently, you make mistakes\n  - __Sampling__ : because of chance, you have to try things repeatedly\n  - __Difficulty__: learning can be much harder than solving a known MDP\n- Since reinforcement learning is still a MDP:\n  - A set of states s ∈ S\n  - A set of actions (per state) A\n  - A model T(s,a,s’)\n  - A reward function R(s,a,s’)\n  - Still looking for a policy π(s)\n  - Twist: We do not know T or R, we need to try actions and states to learn\n__Model-Based Learning__: Learn an approximate model based on experiences, and 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 and 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\n    - For example, use value iteration, as before\n__Model-Free Learning__: Compare results of an action to what we thought was going to happen to what did happen. When something deviates, we adjust values up and down.\nWe just keep track of values of states.\n- __Passive Reinforcement Learning__\n  - Simplified task: policy evaluation\n  - Input: a fixed policy π(s)\n  - You don’t know the transitions T(s,a,s’)\n  - You don’t know the rewards R(s,a,s’)\n  - Goal: learn the state values. Note: this is NOT offline planning since we actually take actions in the world\n  - __Direct evaluation__: Compute values for each state under π\n    - Idea: Average together observed sample values (Act according to π. Every time you visit a state, write down what the sum of discounted \n     rewards turned out to be. Average those samples)\n      - REMEMBER: The value of being in a state is from that point TO THE END\n    - Pros of direct evaluation:\n      - It’s easy to understand\n      - It doesn’t require any knowledge of T, R\n      - It eventually computes the correct average values, using just sample transitions\n    - Cons of direct evaluation:\n      - It wastes information about state connections\n      - Each state must be learned separately\n      - So, it takes a long time to learn\n    - So can we use __policy evaluation__? We would need T and R!\n    - What about __sample-based policy evaluation__?\n      - We want to improve our estimate of V by computing these averages:\n        - V^π_(k+1)(s) = ∑_s' T(s, π(s), s')[R(s, π(s), s') + γV^π_k(s')]\n      - We do this by taking samples of outcomes s' and average\n        - sample_1 = R(s,π(s),s_1')+ γV^π_k(s_1')\n        - V^π_(k+1)(s) = 1/n ∑_i sample_i\n  - __Temporal Difference Learning__: learn from every experience (instead of waiting for the end)!\n    - Update V(s) each time we experience a transition (s, a, s’, r)\n    - 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    - Sample of V(s): sample = R(s,π(s),s')+ γV^π_k(s')\n    - Update to V(s): V^π(s) = (1-a)V^π(s)+ (a)sample\n      - a (alpha) is a value we get to set, it tells us how much our sample should update the value\n      - This is the same as V^π(s) = V^π(s)+ a(sample - V^π(s))\n    - __Exponential moving average__\n      - The running interpolation update: (bar on top) x_n = (1-a)x_(n-1)+ax_n\n      - Makes recent samples more important!\n      - Forgets about the past (distant past values were wrong anyway)\n    - Problems with temporal difference value learning:\n      - TD value leaning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages\n      - However, if we want to turn values into a (new) policy, we’re sunk\n        - π(s) = argmax_s Q(s,a)\n      - Idea: learn Q-values, not values!\n- __Active Reinforcement Learning (Q-Learning)__: full reinforcement learning: optimal policies (like value iteration)\n  - We can choose the actions now\n  - Goal: learn the optimal policy/values\n  - Learner makees the choices!\n  - Fundamental tradeoff: exploration vs. exploitation\n  - NOT offline planning: we take actions in the world and find out what happens\n  - __Q-Value Iteration__:\n    - For value iteration: start with V_0(s) = 0, which we know is right and calculate V_(k+1)(s) = max_a  ∑_s' T(s, a, s')[R(s, a, s') + γV_k(s')]\n    - For Q-value iteration: Start with Q_0(s,a) = 0, which we know is right\n      - Given Q)k, calculate the depth k+1 q-values for all q-states: Q_(k+1)(s,a) = ∑_s' T(s, a, s')[R(s, a, s') + γmax_a' Q_k(s',a')]\n  - __Q-Learning__: instead of Q-value iteration, we're going to do it based on SAMPLEs that we learn\n    - Learn Q(s,a) values as you go\n      - Samples (s,a,s',r)\n      - Consider old estimate: Q(s,a)\n      - Consider new sample estimate: sample = R(s,a,s')+γmax_a' Q_k(s',a')\n      - Incorporate the new estimate into a running average: Q(s,a) = (1-a)Q(s,a) + a[sample]\n      - Amazing result: __Q-learning converges to optimal policy__, even if you're acting suboptimally!\n      - This is called __off-policy learning__\n      - Caveats: \n        - You have to explore enough\n        - You have to eventually make the learning rate small enough, but not decrease it too quickly\n        - Basically, in the limit, it doesn’t matter how you select actions (!)\n- How do we explore? We have several schemes for forcing exploration\n  - Simplest: __random actions (ε-greedy):\n    - With (small) probability ε, act randomly\n    - With (large) probability 1-ε, act on current policy\n    - Problems: We do eventually explore the space, but keep thrashing (pick things repeatedly that are bad) around once learning is done\n      - One solution: lower ε over time\n      - Another solution: exploration fucntions\n  - __Exploration function__: Takes a value estimate u (current utility estimate) and a visit count n (# of times we've visited that state), \n  and returns an optimistic utility, e.g f(u,n) = u + k/n, k is a bonus for exploring a state\n    - Modified Q-update: Q(s,a) = R(s,a,s')+γmax_a'f(Q(s',a'), N(s',a'))\n__Regret__ is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n- __Approximate Q-Learning__: In realistic situations, we cannot possibly learn about every single state! Too many states to visit all, too many states to hold q-tables in memory\n  - Instead, we want to generalize: learn about some small number of training states from experience\n  - Flashback: __evaluation functions__ score non-terminals in depth-limited search\n    - Ideal function: returns the actual minimax value of the position\n    - In practice: typically weighted linear sum of features:\n      - Eval(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)\n        e.g. f_1(s) = (num white queens - num black queens)\n  - __Linear value functions__: Using a feature representation, we can write a q function (or value function) for any state using a few weights\n    - V(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)\n    - Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a) + ... + w_nf_n(s,a)\n    - Advantage: our experience is summed up in a few powerful numbers\n    - Disadvantage: states may share features but actually be very different in value!\n  - EQUATION for Approximate Q-Learning: Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a) + ... + w_nf_n(s,a)\n  - Given a transition (s,a,r,s'), what is the difference = [r+γmax_a' Q(s',a')]-Q(s,a)\n    - Q(s,a) = Q(s,a) + a[difference] is Exact Q's\n    - w_i = w_i + a[difference]f_i(s,a) is Approximate Q's\n      - So APPROXIMATE Q-learning is us updating the WEIGHTs\n    - Intuitive interpretation: Adjust weights of active features. e.g., if something unexpectedly bad happens, blame the features that were on:\n    disprefer all states with that state’s features\n \n\n## Module 9 Definitions\n* **Gittins index** - provides simple optimal policy for any bandit problem\n* **Thompson sampling** - chooses an arm randomly according to the prob. that the arm is optimal given the samples so far\n* **Bandit superprocess (bsp)** - each arm is a full Markov decision process rather than being a Markov reward process (w/ only one action)\n* **Dominating policy** - by addings actions to states, we can always create a relaxed version of an MDP\n* **Prioritized sweeping heuristic** - ranks possible adjustments in TD learning to prefer adjustments to states whose likely successors have just undergone a large adjustment in their utility estimates\n* **Greedy agent** - greedily takes the action that it currently believes to be optimal at each step\n* **Glie** - Greedy in the limit of infinite exploration\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- To make choices, an agent must first have preferences among the different possible outcomes of the various plans.\n- We use utility theory to represent preferences and reason quantitatively with them\n- __Decision theory__: Decision theory = probability theory + utility theory\n- Principle of __maximum expected utility (MEU)__: _an agent is rational if and only if it chooses the action that yields the highest \nexpected utility, averaged over all the possible outcomes of the action_\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- Conditional probability: P(a|b) = P(a∧b)/P(b) OR  P(a∧b) = P(a|b)P(b) .\n- __Probability density functions__ (sometimes called pdfs) differ in meaning from discrete distributions\n  - Saying that the probability density is uniform from 18C to 26C means that there is a 100% chance that the temperature \n  will fall somewhere in that 8C-wide region and a 50% chance that it will fall in any 4C-wide sub-region, and so on\n- __Joint probability distribution__: distributions on multiple variables\n- __inclusion–exclusion principle__: P(a∨b) = P(a)+P(b)−P(a∧b)\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- __marginalization__: P(Y) = ∑_z P(Y,Z=z),\n\n\n## AIMA Chapter 12.4 Independence\n\n- __independence__: P(X |Y)=P(X) or P(Y |X)=P(Y) or P(X,Y)=P(X)P(Y)\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n- __Bayes' rule__: P(Y|X)= P(X|Y)P(Y) / P(X)\n- __Conditional independence__: P(X,Y|Z) = P(X|Z)P(Y|Z)\n  - P(X|Y,Z)=P(X|Z) and P(Y|X,Z)=P(Y|Z)\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- Commonly occurring pattern in which a single cause directly \ninfluences a number of effects, all of which are conditionally independent, given the cause. The full joint distribution can be written as\n  - P(Cause,Effect_1,...,Effect_n) = P(Cause)∏P(Effect_i|Cause)\n- This probability distribution is called a __naive Bayes__ model\n  - Sometimes called a __Bayesian classifier__\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n\nLet’s begin with the task of computing P(w|h), the probability of a word w given\nsome history h.\nNow how can we compute probabilities of entire sequences like P(w1,w2,...,wn)?\nOne thing we can do is decompose this probability using the chain rule of probability:\n- P(X1...Xn) = P(X1)P(X2|X1)P(X3|X1:2)...P(Xn|X1:n−1) \nThe bigram model, for example, approximates the probability of a word given\nall the previous words P(wn|w1:n−1) by using only the conditional probability of the\npreceding word P(wn|wn−1) --> this is a __Markov__ assumption\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nThe best way to evaluate the performance of a language model is to embed it in\nan application and measure how much the application improves. Such end-to-end\nevaluation is called __extrinsic evaluation__. An __intrinsic evaluation__ metric is one that measures \nthe quality of a model independent of any application. \n- __perplexity__ can be thought of as the __weighted average branching factor of a language__.\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n\nTo keep a language model from assigning\nzero probability to these unseen events, we’ll have to shave off a bit of probability\nmass from some more frequent events and give it to the events we’ve never seen.\n__smoothing__. This modification is called __smoothing__ or __discounting__.\nThe simplest way to do smoothing is to add one to all the n-gram counts, before\nwe normalize them into probabilities. All the counts that used to be zero will now\nhave a count of 1, the counts of 1 will be 2, and so on. This algorithm is called\n__Laplace smoothing__. \n\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n__Uncertainty__:\n- __Observed variables (evidence)__: Agent knows certain things about the state of the world (e.g.,\nsensor readings or symptoms)\n- __Unobserved variables (states)__: Agent needs to reason about other aspects (e.g. where an object\nis or what disease is present)\n- __Model__: Agent knows something about how the known variables relate to the unknown variables\n__Axioms of Probability__:\n- 0 <= P(w) <= 1 for every w\n- ∑_(w in Omega) P(w) = 1\n__Joint Distributions__:\n- A joint distribution over a set of random variables: X_1, X_2,...,X_n specifies a real number for each assignment (or outcome): \n- A probabilistic model is a joint distribution over a set of random variables\n- Joint distributions: say whether assignments (outcomes) are likely\n__Events__: an event is a set E of outcomes\n__Marginal Distributions__: Marginal distributions are sub-tables which eliminate variables\n- Marginalization (summing out): Combine collapsed rows by adding\n  - P(t) = ∑_s P(t,s)\n__Conditional Distributions__:\n- Conditional distributions are probability distributions over some variables given fixed values of others (i.e. P(W|T=hot))\n__Probabilistic inference__: compute a desired probability from other known probabilities (e.g. conditional from joint)\n- Probabilities change with new evidence\n- Inference by enumeration, general case, we split our random variables into 3 sets of things:\n  - Evidence variables E_1...E_k = e_1...e_k\n  - Query* variable: Q (things we care about)\n  - Hidden variables H_1...H_r (things that occur in our big joint probability, not things we've observed or are actively reasoning about)\n  - We want: P(Q|e_1...e_k)\n  - Step 1: Select the entries consistent with the evidence\n  - Step 2: Sum out H to get joint of query and evidence\n    - If we had a,b,c, we would have ∑_b P(a,b,c) = P(a,c) (if b is the hidden variable)\n  - Step 3: Normalize (x 1/Z)\n- __Product Rule__: P(y)P(x|y) = P(x,y)\n  - More generally, __chain rule__: P(x_1,x_2,...,x_n) = product from i to n of (P(x_i| x_1...x_i-1))\n- __Bayes' Rule__: P(x|y) = P(y|x)P(x)/P(y)\n__Probabilistic Language Models__\n- Assign a probability to a sentence (autocomplete for texting, machine translation, spelling correction, speech recognition)\n  - Goal: Compute probability of a sequence of words: P(W) = P(w_1,w_2,...,w_n)\n  - Related task: compute probability of an upcoming word: P(w_5|w_1,w_2,w_3,w_4)\n  - Example: P(\"the underdog Philadelphia Eagles won\") = P(the) x P(underdog|the) x P(Philadelphia| the underdog) x P(Eagles| the underdog Philadelphia) x P(won|the underdog Philadelphia Eagles)\n  - How to estimate these probabilities? __Maximum likelihood estimation (MLE)__\n    - P(won|the underdog team) = Count(the underdog team won) / Count(the underdog team)\n    - Problem: some sentences never appear in the sample, so we're limited by data constraints\n  - So we use a simplifying assupmtion: __Markov Assumption__! The probability of moving to next state only depends on the current state\n    - So we're saying that P(won|the underdog team) approx equals P(won|team)\n    - Only depends on previous k words, not the whole context (example above is k=1)\n    - unigram = no history, bigram = 1 word as history, trigram = 2 words as history, 4-gram = 3 words as history\n    - __Bigram model__: Condition on the previous word: P(w_i|w_1w_2...w_i-1) approx equals P(w_i|w_i-1)\n      - Maximum likelihood estimate: P(w_i|w_i-1) = count(w_i-1, w_i)/count(w_i-1)\n\nHow many ways are there to apply the chain rule to a joint distribution with NN random variables? N!\n\nHow are n-gram language models typically evaluated? (Perplexity on a test set)\n\n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states that an agent might be in\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\nA Bayesian network is a directed graph in which each node is annotated with quantitative probability information. \n1. Each node corresponds to a random variable, which may be discrete or continuous.\n2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to node Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a DAG.\n3. Each node Xi has associated probability information θ(Xi |Parents(Xi)) that quantifies the effect of the parents on the node using a finite number of __parameters__.\nThe topology of the network (sets of nodes and links) specifies the conditional independence relationships that hold.\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nThe __syntax__ of a Bayes net consists of a directed acyclic graph with some local \nprobability information attached to each node. The __semantics__ defines how the syntax corresponds to a \njoint distribution over the variables of the network. Assume that the Bayes net contains n variables, X1,...,Xn. \nA generic entry in the joint distribution is then P(X1=x1 ∧...∧Xn=xn), or P(x1,...,xn).\nBayes nets defines each entry in the joint distribution as follows:\nP(x1,...,xn) = ∏^n_(i=1)θ(x_i | parents(X_i))\n- __Chain rule__: P(x1,...,xn) = P(xn |xn−1,...,x1)P(xn−1 |xn−2,...,x1) ··· P(x2 |x1)P(x1) = ∏^n_(i=1) P(xi|xi−1,...,x1).\n- Compactness of Bayesian networks is an example of a general proprety of __locally structured (sparse)__ systems\n- A variable is conditionally independent of all other nodes in the network, given its parents,\nchildren, and children’s parents-that is, given its __Markov blanket__.\n\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- __variable elimination algorithm__: works by evaluating expressions in right-to-left order\n- __singly connected networks or polytrees__: have a particularly nice property:  the time and space complexity of exact inference in \npolytrees is linear in the size of the network\n- __multiply connected networks__: variable elimination can have exponential time and space complexity in the worst case, even\nwhen the number of parents per node is bounded\n  - inference in Bayes nets is NP-hard\n- Using __clustering__ algorithms can help us bring O(n^2) to O(n)\n  - Idea is to 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 \nX and Y are independent if for all x, y P(x,y) = P(x)P(y)\n\nX and Y are __conditionally indpendent__ given Z if P(x,y|z) = P(x|z)P(y|z)\n\n\n__Common cause__: Y points to X and Y points to Z\n- P(x,y,z) = P(y)P(x|y)P(z|y)\n\n__Common effect__: X and Y point to Z\n\nGiven a Bayes net, are two variables independent (given some evidence)? I.e. Are X and Y conditionally independent given evidence variables {Z}?\n- Yes, if X and Y \"d-separated\" by Z\n- Consider all (undirected) paths from X to Y\n- No active paths = independence!\n\n\nA path is active if each triple is active:\n- Causal chain A -> B -> C where B is unobserved (either direction)\n- Common cause A <- B -> C where B is unobserved\n- Common effect (aka v-structure) A -> B <- C where B or one of its descendents is observed\n\n\n__D-separation algorithm__\n- Check all (UNDIRECTED) paths between X_i and X_j\n  - If one or more active, then independence is NOT guaranteed\n  - If ALL paths inactive, then independence is guaranteed\n\n\n## Module 11 Definitions\n* **Leak-node** - covers 'miscellaneous causes'\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Nonparametric representation** - define the conditional probability implicitly with a collection of instances\n* **Hybrid bayesian network** - a network with both discrete and continuous variables\n* **Conditional gaussian** - when discrete variables are added as parents (not as children) of continuous variables\n* **Expit/inverse logit model** - uses the logistic function 1//(1+e^-x) to produce a soft threshold\n* **Hidden variables** - neither input nor output variables, but essential for structuring the network so it's reasonably sparse\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\nThe components of agents include:\n1. A direct mapping from conditions on the current state to actions.\n2. A means to infer relevant properties of the world from the percept sequence.\n3. Information about the way the world evolves and about the results of possible actions\n4. Utility information indicating the desirability of world states.\n5. Action-value information indicating the desirability of actions.\n6. Goals that describe the most desirable states.\n7. A problem generator, critic, and learning element that enable the system to improve.\nThree types of __feedback__ that can accompany inputs and determine the three main types of learning:\n- In __supervised learning__ the agent observes input-output pairs and learns a function that maps from input to output. \nFor example, the inputs could be camera images, each one accompanied by an output saying “bus” or “pedestrian,” etc. \nAn output like this is called a __label__. The agent learns a function that, when given a new image, predicts the appropriate label. \nIn the case of braking actions (component 1 above), an input is the current state (speed and direction of the car, road condition),\nand an output is the distance it took to stop. In this case a set of output values can be obtained by the agent from its own percepts (after the fact); \nthe environment is the teacher, and the agent learns a function that maps states to stopping distance.\n- In __unsupervised learning__ the agent learns patterns in the input without any explicit feedback. \nThe most common unsupervised learning task is clustering: detecting poten- tially useful clusters of input examples. \nFor example, when shown millions of images taken from the Internet, a computer vision system can identify a large cluster of \nsimilar images which an English speaker would call “cats.”\n- In __reinforcement learning__ the agent learns from a series of reinforcements: rewards and punishments. \nFor example, at the end of a chess game the agent is told that it has won (a reward) or lost (a punishment). \nIt is up to the agent to decide which of the actions prior to the reinforcement were most responsible for it, \nand to alter its actions to aim towards more rewards in the future.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nThe task of __supervised learning__ is: Given a training set of N example input–output pairs (x_1,y_1),(x_2,y_2),...(x_N,y_N),\nwhere each pair was generated by an unknown function y=f(x), discover a function h that approximates the true function f.\n- The function h is called a __hypothesis__ about the world\n- h is a __model__ of the data, drawn from a model class H, or we can say a function drawn from a function class\nWe call the output y_i the ground truth-the true answer we are asking our model to predict\n- __exploratory data analysis__: examining the data with statistical tests and visualizations—histograms, \nscatter plots, box plots—to get a feel for the data, and some insight into what hypothesis space might be appropriate\n- __consistent hypothesis__: an h such that each x in the training set has h(x ) = y \n- By __bias__ we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets\n- a hypothesis is __underfitting__ when it fails to find a pattern in the data\nOften there is a bias–variance tradeoff: a choice between more complex, low-bias hy- potheses that fit the training data well and simpler, \nlow-variance hypotheses that may gen- eralize better\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nA __decision tree__ is a representation of a function that maps a vector of attribute values to a single output value; a “decision.”\n- A decision tree reaches its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached\n- The decision tree learning algorithm chooses the attribute with the highest IMPORTANCE\n  - Importance is measured in terms of __entropy__, the fundamental quantity in information theory\n    - __Entropy__ = measure of uncertainy of a random variable. More information = less entropy\n    - Entropy: H(V) = ∑_kP(vk)lg P(vk) = −∑_kP(vk)lg P(vk)\n    - Rolling die = 2 bits of entropy, flipping a fair coin = 1 bit of entropy\n- For decision trees, a technique called __decision tree pruning__ combats overfitting \n  - Start with a full tree\n  - Look at test node that has only leaf nodes as descendants\n  - If the test seems irrelevant (detecting only noise), then we eliminate the test, replacing it with a leaf node\n- Statistical __significance test__: __null hypothesis__ (assume no underlying pattern)\nDecision trees can be made more widely useful by handling the following complications:\n- __Missing data__\n- __Continuous and multivalued input attributes__: better way to deal with this is a __split point__ test, an equality\ntest on the value of an attribute (like Weight > 160)\n- __Continuous-valued output attribute__: trying to predict a numerical output requires a __regression tree__ rather than a classification\ntree\nDecision trees are also __unstable__ in that adding just one new example can change the test at the root, which changes the entire tree\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nOur goal in machine learning is to select a hypothesis that will optimally fit future examples. To make that precise we need to define “future example” and “optimal fit.”\n__stationarity assumption__: we assume that each example E_j has the same prior probability distribution: P(E_j) = P(E_j+1)=P(E_j+2)=...\nand is independent of the previous examples: P(E_j) = P(E_j|E_j-1 E_j-2)\n- Examples that satisfy these equations are independent and identically distributed or i.i.d.\n__optimal fit__: the hypothesis that minimizes the __error rate__: the proportion of times that h(x) is not equal to y for an (x,y)\nexample\nNeed three data sets:\n1. A __training set__ to train candidate models.\n2. A __validation set__, also known as a __development set__ or dev set, to evaluate the candidate\nmodels and choose the best one.\n3. A __test set__ to do a final unbiased evaluation of the best model.\nWhat if we don’t have enough data to make all three of these data sets? We can squeeze more out of the data using a technique called __k-fold cross-validation__.\n- Each sample serves double duty: as training data and validation data\n- First split the data into k equal subsets\n- Then perform k rounds of learning, on each round 1/k of the data are held out as validation set and the remaining are used as training set\nThe extreme is k = n, also known as __leave-one-out cross-validation or LOOCV__.\nWe can think of the task of finding a good hypothesis as two subtasks: __model selection__ chooses a good hypothesis \nspace, and __optimization__ (also called training) finds the best hypothesis within that space\n__Model selection__:  It takes as argument a learn- ing algorithm, Learner\n__Bayesian optimization__ treats the task of choosing good hyperparameter values as a machine learning problem in itself.\nAn alternative to __Bayesian optimization__ is __population-based training (PBT)__. PBT starts by using random search to train (in parallel) a population of models, each with different hyperparameter values. Then a second generation of models are trained, \nbut they can choose hyperparameter values based on the successful values from the previous generation, as well as by random mutation, as in genetic algorithms\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nWe now show how to apply PAC learning to a new hypothesis space: __decision lists__. A decision list consists of a series of tests, each of which is a conjunction of literals.\nIf a test succeeds when applied to an example description, the __decision list__ specifies the value to be returned. \nIf the test fails, processing continues with the next test in the list. Decision lists resemble decision trees, but their overall structure is simpler: they branch only in one direction.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nA __univariate linear function__ (a straight line) with input x and output y has the form y=w_1x+ w_0, where w_0 and w_1 are real-valued coefficients to be learned.\nput y has the form y=w1x+ w0, where w0 and w1 are real-valued coefficients to be learned. \nWe use the letter w because we think of the coefficients as weights; the value of y is changed by changing the relative weight of one term or another.\nWe’ll define w to be the vector ⟨w0,w1⟩, and define the linear function with those weights as h_w(x)=w_1x+w_0.\nThe task of finding the h_w that best fits these data is called __linear regression__.\nAs discussed in Section 4.2 (page 119) we can search through a continuous weight space by incrementally modifying the parameters. \nThere we called the algorithm __hill climbing__, but here we are __minimizing loss, not maximizing gain__, so we will use the term __gradient descent__.\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\nIn this chapter, we intrdouce the naive Bayes algorithm and apply it to __text categorization__, the task of assigning a label or category to an entire text or document.\nWe focus on one common text categorization task, __sentiment analysis__, the extraction of sentiment.\n__Spam detection__ is another important commercial application, the binary classification task of assigning an email to one of the two classes spam or not-spam\n__Multinomial naive Bayes classifier__: a Bayesian classifier that makes a simplifying (naive) assumptino about how the features interact.\n__Naive bayes assumption__: conditional independence assumption that the probabilities P(f_i|c) are independent given teh class c and can be \nnaively multiplied as follows: P(f_1,f_2,...,f_n|c) = P(f_1|c) x P(f_2|c) x ... x P(f_n|c)\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\nP(w_i|c) = count(w_i,c)/sum of w in V (count(w,c)) (look in lecture notes!)\n \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\nClassification: given inputs x, predict labels y\nExamples:\n- Spam detection (input: document,\nclasses: spam / ham)\n-  OCR (input: images, classes: characters)\n- Medical diagnosis (input: symptoms,\nclasses: diseases)\n-  Automatic essay grading (input: document,\nclasses: grades)\n- Fraud detection (input: account activity,\nclasses: fraud / no fraud)\n- Customer service email routing\n\nClassification is an important commercial technology/n\n\n__Inference for Naive Bayes__:\n\nGoal: compute posterior distribution over label variable Y\n1. Get joint probability of label and evidence for each label\n\n  P(Y, f_1...f_n = [P(y_1,f_1...f_n); P(y_2,f_1...f_n); ... ; P(y_k,f_1...f_n)])\n2. Sum to get probability of evidence\n3. Normalize by dividing Step 1 by Step 2\n\n\n__General Naive Bayes__\nWhat do we need in order to use Naïve Bayes?\n- Inference method (we just saw this part)\n  - Start with a bunch of probabilities: P(Y) and the P(Fi\n|Y) tables\n  - Use standard inference to compute P(Y|F1…Fn)\n  - Nothing new here\n- Estimates of local conditional probability tables\n  - P(Y), the prior over labels\n  - P(Fi|Y) for each feature (evidence variable)\n  - These probabilities are collectively called the parameters of the model and denoted by q\n  - Up until now, we assumed these appeared by magic, but…\n  - ... they typically come from training data counts: we’ll look at this soon\n\n\n__Naive Bayes for Text__\nP(Y, W_1...W_n) = P(Y)Pi_i P(W_i|Y)\n\n__Generalization and Overfitting__\nRelative frequency parameters will overfit the training data!\n- Just because we never saw a 3 with pixel (15,15) on during training doesn’t mean we won’t\nsee it at test time\n- Unlikely that every occurrence of “minute” is 100% spam\n- Unlikely that every occurrence of “seriously” is 100% ham\n- What about all the words that don’t occur in the training set at all?\n- In general, we can’t go around giving unseen events zero probability\nAs an extreme case, imagine using the entire email as the only feature\n- Would get the training data perfect (if deterministic labeling)\n- Wouldn’t generalize at all\n- Just making the bag-of-words assumption gives us some generalization, but isn’t enough\nTo generalize better: we need to smooth or regularize the estimates\n\n\n## Module 12 Definitions\n* **Trasnfer learning** - knowledge from one domain is transferred to a new domain\n* **Factored representation** - a vector of attribute values\n* **Classification** - when the output is one of a finite set of values\n* **Underfitting** - when a hypothesis fails to find a pattern in the data\n* **Variance** - the amount of change in the hypothesis due to fluctuation in the training data\n* **Overfitting** - paying too much attention to the particular data set it is trained on, causing it to perform poorly on unseen data\n* **Bias-variance tradeoff** - a choice between more complex, low bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may generalize better\n* **Ockham’s razor** - simplest hypothesis should be chosen\n* **Early stopping** - having the decision tree algo stop generating nodes when there is no good attribute to split on\n* **Cart** - Classification and Regression Trees\n* **Hyperparameters** - parameters of the model class, not the individual model\n* **Regularization** - looking for functions that are more regular\n* **Computational learning theory** - any hypothesis that is seriously wrong will almost certainly be “found out” with high probability after a small number of examples\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\nThe most important difference between naive Bayes and logistic regression is that logistic regression is a \n__discriminative__ classifier while naive Bayes is a __generative__ classifier.\nConsider a visual\nmetaphor: imagine we’re trying to distinguish dog\nimages from cat images. A generative model would\nhave the goal of understanding what dogs look like\nand what cats look like. A discriminative model, by contrast, is only trying to learn to distinguish the classes.\n__Components of a probabilistic machine learning classifier__: Like naive Bayes,\nlogistic regression is a probabilistic classifier that makes use of supervised machine\nlearning. Machine learning classifiers require a training corpus of m input/output\npairs (x^i, y^i). \n1. A __feature representation__ of the input\n2. A classification function that computes y hat, the estimated class, via p(y|x)\n3. An objective function (__cross-entropy loss function__)\n4. Al algorithm for optimizing the objective function (__stochastic gradient descent))\n\nLogistic regression has two phases:\n\n__training__: we train the system (specifically the weights w and b) using stochastic\ngradient descent and the cross-entropy loss.\n\n__test__: Given a test example x we compute p(y|x) and return the higher probability\nlabel y = 1 or y = 0.\n\n\nThe goal of __binary logistic regression__ is to train a classifier that can make a binary\ndecision about the class of a new input observation. Here we introduce the sigmoid\nclassifier that will help us make this decision.\n\n\"positive sentiment\" vs \"negative sentiment\".\n\nTo create a probability, we’ll pass z through the __sigmoid function, σ(z)__.\nConsider the task of __period disambiguation__: deciding\nif a period is the end of a sentence or part of a word, by classifying each period\ninto one of two classes EOS (end-of-sentence) and not-EOS\n\nLogistic regression has a number of advantages over naive\nBayes. Naive Bayes has overly strong conditional independence assumptions\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \nWe need a loss function that expresses, for an observation x, how close the classifier\noutput __(y hat = σ(w· x+b))__ is to the correct output (y, which is 0 or 1)\n\nWe do this via a loss function that prefers the correct class labels of the training examples to be more likely. This is called __conditional maximum likelihood\nestimation__: we choose the parameters w,b that maximize the log probability of\nthe true y labels in the training data given the observations x. The resulting loss function is called __cross-entropy loss__.\n\n\n\n## SLP Chapter 5.4 Gradient Descent\n\nFor logistic regression, this loss function is conveniently __convex__. A convex function has just one minimum; there are no local minima to get stuck in, so gradient\ndescent starting from any point is guaranteed to find the minimum.\nThe magnitude of the amount to move in gradient descent is the value of the\nslope d/dw learning rate L(f(x;w), y) weighted by a learning rate η.\n\nhigher (faster) learning rate means that we should move w more on each step\n\nStochastic gradient descent is an online algorithm that minimizes the loss function\nby computing its gradient after each training example, and nudging θ in the right\ndirection (the opposite direction of the gradient). (an “online algorithm” is one that\nprocesses its input example by example, rather than waiting until it sees the entire\ninput).\n\nThe __learning rate η is a hyperparameter__ that must be adjusted. If it’s too high,\nthe learner will take steps that are too large, overshooting the minimum of the loss\nfunction. If it’s too low, the learner will take steps that are too small, and take too\nlong to get to the minimum. It is common to start with a higher learning rate and then\nslowly decrease it, so that it is a function of the iteration k of training; the notation\nηk can be used to mean the value of the learning rate at iteration k\n\nStochastic gradient descent is called stochastic because it chooses a single random\nexample at a time, moving the weights so as to improve performance on that single\nexample. That can result in very choppy movements, so it’s common to compute the\ngradient over batches of training instances rather than a single instance.\n\nFor example in __batch training__ we compute the gradient over the entire dataset.\nBy seeing so many examples, batch training offers a superb estimate of which direction to move the weights, at the cost of spending a lot of time processing every\nsingle example in the training set to compute this perfect direction.\nA compromise is __mini-batch training__: we train on a group of m examples (perhaps 512, or 1024) that is less than the whole dataset.\n\n\n## SLP Chapter 5.5 Regularization\n\nThere is a problem with learning weights that make the model perfectly match the\ntraining data. If a feature is perfectly predictive of the outcome because it happens\nto only occur in one class, it will be assigned a very high weight. The weights for\nfeatures will attempt to perfectly fit details of the training set, in fact too perfectly,\nmodeling noisy factors that just accidentally correlate with the class. This problem is called __overfitting__.\nA good model should be able to __generalize__ well from the training data to the unseen test set, but a model that overfits will have poor generalization.\n__L2 regularization__ is a quadratic function of the weight values, named because it uses the (square of the) L2 norm of the weight\nvalues. The L2 norm, ||θ||_2, is the same as the Euclidean distance of the vector θ from the origin.\n\n__L1 regularization__ is a linear function of the weight values, named after the L1 norm L1\nregularization ||W||1, the sum of the absolute values of the weights, or Manhattan distance.\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n\nSometimes we need more than two classes. Perhaps we might want to do 3-way\nsentiment classification (positive, negative, or neutral). Or we could be assigning\nsome of the labels we will introduce in Chapter 8, like the part of speech of a word\n(choosing from 10, 30, or even 50 different parts of speech), or the named entity\ntype of a phrase (choosing from tags like person, location, organization).\n\nIn such cases we use __multinomal logistic regression__, also called __softmax regression__.\nThe multinomial logistic classifier uses a generalization of the sigmoid, called\nsoftmax the softmax function, to compute the probability p(y = c|x).\n\nRecall cross-entropy loss for binary:\n\nLCE(yˆ, y) = −log p(y|x) = −[y log ˆy+ (1−y)log(1−yˆ)]\n\nBecause only one class (let’s call it i) is the correct one, the vector y takes the value\n1 only for this value of k, i.e., has yi = 1 and yj = 0 ∀ j 6= i. A vector like this,\nwith one value=1 and the rest 0, is called a __one-hot vector__.\n\n\n## SLP Chapter 7.1 Units\n\nThe architecture we\nfeedforward introduce is called a __feedforward network__ because the computation proceeds iteratively from one layer of units to the next.\n \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n__Classifier components__\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x^(i),y^(i)).\n1. A __feature representation__ of the input. For each input observation\nx(i), this will be a vector of features [x1,x2,...,xn].\n2. A __classification function__ that computes the estimated class y hat! viap(y|x).\n3. An __objective function__ for learning, usually involving minimizing error on training examples.\n4. An algorithm for __optimizing__ the objective function.\n\n\n__Sentiment classification__: z = w . x + b\n\n__Sigmoid function__: y = 1/(1+e^-z)\n- P(y=1) = sigma(wx +b) = 1/(1+e^-(wx+b))\n\n\n__Learning in logistic regression__\nHow do we get the weights of the model? We learn the parameters\n(weights + bias) via learning. This requires 2 components:\n1. An objective function or __loss function__ that tells us distance between\nthe system output and the gold output. We will use __cross-entropy loss__.\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to __minimize the loss function__.\n\n\nFor one observation x, let’s maximize the probability of the correct label p(y|x).\n- P(y|x) = y hat^y (1-y hat)^(1-y)\n\nIf y = 1, then p(y|x) = yhat\nIf y = 0, then p(y|x) = 1- yhat\n\n\n__Change to logs and then negate, and we get cross-entropy loss, and we want to minimze:\n- L_CE(yhat, y) = -logp(y|x)=-[ylog yhat + (1-y)log(1-yhat)]\n- Plug in sigmoid function for p(y|x)\n\n\nWhy does minimizing this negative log probability do what we want? We\nwant the loss to be smaller if the model’s estimate is close to correct,\nand we want the loss to be bigger if it is confused.\n\n\n__Gradient descent__ is a method that finds a minimum of a function by figuring out in\nwhich direction (in the space of the parameters θ) the function’s slope is rising the most\nsteeply, and moving in the opposite direction.\n\nFor logistic regression, this loss function is conveniently __convex__.\nA convex function has just one minimum, so there are no local minima\nto get stuck in\n\n\n__Stochastic gradient descent__ chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\nAn alternate is __batch training__, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\nA commonly used compromise is __mini-batch training__, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n\n__Overfitting__ is a problem with many machine learning models. Overfitting results in\npoor generalization and poor performance on unseen test set.\nIn logistic regression, if a feature only occurs in one class then it will get a high weight.\nSometimes we are just modelling noisy factors that just accidentally correlate with the\nclass.\n__Regularization__ is a way to penalize large weights. A regularization term is added to\nthe loss function.\nLasso regression uses L1 regularization\nRidge regression uses L2 regularization\n\n\n__Multinomal logistic regression__\nInstead of binary classification, we often want more than two classes. For sentiment\nclassification we might extend the class labels to be positive, negative, and neutral.\nWe want to know the probability of y for each class c ∈ C, p(y = c|x).\nTo get a proper probability, we will use a generalization of the sigmoid function\ncalled the __softmax function__.\n\n\n__Sigmoid neurons__\nProblem: a small change in the weights or bias of any single perceptron in the network\ncan causes the output to completely flip from 0 to 1.\nSolution: sigmoid neuron\n\n\n__Activation functions__\nInstead of directly outputting z = w·x+b, which is a linear function of x, neuron units\napply a non-linear function f to z.\nThe output of this function is called the activation value for the unit, represented by\nthe variable a. The output of a neural network is called y, so if the activation of a node\nis the final output of a network then. y = a = f(z)\n\n\n\nThe simplest kind of NN is the __Feed-Forward Neural Network__\nMultilayer network, all units are usually fully-connected, and no cycles.\nThe outputs from each layer are passed to units in the next higher layer, and no\noutputs are passed back to lower layers. \nA single hidden unit has parameters w (the weight vector) and b (the bias scalar).\nWe represent the parameters for the __entire hidden layer__ by combining the weight\nvector wi and bias bi for each unit i into a single weight matrix W and a single bias\nvector b for the whole layer.\n\nThe advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\nThe computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\nThe output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ:\n- h=σ(wx+b)\n\n\n\n__Training Neural Nets__\n\nLike logistic regression, we want to learn the best parameters for the neural net to\nmake its predictions yhat as close to possible as the gold standard labels in our training\ndata y.\nWhat do we need?\n- A loss function – cross-entropy loss\n- An optimization algorithm – gradient descent\n- A way of computing the gradient of the loss function – error propagation \n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\nA __recurrent neural network (RNN)__ is any network that contains a cycle within its\nnetwork connections, meaning that the value of some unit is directly, or indirectly,\ndependent on its own earlier outputs as an input.\n\n__Forward inference__ (mapping a sequence of inputs to a sequence of outputs) in an\nRNN is nearly identical to what we’ve already seen with feedforward networks.\n```\nfunction FORWARDRNN(x, network) returns output sequence y\n  ^0←0\n  for i←1 to LENGTH(x) do\n  h_i←g(Uh_i−1 + W_x_i)\n  y_i← f(V_h_i)\n  return y\n```\nAs with feedforward networks, __we’ll use a training set, a loss function, \nand backpropagation__ to obtain the gradients needed to adjust the weights in these recurrent\nnetworks.\n\nTailoring the backpropagation algorithm to this situation leads to a two-pass algorithm for training the weights in RNNs. In the first pass, we perform forward\ninference, computing ht, yt, accumulating the loss at each step in time, saving the\nvalue of the hidden layer at each step for use at the next time step. In the second\nphase, we process the sequence in reverse, computing the required gradients as we\ngo, computing and saving the error term for use in the hidden layer for each step\nbackward in time.\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\nRNN language models process the input sequence one word at a time, attempting to predict the next word from the current word and \nthe previous hidden state.\nTo train an RNN as a language model, we use a corpus of text as training material,\nhaving the model predict the next word at each time step t. We train the model to\nminimize the error in predicting the true next word in the training sequence, using\ncross-entropy as the loss function. Recall that the cross-entropy loss measures the\ndifference between a predicted probability distribution and the correct distribution.\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\nThis link between similarity in how words are distributed and similarity\nin what they mean is called the __distributional hypothesis__.\n\n__Vector semantics__: instantiates this linguistic hypothesis by learning representations of the meaning of words, called embeddings,\ndirectly from their distributions in texts.\n\nOne of the fundamental tenets of semantics, called the __principle of contrast__ states that a difference \nin linguistic form is always associated with some difference in meaning.\n\nOne common kind of relatedness between words is if they belong to the same\n__semantic field__. A semantic field is a set of words which cover a particular semantic\ndomain and bear structured relations with each other. For example, words might be\nrelated by being in the semantic field of hospitals (surgeon, scalpel, nurse, anesthetic, hospital), restaurants (waiter, menu, plate, food, chef).\n\nFinally, words have affective meanings or __connotations__.\n \n\n## SLP Chapter 6.2 Vector Semantics\n \n__Vector semantics__ is the standard way to represent word meaning in NLP, helping us model many of the aspects of word meaning.\n\nVectors for representing words are called __embeddings__ (although\nthe term is sometimes more strictly applied only to dense vectors like word2vec rather than sparse tf-idf or PPMI vectors).\n\n\n## SLP Chapter 6.3 Words and Vectors\n\nIn a __term-document matrix__, each row represents a word in the vocabulary and each term-document\nmatrix column represents a document from some collection of documents. This was first defined as part of the \n__vector space model__ of information retrieval (a document represented as a count vector).\nTerm-document matrices were originally defined as a means of finding similar\ndocuments for the task of document __information retrieval__. Information retrieval (IR) is the task of finding the document d from the D\ndocuments in some collection that best matches a query q.\n\nAn alternative to using the __term-document matrix__ to represent words as vectors of\ndocument counts, is to use the __term-term matrix__, also called the __word-word matrix__ or the __term-context matrix__.\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\nTo measure similarity between two target words v and w, we need a metric that\ntakes two vectors (of the same dimensionality, either both with words as dimensions,\nhence of length |V|, or both with documents as dimensions as documents, of length\n|D|) and gives a measure of their similarity. By far the most common similarity\nmetric is the __cosine of the angle between the vectors__.\n\nAs we will see, most metrics for similarity between vectors are based on the dot\nproduct. The dot product acts as a similarity metric because it will tend to be high\njust when the two vectors have large values in the same dimensions.\n\nThe dot product is higher if a vector is longer, with higher values in each dimension.\nMore frequent words have longer vectors, since they tend to co-occur with more\nwords and have higher co-occurrence values with each of them. The raw dot product\nthus will be higher for frequent words. But this is a problem; we’d like a similarity\nmetric that tells us how similar two words are regardless of their frequency.\n\nWe modify the dot product to normalize for the vector length by dividing the\ndot product by the lengths of each of the two vectors. This __normalized dot product__\nturns out to be the same as the cosine of the angle between the two vectors, following\nfrom the definition of the dot product between two vectors a and b:\n \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n__Word Meaning__\nHow should we represent the meaning of a word?\nIn N-gram LMs we represented words as a string of letters or as an index in a\nvocabulary list.\nIdeally, we want a meaning representation to encode:\n1. Synonyms – words that have similar meanings\n2. Antonyms – words that have opposite meanings\n3. Connotations – words that are positive or negative\n4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\npurchasing event\n5. Support for entailment\n\n\n\n\n__Term-Document Matrix__:\n- Each column vector represents a document\n- Each row vector represents a Term (a word)\n- The value in a cell is based on how often that term occurred in that document\n- The length of the document vectors is the size of the vocabulary\n- Document vectors can be sparse (most values are 0)\n- We can measure how similar two documents are by comparing their column vectors\n- Two rows can show us how similar two words are\n\n\n\n__Term-Term matrix/term-context matrix__:\n- Terms on the rows and column headers\n- Length of the row vector is now |V| instead of number of documents\n- The value in a cell indicates how often a word appears in a context window surrounding the word\n  - __Context windows__: w-2, w-1, target_word, w+1, w+2\n\n\n__Alternates to counts__\n\nRaw word frequency is not a great measure of association between words. It’s very\nskewed “the” and “of” are very frequent, but maybe not the most discriminative\nWe’d rather have a measure that asks whether a context word is particularly\ninformative about the target word.\nInstead of raw counts, it’s common to transform vectors using TF-IDF or PPM\n\n\n\n__TF-IDF__:\n- term frequency (how often a word occurred in a document) * inverse document frequency (1 over the number of documents that it occurred in)\n\n\n\n\n__Sparse v. Dense Vectors__\nCo-occurrence matrix (weighted by TF-IDF or mutual information)\n- Long (length |V| = 50,000+)\n- Sparse (most elements are zeros)\nAlternative: learn vectors that are\n- Short (length 200-1000)\n- Dense (most elements are non-zero)\n\n\n\nChain rule\nIn LMs we user chain rule to get the conditional probability of the next\nword in the sequence given all of the previous words:\n- P(w1w2...wt) = Pi_(t=1)^TP(wt|w1...w_(t-1))\nWhat assumption do we make in n-gram LMs to simplify this?\nThe probability of the next word only depends on the previous n-1\nwords.\nA small n makes it easier for us to get an estimate of the probability from data.\n\n\n\nUnseen sequences\nWhat happens when we have a new (unseen) combination of n words?\n__1. Back-off\n2. Smoothing / interpolation__\nWe are basically just stitching together short sequences of observed\nwords.\n\n\n\n__Alternate idea: Generalizing__\n\nTaking a sentence like \"The cat is walking in the bedroom\" and use it when we assign probabilities to similar sentences like\n\"The dog is running around the room\".\n\n\n\n__Neural Language Models__\n\nNeural Language models have several advantages over n-gram LMs:\n1. They don’t need smoothing\n2. They can handle much longer histories.\n3. They can generalize over contexts of similar words.\n4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\nDisadvantage: slower to train than traditional n-gram LMs\n\n\n\n__The input__ to the neural network is a k-gram of words w1:k.\n__The output__ is a probability distribution over the next word.\nThe k context words are treated as a word window. Each word is associated with an\n__embedding__ vector: x = [v(w1);v(w2);...;v(wk)]\n\n\n\n__Training__\n\nThe training examples are simply word k-grams from the corpus\nThe identities of the first k-1 words are used as features, and the last word is used as\nthe target label for the classification.\nConceptually, the model is trained using cross-entropy loss\n\n\n\n__Advantages of NN LMs__\n\nBetter results. They achieve better preplexity scores than SOTA n-gram LMs.\nLarger N. NN LMs can scale to much larger orders of n. This is achievable because\nparameters are associated only with individual words, and not with n-grams.\nThey generalize across contexts. For example, by observing that the words blue,\ngreen, red, black, etc. appear in similar contexts, the model will be able to assign a\nreasonable score to the green car even though it never observed in training, because it\ndid observe blue car and red car.\nA by-product of training are word embeddings\n\n\n\n__Word2vec__\n\n- Instead of counting how often each word w occurs near \"apricot\"\n- Train a classifier on a binary prediction task:\n  - Is w likely to show up near \"apricot\"?\n- We don’t actually care about this task\n- But we'll take the learned classifier weights as the word embeddings\n\n\n\n__Skip-gram algorithm__\n1. Treat the target word and a neighboring context\nword as positive examples.\n2. Randomly sample other words in the lexicon to get\nnegative samples\n3. Use logistic regression to train a classifier to\ndistinguish those two cases\n4. Use the weights as the embeddings\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}