{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Daniel Wigg CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "aPtM8g7R0Pds"
      ]
    },
    "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": "3030af5e-2269-4b14-e846-1d8db6c5fe22"
      },
      "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": 25,
      "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": "989ef799-602f-4469-cb22-fc596620adba"
      },
      "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": 26,
      "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": 27,
      "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",
        "chapter16_1 = \"\"\"Decision theory decides which action to choose based on the desirability of \\\n",
        "its immediate outcomes. An agent's preferences are captured by a utility function \\\n",
        "which assigns a numeric value to express desirability.\n",
        "\n",
        "The MEU principle can be seen as a recipe for intelligent behaviour. It formalises \\\n",
        "the notion that an agent should do the right thing but doesn't operationalise it. \\\n",
        "Estimating the probability distribution over possible states of the world requires \\\n",
        "perception, learning, knowledge representation and inference; a model of the world. \\\n",
        "Utility functions may require further searching or planning to find the best state, \\\n",
        "and agent's acting on behalf of humans may not even know what the true utility function \\\n",
        "is!\n",
        "\n",
        "An agent will achieve the highest possible performance score, averaged over all possible \\\n",
        "environments, if it acts to maximise a utility function that properly reflects its \\\n",
        "performance measure. The utility function thus internalises and guides an agent's \n",
        "actions (as opposed to a retrospective, external performance measure).\"\"\"\n",
        "\n",
        "chapter16_2 =  \"\"\"We can derive the MEU principle from some constraints such as the agent preferring \\\n",
        "$A$ over $B$, is indifferent between them, or both. $A$ and $B$ could be states of \\\n",
        "the world or uncertainty about what's on offer. Its set of outcomes can be thought of \\\n",
        "as a lottery, with each action a ticket. Each outcome can either be an atomic state \\\n",
        "or another lottery.\n",
        "\n",
        "The main concern for utility theory is how preferences between lotteries are related \\\n",
        "to preferences about their underlying states. There are six constraints that a \\\n",
        "preference relation must therefore obey (axioms of utility theory):\n",
        "- Orderability: exactly one of $(A \\\\succ B), (B \\\\succ A)$ or $(A \\\\sim B)$\n",
        "- Transitivity: $(A \\\\succ B) \\\\wedge (B \\\\succ C) \\\\Rightarrow (A \\\\succ C)$\n",
        "- Continuity: $A \\\\succ B \\\\succ C \\\\Rightarrow \\\\exists p [p,A;1-p,C]\\\\sim B$\n",
        "- Substitutability: if an agent is indifferent between lotteries $A$ and $B$ then \\\n",
        "it will be indifferent between two more complex lotteries that are the same other \\\n",
        "than $B$ being substituted for $A$, regardless of the probabilities. This also holds \\\n",
        "for preference instead of indifference.\n",
        "- Monotonicity: if an agent prefers $A$ to $B$ in two lotteries, then it prefers \\\n",
        "the lottery that has a higher probility for $A$.\n",
        "- Decomposability: compound lotteries can be reduced to simpler ones using probability \\\n",
        "laws.\n",
        "\n",
        "The axioms derive the following consequences:\n",
        "- Existence of Utility Function: $U(A) > U(B)$ iff $A$ is preferred to $B$. $>$ \\\n",
        "can also be replaced with $\\\\sim$ when indifferent.\n",
        "- Expected Utility of Lottery: utility is the sum of the probability of each outcome \\\n",
        "multiplied by the outcome's utility\n",
        "\n",
        "Once probabilities and utilities are specified for possible outcome states, the \\\n",
        "utility of a compound lottery involving those states is determined. The outcome of \\\n",
        "a nondeterministic action is a lottery so it follows an agent can act rationally \\\n",
        "by choosing actions that maximises its expected utility.\n",
        "\n",
        "Utility functions can be transformed and remain the same.\n",
        "\n",
        "Rational behaviour can be generated in a number of ways, and an agent isn't necessarily \\\n",
        "maximising it's utility by itself. Observer's can also learn about an agent's utility \\\n",
        "function through observations about what it's trying to achieve.\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\"Building a decision-theoretic system that acts on behalf of a human or assists in \\\n",
        "making their decisions is achieved via preference elicitation.\n",
        "\n",
        "Since utilities can be transformed, there is no absolute scale, however fixing \\\n",
        "utilities of two particular outcomes can be helpful so they can be recorded and \\\n",
        "compared. This is typically done for the best and worst possible outcomes. Normalised \\\n",
        "utilities use a scale of 0 to 1.\n",
        "\n",
        "Given a utility scale, the utility of any prize can be assessed by asking the agent \\\n",
        "to choose between it and a standard lottery. The probability is adjusted until the \\\n",
        "agent is indifferent between the two and this probability determines the utility.\n",
        "\n",
        "Money is a candidate for a utility measure, provided by economics. An agent has \\\n",
        "a monotonic preference for more money. Accepting a gamble depends on the utility of \\\n",
        "accepting vs. declining. For example, someone with a high net worth is more likely \\\n",
        "to accept a gamble as their expected utility of accepting would be higher than declining.\n",
        "\n",
        "The utility of money yields a kind of S-curve. Those in the positive part of the curve \\\n",
        "prefer the expected monetary value as a sure thing - they are risk-averse. On the \\\n",
        "other hand, behaviour is risk-seeking on the negative side. Small changes in wealth \\\n",
        "has a linear curve and is known as risk-neutral.\n",
        "\n",
        "In reality models of probability are simplifications of the world or are too complex \\\n",
        "to calculate. Therefore we are working with estimates of the true expected utility. \\\n",
        "If estimates are unbiased, the expected value of the error is $0$ and the action \\\n",
        "chosen would be the best on average when executed. However, the real outcome is usually \\\n",
        "significantly worse than estimated as we favour overly optimistic estimates because \\\n",
        "of the optimizer's curse.\n",
        "\n",
        "People can act irrationally (i.e. Allais paradox). One explanation is due to the \\\n",
        "certainty effect. People may prefer to reduce their computational burden and \\\n",
        "distrust legitimacy of stated probabilities. People may also account for their \\\n",
        "emotional state as well as financial state. Other reasons include ambiguity aversion, \\\n",
        "the framing effect, and the anchoring effect. Preferences are however open to revision \\\n",
        "when choices are explained better. Evolutionary psychology questions human irrationality \\\n",
        "and suggest that we didn't evolve to solve word problems with probabilities and prizes \\\n",
        "stated as decimal numbers. Other representations, such as visuals, can be shown to \\\n",
        "increase rationality.\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "A **Markov decision process (MDP)** is a sequential decision problem for fully \n",
        "observable, stochastic environments. It has a Markovian transition model, \n",
        "meaning the probability of reaching $s'$ from $s$ depends only on $s$ and ignores\n",
        " the earlier history of getting there, and additive rewards from its environment \n",
        " history (i.e. its sequence of state-actions). An MDP consists of a set of states \n",
        " $s$, with initial state $s_0$, a set of actions $a$ in each state, a transition \n",
        " model $P(s' | s,a)$ and a reward function $R(s,a,s')$. Methods for solving usually \n",
        " involve dynamic programming using recursion.\n",
        "\n",
        "A **policy** $\\\\pi$ is a solution which specifies what an agent should do for any \n",
        "state that it might reach. $\\\\pi(s)$ is the action recommended by the policy. \n",
        "Furthermore, an **optimal policy** $\\\\pi^*$* is a policy that generates the highest \n",
        "expected utility. The agent then uses this policy at $s$ to decide which next action \n",
        "to take. Policies change based on the value of $R(s,a,s')$ at non-terminal states.\n",
        "\n",
        "In decision making with a **finite horizon**, an optimal action in a given state \n",
        "may depend on how much time is left. Policies that depend on the time are known \n",
        "as **nonstationary**. Conversely, a **stationary** policy with no fixed time limit, \n",
        "behaviour would not change in the same state at different times.\n",
        "\n",
        "**Additive discounted rewards** are used to calculate the utility of state sequences. \n",
        "$\\\\gamma$ represents the **discount factor** which is a value between $0$ and $1$ \n",
        "inclusive. This shows the agent's preference for short-term rewards over long-term \n",
        "rewards.\n",
        "The advantages of using this measure are:\n",
        "1. empirical; humans and animals value near-term rewards more highly\n",
        "2. economic; early rewards can be invested\n",
        "3. uncertainty; rewards may never arrive\n",
        "4. stationarity for preferences; only this measure can satisfy\n",
        "5. infinite horizons become finite:\n",
        "\t- if $\\\\gamma < 1$ and rewards are bounded by $\\\\pm R_{max}$, the utility becomes \n",
        "  finite\n",
        "\t- a **proper policy** is guaranteed to reach a terminal state (so $\\\\gamma = 1$ \n",
        "  allowed) whereas an **improper policy** never will <- need to use discounting\n",
        "\t- compare infinite sequences in terms of **average reward**\n",
        "\n",
        "$\\\\pi^*$ represents an optimal policy and the true utility of a state is written \n",
        "as $U(s)$.\n",
        "\n",
        "The utility of a state is the expected reward for the next transition plus the \n",
        "discounted utility of the next state, assuming the agent chooses the optimal action: \n",
        "$U(s) = \\\\underset{a \\\\in A(s)}{max} \\\\underset{s'}\\\\sum P(s' | s,a) [R(s,a,s') + \n",
        "\\\\gamma U(s')]$\n",
        "This is the **Bellman equation**.\n",
        "\n",
        "The **action-utility function** or **Q-function** $Q(s,a)$ is the expected utility\n",
        " of taking a given action in a given state. We can develop a Bellman equation for \n",
        " Q-functions in a similar fashion:\n",
        "$Q(s,a) = \\\\underset{s'}\\\\sum P(s' | s,a) [R(s,a,s') + \\\\gamma ~\\\\underset{a'}{max} Q(s', a')]$\n",
        "\n",
        "The scale of utilities is arbitrary and an affine transformation doesn't change \n",
        "the optimal decision.\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "**Value iteration**\n",
        "The Bellman equation is the basis for the algorithm. With $n$ possible states, there \n",
        "are $n$ Bellman equations. Systems of linear equations can be solved using linear \n",
        "algebra; however this equation is nonlinear.\n",
        "\n",
        "We use an iterative approach, starting with arbitrary initial utility values. The \n",
        "$i$th iteration is called a **Bellman update**:\n",
        "$U_{i+1}(s) \\\\leftarrow \\\\underset{a \\\\in A(s)}{max} \\\\underset{s'}{\\\\sum} P(s'|s,a)[R(s,a,s')\n",
        " + \\\\gamma U_i (s')]$\n",
        "Applying this infinitely often we will eventually reach an equilibrium (i.e. \n",
        "convergence) in which we find the unique solutions to the Bellman equations. The \n",
        "resulting policy is optimal.\n",
        "\n",
        "The value iteration algorithm propagates information through the state space via \n",
        "local updates.\n",
        "\n",
        "**Convergence of value iteration**\n",
        "**Contraction** generates two different outputs that are \"closer together\" when \n",
        "given some inputs, e.g. division by $2$. Contractions have one fixed point (e.g. \n",
        "$0$ in the previous example) and values move closer to the fixed point upon repeated \n",
        "application.\n",
        "\n",
        "In summary, the Bellman update is a contraction by a factor of $\\\\gamma$ on the \n",
        "space of utility vectors, therefore value iteration converges to a unique solution \n",
        "of the Bellman equations when $\\\\gamma < 1$.\n",
        "\n",
        "The number of iterations $N$ required to reach convergence is $\\\\gamma ^N$. Therefore\n",
        " convergence is exponential when $\\\\gamma$ is very small, but grows larger when it \n",
        " is closer to $1$. If $\\\\gamma$ is too small then the agent will have a shorter \n",
        " horizon and could miss the longer-term effects of its actions.\n",
        "\n",
        "If an agent derives the policy $\\\\pi_i$ based on value iteration, its resulting \n",
        "behaviour will be nearly as good as the optimal behaviour.\n",
        "\n",
        "**Policy iteration**\n",
        "The algorithm alternates between two steps, beginning from an initial policy $\\\\pi_0$:\n",
        "- **Policy evaluation**: given a policy $\\\\pi_i$, calculate the utility of each state\n",
        "- **Policy improvement**: calculate a new policy $pi_{i+1}$ using one-step look-ahead\n",
        " based on the previous utility\n",
        "Terminates when policy improvement no longer changes the utilities.\n",
        "\n",
        "Implementing (approximate) policy evaluation (known as **modified policy iteration**)\n",
        " uses a simpler version of the Bellman equations: $U_{i+1}(s) \\\\leftarrow \\\\underset{s'}{\\\\sum} \n",
        " P(s'|s,\\\\pi_i(s))[R(s,\\\\pi_i(s),s') + \\\\gamma U_i(s')]$\n",
        "This is repeated several times to produce the next utility estimate.\n",
        "\n",
        "The (exact) equations are linear so can be solved with linear algebra in $\\\\mathcal{O}(n^3)$\n",
        " (for $n$ states there are $n$ linear equations with $n$ unknowns).\n",
        "\n",
        "**Asynchronous policy iteration** updates subsets of states (rather than all states\n",
        " at once) and applies either value iteration or policy improvement; this can result \n",
        " in more efficient heuristic algorithms.\n",
        "\n",
        "**Linear programming** is a general approach for formulating constrained optimisation\n",
        " problems; an MDP can be solved with it. Dynamic programming methods can often be \n",
        " more efficient in practice.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "MDP: type of non-deterministic search\n",
        "\n",
        "**Stochastic transition models**\n",
        "Search algorithms so far had deterministic transition models where the outcome was \n",
        "guaranteed.\n",
        "In the stochastic transition model, the transition function is given by $T(s, a, s')$ \n",
        "or as a probability $p(s' | s,a)$.\n",
        "\n",
        "We ignore history of states up until the current state, therefore transitions are \n",
        "Markovian. Probability only depends on $s$.\n",
        "\n",
        "**Reward function**\n",
        "Rewards can be positive or negative but bounded by values.\n",
        "Agent receives an award at each step as defined by $R(s, a, s')$.\n",
        "Rewards are additive and based on the sum of sequences of state-action pairs \n",
        "(environment history) that are executed.\n",
        "\n",
        "---\n",
        "**Markov Decision Process (MDP)**\n",
        "- sequential decision problems\n",
        "- for fully observable environments\n",
        "- has a stochastic transition model\n",
        "- and additive rewards\n",
        "\n",
        "To find a solution, need to define:\n",
        "- set of states $s \\\\in S$\n",
        "- set of actions $a \\\\in A$\n",
        "- transition function $T(s, a, s')$\n",
        "\t- probability is $p(s' | s,a)$, known as the *model*\n",
        "- reward function $R(s, a, s')$\n",
        "\t- sometimes $R(s)$ or $R(s')$\n",
        "- initial state $s_0$\n",
        "- optionally: one or more terminal states\n",
        "\n",
        "**Solution == policy**\n",
        "In search problems a solution had a shortest path of a sequence of actions.\n",
        "MDPs have a policy, mapping a state onto an action, defined as $\\\\pi(s) = a$. $\\\\pi^*$ \n",
        "indicates the most optimal policy.\n",
        "\n",
        "**Policies and rewards**\n",
        "Need to compute the expected utility of all possible paths generated by a policy.\n",
        "Reward function shapes optimal plan.\n",
        "\n",
        "**Sequence of rewards**\n",
        "Performance of an agent is the sum of rewards of its transitions.\n",
        "An agent would prefer more rewards overall and get them earlier rather than later.\n",
        "\n",
        "**Discounting**\n",
        "Solution to maximising sum of rewards and preferring them now is decaying values \n",
        "of rewards exponentially as time progresses.\n",
        "\n",
        "Discount by multiplying the discount once per level in a tree.\n",
        "Sooner rewards have higher utility than later rewards.\n",
        "Algorithms converge to put a limit on search depth. Later rewards are diminishingly \n",
        "small so truncating early does not have a large effect.\n",
        "\n",
        "**Stationary preferences**\n",
        "Theorem: assuming stationary preferences:\n",
        "$[a_1, a_2,...] \\\\succ [b_1, b_2, ...]$\n",
        "Appending the same reward $r$ to both gives the same result\n",
        "$[r, a_1, a_2,...] \\\\succ [r, b_1, b_2, ...]$\n",
        "\n",
        "Then there are only two ways to define utilities:\n",
        "Additive utility: $U([r_0, r_1. r_2,...]) = r_0 + r_1 + r_2 + ...$\n",
        "Discounted utility: $U([r_0, r_1. r_2,...]) = r_0 + \\\\gamma r_1 + \\\\gamma^2 r_2 + ...$\n",
        "\n",
        "**Infinite utilities**\n",
        "Solutions:\n",
        "- finite horizon: (similar to depth-limited search)\n",
        "\t- terminate episodes after a fixed number of steps (e.g. life)\n",
        "\t- gives non-stationary policies ($\\\\pi$ depends on time remaining)\n",
        "- discounting: (use $0 < \\\\gamma < 1$)\n",
        "\t- smaller $\\\\gamma$ means smaller horizon\n",
        "- absorbing state:\n",
        "\t- guarantee that for every policy a terminal state will eventually be reached \n",
        "  (e.g. \"overheating\" in racing games)\n",
        "\n",
        "---\n",
        "**MDP search trees**\n",
        "Each MDP state projects an expectimax-like search tree.\n",
        "\n",
        "**Optimal quantities**\n",
        "Value (utility) of a state $s$:\n",
        "$V^*(s)$ = expected utility starting in s and acting optimally\n",
        "\n",
        "Value (utility) of a q-state $(s,a)$:\n",
        "$Q^*(s,a)$ = expected utility starting out having taken action $a$ from state $s$\n",
        " and then acting optimally\n",
        "\n",
        "Optimal policy:\n",
        "$\\\\pi^*(s)$ = optimal action from state $s$\n",
        "\n",
        "**Value of states**\n",
        "Fundamental operation: compute (expectimax) value of a state:\n",
        "- expected utility under optimal action\n",
        "- average sum of (discounted) rewards\n",
        "- what expectimax computed!\n",
        "\n",
        "Recursive definition of value:\n",
        "$Q^*(s, a) = \\\\sum_{s'}T(s,a,s')~[R(s,a,s')+ \\\\gamma V^*(s')]$\n",
        "(weighted average of all possible outcomes according to transition function)\n",
        "where\n",
        "$V^*(s) = {max}_a~Q^*(s,a)$\n",
        "\n",
        "This is known as a **Bellman equation**.\n",
        "\n",
        "Need to do a lot of work with expectimax:\n",
        "- states are repeated: only compute needed quantities once\n",
        "- tree goes on infinitely: do depth-limited computation until change is small (\n",
        "  deep levels don't contribute much if $\\\\gamma < 1$)\n",
        "\n",
        "---\n",
        "Value iteration:\n",
        "**Algorithm**\n",
        "- start with $V_0(s) = 0$: no steps left means an expected reward sum of zero\n",
        "- given vector $V_k(s)$ values, perform one ply of expectimax from each state: \n",
        "$V_{k+1}(s) = {max}_a~\\\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\\\gamma V_k(s')]$\n",
        "- repeat until convergence\n",
        "\n",
        "Complexity of each iteration: $\\\\mathcal{O}(s^2a)$ - worst case where a state is c\n",
        "onnected to every other state.\n",
        "\n",
        "Theorem: converges to unique optimal values.\n",
        "- approximations get refined towards optimal values\n",
        "- policy may converge long before values do\n",
        "\n",
        "**Convergence**\n",
        "Cases of $V_k$ convergence:\n",
        "1. with maximum depth $M$, $V_M$ holds actual (untruncated) values\n",
        "2. discount $\\\\gamma < 1$ **review proof**\n",
        "\n",
        "---\n",
        "Policy evaluation:\n",
        "**Policy methods**\n",
        "To find the best policy, you can directly compare policies to one another and \n",
        "decide which one is better.\n",
        "\n",
        "Calculate values given a policy.\n",
        "\n",
        "**Fixed policies**\n",
        "A fixed policy $\\\\pi(s)$ has a simpler tree as there is only one action per state.\n",
        "We can compute the utility of $s$:\n",
        "- $V^{\\\\pi}(s)$ = expected total discounted rewards starting at $s$ and following $\\\\pi$\n",
        "- recursive relation: $V^{\\\\pi}(s) = \\sum_{s'}T(s,\\\\pi(s),s')~[R(s,\\\\pi(s),s') + \n",
        "\\\\gamma V^{\\\\pi}(s')]$\n",
        "\n",
        "**Policy evaluation**\n",
        "Calculating the values for a fixed policy $\\\\pi$ can be done:\n",
        "1. turn recursive Bellman equations into updates (like value iteration).\n",
        "\tefficiency is $\\\\mathcal{O}(s^2)$ per iteration - no need to decide actions as \n",
        "  it's provided by the policy\n",
        "2. without needing to find the maximum of an action, Bellman equations are a system \n",
        "of linear equations that can be solved directly\n",
        "\n",
        "On the other hand, calculate policies given values.\n",
        "\n",
        "**Computing actions from values**\n",
        "Not obvious how to act.\n",
        "\n",
        "Need to do a mini-expectimax of one step for each action that can be taken: \n",
        "$\\\\pi^*(s) = {max}_a~\\\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\\\gamma V^*(s')]$\n",
        "\n",
        "Known as **policy extraction** as it derives the policy implied by values.\n",
        "\n",
        "**Computing actions from q-values**\n",
        "Trivial to decide which action to take. Select maximum q-value: $\\\\pi^*(s) = {max}_a Q^*(s,a)$\n",
        "\n",
        "*Easier to select actions from q-values than values!*\n",
        "\n",
        "---\n",
        "Problems with value iteration:\n",
        "1. slow - $\\\\mathcal{O}(s^2a)$ per iteration\n",
        "2. the max at each stage of the Bellman equation rarely changes\n",
        "3. policy often converges long before values\n",
        "\n",
        "**Algorithm**\n",
        "Steps:\n",
        "1. **policy evaluation**: calculate utilities for some fixed (not optimal) policy until convergence:\n",
        "\t$V^{\\\\pi_i}_{k+1}(s) = \\\\sum_{s'}T(s,\\\\pi_i(s),s')~[R(s,\\\\pi_i(s),s') + \\\\gamma V^{\\\\pi_i}_{k}(s')]$\n",
        "2. **policy improvement**: update policy using one-step look-ahead with converged (not optimal) \n",
        "utilities as future values\n",
        "\t$\\\\pi_{i+1}(s) = {max}_a \\\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\\\gamma V^{\\pi_i}(s')]$\n",
        "2. repeat until policy converges\n",
        "\n",
        "Optimal. Can converge faster under some conditions.\n",
        "\n",
        "**Comparison**\n",
        "Both value and policy iteration achieve the same outcome: find optimal values, \n",
        "apply policy extraction and derive optimal policy.\n",
        "\n",
        "Value iteration:\n",
        "- every iteration updates values and (implicitly) the policy\n",
        "- doesn't track policy, but taking the max over actions implicitly recomputes it\n",
        "\n",
        "Policy iteration:\n",
        "- several passes that update utilities with a fixed policy - fast because it \n",
        "considers only a single action\n",
        "- after policy is evaluated, a new policy is chosen - slow like value iteration\n",
        "- new policy will be better (or it's finished)\n",
        "\n",
        "Both are dynamic programs for solving MDPs.\n",
        "\n",
        "**Summary: MDP algorithms**\n",
        "- compute optimal values using value or policy iteration\n",
        "- compute values for a particular policy: use policy evaluation\n",
        "- turn values in a policy: use policy extraction (one-step look-ahead)\n",
        "\n",
        "All very similar - variations of Bellman equations; all use one-step look-ahead \n",
        "expectimax fragments; differ in whether we plug-in a fixed policy or max over actions.\n",
        "\n",
        "---\n",
        "Principle of maximum expected utility:\n",
        "A rational agent should choose the action that maximizes its expected utility, \n",
        "given its knowledge.\n",
        "\n",
        "For worst-case minimax reasoning, terminal function scale doesn't matter; known as \n",
        "*insensitivity to monotonic transformations*.\n",
        "However, for average-case expectimax reasoning, magnitudes need to be meaningful - \n",
        "transformations could affect the outcome.\n",
        "\n",
        "**Utilities**\n",
        "*Utilities are functions from outcomes (states) to real numbers that describe an \n",
        "agent's preferences.* They summarise an agen't goals.\n",
        "\n",
        "In games: utilities may be simple (+1/-1 for win/lose).\n",
        "\n",
        "Theorem: any rational preference can be summarised by a utility function.\n",
        "\n",
        "Behaviours emerge from hard-coded utilities. We do not prescribe behaviours or let\n",
        " agents pick utilities to avoid unintended consequences.\n",
        "\n",
        "**Rational preferences**\n",
        "Axioms of rationality:\n",
        "- Transitivity: $(A \\\\succ B)~\\\\land~(B \\\\succ C) \\\\implies (A \\\\succ C)$\n",
        "- Orderability: $(A \\\\succ B)~\\\\lor~(B \\\\succ A) \\\\lor (A \\\\sim B)$\n",
        "- Continuity: $A \\\\succ B \\\\succ C \\\\implies \\\\exists_p~[p, A; 1-p, C] \\\\sim B$\n",
        "- Substitutability: $A \\\\sim B \\\\implies [p, A; 1-p, C] \\\\sim [p, B; 1-p, C]$\n",
        "- Monotonicity: $A \\\\succ B \\\\implies (p \\\\geq q \\\\Longleftrightarrow [p, A; 1-p, B] \\\\succeq [q, A; 1-q, B])$\n",
        "Theorem: rational preferences imply behaviour describable as maximum of expected utility.\n",
        "\n",
        "**MEU principle**\n",
        "*Theorem: given any preferences satisfying the constraints (axioms), there exists \n",
        "a real-valued function $U$ such that*\n",
        "$U(A) \\\\geq U(B) \\\\Longleftrightarrow A \\\\succeq B$\n",
        "$U([p_1, S_1; ...; p_n, S_n]) = \\\\sum_i p_i U(S_i)$\n",
        "That is, *values assigned by $U$ preserve preferences of both prizes and lotteries*.\n",
        "\n",
        "MEU principle:\n",
        "- choose action that maximizes expected utility\n",
        "- (an agent can be rational (consistent with MEU) without ever representing/manipulating \n",
        "utilities and probabilities; e.g. can use a lookup table for some problems)\n",
        "\n",
        "**Utility scales**\n",
        "- normalised utilities: $u_+ = 1, u_- = 0$\n",
        "- micromorts: one-millionth chance of death\n",
        "- QALYs: quality-adjusted life years\n",
        "\n",
        "Behaviour is invariant under positive linear transformations: $U'(x) = k_1 U(x) + k_2$ \n",
        "where $k_1 > 0$\n",
        "With deterministic prizes (i.e. no lottery choices), only ordinal utility can be \n",
        "determined, i.e. total order on prizes.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 28,
      "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": "f054e1d5-f126-42ae-c5e8-22a2c21dd77f"
      },
      "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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nDecision theory decides which action to choose based on the desirability of its immediate outcomes. An agent's preferences are captured by a utility function which assigns a numeric value to express desirability.\n\nThe MEU principle can be seen as a recipe for intelligent behaviour. It formalises the notion that an agent should do the right thing but doesn't operationalise it. Estimating the probability distribution over possible states of the world requires perception, learning, knowledge representation and inference; a model of the world. Utility functions may require further searching or planning to find the best state, and agent's acting on behalf of humans may not even know what the true utility function is!\n\nAn agent will achieve the highest possible performance score, averaged over all possible environments, if it acts to maximise a utility function that properly reflects its performance measure. The utility function thus internalises and guides an agent's \nactions (as opposed to a retrospective, external performance measure).\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nWe can derive the MEU principle from some constraints such as the agent preferring $A$ over $B$, is indifferent between them, or both. $A$ and $B$ could be states of the world or uncertainty about what's on offer. Its set of outcomes can be thought of as a lottery, with each action a ticket. Each outcome can either be an atomic state or another lottery.\n\nThe main concern for utility theory is how preferences between lotteries are related to preferences about their underlying states. There are six constraints that a preference relation must therefore obey (axioms of utility theory):\n- Orderability: exactly one of $(A \\succ B), (B \\succ A)$ or $(A \\sim B)$\n- Transitivity: $(A \\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C)$\n- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p,A;1-p,C]\\sim B$\n- Substitutability: if an agent is indifferent between lotteries $A$ and $B$ then it will be indifferent between two more complex lotteries that are the same other than $B$ being substituted for $A$, regardless of the probabilities. This also holds for preference instead of indifference.\n- Monotonicity: if an agent prefers $A$ to $B$ in two lotteries, then it prefers the lottery that has a higher probility for $A$.\n- Decomposability: compound lotteries can be reduced to simpler ones using probability laws.\n\nThe axioms derive the following consequences:\n- Existence of Utility Function: $U(A) > U(B)$ iff $A$ is preferred to $B$. $>$ can also be replaced with $\\sim$ when indifferent.\n- Expected Utility of Lottery: utility is the sum of the probability of each outcome multiplied by the outcome's utility\n\nOnce probabilities and utilities are specified for possible outcome states, the utility of a compound lottery involving those states is determined. The outcome of a nondeterministic action is a lottery so it follows an agent can act rationally by choosing actions that maximises its expected utility.\n\nUtility functions can be transformed and remain the same.\n\nRational behaviour can be generated in a number of ways, and an agent isn't necessarily maximising it's utility by itself. Observer's can also learn about an agent's utility function through observations about what it's trying to achieve.\n\n## AIMA Chapter 16.3 Utility Functions\nBuilding a decision-theoretic system that acts on behalf of a human or assists in making their decisions is achieved via preference elicitation.\n\nSince utilities can be transformed, there is no absolute scale, however fixing utilities of two particular outcomes can be helpful so they can be recorded and compared. This is typically done for the best and worst possible outcomes. Normalised utilities use a scale of 0 to 1.\n\nGiven a utility scale, the utility of any prize can be assessed by asking the agent to choose between it and a standard lottery. The probability is adjusted until the agent is indifferent between the two and this probability determines the utility.\n\nMoney is a candidate for a utility measure, provided by economics. An agent has a monotonic preference for more money. Accepting a gamble depends on the utility of accepting vs. declining. For example, someone with a high net worth is more likely to accept a gamble as their expected utility of accepting would be higher than declining.\n\nThe utility of money yields a kind of S-curve. Those in the positive part of the curve prefer the expected monetary value as a sure thing - they are risk-averse. On the other hand, behaviour is risk-seeking on the negative side. Small changes in wealth has a linear curve and is known as risk-neutral.\n\nIn reality models of probability are simplifications of the world or are too complex to calculate. Therefore we are working with estimates of the true expected utility. If estimates are unbiased, the expected value of the error is $0$ and the action chosen would be the best on average when executed. However, the real outcome is usually significantly worse than estimated as we favour overly optimistic estimates because of the optimizer's curse.\n\nPeople can act irrationally (i.e. Allais paradox). One explanation is due to the certainty effect. People may prefer to reduce their computational burden and distrust legitimacy of stated probabilities. People may also account for their emotional state as well as financial state. Other reasons include ambiguity aversion, the framing effect, and the anchoring effect. Preferences are however open to revision when choices are explained better. Evolutionary psychology questions human irrationality and suggest that we didn't evolve to solve word problems with probabilities and prizes stated as decimal numbers. Other representations, such as visuals, can be shown to increase rationality.\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nA **Markov decision process (MDP)** is a sequential decision problem for fully \nobservable, stochastic environments. It has a Markovian transition model, \nmeaning the probability of reaching $s'$ from $s$ depends only on $s$ and ignores\n the earlier history of getting there, and additive rewards from its environment \n history (i.e. its sequence of state-actions). An MDP consists of a set of states \n $s$, with initial state $s_0$, a set of actions $a$ in each state, a transition \n model $P(s' | s,a)$ and a reward function $R(s,a,s')$. Methods for solving usually \n involve dynamic programming using recursion.\n\nA **policy** $\\pi$ is a solution which specifies what an agent should do for any \nstate that it might reach. $\\pi(s)$ is the action recommended by the policy. \nFurthermore, an **optimal policy** $\\pi^*$* is a policy that generates the highest \nexpected utility. The agent then uses this policy at $s$ to decide which next action \nto take. Policies change based on the value of $R(s,a,s')$ at non-terminal states.\n\nIn decision making with a **finite horizon**, an optimal action in a given state \nmay depend on how much time is left. Policies that depend on the time are known \nas **nonstationary**. Conversely, a **stationary** policy with no fixed time limit, \nbehaviour would not change in the same state at different times.\n\n**Additive discounted rewards** are used to calculate the utility of state sequences. \n$\\gamma$ represents the **discount factor** which is a value between $0$ and $1$ \ninclusive. This shows the agent's preference for short-term rewards over long-term \nrewards.\nThe advantages of using this measure are:\n1. empirical; humans and animals value near-term rewards more highly\n2. economic; early rewards can be invested\n3. uncertainty; rewards may never arrive\n4. stationarity for preferences; only this measure can satisfy\n5. infinite horizons become finite:\n\t- if $\\gamma < 1$ and rewards are bounded by $\\pm R_{max}$, the utility becomes \n  finite\n\t- a **proper policy** is guaranteed to reach a terminal state (so $\\gamma = 1$ \n  allowed) whereas an **improper policy** never will <- need to use discounting\n\t- compare infinite sequences in terms of **average reward**\n\n$\\pi^*$ represents an optimal policy and the true utility of a state is written \nas $U(s)$.\n\nThe utility of a state is the expected reward for the next transition plus the \ndiscounted utility of the next state, assuming the agent chooses the optimal action: \n$U(s) = \\underset{a \\in A(s)}{max} \\underset{s'}\\sum P(s' | s,a) [R(s,a,s') + \n\\gamma U(s')]$\nThis is the **Bellman equation**.\n\nThe **action-utility function** or **Q-function** $Q(s,a)$ is the expected utility\n of taking a given action in a given state. We can develop a Bellman equation for \n Q-functions in a similar fashion:\n$Q(s,a) = \\underset{s'}\\sum P(s' | s,a) [R(s,a,s') + \\gamma ~\\underset{a'}{max} Q(s', a')]$\n\nThe scale of utilities is arbitrary and an affine transformation doesn't change \nthe optimal decision.\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n**Value iteration**\nThe Bellman equation is the basis for the algorithm. With $n$ possible states, there \nare $n$ Bellman equations. Systems of linear equations can be solved using linear \nalgebra; however this equation is nonlinear.\n\nWe use an iterative approach, starting with arbitrary initial utility values. The \n$i$th iteration is called a **Bellman update**:\n$U_{i+1}(s) \\leftarrow \\underset{a \\in A(s)}{max} \\underset{s'}{\\sum} P(s'|s,a)[R(s,a,s')\n + \\gamma U_i (s')]$\nApplying this infinitely often we will eventually reach an equilibrium (i.e. \nconvergence) in which we find the unique solutions to the Bellman equations. The \nresulting policy is optimal.\n\nThe value iteration algorithm propagates information through the state space via \nlocal updates.\n\n**Convergence of value iteration**\n**Contraction** generates two different outputs that are \"closer together\" when \ngiven some inputs, e.g. division by $2$. Contractions have one fixed point (e.g. \n$0$ in the previous example) and values move closer to the fixed point upon repeated \napplication.\n\nIn summary, the Bellman update is a contraction by a factor of $\\gamma$ on the \nspace of utility vectors, therefore value iteration converges to a unique solution \nof the Bellman equations when $\\gamma < 1$.\n\nThe number of iterations $N$ required to reach convergence is $\\gamma ^N$. Therefore\n convergence is exponential when $\\gamma$ is very small, but grows larger when it \n is closer to $1$. If $\\gamma$ is too small then the agent will have a shorter \n horizon and could miss the longer-term effects of its actions.\n\nIf an agent derives the policy $\\pi_i$ based on value iteration, its resulting \nbehaviour will be nearly as good as the optimal behaviour.\n\n**Policy iteration**\nThe algorithm alternates between two steps, beginning from an initial policy $\\pi_0$:\n- **Policy evaluation**: given a policy $\\pi_i$, calculate the utility of each state\n- **Policy improvement**: calculate a new policy $pi_{i+1}$ using one-step look-ahead\n based on the previous utility\nTerminates when policy improvement no longer changes the utilities.\n\nImplementing (approximate) policy evaluation (known as **modified policy iteration**)\n uses a simpler version of the Bellman equations: $U_{i+1}(s) \\leftarrow \\underset{s'}{\\sum} \n P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$\nThis is repeated several times to produce the next utility estimate.\n\nThe (exact) equations are linear so can be solved with linear algebra in $\\mathcal{O}(n^3)$\n (for $n$ states there are $n$ linear equations with $n$ unknowns).\n\n**Asynchronous policy iteration** updates subsets of states (rather than all states\n at once) and applies either value iteration or policy improvement; this can result \n in more efficient heuristic algorithms.\n\n**Linear programming** is a general approach for formulating constrained optimisation\n problems; an MDP can be solved with it. Dynamic programming methods can often be \n more efficient in practice.\n\n\n## Module 8 Lecture Notes\n\nMDP: type of non-deterministic search\n\n**Stochastic transition models**\nSearch algorithms so far had deterministic transition models where the outcome was \nguaranteed.\nIn the stochastic transition model, the transition function is given by $T(s, a, s')$ \nor as a probability $p(s' | s,a)$.\n\nWe ignore history of states up until the current state, therefore transitions are \nMarkovian. Probability only depends on $s$.\n\n**Reward function**\nRewards can be positive or negative but bounded by values.\nAgent receives an award at each step as defined by $R(s, a, s')$.\nRewards are additive and based on the sum of sequences of state-action pairs \n(environment history) that are executed.\n\n---\n**Markov Decision Process (MDP)**\n- sequential decision problems\n- for fully observable environments\n- has a stochastic transition model\n- and additive rewards\n\nTo find a solution, need to define:\n- set of states $s \\in S$\n- set of actions $a \\in A$\n- transition function $T(s, a, s')$\n\t- probability is $p(s' | s,a)$, known as the *model*\n- reward function $R(s, a, s')$\n\t- sometimes $R(s)$ or $R(s')$\n- initial state $s_0$\n- optionally: one or more terminal states\n\n**Solution == policy**\nIn search problems a solution had a shortest path of a sequence of actions.\nMDPs have a policy, mapping a state onto an action, defined as $\\pi(s) = a$. $\\pi^*$ \nindicates the most optimal policy.\n\n**Policies and rewards**\nNeed to compute the expected utility of all possible paths generated by a policy.\nReward function shapes optimal plan.\n\n**Sequence of rewards**\nPerformance of an agent is the sum of rewards of its transitions.\nAn agent would prefer more rewards overall and get them earlier rather than later.\n\n**Discounting**\nSolution to maximising sum of rewards and preferring them now is decaying values \nof rewards exponentially as time progresses.\n\nDiscount by multiplying the discount once per level in a tree.\nSooner rewards have higher utility than later rewards.\nAlgorithms converge to put a limit on search depth. Later rewards are diminishingly \nsmall so truncating early does not have a large effect.\n\n**Stationary preferences**\nTheorem: assuming stationary preferences:\n$[a_1, a_2,...] \\succ [b_1, b_2, ...]$\nAppending the same reward $r$ to both gives the same result\n$[r, a_1, a_2,...] \\succ [r, b_1, b_2, ...]$\n\nThen there are only two ways to define utilities:\nAdditive utility: $U([r_0, r_1. r_2,...]) = r_0 + r_1 + r_2 + ...$\nDiscounted utility: $U([r_0, r_1. r_2,...]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 + ...$\n\n**Infinite utilities**\nSolutions:\n- finite horizon: (similar to depth-limited search)\n\t- terminate episodes after a fixed number of steps (e.g. life)\n\t- gives non-stationary policies ($\\pi$ depends on time remaining)\n- discounting: (use $0 < \\gamma < 1$)\n\t- smaller $\\gamma$ means smaller horizon\n- absorbing state:\n\t- guarantee that for every policy a terminal state will eventually be reached \n  (e.g. \"overheating\" in racing games)\n\n---\n**MDP search trees**\nEach MDP state projects an expectimax-like search tree.\n\n**Optimal quantities**\nValue (utility) of a state $s$:\n$V^*(s)$ = expected utility starting in s and acting optimally\n\nValue (utility) of a q-state $(s,a)$:\n$Q^*(s,a)$ = expected utility starting out having taken action $a$ from state $s$\n and then acting optimally\n\nOptimal policy:\n$\\pi^*(s)$ = optimal action from state $s$\n\n**Value of states**\nFundamental operation: compute (expectimax) value of a state:\n- expected utility under optimal action\n- average sum of (discounted) rewards\n- what expectimax computed!\n\nRecursive definition of value:\n$Q^*(s, a) = \\sum_{s'}T(s,a,s')~[R(s,a,s')+ \\gamma V^*(s')]$\n(weighted average of all possible outcomes according to transition function)\nwhere\n$V^*(s) = {max}_a~Q^*(s,a)$\n\nThis is known as a **Bellman equation**.\n\nNeed to do a lot of work with expectimax:\n- states are repeated: only compute needed quantities once\n- tree goes on infinitely: do depth-limited computation until change is small (\n  deep levels don't contribute much if $\\gamma < 1$)\n\n---\nValue iteration:\n**Algorithm**\n- start with $V_0(s) = 0$: no steps left means an expected reward sum of zero\n- given vector $V_k(s)$ values, perform one ply of expectimax from each state: \n$V_{k+1}(s) = {max}_a~\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\gamma V_k(s')]$\n- repeat until convergence\n\nComplexity of each iteration: $\\mathcal{O}(s^2a)$ - worst case where a state is c\nonnected to every other state.\n\nTheorem: converges to unique optimal values.\n- approximations get refined towards optimal values\n- policy may converge long before values do\n\n**Convergence**\nCases of $V_k$ convergence:\n1. with maximum depth $M$, $V_M$ holds actual (untruncated) values\n2. discount $\\gamma < 1$ **review proof**\n\n---\nPolicy evaluation:\n**Policy methods**\nTo find the best policy, you can directly compare policies to one another and \ndecide which one is better.\n\nCalculate values given a policy.\n\n**Fixed policies**\nA fixed policy $\\pi(s)$ has a simpler tree as there is only one action per state.\nWe can compute the utility of $s$:\n- $V^{\\pi}(s)$ = expected total discounted rewards starting at $s$ and following $\\pi$\n- recursive relation: $V^{\\pi}(s) = \\sum_{s'}T(s,\\pi(s),s')~[R(s,\\pi(s),s') + \n\\gamma V^{\\pi}(s')]$\n\n**Policy evaluation**\nCalculating the values for a fixed policy $\\pi$ can be done:\n1. turn recursive Bellman equations into updates (like value iteration).\n\tefficiency is $\\mathcal{O}(s^2)$ per iteration - no need to decide actions as \n  it's provided by the policy\n2. without needing to find the maximum of an action, Bellman equations are a system \nof linear equations that can be solved directly\n\nOn the other hand, calculate policies given values.\n\n**Computing actions from values**\nNot obvious how to act.\n\nNeed to do a mini-expectimax of one step for each action that can be taken: \n$\\pi^*(s) = {max}_a~\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\gamma V^*(s')]$\n\nKnown as **policy extraction** as it derives the policy implied by values.\n\n**Computing actions from q-values**\nTrivial to decide which action to take. Select maximum q-value: $\\pi^*(s) = {max}_a Q^*(s,a)$\n\n*Easier to select actions from q-values than values!*\n\n---\nProblems with value iteration:\n1. slow - $\\mathcal{O}(s^2a)$ per iteration\n2. the max at each stage of the Bellman equation rarely changes\n3. policy often converges long before values\n\n**Algorithm**\nSteps:\n1. **policy evaluation**: calculate utilities for some fixed (not optimal) policy until convergence:\n\t$V^{\\pi_i}_{k+1}(s) = \\sum_{s'}T(s,\\pi_i(s),s')~[R(s,\\pi_i(s),s') + \\gamma V^{\\pi_i}_{k}(s')]$\n2. **policy improvement**: update policy using one-step look-ahead with converged (not optimal) \nutilities as future values\n\t$\\pi_{i+1}(s) = {max}_a \\sum_{s'}T(s,a,s')~[R(s,a,s') + \\gamma V^{\\pi_i}(s')]$\n2. repeat until policy converges\n\nOptimal. Can converge faster under some conditions.\n\n**Comparison**\nBoth value and policy iteration achieve the same outcome: find optimal values, \napply policy extraction and derive optimal policy.\n\nValue iteration:\n- every iteration updates values and (implicitly) the policy\n- doesn't track policy, but taking the max over actions implicitly recomputes it\n\nPolicy iteration:\n- several passes that update utilities with a fixed policy - fast because it \nconsiders only a single action\n- after policy is evaluated, a new policy is chosen - slow like value iteration\n- new policy will be better (or it's finished)\n\nBoth are dynamic programs for solving MDPs.\n\n**Summary: MDP algorithms**\n- compute optimal values using value or policy iteration\n- compute values for a particular policy: use policy evaluation\n- turn values in a policy: use policy extraction (one-step look-ahead)\n\nAll very similar - variations of Bellman equations; all use one-step look-ahead \nexpectimax fragments; differ in whether we plug-in a fixed policy or max over actions.\n\n---\nPrinciple of maximum expected utility:\nA rational agent should choose the action that maximizes its expected utility, \ngiven its knowledge.\n\nFor worst-case minimax reasoning, terminal function scale doesn't matter; known as \n*insensitivity to monotonic transformations*.\nHowever, for average-case expectimax reasoning, magnitudes need to be meaningful - \ntransformations could affect the outcome.\n\n**Utilities**\n*Utilities are functions from outcomes (states) to real numbers that describe an \nagent's preferences.* They summarise an agen't goals.\n\nIn games: utilities may be simple (+1/-1 for win/lose).\n\nTheorem: any rational preference can be summarised by a utility function.\n\nBehaviours emerge from hard-coded utilities. We do not prescribe behaviours or let\n agents pick utilities to avoid unintended consequences.\n\n**Rational preferences**\nAxioms of rationality:\n- Transitivity: $(A \\succ B)~\\land~(B \\succ C) \\implies (A \\succ C)$\n- Orderability: $(A \\succ B)~\\lor~(B \\succ A) \\lor (A \\sim B)$\n- Continuity: $A \\succ B \\succ C \\implies \\exists_p~[p, A; 1-p, C] \\sim B$\n- Substitutability: $A \\sim B \\implies [p, A; 1-p, C] \\sim [p, B; 1-p, C]$\n- Monotonicity: $A \\succ B \\implies (p \\geq q \\Longleftrightarrow [p, A; 1-p, B] \\succeq [q, A; 1-q, B])$\nTheorem: rational preferences imply behaviour describable as maximum of expected utility.\n\n**MEU principle**\n*Theorem: given any preferences satisfying the constraints (axioms), there exists \na real-valued function $U$ such that*\n$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$\n$U([p_1, S_1; ...; p_n, S_n]) = \\sum_i p_i U(S_i)$\nThat is, *values assigned by $U$ preserve preferences of both prizes and lotteries*.\n\nMEU principle:\n- choose action that maximizes expected utility\n- (an agent can be rational (consistent with MEU) without ever representing/manipulating \nutilities and probabilities; e.g. can use a lookup table for some problems)\n\n**Utility scales**\n- normalised utilities: $u_+ = 1, u_- = 0$\n- micromorts: one-millionth chance of death\n- QALYs: quality-adjusted life years\n\nBehaviour is invariant under positive linear transformations: $U'(x) = k_1 U(x) + k_2$ \nwhere $k_1 > 0$\nWith deterministic prizes (i.e. no lottery choices), only ordinal utility can be \ndetermined, i.e. total order on prizes.\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "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",
        "A one-armed bandit is a slot machine with one lever, and an **n-armed bandit** has \n",
        "$n$ levers.\n",
        "\n",
        "There is a choice between **exploitation**, choosing the arm that has the best reward\n",
        "so far, and **exploration**, choosing the arm of an unknown state and action to \n",
        "gain new information.\n",
        "\n",
        "There a several definitions of **bandit problems**, one is:\n",
        "- each arm $M_i$ is a **Markov reward process (MRP)**, i.e. an MDP with one action\n",
        " $a_i$. The arm defines a distribution over reward sequences.\n",
        "- the overall problem is an MDP: state space is Cartesian product $S = S_i x ... S_n$;\n",
        " actions are $a_1, ..., a_n$; transition model depends on arm $M_i$ selected; \n",
        " discount factor is $\\\\gamma$.\n",
        "\n",
        "The **Gittins index** provides a simple optimal policy for any bandit problem: \n",
        "pull the arm that has the highest index then update the Gittin indices. The index \n",
        "of arm $M_i$ depends only on its properties therefore an optimal decision on the \n",
        "first iteration can be made in $\\\\mathcal{O}(n)$ ($n$ being the number of arms) \n",
        "and subsequent decisions in $\\\\mathcal{O}(1)$ since their indices remain unchanged.\n",
        "\n",
        "The value of the Gittins index is the maximum value attained from the ratio. Beyond \n",
        "this point, $M_\\\\lambda$ is chosen by the optimal policy over $M$. \n",
        "\n",
        "The Gittins index for an arm $M$ with state $s$ can be calculated by seeing that \n",
        "a tipping point where an optimal policy is indifferent between $M$ and $M_\\\\lambda$, \n",
        "the value of choosing $M$ is the same as choosing an infinite sequence of $\\\\lambda$-rewards.\n",
        "\n",
        "$M$ can be turned into an MDP whose optimal policy is the optimal stopping rule \n",
        "for $M$. The type of MDP to solve this is called a **restart MDP** where the agent \n",
        "returns to $M$'s initial state $s$, which is equivalent to deciding to quit and \n",
        "receive infinite $\\\\lambda$-rewards.\n",
        "\n",
        "Any of the previous MDP algorithms can solve this MDP. The general result is the \n",
        "Gittins index for $M$ in state $s$ is equal to the optimal policy of the restart \n",
        "MDP times $1-\\\\gamma$.\n",
        "\n",
        "The **Bernoulli bandit** has arms $M_i$ that produce rewards $0$ or $1$ with fixed,\n",
        " unknown probability $\\\\mu_i$. The state of $M_i$ is defined by the counts success \n",
        " $s_i$ and failure $f_i$. The transition function for next outcome $1$ is $s_i / (s_i + f_i)$\n",
        "  and opposite for $0$.\n",
        "\n",
        "#### Approximately optimal bandit policies\n",
        "The **upper confidence bound (UCB)** heuristic method samples each arm to find a\n",
        " confidence interval for the value of the arm, then the arm with the highest UCB is \n",
        " selected. This is strictly not a Gittins index since the total number of samples \n",
        " used is drawn across all arms, not just the arm in question.\n",
        "\n",
        "**Thompson sampling** chooses an arm randomly according to the probability the arm \n",
        "is optimal given samples so far.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "In RL, an agent interacts with the world and receives rewards that reflect how well\n",
        " it's doing. The goal is to maximize the expected sum of rewards. The agent does not\n",
        "  know the transition model or reward function.\n",
        "\n",
        "The main approaches to RL are:\n",
        "- **Model-based RL:** agent uses a transition model of environment to interpret \n",
        "reward signals and make decisions. The agent may need to learn the model from \n",
        "observing the effects of its actions if it initially unknown, otherwise it may \n",
        "already be known. Often learns from a utility function.\n",
        "- **Model-free RL:** the agent neither knows nor learns a transition model and \n",
        "learns a more direct representation of how to behave. Two approaches:\n",
        "\t- **Action-utility learning:** most common is **Q-learning** which uses a **Q-function**\n",
        "   $Q(s,a)$ which denotes the sum of rewards from state $s$ onward if action $a$ is taken.\n",
        "\t- **Policy search:** the agent learns a policy $\\\\pi(s)$ that maps states to actions,\n",
        "   i.e. a reflex agent.\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "**Passive RL** is where an agent has a fixed policy $\\\\pi(s)$ and the task is to \n",
        "learn the utilities of states (or state-action pairs) $U^{\\\\pi}(s)$. This is a \n",
        "**passive learning agent**.\n",
        "\n",
        "The agent does not know the transition model or reward function. It executes a \n",
        "set of trials using $\\\\pi$ and the objective is to use information about rewards \n",
        "in each experienced transition to learn the expected utility associated with each \n",
        "nonterminal state $s$.\n",
        "\n",
        "---\n",
        "**Direct utility estimation** gives the utility of a state as the expected total \n",
        "reward from that state onward (known as the expected **reward-to-go**) and each \n",
        "trial provides a sample for each of these states. In the limit, the sample average\n",
        " will converge to the true expectation.\n",
        "\n",
        "Each example becomes a (state, reward-to-go) pair. However, it ignores that the \n",
        "utility of a state is determined by the reward and expected utility of successor \n",
        "states, i.e. it ignores connections between states. States learn nothing until \n",
        "the end of a trial.\n",
        "\n",
        "Hence, direct utility estimation includes functions that violate the Bellman equations\n",
        " (i.e. it views the space as much larger) so converges slowly.\n",
        "\n",
        "---\n",
        "**Adaptive dynamic programming (ADP)** agents learn the transition model that \n",
        "connects states and solves the corresponding MDP with dynamic programming. For a\n",
        " passive learning agent, that means plugging in the learned transition model and \n",
        " observed rewards into the Bellman equation for expected utilities.\n",
        "\n",
        "**Modified policy iteration** can also be used with a simplified value iteration \n",
        "process to update utility estimates after each change to the learned model.\n",
        "\n",
        "Learning the transition model is simple as it uses the counts of a state transition\n",
        " to a new state to calculate the estimated transition probabilities.\n",
        "\n",
        "---\n",
        "**Temporal difference learning** is changing the estimate based on the difference\n",
        " between the observed current reward and reward expected based on what has been \n",
        " observed so far. Therefore we apply the following update:\n",
        "$U^{\\\\pi}(s) \\\\leftarrow U^{\\\\pi}(s) + \\\\alpha[R(s,\\\\pi(s),s') + \\\\gamma U^{\\\\pi}(s') - \n",
        "U^{\\\\pi}(s)]$\n",
        "where $\\\\alpha$ is the **learning rate**.\n",
        "The update is intended to reduce the error. Reducing $\\\\alpha$ as the number of times\n",
        " a state is visited increases eventually causes the utility to converge.\n",
        "\n",
        "TDL does not require a transition model to perform updates.\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "Passive learning agents have fixed policies that determine behaviour; active learning\n",
        " decides what actions to take.\n",
        "\n",
        "#### Exploration\n",
        "A **greedy agent** greedily takes the action that it believes to be optimal from\n",
        " a learned model, but this might not be optimal as the learned model may not be \n",
        " the same as the true environment. Sometimes it converges to the optimal, often not.\n",
        "\n",
        "Actions do more than provide rewards, they also provide information about resulting\n",
        " states. An agent must decide between exploitation and exploration. \n",
        "\n",
        "Any scheme the agent follows should be greedy in the limit of infinite exploitation,\n",
        " or **GLIE**, meaning it must try each action in each state a number of times to \n",
        " avoid missing an optimal action.\n",
        "\n",
        "There are several GLIE schemes:\n",
        "- agent chooses a random action at time step $t$ with probability $1/t$ and the \n",
        "greedy option otherwise; simple but slow.\n",
        "- give weights to actions that haven't been tried very often while avoiding actions\n",
        " with low utilities. The exploration function $f(u,n)$ determines how greed is \n",
        " traded off against curiosity. Actions that lead toward unexplored regions are weighted\n",
        "  more highly, which are propagated back from further afield.\n",
        "\n",
        "#### Safe exploration\n",
        "Many actions are irreversible, i.e. no action can restore previous states. In the\n",
        " worst case we have an **absorbing state** where no actions have an affect and no\n",
        "  rewards are received.\n",
        "\n",
        "We should choose a policy that works well for the whole range of models that stand\n",
        " a good chance of being the true model, even if it is suboptimal. These approaches are:\n",
        "- Bayesian RL: finds the optimal policy produced by the one with the highest expected utility.\n",
        "- Robust control theory: allows for a set of possible models without assigning \n",
        "probabilities, and finds an optimal policy as one that gives the best outcome in \n",
        "the worst case.\n",
        "\n",
        "Human knowledge can keep a system safe by recording a set of actions by an experienced\n",
        " teacher and the system can improve from there. Another way is for a secondary program \n",
        " enforce constraints, for example taking control if the system gets close to an \n",
        " absorbing state.\n",
        "\n",
        "#### Temporal-difference Q-learning\n",
        "The **Q-learning** doesn't require a transition model either for learning or action\n",
        " selection. However, it has no means of looking into the future so it can have \n",
        " difficulty with sparse rewards and long action sequences will be required.\n",
        "\n",
        "**SARSA** (state, action, reward, state, action) updates with the Q-value of the\n",
        " action $a'$ actually taken (rather than the best action). If exploration produces\n",
        "  a negative reward, it penalizes the action (Q-learning does not).\n",
        "\n",
        "Q-learning is **off-policy** (start acting according to best action policy) and \n",
        "SARSA is **on-policy** (stick with current policy).\n",
        "\n",
        "Q-learning is more flexible as it learns well with different exploration policies.\n",
        " SARSA is more appropriate if it's (partly) controlled by other agents or programs.\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "Introduction to Reinforcement Learning\n",
        "\n",
        "#### Bandit Problems\n",
        "Bandit problems came from slot machines with $>1$ levers.\n",
        "Can be solved as an MDP (offline planning), through value or policy iteration.\n",
        "\n",
        "With reinforcement learning, you can't plan as you don't know the underlying probability\n",
        " distribution of actions therefore it can't be solved with just computation alone. \n",
        " You need to figure it out through observation of results and associated rewards \n",
        " (i.e. learning).\n",
        "\n",
        "Key terms:\n",
        "- **Exploration:** try unknown actions to get information\n",
        "- **Exploitation:** use what you know\n",
        "- **Regret:** even if you learn, mistakes happen\n",
        "- **Sampling:** there is chance so need to repeat actions\n",
        "- **Difficulty:** learning can be harder than solving known MDPs\n",
        "\n",
        "#### Reinforcement Learning\n",
        "Basic idea:\n",
        "- receive feedback in terms of rewards\n",
        "- utility is defined by reward function\n",
        "- must learn to maximize expected rewards\n",
        "- all learning based on sample of observed outcomes\n",
        "\n",
        "Describing a problem is the same as an MDP, except the transition model and \n",
        "resulting reward are hidden so we don't know which states are good and must attempt\n",
        " actions to learn. Aim is still to find a good policy, $\\\\pi(s)$.\n",
        "\n",
        "MDPs are offline (compute/simulate plan) and RL is online (learn as you go).\n",
        "\n",
        "#### Model-Based Learning\n",
        "Learn an approximate model based on experiences and solve (with MDPs) for values\n",
        " as if the learned model was correct.\n",
        "\n",
        "Steps:\n",
        "1. Learn empirical MDP model\n",
        "\t1. count outcomes $s'$ for each $s, a$\n",
        "\t2. normalize to give an estimate $\\\\hat{T}(s,a,s')$\n",
        "\t3. discover each $\\\\hat{R}(s,a,s')$\n",
        "2. Solve the learned MDP\n",
        "\t1. Use, for example, value iteration (and policy extraction)\n",
        "\n",
        "---\n",
        "Passive Reinforcement Learning\n",
        "\n",
        "#### Model-Free Learning\n",
        "We don't construct an explicit probability model to the transition function. Instead,\n",
        " for every action, compare the results to expected results. Then, adjust values when\n",
        "  result is different from expectation. We only keep track of values of interest \n",
        "  and not transition or reward functions.\n",
        "\n",
        "#### Passive RL\n",
        "Try policy provided to us. Don't attempt to act optimally, instead evaluate policy\n",
        " (i.e. policy iteration).\n",
        "\n",
        "Simplified task: policy evaluation:\n",
        "- input: fixed policy $\\\\pi(s)$\n",
        "- transition and reward functions are unknown\n",
        "- goal: learn state values\n",
        "The learner is \"along for the ride\" and has no choice in which actions to take. \n",
        "The agent executes the policy and learns from experience.\n",
        "\n",
        "**Direct evaluation**\n",
        "Goal is to compute values for each state under $\\\\pi$.\n",
        "Idea: average sum of observed sample values\n",
        "- act according to $\\\\pi$\n",
        "- at each state, record sum of discounted rewards\n",
        "- average samples\n",
        "\n",
        "Advantages:\n",
        "- easy to understand\n",
        "- doesn't require knowledge of $T, R$\n",
        "- eventually computes correct average values using sample transitions\n",
        "\n",
        "Disadvantages:\n",
        "- discards information about state connections\n",
        "- each state learned separately\n",
        "- slow to learn!\n",
        "\n",
        "Therefore, use policy evaluation. However, need information about $T$ and $R$.\n",
        "\n",
        "Idea: take sample of outcomes $s'$ by taking the action and average over samples \n",
        "(removes the need for knowing the probability distribution). However, cannot gather\n",
        " repeated samples from state $s$ as there is no guarantee that we'll be at that \n",
        " $s$ several times.\n",
        "\n",
        "---\n",
        "Temporal Difference Learning\n",
        "\n",
        "Big idea: learn from every experience!\n",
        "- update $V(s)$ each time we experience a transition $(s,a,s')$\n",
        "- likely outcomes will contribute updates more often\n",
        "\n",
        "Sample of $V(s)$: ${sample} = R(s, \\\\pi(s), s') + \\\\gamma V^{\\\\pi}(s')$\n",
        "Update to $V(s)$: $V^{\\\\pi}(s) \\\\leftarrow (1-\\\\alpha)V^{\\\\pi}(s) + \\\\alpha \\\\cdot {sample}$\n",
        "where $\\\\alpha$ is the learning rate which allows us to control how much weight we \n",
        "want to apply current estimate vs. new sample estimate. This form is known as **interpolation**.\n",
        "This can be re-written as $V^{\\\\pi}(s) \\\\leftarrow V^{\\\\pi}(s) + \\\\alpha({sample} - V^{\\\\pi}(s))$.\n",
        "\n",
        "**Exponential moving average**\n",
        "The running interpolation update $\\\\bar{x}_n = (1-\\\\alpha)  \\\\cdot \\\\bar{x}_{n-1} + \n",
        "\\\\alpha \\\\cdot x_n$ makes recent examples more important, therefore forgetting about\n",
        " the past since distant values were inaccurate.\n",
        "\n",
        "Decreasing the learning rate $\\\\alpha$ converges averages over time.\n",
        "\n",
        "**TDL**\n",
        "Model-free way to do policy evaluation.\n",
        "However, it can't be turned into a new policy! We require Q-values, but for that,\n",
        " we need the transition model and reward.\n",
        "\n",
        "Idea: learn Q-values, not values. This makes action selection model-free too.\n",
        "\n",
        "---\n",
        "Active Reinforcement Learning (Q-Learning)\n",
        "\n",
        "Full RL: optimal policies (like value iteration).\n",
        "Goal: learn optimal policy and values.\n",
        "\n",
        "The learner makes choices, and must decide between exploration and exploitation.\n",
        " This is not offline planning as we learn as actions are taken.\n",
        "\n",
        "#### Q-Value Learning\n",
        "Q-value iteration: [[MDP Examples]]\n",
        "\n",
        "**Q-learning**: sample-based Q-value iteration.\n",
        "Learn $Q(s,a)$ values as we go:\n",
        "- receive sample $(s,a,s',r)$\n",
        "- consider old estimate $Q(s,a)$\n",
        "- consider new sample estimate: ${sample} = R(s, a, s') + \\\\gamma~\\\\underset{a'}{max} Q(s',a')$\n",
        "- incorporate new estimate into running average: $Q(s,a) \\\\leftarrow (1-\\\\alpha)Q(s,a) + \\\\alpha \\\\cdot {sample}$\n",
        "\n",
        "**Q-Learning Properties**\n",
        "Q-learning converges to optimal policy, even when acting sub-optimally! This is \n",
        "called **off-policy learning**.\n",
        "\n",
        "Caveats:\n",
        "- need enough exploration\n",
        "- eventually make the learning rate $\\\\alpha$ small enough, but not decrease it \n",
        "too quickly\n",
        "In the limit, it doesn't matter how actions are selected!\n",
        "\n",
        "---\n",
        "Exploration vs Exploitation\n",
        "\n",
        "Several schemes for forcing exploration:\n",
        "**Simplest: random actions ($\\\\epsilon$-greedy)**\n",
        "- Idea: at every time step, flip a coin. With (small) probability $\\\\epsilon$, act\n",
        " randomly. Otherwise, with $1-\\\\epsilon$, act on current policy.\n",
        "- Problems: space is eventually explored, but it will keep thrashing around once\n",
        " learning is done. \n",
        "- Solutions: lower $\\\\epsilon$ over time; exploration functions.\n",
        "\t\n",
        "**Exploration Functions**\n",
        "Can explore at a fixed amount of randomness, or a better option is to explore \n",
        "areas whose 'badness' is not yet known then eventually stop exploring.\n",
        "\n",
        "Define $f(u,n)=u+k/n$, where $u$ is a value estimate (i.e. current utility value),\n",
        " $n$ is a visit count, $k$ is a bonus and $f(u,n)$ is the returned optimistic utility.\n",
        "\n",
        "Therefore\n",
        "Regular Q-state: $Q(s,a) \\\\leftarrow \\\\alpha ( R(s, a, s') + \\\\gamma~\\\\underset{a'}{max}~Q(s',a') )$\n",
        "Modified Q-state: $Q(s,a) \\\\leftarrow \\\\alpha ( R(s, a, s') + \\\\gamma~\\\\underset{a'}{max}~f(Q(s',a'), N(s',a')) )$\n",
        "This also propagates the bonus back to states that lead to unknown states.\n",
        "\n",
        "**Regret**\n",
        "Measures total cost of mistakes: difference between expected rewards, including \n",
        "youthful sub-optimality, and optimal expected rewards.\n",
        "\n",
        "Minimizing regret goes beyond learning to be optimal - it is learning the optimal\n",
        " policy as quickly as is possible, i.e. optimally learning to be optimal.\n",
        "\n",
        "Random exploration has higher regret than exploration functions.\n",
        "\n",
        "---\n",
        "Approximate Q-Learning\n",
        "\n",
        "#### Generalising across states\n",
        "Basic Q-learning keeps a table of all q-values. In realistic situations, we cannot\n",
        " learn about every single state as there are too many to visit and hold in memory.\n",
        "\n",
        "Instead, we want to generalise by learning about a small number of states from \n",
        "experience and then applying that knowledge to new, similar situations.\n",
        "\n",
        "Evaluation functions score non-terminal states in depth-limited search. The ideal \n",
        "function would return the actual minimax value of a position, however in practice \n",
        "we use a weighted linear sum of features, ${eval}(s) = w_1f_1(s)+...+w_nf_n(s)$.\n",
        "\n",
        "Using feature representation, a Q-function or value function can be written for any state.\n",
        "- Advantage: experience is summed up in a few numbers\n",
        "- Disadvantage: states may share features, but actually have very different values\n",
        "Generalisation depends on how well we represent states using features.\n",
        "\n",
        "$Q(s,a) = w_1f_1(s,a)+...+w_nf_n(s,a)$\n",
        "\n",
        "**Q-learning with linear Q-functions**\n",
        "${transition} = (s,a,s',r)$\n",
        "${difference} = [r + \\\\gamma~\\\\underset{a'}{max}~Q(s',a')] - Q(s,a)$\n",
        "Exact Q's given by: $Q(s,a) + \\\\alpha[{difference}]$\n",
        "Approximate Q's given by: $w_i \\\\leftarrow w_i + \\\\alpha[{difference}]f_i(s,a)$\n",
        "\n",
        "Intuition: adjust weights of active features, i.e. blame features that lead to a\n",
        " bad action and 'disprefer' all states with that state's features\n",
        "\n",
        "Formal justification: online least squares (covered in future)\n",
        "\n",
        "Does not *always* converge to the optimal policy.\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1800eff2-60eb-4977-fbab-05aed418729b"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nA one-armed bandit is a slot machine with one lever, and an **n-armed bandit** has \n$n$ levers.\n\nThere is a choice between **exploitation**, choosing the arm that has the best reward\nso far, and **exploration**, choosing the arm of an unknown state and action to \ngain new information.\n\nThere a several definitions of **bandit problems**, one is:\n- each arm $M_i$ is a **Markov reward process (MRP)**, i.e. an MDP with one action\n $a_i$. The arm defines a distribution over reward sequences.\n- the overall problem is an MDP: state space is Cartesian product $S = S_i x ... S_n$;\n actions are $a_1, ..., a_n$; transition model depends on arm $M_i$ selected; \n discount factor is $\\gamma$.\n\nThe **Gittins index** provides a simple optimal policy for any bandit problem: \npull the arm that has the highest index then update the Gittin indices. The index \nof arm $M_i$ depends only on its properties therefore an optimal decision on the \nfirst iteration can be made in $\\mathcal{O}(n)$ ($n$ being the number of arms) \nand subsequent decisions in $\\mathcal{O}(1)$ since their indices remain unchanged.\n\nThe value of the Gittins index is the maximum value attained from the ratio. Beyond \nthis point, $M_\\lambda$ is chosen by the optimal policy over $M$. \n\nThe Gittins index for an arm $M$ with state $s$ can be calculated by seeing that \na tipping point where an optimal policy is indifferent between $M$ and $M_\\lambda$, \nthe value of choosing $M$ is the same as choosing an infinite sequence of $\\lambda$-rewards.\n\n$M$ can be turned into an MDP whose optimal policy is the optimal stopping rule \nfor $M$. The type of MDP to solve this is called a **restart MDP** where the agent \nreturns to $M$'s initial state $s$, which is equivalent to deciding to quit and \nreceive infinite $\\lambda$-rewards.\n\nAny of the previous MDP algorithms can solve this MDP. The general result is the \nGittins index for $M$ in state $s$ is equal to the optimal policy of the restart \nMDP times $1-\\gamma$.\n\nThe **Bernoulli bandit** has arms $M_i$ that produce rewards $0$ or $1$ with fixed,\n unknown probability $\\mu_i$. The state of $M_i$ is defined by the counts success \n $s_i$ and failure $f_i$. The transition function for next outcome $1$ is $s_i / (s_i + f_i)$\n  and opposite for $0$.\n\n#### Approximately optimal bandit policies\nThe **upper confidence bound (UCB)** heuristic method samples each arm to find a\n confidence interval for the value of the arm, then the arm with the highest UCB is \n selected. This is strictly not a Gittins index since the total number of samples \n used is drawn across all arms, not just the arm in question.\n\n**Thompson sampling** chooses an arm randomly according to the probability the arm \nis optimal given samples so far.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nIn RL, an agent interacts with the world and receives rewards that reflect how well\n it's doing. The goal is to maximize the expected sum of rewards. The agent does not\n  know the transition model or reward function.\n\nThe main approaches to RL are:\n- **Model-based RL:** agent uses a transition model of environment to interpret \nreward signals and make decisions. The agent may need to learn the model from \nobserving the effects of its actions if it initially unknown, otherwise it may \nalready be known. Often learns from a utility function.\n- **Model-free RL:** the agent neither knows nor learns a transition model and \nlearns a more direct representation of how to behave. Two approaches:\n\t- **Action-utility learning:** most common is **Q-learning** which uses a **Q-function**\n   $Q(s,a)$ which denotes the sum of rewards from state $s$ onward if action $a$ is taken.\n\t- **Policy search:** the agent learns a policy $\\pi(s)$ that maps states to actions,\n   i.e. a reflex agent.\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n**Passive RL** is where an agent has a fixed policy $\\pi(s)$ and the task is to \nlearn the utilities of states (or state-action pairs) $U^{\\pi}(s)$. This is a \n**passive learning agent**.\n\nThe agent does not know the transition model or reward function. It executes a \nset of trials using $\\pi$ and the objective is to use information about rewards \nin each experienced transition to learn the expected utility associated with each \nnonterminal state $s$.\n\n---\n**Direct utility estimation** gives the utility of a state as the expected total \nreward from that state onward (known as the expected **reward-to-go**) and each \ntrial provides a sample for each of these states. In the limit, the sample average\n will converge to the true expectation.\n\nEach example becomes a (state, reward-to-go) pair. However, it ignores that the \nutility of a state is determined by the reward and expected utility of successor \nstates, i.e. it ignores connections between states. States learn nothing until \nthe end of a trial.\n\nHence, direct utility estimation includes functions that violate the Bellman equations\n (i.e. it views the space as much larger) so converges slowly.\n\n---\n**Adaptive dynamic programming (ADP)** agents learn the transition model that \nconnects states and solves the corresponding MDP with dynamic programming. For a\n passive learning agent, that means plugging in the learned transition model and \n observed rewards into the Bellman equation for expected utilities.\n\n**Modified policy iteration** can also be used with a simplified value iteration \nprocess to update utility estimates after each change to the learned model.\n\nLearning the transition model is simple as it uses the counts of a state transition\n to a new state to calculate the estimated transition probabilities.\n\n---\n**Temporal difference learning** is changing the estimate based on the difference\n between the observed current reward and reward expected based on what has been \n observed so far. Therefore we apply the following update:\n$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s,\\pi(s),s') + \\gamma U^{\\pi}(s') - \nU^{\\pi}(s)]$\nwhere $\\alpha$ is the **learning rate**.\nThe update is intended to reduce the error. Reducing $\\alpha$ as the number of times\n a state is visited increases eventually causes the utility to converge.\n\nTDL does not require a transition model to perform updates.\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nPassive learning agents have fixed policies that determine behaviour; active learning\n decides what actions to take.\n\n#### Exploration\nA **greedy agent** greedily takes the action that it believes to be optimal from\n a learned model, but this might not be optimal as the learned model may not be \n the same as the true environment. Sometimes it converges to the optimal, often not.\n\nActions do more than provide rewards, they also provide information about resulting\n states. An agent must decide between exploitation and exploration. \n\nAny scheme the agent follows should be greedy in the limit of infinite exploitation,\n or **GLIE**, meaning it must try each action in each state a number of times to \n avoid missing an optimal action.\n\nThere are several GLIE schemes:\n- agent chooses a random action at time step $t$ with probability $1/t$ and the \ngreedy option otherwise; simple but slow.\n- give weights to actions that haven't been tried very often while avoiding actions\n with low utilities. The exploration function $f(u,n)$ determines how greed is \n traded off against curiosity. Actions that lead toward unexplored regions are weighted\n  more highly, which are propagated back from further afield.\n\n#### Safe exploration\nMany actions are irreversible, i.e. no action can restore previous states. In the\n worst case we have an **absorbing state** where no actions have an affect and no\n  rewards are received.\n\nWe should choose a policy that works well for the whole range of models that stand\n a good chance of being the true model, even if it is suboptimal. These approaches are:\n- Bayesian RL: finds the optimal policy produced by the one with the highest expected utility.\n- Robust control theory: allows for a set of possible models without assigning \nprobabilities, and finds an optimal policy as one that gives the best outcome in \nthe worst case.\n\nHuman knowledge can keep a system safe by recording a set of actions by an experienced\n teacher and the system can improve from there. Another way is for a secondary program \n enforce constraints, for example taking control if the system gets close to an \n absorbing state.\n\n#### Temporal-difference Q-learning\nThe **Q-learning** doesn't require a transition model either for learning or action\n selection. However, it has no means of looking into the future so it can have \n difficulty with sparse rewards and long action sequences will be required.\n\n**SARSA** (state, action, reward, state, action) updates with the Q-value of the\n action $a'$ actually taken (rather than the best action). If exploration produces\n  a negative reward, it penalizes the action (Q-learning does not).\n\nQ-learning is **off-policy** (start acting according to best action policy) and \nSARSA is **on-policy** (stick with current policy).\n\nQ-learning is more flexible as it learns well with different exploration policies.\n SARSA is more appropriate if it's (partly) controlled by other agents or programs.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\nIntroduction to Reinforcement Learning\n\n#### Bandit Problems\nBandit problems came from slot machines with $>1$ levers.\nCan be solved as an MDP (offline planning), through value or policy iteration.\n\nWith reinforcement learning, you can't plan as you don't know the underlying probability\n distribution of actions therefore it can't be solved with just computation alone. \n You need to figure it out through observation of results and associated rewards \n (i.e. learning).\n\nKey terms:\n- **Exploration:** try unknown actions to get information\n- **Exploitation:** use what you know\n- **Regret:** even if you learn, mistakes happen\n- **Sampling:** there is chance so need to repeat actions\n- **Difficulty:** learning can be harder than solving known MDPs\n\n#### Reinforcement Learning\nBasic idea:\n- receive feedback in terms of rewards\n- utility is defined by reward function\n- must learn to maximize expected rewards\n- all learning based on sample of observed outcomes\n\nDescribing a problem is the same as an MDP, except the transition model and \nresulting reward are hidden so we don't know which states are good and must attempt\n actions to learn. Aim is still to find a good policy, $\\pi(s)$.\n\nMDPs are offline (compute/simulate plan) and RL is online (learn as you go).\n\n#### Model-Based Learning\nLearn an approximate model based on experiences and solve (with MDPs) for values\n as if the learned model was correct.\n\nSteps:\n1. Learn empirical MDP model\n\t1. count outcomes $s'$ for each $s, a$\n\t2. normalize to give an estimate $\\hat{T}(s,a,s')$\n\t3. discover each $\\hat{R}(s,a,s')$\n2. Solve the learned MDP\n\t1. Use, for example, value iteration (and policy extraction)\n\n---\nPassive Reinforcement Learning\n\n#### Model-Free Learning\nWe don't construct an explicit probability model to the transition function. Instead,\n for every action, compare the results to expected results. Then, adjust values when\n  result is different from expectation. We only keep track of values of interest \n  and not transition or reward functions.\n\n#### Passive RL\nTry policy provided to us. Don't attempt to act optimally, instead evaluate policy\n (i.e. policy iteration).\n\nSimplified task: policy evaluation:\n- input: fixed policy $\\pi(s)$\n- transition and reward functions are unknown\n- goal: learn state values\nThe learner is \"along for the ride\" and has no choice in which actions to take. \nThe agent executes the policy and learns from experience.\n\n**Direct evaluation**\nGoal is to compute values for each state under $\\pi$.\nIdea: average sum of observed sample values\n- act according to $\\pi$\n- at each state, record sum of discounted rewards\n- average samples\n\nAdvantages:\n- easy to understand\n- doesn't require knowledge of $T, R$\n- eventually computes correct average values using sample transitions\n\nDisadvantages:\n- discards information about state connections\n- each state learned separately\n- slow to learn!\n\nTherefore, use policy evaluation. However, need information about $T$ and $R$.\n\nIdea: take sample of outcomes $s'$ by taking the action and average over samples \n(removes the need for knowing the probability distribution). However, cannot gather\n repeated samples from state $s$ as there is no guarantee that we'll be at that \n $s$ several times.\n\n---\nTemporal Difference Learning\n\nBig idea: learn from every experience!\n- update $V(s)$ each time we experience a transition $(s,a,s')$\n- likely outcomes will contribute updates more often\n\nSample of $V(s)$: ${sample} = R(s, \\pi(s), s') + \\gamma V^{\\pi}(s')$\nUpdate to $V(s)$: $V^{\\pi}(s) \\leftarrow (1-\\alpha)V^{\\pi}(s) + \\alpha \\cdot {sample}$\nwhere $\\alpha$ is the learning rate which allows us to control how much weight we \nwant to apply current estimate vs. new sample estimate. This form is known as **interpolation**.\nThis can be re-written as $V^{\\pi}(s) \\leftarrow V^{\\pi}(s) + \\alpha({sample} - V^{\\pi}(s))$.\n\n**Exponential moving average**\nThe running interpolation update $\\bar{x}_n = (1-\\alpha)  \\cdot \\bar{x}_{n-1} + \n\\alpha \\cdot x_n$ makes recent examples more important, therefore forgetting about\n the past since distant values were inaccurate.\n\nDecreasing the learning rate $\\alpha$ converges averages over time.\n\n**TDL**\nModel-free way to do policy evaluation.\nHowever, it can't be turned into a new policy! We require Q-values, but for that,\n we need the transition model and reward.\n\nIdea: learn Q-values, not values. This makes action selection model-free too.\n\n---\nActive Reinforcement Learning (Q-Learning)\n\nFull RL: optimal policies (like value iteration).\nGoal: learn optimal policy and values.\n\nThe learner makes choices, and must decide between exploration and exploitation.\n This is not offline planning as we learn as actions are taken.\n\n#### Q-Value Learning\nQ-value iteration: [[MDP Examples]]\n\n**Q-learning**: sample-based Q-value iteration.\nLearn $Q(s,a)$ values as we go:\n- receive sample $(s,a,s',r)$\n- consider old estimate $Q(s,a)$\n- consider new sample estimate: ${sample} = R(s, a, s') + \\gamma~\\underset{a'}{max} Q(s',a')$\n- incorporate new estimate into running average: $Q(s,a) \\leftarrow (1-\\alpha)Q(s,a) + \\alpha \\cdot {sample}$\n\n**Q-Learning Properties**\nQ-learning converges to optimal policy, even when acting sub-optimally! This is \ncalled **off-policy learning**.\n\nCaveats:\n- need enough exploration\n- eventually make the learning rate $\\alpha$ small enough, but not decrease it \ntoo quickly\nIn the limit, it doesn't matter how actions are selected!\n\n---\nExploration vs Exploitation\n\nSeveral schemes for forcing exploration:\n**Simplest: random actions ($\\epsilon$-greedy)**\n- Idea: at every time step, flip a coin. With (small) probability $\\epsilon$, act\n randomly. Otherwise, with $1-\\epsilon$, act on current policy.\n- Problems: space is eventually explored, but it will keep thrashing around once\n learning is done. \n- Solutions: lower $\\epsilon$ over time; exploration functions.\n\t\n**Exploration Functions**\nCan explore at a fixed amount of randomness, or a better option is to explore \nareas whose 'badness' is not yet known then eventually stop exploring.\n\nDefine $f(u,n)=u+k/n$, where $u$ is a value estimate (i.e. current utility value),\n $n$ is a visit count, $k$ is a bonus and $f(u,n)$ is the returned optimistic utility.\n\nTherefore\nRegular Q-state: $Q(s,a) \\leftarrow \\alpha ( R(s, a, s') + \\gamma~\\underset{a'}{max}~Q(s',a') )$\nModified Q-state: $Q(s,a) \\leftarrow \\alpha ( R(s, a, s') + \\gamma~\\underset{a'}{max}~f(Q(s',a'), N(s',a')) )$\nThis also propagates the bonus back to states that lead to unknown states.\n\n**Regret**\nMeasures total cost of mistakes: difference between expected rewards, including \nyouthful sub-optimality, and optimal expected rewards.\n\nMinimizing regret goes beyond learning to be optimal - it is learning the optimal\n policy as quickly as is possible, i.e. optimally learning to be optimal.\n\nRandom exploration has higher regret than exploration functions.\n\n---\nApproximate Q-Learning\n\n#### Generalising across states\nBasic Q-learning keeps a table of all q-values. In realistic situations, we cannot\n learn about every single state as there are too many to visit and hold in memory.\n\nInstead, we want to generalise by learning about a small number of states from \nexperience and then applying that knowledge to new, similar situations.\n\nEvaluation functions score non-terminal states in depth-limited search. The ideal \nfunction would return the actual minimax value of a position, however in practice \nwe use a weighted linear sum of features, ${eval}(s) = w_1f_1(s)+...+w_nf_n(s)$.\n\nUsing feature representation, a Q-function or value function can be written for any state.\n- Advantage: experience is summed up in a few numbers\n- Disadvantage: states may share features, but actually have very different values\nGeneralisation depends on how well we represent states using features.\n\n$Q(s,a) = w_1f_1(s,a)+...+w_nf_n(s,a)$\n\n**Q-learning with linear Q-functions**\n${transition} = (s,a,s',r)$\n${difference} = [r + \\gamma~\\underset{a'}{max}~Q(s',a')] - Q(s,a)$\nExact Q's given by: $Q(s,a) + \\alpha[{difference}]$\nApproximate Q's given by: $w_i \\leftarrow w_i + \\alpha[{difference}]f_i(s,a)$\n\nIntuition: adjust weights of active features, i.e. blame features that lead to a\n bad action and 'disprefer' all states with that state's features\n\nFormal justification: online least squares (covered in future)\n\nDoes not *always* converge to the optimal policy.\n\n\n## Module 9 Definitions\n* **Term** - your definition here\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "Review on Probabilities\n",
        "\n",
        "##### Uncertainty\n",
        "Probabilistic reasoning provides a framework:\n",
        "- observed variables (evidence) - things agent knows about the world (e.g. sensor \n",
        "readings, symptoms)\n",
        "- unobserved variables (states) - things agent needs to reason about (e.g. where \n",
        "an object is, disease present)\n",
        "- model - agent knows something about how known variables relate to unknown variables\n",
        "\n",
        "Similar to logical assertions, probabilities are about possible worlds, but also \n",
        "quantify how likely a possible world is.\n",
        "\n",
        "Possible worlds = **sample space**; they are **mutually exclusive** and **exhaustive**.\n",
        "\n",
        "A probability model associates a probability $P(w)$ with each world $w$.\n",
        "\n",
        "##### Random Variables\n",
        "Some aspect of the world which may have uncertainty. Denoted by capital letters.\n",
        "\n",
        "##### Axioms of Probability\n",
        "Probability of any possible world is between $0$ and $1$:\n",
        "$0 \\\\leq P(w) \\\\leq 1$ for every $w$.\n",
        "\n",
        "Total probability of the set of all possible worlds is $1$:\n",
        "$\\\\underset{w \\\\in \\\\Omega}{\\\\sum} P(w) = 1$\n",
        "\n",
        "---\n",
        "Distributions\n",
        "\n",
        "##### Probability Distributions\n",
        "Unobserved R.V.s have distributions; a table of probabilities of values.\n",
        "A probability is a single number, e.g. $P(w = \\\\text{rain}) = 0.1$.\n",
        "Must adhere to axioms: [[Review on Probabilities]]\n",
        "\n",
        "##### Joint Distributions\n",
        "Joint distributions over a set of R.V.s $X_1, ..., X_n$ specifies a real number \n",
        "for each assignment or outcome.\n",
        "E.g. $P(X_1 = x_1, ..., X_n = x_n) = P(x_1, ..., x_n)$.\n",
        "Has an associated probability distribution, e.g. $P(T,W)$ equals some value.\n",
        "Again, must adhere to axioms: [[Review on Probabilities]]\n",
        "\n",
        "Size of distribution for $n$ variables with domain size $d$: $d^n$.\n",
        "Impractical to write out!\n",
        "\n",
        "##### Probabilistic Models\n",
        "Probabilistic models are a joint distribution over a set of R.V.s.\n",
        "- random variables with *domains*\n",
        "- assignments called *outcomes*\n",
        "- joint distributions say whether assignments are likely\n",
        "- *normalised* (sum to $1$)\n",
        "- ideally: most variables independent\n",
        "\n",
        "##### Events\n",
        "An event is a set $E$ of outcomes:\n",
        "$P(E) = \\\\underset{x_1...x_n \\\\in E}{\\\\sum} P(x_1...x_n)$\n",
        "Can calculate probability of any event, e.g. probability that it's hot and sunny,\n",
        " hot or sunny, just sunny...\n",
        "\n",
        "##### Marginal Distributions\n",
        "Typically only care about partial assignments, e.g. $P(T=hot)$.\n",
        "Marginal distributions are sub-tables which eliminate variables. Marginalization:\n",
        " combine collapsed rows by summing:\n",
        "$P(t) = \\\\underset{s}{\\\\sum} P(t,s)$.\n",
        "\n",
        "##### Conditional Probabilities\n",
        "Simple relation between joint and conditional probabilities:\n",
        "$P(a | b) = \\\\frac{P(a,b)}{P(b)}$\n",
        "\n",
        "##### Conditional Distributions\n",
        "Probability distributions over some variables given fixed values of others.\n",
        "Can calculate a set of conditional distribution tables from a joint distribution\n",
        " table.\n",
        "\n",
        " ---\n",
        "Probabilistic Inference and Rules\n",
        "\n",
        "##### Probabilistic Inference\n",
        "Compute a desired probability from other known probabilities, e.g. conditional from joint.\n",
        "\n",
        "Usually we compute conditional probabilities - represent agent's beliefs given the evidence.\n",
        "Probabilities change with new evidence - causes beliefs to be updated.\n",
        "\n",
        "##### Inference by Enumeration\n",
        "Structure:\n",
        "-  evidence variables: $E_1...E_k = e_1...e_k$\n",
        "-  query variable: $Q$\n",
        "-  hidden variables: $H_1...H_r$\n",
        "These together form all variables $X_1, X_2,...,X_n$\n",
        "\n",
        "Calculate: $P(Q | e_1...e_k)$\n",
        "\n",
        "Steps:\n",
        "1. select entries consistent with evidence, $e_i$\n",
        "2. sum out $H$ to find joint of query and evidence, $P(Q,e_1...e_k)=\\\\underset{h_1...h_r}{\\\\sum} P(Q, h_1...h_r, e_1...e_k)$\n",
        "3. normalize, multiply by $\\\\frac{1}{Z}$ where $Z=\\\\underset{q}{\\\\sum} P(Q, e_1...e_k)$\n",
        "\n",
        "##### The Product Rule\n",
        "Opposite of inference by enumeration: construct probability distribution given \n",
        "conditional probability.\n",
        "\n",
        "$P(y)P(x|y) = P(x,y)$\n",
        "\n",
        "##### The Chain Rule\n",
        "More generally, can write any joint distribution as an incremental product of \n",
        "conditional distributions.\n",
        "\n",
        "$P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$\n",
        "$P(x_1,x_2,...x_n) = \\\\underset{i}{\\\\Pi}~P(x_i|x_1...x_{i-1})$\n",
        "\n",
        "##### Bayes' Rule\n",
        "Two ways to factor a joint distribution over two variables:\n",
        "$P(x,y) = P(x|y)P(y) = P(y|x)P(x)$\n",
        "Dividing gives:\n",
        "$P(x|y) = \\\\frac{P(y|x)}{P(y)} P(x)$\n",
        "\n",
        "Reasons why it's helpful:\n",
        "- build one conditional from its reverse\n",
        "- one conditional may be difficult, the other simple\n",
        "- foundation of many systems, e.g. ASR, MT\n",
        "\n",
        "---\n",
        "Probabilistic Language Models\n",
        "\n",
        "##### Probabilistic Language Models\n",
        "One goal: assign probability to a sentence or sequence of words\n",
        "E.g. keyboard auto-complete, machine translation, spelling correction, speech recognition\n",
        "\n",
        "Related task: probability of upcoming word.\n",
        "\n",
        "Model that computes either is called a **language model (LM)**.\n",
        "\n",
        "Computing the probability of a given sentence (or probability of next word) can be\n",
        " accomplished through the chain rule.\n",
        "\n",
        "Joint probability of words in a sentence:\n",
        "$P(w_1,w_2,...w_n) = \\\\underset{i}{\\\\Pi}~P(w_i|w_1...w_{i-1})$\n",
        "\n",
        "Estimating these probabilities can be done by **maximum likelihood estimation (MLE)**:\n",
        " e.g. $P(\\\\text{won}|\\\\text{the underdog team}) = \\\\frac{\\\\text{count(the underdog team won)}}{\\\\text{count(the underdog team)}}$\n",
        "\n",
        "Problem is some sentences may never appear in a corpus. Needs huge datasets; inefficient.\n",
        " Many different ways of combining words.\n",
        "\n",
        "Simplifying assumption: **Markov assumption**. Only depends on previous $k$ words, \n",
        "not entire context. Therefore $P(w_1,w_2,...w_n) \\\\approx \\\\overset{n} {\\\\underset{i}{\\\\Pi}}~P(w_i|w_{i-k}...w_{i-1})$.\n",
        "Now can use MLE.\n",
        "\n",
        "History count:\n",
        "- unigram: no history\n",
        "- bigram: 1 word as history\n",
        "- trigram: 2 words\n",
        "- 4-gram: 3 words\n",
        "- n-gram: n-1 words\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1793a6a0-5ea5-4e79-ff8b-601333883ca9"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nReview on Probabilities\n\n##### Uncertainty\nProbabilistic reasoning provides a framework:\n- observed variables (evidence) - things agent knows about the world (e.g. sensor \nreadings, symptoms)\n- unobserved variables (states) - things agent needs to reason about (e.g. where \nan object is, disease present)\n- model - agent knows something about how known variables relate to unknown variables\n\nSimilar to logical assertions, probabilities are about possible worlds, but also \nquantify how likely a possible world is.\n\nPossible worlds = **sample space**; they are **mutually exclusive** and **exhaustive**.\n\nA probability model associates a probability $P(w)$ with each world $w$.\n\n##### Random Variables\nSome aspect of the world which may have uncertainty. Denoted by capital letters.\n\n##### Axioms of Probability\nProbability of any possible world is between $0$ and $1$:\n$0 \\leq P(w) \\leq 1$ for every $w$.\n\nTotal probability of the set of all possible worlds is $1$:\n$\\underset{w \\in \\Omega}{\\sum} P(w) = 1$\n\n---\nDistributions\n\n##### Probability Distributions\nUnobserved R.V.s have distributions; a table of probabilities of values.\nA probability is a single number, e.g. $P(w = \\text{rain}) = 0.1$.\nMust adhere to axioms: [[Review on Probabilities]]\n\n##### Joint Distributions\nJoint distributions over a set of R.V.s $X_1, ..., X_n$ specifies a real number \nfor each assignment or outcome.\nE.g. $P(X_1 = x_1, ..., X_n = x_n) = P(x_1, ..., x_n)$.\nHas an associated probability distribution, e.g. $P(T,W)$ equals some value.\nAgain, must adhere to axioms: [[Review on Probabilities]]\n\nSize of distribution for $n$ variables with domain size $d$: $d^n$.\nImpractical to write out!\n\n##### Probabilistic Models\nProbabilistic models are a joint distribution over a set of R.V.s.\n- random variables with *domains*\n- assignments called *outcomes*\n- joint distributions say whether assignments are likely\n- *normalised* (sum to $1$)\n- ideally: most variables independent\n\n##### Events\nAn event is a set $E$ of outcomes:\n$P(E) = \\underset{x_1...x_n \\in E}{\\sum} P(x_1...x_n)$\nCan calculate probability of any event, e.g. probability that it's hot and sunny,\n hot or sunny, just sunny...\n\n##### Marginal Distributions\nTypically only care about partial assignments, e.g. $P(T=hot)$.\nMarginal distributions are sub-tables which eliminate variables. Marginalization:\n combine collapsed rows by summing:\n$P(t) = \\underset{s}{\\sum} P(t,s)$.\n\n##### Conditional Probabilities\nSimple relation between joint and conditional probabilities:\n$P(a | b) = \\frac{P(a,b)}{P(b)}$\n\n##### Conditional Distributions\nProbability distributions over some variables given fixed values of others.\nCan calculate a set of conditional distribution tables from a joint distribution\n table.\n\n ---\nProbabilistic Inference and Rules\n\n##### Probabilistic Inference\nCompute a desired probability from other known probabilities, e.g. conditional from joint.\n\nUsually we compute conditional probabilities - represent agent's beliefs given the evidence.\nProbabilities change with new evidence - causes beliefs to be updated.\n\n##### Inference by Enumeration\nStructure:\n-  evidence variables: $E_1...E_k = e_1...e_k$\n-  query variable: $Q$\n-  hidden variables: $H_1...H_r$\nThese together form all variables $X_1, X_2,...,X_n$\n\nCalculate: $P(Q | e_1...e_k)$\n\nSteps:\n1. select entries consistent with evidence, $e_i$\n2. sum out $H$ to find joint of query and evidence, $P(Q,e_1...e_k)=\\underset{h_1...h_r}{\\sum} P(Q, h_1...h_r, e_1...e_k)$\n3. normalize, multiply by $\\frac{1}{Z}$ where $Z=\\underset{q}{\\sum} P(Q, e_1...e_k)$\n\n##### The Product Rule\nOpposite of inference by enumeration: construct probability distribution given \nconditional probability.\n\n$P(y)P(x|y) = P(x,y)$\n\n##### The Chain Rule\nMore generally, can write any joint distribution as an incremental product of \nconditional distributions.\n\n$P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$\n$P(x_1,x_2,...x_n) = \\underset{i}{\\Pi}~P(x_i|x_1...x_{i-1})$\n\n##### Bayes' Rule\nTwo ways to factor a joint distribution over two variables:\n$P(x,y) = P(x|y)P(y) = P(y|x)P(x)$\nDividing gives:\n$P(x|y) = \\frac{P(y|x)}{P(y)} P(x)$\n\nReasons why it's helpful:\n- build one conditional from its reverse\n- one conditional may be difficult, the other simple\n- foundation of many systems, e.g. ASR, MT\n\n---\nProbabilistic Language Models\n\n##### Probabilistic Language Models\nOne goal: assign probability to a sentence or sequence of words\nE.g. keyboard auto-complete, machine translation, spelling correction, speech recognition\n\nRelated task: probability of upcoming word.\n\nModel that computes either is called a **language model (LM)**.\n\nComputing the probability of a given sentence (or probability of next word) can be\n accomplished through the chain rule.\n\nJoint probability of words in a sentence:\n$P(w_1,w_2,...w_n) = \\underset{i}{\\Pi}~P(w_i|w_1...w_{i-1})$\n\nEstimating these probabilities can be done by **maximum likelihood estimation (MLE)**:\n e.g. $P(\\text{won}|\\text{the underdog team}) = \\frac{\\text{count(the underdog team won)}}{\\text{count(the underdog team)}}$\n\nProblem is some sentences may never appear in a corpus. Needs huge datasets; inefficient.\n Many different ways of combining words.\n\nSimplifying assumption: **Markov assumption**. Only depends on previous $k$ words, \nnot entire context. Therefore $P(w_1,w_2,...w_n) \\approx \\overset{n} {\\underset{i}{\\Pi}}~P(w_i|w_{i-k}...w_{i-1})$.\nNow can use MLE.\n\nHistory count:\n- unigram: no history\n- bigram: 1 word as history\n- trigram: 2 words\n- 4-gram: 3 words\n- n-gram: n-1 words\n\n\n## Module 10 Definitions\n* **Term** - your definition here\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "Review on Independence\n",
        "\n",
        "In Bayes' Nets, we're making independence assumptions based on interaction of variables\n",
        " in a model.\n",
        "\n",
        "Independence is given by:\n",
        "$\\\\forall x,y : P(x,y)=P(x)P(y)$, or $X \\\\perp Y$\n",
        "\n",
        "Conditional independence is given by:\n",
        "$\\\\forall x,y,z : P(x,y|z)=P(x|z)P(y|z)$, or $X \\\\perp Y|Z$\n",
        "Equivalently:\n",
        "$\\\\forall x,y,z : P(x|z,y)=P(x|z)$\n",
        "\n",
        "---\n",
        "Bayes Net Properties\n",
        "\n",
        "##### Bayes Nets Assumptions\n",
        "Assumptions we are required to make to define Bayes' nets when given a graph: $P(x_i|x_1...x_{i-1})\n",
        " = P(x_i|\\\\text{parents}(X_i))$\n",
        "There are often additional conditional independences that can be read off the graph.\n",
        "We must understand the assumptions made when choosing a graph.\n",
        "\n",
        "##### Casual Chain\n",
        "To prove conditional independence in a **casual chain**, we can substitute our Bayes\n",
        " assumption into the re-written full joint probability equation.\n",
        "Evidence along a chain blocks the influence, i.e. the immediate cause is \"stronger\"\n",
        " than earlier causes.\n",
        "\n",
        "##### Common Cause\n",
        "Similar to previous; must prove using substitution of assumption.\n",
        "Observing the cause blocks influence between effects. \n",
        "On the other hand, *not knowing* the cause can give an effect an indication of the\n",
        " likelihood of the other effects.\n",
        "\n",
        "##### Common Effect\n",
        "Causes are not correlated so are independent, but still must prove. Not independent\n",
        " given the common effect because it puts the causes in *competition* with one another as explanation.\n",
        "This is **backwards** from other two cases! Observing an effect activates influence\n",
        " between possible causes.\n",
        "\n",
        "---\n",
        "Reachability & Path\n",
        "\n",
        "A BN can be broken into repetitions of the three cases in [[Bayes Net Properties]]\n",
        " to check independence.\n",
        "\n",
        "We check if two variables are conditionally independent by their reachability \n",
        "and whether or not they are blocked by one of the three cases.\n",
        "\n",
        "\n",
        "##### Active vs. Inactive Paths\n",
        "A path if active if each triple is active:\n",
        "- Casual chain: $A \\\\rightarrow B \\\\rightarrow C$, where $B$ is *unobserved*\n",
        "- Common cause: $A \\\\leftarrow B \\\\rightarrow C$, where $B$ is *unobserved*\n",
        "- Common effect: $A \\\\rightarrow B \\\\leftarrow C$, where $B$ or one of its descendants\n",
        " is *observed*\n",
        "\n",
        "A single inactive segment can block a path.\n",
        "\n",
        "Active = dependence. Inactive = conditional independence.\n",
        "\n",
        "---\n",
        "D-Separation Algorithm\n",
        "\n",
        "If a path is active, there are no guarantees about independence. On the other hand,\n",
        " an inactive path between variables is conditionally independent.\n",
        "\n",
        "**If all paths are inactive then independence is guaranteed.**\n",
        "\n",
        "Refer to diagram.\n",
        "\n",
        "---\n",
        "Inference\n",
        "\n",
        "Inference: calculating some useful quantity from a joint probability distribution.\n",
        "\n",
        "Examples: posterior probability; most likely explanation.\n",
        "\n",
        "---\n",
        "Can perform inference by enumeration on a Bayes' net, similar to [[Probabilistic \n",
        "Inference and Rules]]. \n",
        "\n",
        "However, this is computationally expensive as the probabilities are exponential \n",
        "in the unobserved (hidden) variables; we need to join up the whole joint distribution\n",
        " before summing out hidden variables.\n",
        "\n",
        "Advanced technique to solve this is variable elimination: interleave joining and \n",
        "marginalization. Still NP-hard, but much faster.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5d073d78-faec-4f51-866f-ab5a060e3ce8"
      },
      "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": 35,
      "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 Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\nReview on Independence\n\nIn Bayes' Nets, we're making independence assumptions based on interaction of variables\n in a model.\n\nIndependence is given by:\n$\\forall x,y : P(x,y)=P(x)P(y)$, or $X \\perp Y$\n\nConditional independence is given by:\n$\\forall x,y,z : P(x,y|z)=P(x|z)P(y|z)$, or $X \\perp Y|Z$\nEquivalently:\n$\\forall x,y,z : P(x|z,y)=P(x|z)$\n\n---\nBayes Net Properties\n\n##### Bayes Nets Assumptions\nAssumptions we are required to make to define Bayes' nets when given a graph: $P(x_i|x_1...x_{i-1})\n = P(x_i|\\text{parents}(X_i))$\nThere are often additional conditional independences that can be read off the graph.\nWe must understand the assumptions made when choosing a graph.\n\n##### Casual Chain\nTo prove conditional independence in a **casual chain**, we can substitute our Bayes\n assumption into the re-written full joint probability equation.\nEvidence along a chain blocks the influence, i.e. the immediate cause is \"stronger\"\n than earlier causes.\n\n##### Common Cause\nSimilar to previous; must prove using substitution of assumption.\nObserving the cause blocks influence between effects. \nOn the other hand, *not knowing* the cause can give an effect an indication of the\n likelihood of the other effects.\n\n##### Common Effect\nCauses are not correlated so are independent, but still must prove. Not independent\n given the common effect because it puts the causes in *competition* with one another as explanation.\nThis is **backwards** from other two cases! Observing an effect activates influence\n between possible causes.\n\n---\nReachability & Path\n\nA BN can be broken into repetitions of the three cases in [[Bayes Net Properties]]\n to check independence.\n\nWe check if two variables are conditionally independent by their reachability \nand whether or not they are blocked by one of the three cases.\n\n\n##### Active vs. Inactive Paths\nA path if active if each triple is active:\n- Casual chain: $A \\rightarrow B \\rightarrow C$, where $B$ is *unobserved*\n- Common cause: $A \\leftarrow B \\rightarrow C$, where $B$ is *unobserved*\n- Common effect: $A \\rightarrow B \\leftarrow C$, where $B$ or one of its descendants\n is *observed*\n\nA single inactive segment can block a path.\n\nActive = dependence. Inactive = conditional independence.\n\n---\nD-Separation Algorithm\n\nIf a path is active, there are no guarantees about independence. On the other hand,\n an inactive path between variables is conditionally independent.\n\n**If all paths are inactive then independence is guaranteed.**\n\nRefer to diagram.\n\n---\nInference\n\nInference: calculating some useful quantity from a joint probability distribution.\n\nExamples: posterior probability; most likely explanation.\n\n---\nCan perform inference by enumeration on a Bayes' net, similar to [[Probabilistic \nInference and Rules]]. \n\nHowever, this is computationally expensive as the probabilities are exponential \nin the unobserved (hidden) variables; we need to join up the whole joint distribution\n before summing out hidden variables.\n\nAdvanced technique to solve this is variable elimination: interleave joining and \nmarginalization. Still NP-hard, but much faster.\n\n\n## Module 11 Definitions\n* **Concept** - definition\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "Classification Task\n",
        "\n",
        "##### Machine Learning\n",
        "How to acquire a model from data/experience:\n",
        "- learning parameters, e.g. probabilities\n",
        "- learning structures, e.g. Bayes nets\n",
        "- learning hidden concepts, e.g. clustering\n",
        "---\n",
        "Finite sets of classes are called classification. Real-numbered predictions are \n",
        "called regression.\n",
        "\n",
        "Problem: spam classification\n",
        "- input: email (labeled appropriately)\n",
        "- output: spam/not spam\n",
        "Want to learn a function that takes a new email and predicts a class. The email is \n",
        "transformed into a vector of which elements correspond to a feature.\n",
        "\n",
        "Problem: digit recognition\n",
        "- input: images/pixels grids (labeled appropriately)\n",
        "- output: a digit of 0-9\n",
        "Want to learn a function that predicts labels of new, future digit images.\n",
        "\n",
        "To summarise, classification: given inputs x, predict labels y\n",
        "\n",
        "Examples:\n",
        "- spam detection\n",
        "- OCR\n",
        "- medical diagnosis\n",
        "- essay grading\n",
        "- fraud detection\n",
        "- customer service email routing\n",
        "---\n",
        "##### Model-based Classification\n",
        "Model-based approach:\n",
        "- build a model (e.g. Bayes net) where both the label and features are random variables\n",
        "- instantiate observed features\n",
        "- query for the distribution of the label conditioned on the features \n",
        "\n",
        "Challenges:\n",
        "- structure of BN\n",
        "- learning parameters\n",
        "\n",
        "Can use a technique such as inference by enumeration or variable elimination to get\n",
        " information about query variable.\n",
        "\n",
        "---\n",
        "Naïve Bayes\n",
        "\n",
        "##### Naïve Bayes\n",
        "Assume all features are independent effects of the label.\n",
        "\n",
        "Model: $P(Y,F_{1}...F_{n}) = P(Y)~ \\\\underset{i}{\\\\Pi}~P(F_{i}|Y)$\n",
        "where $F_i$ is a feature representing the input.\n",
        "\n",
        "Full joint distribution would have $|Y| \\\\times |F|^n$ values ($n$ = number of \n",
        "features, $|F|$ = domain of feature), whereas the NB model only has $n \\\\times |F| \n",
        "\\\\times |Y|$ parameters.\n",
        "\n",
        "Advantages:\n",
        "- only need to specify how each feature depends on class\n",
        "- total number of parameters is *linear* in the number of features\n",
        "\n",
        "Disadvantages:\n",
        "- very simplistic (due to independence assumptions), but often works anyway!\n",
        "\n",
        "---\n",
        "##### Inference for NB\n",
        "Goal: compute posterior distribution over label variable Y: $P(Y|f_1...f_n)$\n",
        "\n",
        "Inference method.\n",
        "Steps:\n",
        "1. get joint probability of label and evidence for each label\n",
        "$P(Y,f_1...f_n) = [P(y_1,f_1...f_n),..., P(y_k,f_1...f_n)] \\\\rightarrow [P(y_1)~ \n",
        "\\\\underset{i}{\\\\Pi}~P(f_i|y_1),..., P(y_k)~ \\\\underset{i}{\\\\Pi}~P(f_i|y_k)]$\n",
        "2. sum out classes in step 1 to get probability of evidence\n",
        "$P(f_1...f_n)$\n",
        "3. normalize by dividing step 1 by step 2\n",
        "$P(Y|f_1...f_n)$\n",
        "\n",
        "---\n",
        "Estimates of local conditional probability tables:\n",
        "- $P(Y)$ - prior over labels\n",
        "- $P(F_i|Y)$ for each feature - evidence variable\n",
        "- Collectively called parameters, $\\\\theta$\n",
        "\n",
        "---\n",
        "Basic Concepts on ML\n",
        "\n",
        "Data: labeled instances, e.g. emails marked spam/ham\n",
        "- training set\n",
        "- held out set (also known as development set)\n",
        "- test set\n",
        "\n",
        "Features: attribute-value pairs which characterize each x\n",
        "\n",
        "Experimentation cycle:\n",
        "- learn parameters, e.g. model probabilities, on training set\n",
        "- (tune hyper-parameters on held-out set)\n",
        "- compute accuracy of test set\n",
        "- important: never peek at the test set!\n",
        "\n",
        "Evaluation:\n",
        "- accuracy: fraction of instances predicted correctly\n",
        "\n",
        "Overfitting and generalisation:\n",
        "- overfitting: fitting the training data very closely, but not generalising well\n",
        "- relative frequency parameters will overfit the training data\n",
        "- can't give unseen events $0$ probability\n",
        "- to generalise better: smooth or regularize estimates\n",
        "\n",
        "---\n",
        "##### Parameter Estimation\n",
        "Estimating the distribution of a random variable:\n",
        "- elicitation: ask a human expert\n",
        "- empirically: use training data\n",
        "\t- e.g. for each outcome x, look at the empirical rate of that value - maximum \n",
        "  likelihood estimation, $P_{\\\\text{ML}}(x) = \\\\frac{\\\\text{count}(x)}{\\\\text{total samples}}$\n",
        "\t\tAssignment of probabilities produces a $\\\\theta$.\n",
        "\t- this is the estimate that maximizes the likelihood of the data, $L(x,\\\\theta) = \\\\underset{i}{\\\\Pi} P_{\\\\theta}(x_i)$\n",
        "\n",
        "##### Maximum Likelihood\n",
        "Relative frequencies are the max likelihood estimates:\n",
        "$\\\\theta_{\\\\text{ML}} = \\\\underset{\\\\theta}{\\\\text{argmax}}P(X|\\\\theta) = \\\\underset{\\\\theta}{\\\\text{argmax}}~\\\\underset{i}{\\\\Pi}~P_\\\\theta(X_i)$ \n",
        "(where X is data)\n",
        "$\\\\rightarrow P_{\\\\text{ML}}(x) = \\\\frac{\\\\text{count}(x)}{\\\\text{total samples}}$\n",
        "\n",
        "Problem with this is unseen events.\n",
        "\n",
        "##### Laplace Smoothing\n",
        "Laplace's estimate: pretend you saw every outcome once more than you actually did\n",
        "$P_{\\\\text{LAP}}(x) = \\\\frac{c(x)+1}{\\\\sum_x[c(x)+1]} = \\\\frac{c(x)+1}{N+|X|}$\n",
        "\n",
        "Laplace's estimate (extended): pretend you saw every outcome $k$ more times than \n",
        "you actually did\n",
        "$P_{\\\\text{LAP}}(x) = \\\\frac{c(x)+k}{N+k|X|}$\n",
        "and for conditionals:\n",
        "$$P_{\\\\text{LAP}}(x|y) = \\\\frac{c(x,y)+k}{c(y)+k|X|}$$\n",
        "\n",
        "Set $k$ to tune hyper-parameter.\n",
        "\n",
        "##### Linear Interpolation\n",
        "Laplace performs poorly for $P(X|Y)$ when $|X|$ or $|Y|$ are very large.\n",
        "\n",
        "$$P_{\\\\text{LIN}}(x|y) = \\\\alpha \\\\widehat{P}(x|y) + (1-\\\\alpha)\\\\widehat{P}(x)$$\n",
        "$\\\\widehat{P}$ is the observed max likelihood estimator.\n",
        "\n",
        "Set $\\\\alpha$ to tune hyper-parameter.\n",
        "\n",
        "##### Tuning\n",
        "Need to set: \n",
        "- parameters: probabilities $P(X|Y), P(Y)$\n",
        "- hyper-parameters: the amount/type of smoothing, $\\\\alpha, k$\n",
        "\n",
        "Learn parameters from training data and for each value of the hyper-parameters, \n",
        "train and test on held-out data. Choose the best value and perform final test on test data.\n",
        "\n",
        "##### Features\n",
        "Add more features if there are are errors in model.\n",
        "\n",
        "##### Baselines\n",
        "First step: get a baseline - simple \"straw man\" procedures help determine how hard\n",
        " the task is and how good accuracy is.\n",
        "Weak baseline: most frequent label classifier - gives all test instances whatever\n",
        " label was most common in training set; accuracy might be high if problem is skewed.\n",
        "Real research uses previous work as baseline.\n",
        "\n",
        "---\n",
        "Perceptron\n",
        "\n",
        "![[perceptron.png]]\n",
        "\n",
        "Perceptrons for decision making: device that makes decisions by weighing up evidence.\n",
        "\n",
        "**Notational changes**\n",
        "1. $$\\\\sum_j~w_jx_j \\\\equiv \\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x}$$\n",
        "\n",
        "2. $b \\\\equiv -\\\\text{threshold}$, therefore\n",
        "$$\\\\text{output} = \n",
        "\\\\begin{cases}\n",
        "0~\\\\text{if}~\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b \\\\leq 0 \\\\\n",
        "1~\\\\text{if}~\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b > 0\n",
        "\\\\end{cases}$$\n",
        "where $b$ is the bias. \n",
        "\n",
        "Bias determines how easy it is for the perceptron to *fire*.\n",
        "\n",
        "---\n",
        "**Learning weights from examples**\n",
        "Inputs can be thought of as *features* representing something we want to classify.\n",
        " Feature values for inputs are fixed, but we can choose different weight vectors, \n",
        " which change the classifier.\n",
        "\n",
        "---\n",
        "##### Learning: Binary Perceptron\n",
        "- start with weights $0$\n",
        "For each training instance:\n",
        "- classify with current weights\n",
        "- if correct, i.e. $y=y*$, no change!\n",
        "- if wrong: adjust weight vector by adding or subtracting the feature vector. Subtract if $y* = -1$.\n",
        "- $\\\\boldsymbol{w} = \\\\boldsymbol{w} + \\\\boldsymbol{y^*} \\\\cdot \\\\boldsymbol{f}$\n",
        "\n",
        "---\n",
        "##### Multiclass Decision Rule\n",
        "If we have multiple classes:\n",
        "- a weight vector for each class: $w_y$\n",
        "- score (activation) of class $y$: $w_y \\\\cdot f(x)$\n",
        "- prediction highest score wins: $y = \\\\text{argmax}_y~w_y \\\\cdot f(x)$\n",
        "\n",
        "##### Learning: Multiclass Perceptron\n",
        "- start with weights $0$\n",
        "- pick up training examples one by one\n",
        "- predict with current weights: $y = \\\\text{argmax}_y~w_y \\\\cdot f(x)$\n",
        "- if correct, no change!\n",
        "- if wrong, lower score of wrong answer: $w_y = w_y - f(x)$\n",
        "and raise score of right answer: $w_{y*} = w_{y*} + f(x)$\n",
        "\n",
        "---\n",
        "Improvements on Perceptrons and SVM\n",
        "\n",
        "##### Properties of Perceptrons\n",
        "- separability: true if some parameters get the training set perfectly correct\n",
        "- convergence: if the training is separable, perceptron will eventually converge (binary case)\n",
        "- mistake bound: the maximum number of mistakes (binary case) related to the *margin*\n",
        " or degree of separability $\\\\delta$: $\\\\text{mistakes} < \\\\frac{k}{\\\\delta^2}$\n",
        "\n",
        "##### Problems with Perceptrons\n",
        "- noise: if the data isn't separable, weights might thrash. Averaging weights over\n",
        " time can help (average perceptron)\n",
        "- mediocre generalization: finds a barely separating solution\n",
        "- overtraining (a type of overfitting): test/held-out accuracy usually rises, then\n",
        " falls - early-stopping can help\n",
        "\n",
        "##### Fixing Perceptrons\n",
        "Idea: adjust weight update to mitigate these effects\n",
        "MIRA = Margin Infused Relaxed Algorithm\n",
        "E.g. guessed $y$ instead of $y^*$ on example $x$ with features $f(x)$:\n",
        "$w_y = w'_y - \\\\tau f(x), w_{y^*} = w'_{y^*} + \\\\tau f(x)$\n",
        "Choose an update size that fixes current mistake, but minimises the change to $w$:\n",
        "$$\\\\tau = \\\\frac{(w'_y - w_{y^*} \\\\cdot f + 1)}{2f \\\\cdot f}$$\n",
        "\n",
        "In practice, it's bad to make updates that are too large: example may be labeled\n",
        " incorrectly, may not have enough features.\n",
        "Solution: cap the max possible value of $\\\\tau$ with some constant $c$:\n",
        "$$\\\\tau^* = \\\\min \\\\left( \\\\frac{(w'_y - w_{y^*} \\\\cdot f + 1)}{2f \\\\cdot f}, c \\\\right)$$\n",
        "Corresponds to an optimization that assumes non-separable data, usually converges\n",
        " faster, and better on noisy data.\n",
        "\n",
        "---\n",
        "##### Support Vector Machines\n",
        "Max. the margin: good according to intuition, theory, practice.\n",
        "Only support vectors matter; other training examples are ignorable.\n",
        "*Support vector machines (SVMs)* find the separator with max margin.\n",
        "SVMs are MIRA where you optimise over all examples at once.\n",
        "\n",
        "---\n",
        "##### Non-Linear Separators\n",
        "General idea: original (linearly non-separable) feature space can always be mapped\n",
        " to some higher-dimensional feature space where the training set is separable:\n",
        "$\\\\Phi: x \\\\rightarrow \\\\phi(x)$\n",
        "(known as kernel trick)\n",
        "\n",
        "---\n",
        "##### Summary\n",
        "Naïve Bayes:\n",
        "- builds a model of training data\n",
        "- gives prediction probabilities\n",
        "- strong assumptions about feature independence\n",
        "- one pass through data (counting and smoothing)\n",
        "\n",
        "Perceptrons / MIRA:\n",
        "- makes less assumptions about data\n",
        "- mistake-driven learning\n",
        "- multiple passes through data (prediction)\n",
        "- often more accurate\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 36,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c5d56674-a40f-4911-df0e-ea16b43d59b3"
      },
      "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": 37,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\nClassification Task\n\n##### Machine Learning\nHow to acquire a model from data/experience:\n- learning parameters, e.g. probabilities\n- learning structures, e.g. Bayes nets\n- learning hidden concepts, e.g. clustering\n---\nFinite sets of classes are called classification. Real-numbered predictions are \ncalled regression.\n\nProblem: spam classification\n- input: email (labeled appropriately)\n- output: spam/not spam\nWant to learn a function that takes a new email and predicts a class. The email is \ntransformed into a vector of which elements correspond to a feature.\n\nProblem: digit recognition\n- input: images/pixels grids (labeled appropriately)\n- output: a digit of 0-9\nWant to learn a function that predicts labels of new, future digit images.\n\nTo summarise, classification: given inputs x, predict labels y\n\nExamples:\n- spam detection\n- OCR\n- medical diagnosis\n- essay grading\n- fraud detection\n- customer service email routing\n---\n##### Model-based Classification\nModel-based approach:\n- build a model (e.g. Bayes net) where both the label and features are random variables\n- instantiate observed features\n- query for the distribution of the label conditioned on the features \n\nChallenges:\n- structure of BN\n- learning parameters\n\nCan use a technique such as inference by enumeration or variable elimination to get\n information about query variable.\n\n---\nNaïve Bayes\n\n##### Naïve Bayes\nAssume all features are independent effects of the label.\n\nModel: $P(Y,F_{1}...F_{n}) = P(Y)~ \\underset{i}{\\Pi}~P(F_{i}|Y)$\nwhere $F_i$ is a feature representing the input.\n\nFull joint distribution would have $|Y| \\times |F|^n$ values ($n$ = number of \nfeatures, $|F|$ = domain of feature), whereas the NB model only has $n \\times |F| \n\\times |Y|$ parameters.\n\nAdvantages:\n- only need to specify how each feature depends on class\n- total number of parameters is *linear* in the number of features\n\nDisadvantages:\n- very simplistic (due to independence assumptions), but often works anyway!\n\n---\n##### Inference for NB\nGoal: compute posterior distribution over label variable Y: $P(Y|f_1...f_n)$\n\nInference method.\nSteps:\n1. get joint probability of label and evidence for each label\n$P(Y,f_1...f_n) = [P(y_1,f_1...f_n),..., P(y_k,f_1...f_n)] \\rightarrow [P(y_1)~ \n\\underset{i}{\\Pi}~P(f_i|y_1),..., P(y_k)~ \\underset{i}{\\Pi}~P(f_i|y_k)]$\n2. sum out classes in step 1 to get probability of evidence\n$P(f_1...f_n)$\n3. normalize by dividing step 1 by step 2\n$P(Y|f_1...f_n)$\n\n---\nEstimates of local conditional probability tables:\n- $P(Y)$ - prior over labels\n- $P(F_i|Y)$ for each feature - evidence variable\n- Collectively called parameters, $\\theta$\n\n---\nBasic Concepts on ML\n\nData: labeled instances, e.g. emails marked spam/ham\n- training set\n- held out set (also known as development set)\n- test set\n\nFeatures: attribute-value pairs which characterize each x\n\nExperimentation cycle:\n- learn parameters, e.g. model probabilities, on training set\n- (tune hyper-parameters on held-out set)\n- compute accuracy of test set\n- important: never peek at the test set!\n\nEvaluation:\n- accuracy: fraction of instances predicted correctly\n\nOverfitting and generalisation:\n- overfitting: fitting the training data very closely, but not generalising well\n- relative frequency parameters will overfit the training data\n- can't give unseen events $0$ probability\n- to generalise better: smooth or regularize estimates\n\n---\n##### Parameter Estimation\nEstimating the distribution of a random variable:\n- elicitation: ask a human expert\n- empirically: use training data\n\t- e.g. for each outcome x, look at the empirical rate of that value - maximum \n  likelihood estimation, $P_{\\text{ML}}(x) = \\frac{\\text{count}(x)}{\\text{total samples}}$\n\t\tAssignment of probabilities produces a $\\theta$.\n\t- this is the estimate that maximizes the likelihood of the data, $L(x,\\theta) = \\underset{i}{\\Pi} P_{\\theta}(x_i)$\n\n##### Maximum Likelihood\nRelative frequencies are the max likelihood estimates:\n$\\theta_{\\text{ML}} = \\underset{\\theta}{\\text{argmax}}P(X|\\theta) = \\underset{\\theta}{\\text{argmax}}~\\underset{i}{\\Pi}~P_\\theta(X_i)$ \n(where X is data)\n$\\rightarrow P_{\\text{ML}}(x) = \\frac{\\text{count}(x)}{\\text{total samples}}$\n\nProblem with this is unseen events.\n\n##### Laplace Smoothing\nLaplace's estimate: pretend you saw every outcome once more than you actually did\n$P_{\\text{LAP}}(x) = \\frac{c(x)+1}{\\sum_x[c(x)+1]} = \\frac{c(x)+1}{N+|X|}$\n\nLaplace's estimate (extended): pretend you saw every outcome $k$ more times than \nyou actually did\n$P_{\\text{LAP}}(x) = \\frac{c(x)+k}{N+k|X|}$\nand for conditionals:\n$$P_{\\text{LAP}}(x|y) = \\frac{c(x,y)+k}{c(y)+k|X|}$$\n\nSet $k$ to tune hyper-parameter.\n\n##### Linear Interpolation\nLaplace performs poorly for $P(X|Y)$ when $|X|$ or $|Y|$ are very large.\n\n$$P_{\\text{LIN}}(x|y) = \\alpha \\widehat{P}(x|y) + (1-\\alpha)\\widehat{P}(x)$$\n$\\widehat{P}$ is the observed max likelihood estimator.\n\nSet $\\alpha$ to tune hyper-parameter.\n\n##### Tuning\nNeed to set: \n- parameters: probabilities $P(X|Y), P(Y)$\n- hyper-parameters: the amount/type of smoothing, $\\alpha, k$\n\nLearn parameters from training data and for each value of the hyper-parameters, \ntrain and test on held-out data. Choose the best value and perform final test on test data.\n\n##### Features\nAdd more features if there are are errors in model.\n\n##### Baselines\nFirst step: get a baseline - simple \"straw man\" procedures help determine how hard\n the task is and how good accuracy is.\nWeak baseline: most frequent label classifier - gives all test instances whatever\n label was most common in training set; accuracy might be high if problem is skewed.\nReal research uses previous work as baseline.\n\n---\nPerceptron\n\n![[perceptron.png]]\n\nPerceptrons for decision making: device that makes decisions by weighing up evidence.\n\n**Notational changes**\n1. $$\\sum_j~w_jx_j \\equiv \\boldsymbol{w} \\cdot \\boldsymbol{x}$$\n\n2. $b \\equiv -\\text{threshold}$, therefore\n$$\\text{output} = \n\\begin{cases}\n0~\\text{if}~\\boldsymbol{w} \\cdot \\boldsymbol{x} + b \\leq 0 \\\n1~\\text{if}~\\boldsymbol{w} \\cdot \\boldsymbol{x} + b > 0\n\\end{cases}$$\nwhere $b$ is the bias. \n\nBias determines how easy it is for the perceptron to *fire*.\n\n---\n**Learning weights from examples**\nInputs can be thought of as *features* representing something we want to classify.\n Feature values for inputs are fixed, but we can choose different weight vectors, \n which change the classifier.\n\n---\n##### Learning: Binary Perceptron\n- start with weights $0$\nFor each training instance:\n- classify with current weights\n- if correct, i.e. $y=y*$, no change!\n- if wrong: adjust weight vector by adding or subtracting the feature vector. Subtract if $y* = -1$.\n- $\\boldsymbol{w} = \\boldsymbol{w} + \\boldsymbol{y^*} \\cdot \\boldsymbol{f}$\n\n---\n##### Multiclass Decision Rule\nIf we have multiple classes:\n- a weight vector for each class: $w_y$\n- score (activation) of class $y$: $w_y \\cdot f(x)$\n- prediction highest score wins: $y = \\text{argmax}_y~w_y \\cdot f(x)$\n\n##### Learning: Multiclass Perceptron\n- start with weights $0$\n- pick up training examples one by one\n- predict with current weights: $y = \\text{argmax}_y~w_y \\cdot f(x)$\n- if correct, no change!\n- if wrong, lower score of wrong answer: $w_y = w_y - f(x)$\nand raise score of right answer: $w_{y*} = w_{y*} + f(x)$\n\n---\nImprovements on Perceptrons and SVM\n\n##### Properties of Perceptrons\n- separability: true if some parameters get the training set perfectly correct\n- convergence: if the training is separable, perceptron will eventually converge (binary case)\n- mistake bound: the maximum number of mistakes (binary case) related to the *margin*\n or degree of separability $\\delta$: $\\text{mistakes} < \\frac{k}{\\delta^2}$\n\n##### Problems with Perceptrons\n- noise: if the data isn't separable, weights might thrash. Averaging weights over\n time can help (average perceptron)\n- mediocre generalization: finds a barely separating solution\n- overtraining (a type of overfitting): test/held-out accuracy usually rises, then\n falls - early-stopping can help\n\n##### Fixing Perceptrons\nIdea: adjust weight update to mitigate these effects\nMIRA = Margin Infused Relaxed Algorithm\nE.g. guessed $y$ instead of $y^*$ on example $x$ with features $f(x)$:\n$w_y = w'_y - \\tau f(x), w_{y^*} = w'_{y^*} + \\tau f(x)$\nChoose an update size that fixes current mistake, but minimises the change to $w$:\n$$\\tau = \\frac{(w'_y - w_{y^*} \\cdot f + 1)}{2f \\cdot f}$$\n\nIn practice, it's bad to make updates that are too large: example may be labeled\n incorrectly, may not have enough features.\nSolution: cap the max possible value of $\\tau$ with some constant $c$:\n$$\\tau^* = \\min \\left( \\frac{(w'_y - w_{y^*} \\cdot f + 1)}{2f \\cdot f}, c \\right)$$\nCorresponds to an optimization that assumes non-separable data, usually converges\n faster, and better on noisy data.\n\n---\n##### Support Vector Machines\nMax. the margin: good according to intuition, theory, practice.\nOnly support vectors matter; other training examples are ignorable.\n*Support vector machines (SVMs)* find the separator with max margin.\nSVMs are MIRA where you optimise over all examples at once.\n\n---\n##### Non-Linear Separators\nGeneral idea: original (linearly non-separable) feature space can always be mapped\n to some higher-dimensional feature space where the training set is separable:\n$\\Phi: x \\rightarrow \\phi(x)$\n(known as kernel trick)\n\n---\n##### Summary\nNaïve Bayes:\n- builds a model of training data\n- gives prediction probabilities\n- strong assumptions about feature independence\n- one pass through data (counting and smoothing)\n\nPerceptrons / MIRA:\n- makes less assumptions about data\n- mistake-driven learning\n- multiple passes through data (prediction)\n- often more accurate\n\n\n## Module 12 Definitions\n* **Concept** - definition\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 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "Logistic Regression\n",
        "\n",
        "**Logistic regression** is another type of classifier (supervised ML).\n",
        "\n",
        "##### Classifier Components\n",
        "Classifiers require a training corpus of $M$ observations of input/output pairs \n",
        "$(x^{(i)}, y^{(i)})$.\n",
        "1. **Feature representation** of the input - for each input observation $x^{(i)}$\n",
        " there is a vector of features $[x_1,x_2,...,x_n]$.\n",
        "2. **Classification function** - computes estimated class $\\\\hat{y}$ via $p(y|x)$.\n",
        "3. **Objective function** for learning - involves minimizing error on training examples.\n",
        "4. **Optimization** algorithm - optimize the objective function.\n",
        "\n",
        "##### Sentiment Classifier\n",
        "For sentiment classification, consider a feature representation of an input. The\n",
        " classifier output can be $1$ (positive) or $0$ (negative). Want to estimate $P(Y=1|x)$.\n",
        "Logistic regression gives:\n",
        "$$z= \\\\sum_i w_i x_i + b$$\n",
        "which can also be written as:\n",
        "$$z = \\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b$$\n",
        "where $b$ is bias.\n",
        "\n",
        "##### Sigmoid (logit) function \n",
        "$y=\\\\frac{1}{1+e^{-z}}$ is used to produce $z$ output between $0$ and $1$. Hence\n",
        "$$P(Y=1)=\\\\sigma (\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b)= \\\\frac{1}{1+e^{(\\\\boldsymbol{w}\n",
        " \\\\cdot \\\\boldsymbol{x} + b)}}$$\n",
        "Therefore in binary output, $P(Y=0) = 1 - \\\\sigma (\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b)$.\n",
        "\n",
        "##### Decision boundary\n",
        "$$\\\\hat{y} = \n",
        "\\\\begin{cases} \n",
        "1~\\\\text{if}~P(Y=1|x) > 0.5 \\\\\n",
        "0~\\\\text{otherwise}\n",
        "\\\\end{cases}$$\n",
        "\n",
        "##### Extracting features\n",
        "Feature engineering: select features that represent examples. E.g. count positive/negative\n",
        " lexicons, pronouns, binary features (!, \"no\"), word count.\n",
        "\n",
        "Once feature values have been calculated, assign weight to importance of each.\n",
        "\n",
        "Finally, calculate $z$ and apply $\\\\sigma$.\n",
        "\n",
        "##### Learning in logistic regression\n",
        "Require two components to learn weights and bias (parameters) of model:\n",
        "1. Objective / **loss function** that gives *distance* between system output and\n",
        " gold (human) output; will use **cross-entropy loss**.\n",
        "2. Algorithm for optimizing (minimizing) objective/loss function; will use \n",
        "**stochastic gradient descent**.\n",
        "\n",
        "---\n",
        "Loss Function\n",
        "\n",
        "##### Loss functions\n",
        "Determine how close the classifier output $\\\\hat{y}$ for an observation $x$ is to \n",
        "the correct output $y$.\n",
        "$$L(\\\\hat{y}, y) = \\\\text{how much}~\\\\hat{y}~\\\\text{differs from true}~y$$\n",
        "Example is mean squared error (not great for probabilistic classification as it \n",
        "is non-convex):\n",
        "$$L_{MSE}(\\\\hat{y}, y) = \\\\frac{1}{2} (\\\\hat{y}-y)^2$$\n",
        "\n",
        "Better loss function for probabilistic classification:\n",
        "- prefers the correct (gold) class labels of the training example to be more likely.\n",
        "- conditional max likelihood estimation: choose parameters $w,b$ that max the (log)\n",
        " probabilities of the true (gold) labels in training data.\n",
        "- resulting loss function is the negative log likelihood loss, known as **cross entropy\n",
        " loss**.\n",
        "---\n",
        "For observation $x$, want to max the probability of the correct label $p(y|x)$:\n",
        "$$p(y|x)= \\\\hat{y}^y(1-\\\\hat{y})^{1-y}$$\n",
        "If $y=1$ then $p(y|x) = \\\\hat{y}$ <- as high as possible .\n",
        "If $y=0$ then $p(y|x)= 1-\\\\hat{y}$ <- $\\\\hat{y}$ as low as possible.\n",
        "\n",
        "Then change to logs:\n",
        "$$\\\\log p(y|x)= \\\\log [\\\\hat{y}^y(1-\\\\hat{y})^{1-y}] = y \\\\log \\\\hat{y} + (1-y) \\\\log (1 - \\\\hat{y})$$\n",
        "This maximizes the probability, but for loss functions we want to minimize so we \n",
        "change the sign.\n",
        "\n",
        "Hence the resulting cross-entropy loss:\n",
        "$$L_{CE}(\\\\hat{y}, y) = - \\\\log p(y|x)= - [y \\\\log \\\\hat{y} + (1-y) \\\\log (1 - \\\\hat{y})]$$\n",
        "Finally, plug in the definition for $\\\\hat{y}$:\n",
        "$$L_{CE}(\\\\hat{y}, y) = - [y \\\\log \\\\sigma(\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b) + \n",
        "(1-y) \\\\log (1 - \\\\sigma(\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b))]$$\n",
        "\n",
        "If prediction is **correct**, then CE loss is **lower**.\n",
        "If prediction is **incorrect**, then CE loss is **higher**.\n",
        "\n",
        "##### Loss on all training examples\n",
        "$$\\\\log p(\\\\text{training labels}) = \\\\log \\\\Pi_{i=1}^{m} p (y^{(i)}|x^{(i)}) \\\\ \n",
        "= \\\\sum_{i=1}^{m} \\\\log p (y^{(i)}|x^{(i)}) \\\\\n",
        "= - \\\\sum_{i=1}^{m} L_{CE} (\\\\hat{y}^{(i)}|y^{(i)})$$\n",
        "\n",
        "---\n",
        "Stochastic Gradient Descent\n",
        "\n",
        "We use gradient descent to find good settings for our weights and bias by min the \n",
        "loss function:\n",
        "$$\\\\hat{\\\\theta} = \\\\underset{\\\\theta}{\\\\text{argmin}}~\\\\frac{1}{m} \\\\sum_{i=1}^{m}~L_{CE}(y^{(i)}, x^{(i)}; \\\\theta)$$\n",
        "\n",
        "**Gradient descent** is a method that finds a min of a function by figuring out in \n",
        "which direction (in the space of parameters $\\\\theta$) the function's slope is rising the\n",
        " most steeply and moving in the opposite direction.\n",
        "\n",
        "For logistic regression, this loss function is **convex** such that it only has one\n",
        " minimum so there is no local minima to get stuck in. Hence it is guaranteed to the\n",
        "  find the minimum.\n",
        "\n",
        "The magnitude of the amount to move is the value of the slope weighted by a learning\n",
        " rate $\\\\eta$.\n",
        "A higher/faster learning rate means we should move $w$ more on each step.\n",
        "$$w^{t+1} = w^t - \\\\eta \\\\frac{d}{dw} f(x;w)$$\n",
        "---\n",
        "##### The Gradient\n",
        "To update $\\\\theta$, we need a definition for the gradient $\\\\nabla L(f(x, \\\\theta), y)$.\n",
        "For logistic regression, the cross entropy [[Loss Function]] is\n",
        "$$L_{CE}(\\\\hat{y},y) = - [y \\\\log \\\\sigma(\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b) + \n",
        "(1-y) \\\\log (1 - \\\\sigma(\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b))]$$\n",
        "\n",
        "The derivative of this function for one observation vector $x$ for a single weight $w_j$ is\n",
        "$$\\\\frac{\\\\delta L_{CE}(w,b)}{\\\\delta w_j} = [\\\\sigma(\\\\boldsymbol{w} \\\\cdot \\\\boldsymbol{x} + b) - y]x_j$$\n",
        "I.e. the difference between the true $y$ and our estimate for $x$ multiplied by the\n",
        " corresponding input $x_j$.\n",
        "\n",
        "Average loss:\n",
        "$$\\\\text{cost}(w,b) = \\\\frac{1}{m} \\\\sum_{i=1}^{m} L_{CE}(\\\\hat{y}^{(i)}, y^{i})$$\n",
        "$$= - \\\\frac{1}{m} \\\\sum_{i=1}^{m} y^{(i)} \\\\log \\\\sigma(w \\\\cdot x^{(i)} + b) + (1-y^{(i)})\n",
        " \\\\log (1-\\\\sigma(w \\\\cdot x^{(i)} + b))$$\n",
        "This is what we want to minimize.\n",
        "\n",
        "The loss for a batch of data or an entire data set is just the average loss over \n",
        "the $m$ examples.\n",
        "\n",
        "The gradient for multiple data points is the sum of the individual gradients:\n",
        "$$\\\\frac{\\\\delta \\\\text{cost}(w,b)}{\\\\delta w_j} = \\\\sum_{i=1}^{m} [\\\\sigma(\\\\boldsymbol{w}\n",
        " \\\\cdot x^{(i)} + b) - y^{(i)}]x_j^{(i)}$$\n",
        "\n",
        "Example\n",
        "1. ![[Pasted image 20211127154605.png]]\n",
        "2. ![[Pasted image 20211127154637.png]]\n",
        "3. ![[Pasted image 20211127154709.png]]\n",
        "\n",
        "---\n",
        "##### Mini-batch training\n",
        "**Stochastic** gradient descent chooses a **single random example** at a time and\n",
        " updates its weights on that example, therefore updates can fluctuate.\n",
        "Instead, **batch training** computes the gradient over the entire dataset which gives\n",
        " a much better estimate of which direction to move the weights, but it takes a long\n",
        "  time to compute.\n",
        "A compromise is **mini-batch training** where we train a small batch whose size is\n",
        " determined by computational resources. All examples in the batch can be processed\n",
        "  in parallel and the loss accumulated.\n",
        "\n",
        "---\n",
        "##### Regularization\n",
        "**Overfitting** is a problem in logistic regression: if a feature only occurs in\n",
        " one class it will get a high weight.\n",
        "Regularization penalises large weights by adding a term to the loss function:\n",
        "- Lasso regression uses L1 regularization\n",
        "- Ridge regression uses L2 regularization\n",
        "\n",
        "---\n",
        "##### Multinomial logistic regression\n",
        "Often want more than two (binary) classes and want to known probability $y$ for \n",
        "each class $c \\\\in C, p(y=c|x)$.\n",
        "To get proper probability, we use a generalization of the sigmoid function called\n",
        " the **softmax function**:\n",
        "$$\\\\text{softmax}(z_i) = \\\\frac{e^{z_i}}{\\\\sum_{j=1}^{k}e^{z_j}}, 1 \\\\leq i \\\\leq k$$\n",
        "\n",
        "Softmax takes in an input vector $z=[z_1,z_2,...,z_k]$ and outputs a vector of values\n",
        " normalized into probabilities.\n",
        "\n",
        "---\n",
        "Neural Networks\n",
        "\n",
        "##### Sigmoid neurons\n",
        "Problem: a small change in weights or bias of any single perceptron in the network\n",
        " can cause the output to completely flip from $0$ to $1$.\n",
        "Solution: sigmoid neuron.\n",
        "\n",
        "Smoothness of $\\\\sigma$ means small changes on the weights $w_j$ and bias $b$ will\n",
        " produce a small change in the output of the neuron.\n",
        "\n",
        "##### Activation functions\n",
        "There are three commonly used non-linear functions used for the activation function $f$:\n",
        "- sigmoid function\n",
        "- tanh function\n",
        "- rectified linear unit (ReLU)\n",
        "\n",
        "##### Feed-forward Neural Network\n",
        "Simplest kind of NN. **Multilayer** network where all units are usually **fully-connected**\n",
        " and no cycles.\n",
        "The outputs from each layer are passed to units in the next higher layer. No outputs\n",
        " are passed back to lower layers.\n",
        "\n",
        "---\n",
        "##### Training NN\n",
        "Want to learn best parameters for the NN to make its predictions $\\\\hat{y}$ as close\n",
        " as possible to the gold standard labels in the training data $y$. Require:\n",
        "- loss function: cross-entropy loss\n",
        "- optimization algorithm: gradient descent\n",
        "- a way to compute the gradient of the loss function: error propagation\n",
        "\n",
        "##### Cross-entropy loss\n",
        "If the NN is a binary classifier with a sigmoid function at the final layer, the \n",
        "[[Loss Function]] is exactly the same as logistic regression.\n",
        "\n",
        "For multinomial regression:\n",
        "$$L_{CE}(\\\\hat{y}, y) = - \\\\sum_{i=1}^{C} y_i \\\\log \\\\hat{y}_i$$\n",
        "\n",
        "If there is only one correct answer, where the truth is $y_i=1$ then this simplifies to\n",
        "$$L_{CE}(\\\\hat{y}, y) = - \\\\log \\\\hat{y}_i$$\n",
        "\n",
        "Plugging into softmax:\n",
        "$$L_{CE}(\\\\hat{y}, y) = - \\\\log \\\\frac{e^{z_i}}{\\\\sum_{j=1}^{k}e^{z_j}}$$\n",
        "\n",
        "##### Computing the gradient\n",
        "Logistic regression can be through of as a network with just one weight layer and\n",
        " a sigmoid output. See [[Stochastic Gradient Descent]].\n",
        "\n",
        "But these derivatives only give the correct updates for the last weight layer. For\n",
        " deeper networks, we need to look back through all earlier layers, even though loss\n",
        "  is only computed with respect to the output. Solution: error backpropagation algorithm.\n",
        "\n",
        "##### Computation graphs\n",
        "Related to general **backward differentiation** procedure which depends on **computation graphs**\n",
        " - represents process of computing a mathematical expression and broken down into separate operations.\n",
        "  Each operation is a node in a graph - use **forward pass** to calculate.\n",
        "\n",
        "##### Backward differentiation\n",
        "**Backward pass** used to compute the derivatives needed for the weight update. Computing\n",
        " the derivative of the output function with respect to the inputs via the chain rule (from calculus).\n",
        "\n",
        "*Calculate partial derivative at each node and pass back.*\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 38,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "07e3ac93-62ec-4561-9f91-6e76d2b29de2"
      },
      "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": 39,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\nLogistic Regression\n\n**Logistic regression** is another type of classifier (supervised ML).\n\n##### Classifier Components\nClassifiers require a training corpus of $M$ observations of input/output pairs \n$(x^{(i)}, y^{(i)})$.\n1. **Feature representation** of the input - for each input observation $x^{(i)}$\n there is a vector of features $[x_1,x_2,...,x_n]$.\n2. **Classification function** - computes estimated class $\\hat{y}$ via $p(y|x)$.\n3. **Objective function** for learning - involves minimizing error on training examples.\n4. **Optimization** algorithm - optimize the objective function.\n\n##### Sentiment Classifier\nFor sentiment classification, consider a feature representation of an input. The\n classifier output can be $1$ (positive) or $0$ (negative). Want to estimate $P(Y=1|x)$.\nLogistic regression gives:\n$$z= \\sum_i w_i x_i + b$$\nwhich can also be written as:\n$$z = \\boldsymbol{w} \\cdot \\boldsymbol{x} + b$$\nwhere $b$ is bias.\n\n##### Sigmoid (logit) function \n$y=\\frac{1}{1+e^{-z}}$ is used to produce $z$ output between $0$ and $1$. Hence\n$$P(Y=1)=\\sigma (\\boldsymbol{w} \\cdot \\boldsymbol{x} + b)= \\frac{1}{1+e^{(\\boldsymbol{w}\n \\cdot \\boldsymbol{x} + b)}}$$\nTherefore in binary output, $P(Y=0) = 1 - \\sigma (\\boldsymbol{w} \\cdot \\boldsymbol{x} + b)$.\n\n##### Decision boundary\n$$\\hat{y} = \n\\begin{cases} \n1~\\text{if}~P(Y=1|x) > 0.5 \\\n0~\\text{otherwise}\n\\end{cases}$$\n\n##### Extracting features\nFeature engineering: select features that represent examples. E.g. count positive/negative\n lexicons, pronouns, binary features (!, \"no\"), word count.\n\nOnce feature values have been calculated, assign weight to importance of each.\n\nFinally, calculate $z$ and apply $\\sigma$.\n\n##### Learning in logistic regression\nRequire two components to learn weights and bias (parameters) of model:\n1. Objective / **loss function** that gives *distance* between system output and\n gold (human) output; will use **cross-entropy loss**.\n2. Algorithm for optimizing (minimizing) objective/loss function; will use \n**stochastic gradient descent**.\n\n---\nLoss Function\n\n##### Loss functions\nDetermine how close the classifier output $\\hat{y}$ for an observation $x$ is to \nthe correct output $y$.\n$$L(\\hat{y}, y) = \\text{how much}~\\hat{y}~\\text{differs from true}~y$$\nExample is mean squared error (not great for probabilistic classification as it \nis non-convex):\n$$L_{MSE}(\\hat{y}, y) = \\frac{1}{2} (\\hat{y}-y)^2$$\n\nBetter loss function for probabilistic classification:\n- prefers the correct (gold) class labels of the training example to be more likely.\n- conditional max likelihood estimation: choose parameters $w,b$ that max the (log)\n probabilities of the true (gold) labels in training data.\n- resulting loss function is the negative log likelihood loss, known as **cross entropy\n loss**.\n---\nFor observation $x$, want to max the probability of the correct label $p(y|x)$:\n$$p(y|x)= \\hat{y}^y(1-\\hat{y})^{1-y}$$\nIf $y=1$ then $p(y|x) = \\hat{y}$ <- as high as possible .\nIf $y=0$ then $p(y|x)= 1-\\hat{y}$ <- $\\hat{y}$ as low as possible.\n\nThen change to logs:\n$$\\log p(y|x)= \\log [\\hat{y}^y(1-\\hat{y})^{1-y}] = y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})$$\nThis maximizes the probability, but for loss functions we want to minimize so we \nchange the sign.\n\nHence the resulting cross-entropy loss:\n$$L_{CE}(\\hat{y}, y) = - \\log p(y|x)= - [y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})]$$\nFinally, plug in the definition for $\\hat{y}$:\n$$L_{CE}(\\hat{y}, y) = - [y \\log \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b) + \n(1-y) \\log (1 - \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b))]$$\n\nIf prediction is **correct**, then CE loss is **lower**.\nIf prediction is **incorrect**, then CE loss is **higher**.\n\n##### Loss on all training examples\n$$\\log p(\\text{training labels}) = \\log \\Pi_{i=1}^{m} p (y^{(i)}|x^{(i)}) \\ \n= \\sum_{i=1}^{m} \\log p (y^{(i)}|x^{(i)}) \\\n= - \\sum_{i=1}^{m} L_{CE} (\\hat{y}^{(i)}|y^{(i)})$$\n\n---\nStochastic Gradient Descent\n\nWe use gradient descent to find good settings for our weights and bias by min the \nloss function:\n$$\\hat{\\theta} = \\underset{\\theta}{\\text{argmin}}~\\frac{1}{m} \\sum_{i=1}^{m}~L_{CE}(y^{(i)}, x^{(i)}; \\theta)$$\n\n**Gradient descent** is a method that finds a min of a function by figuring out in \nwhich direction (in the space of parameters $\\theta$) the function's slope is rising the\n most steeply and moving in the opposite direction.\n\nFor logistic regression, this loss function is **convex** such that it only has one\n minimum so there is no local minima to get stuck in. Hence it is guaranteed to the\n  find the minimum.\n\nThe magnitude of the amount to move is the value of the slope weighted by a learning\n rate $\\eta$.\nA higher/faster learning rate means we should move $w$ more on each step.\n$$w^{t+1} = w^t - \\eta \\frac{d}{dw} f(x;w)$$\n---\n##### The Gradient\nTo update $\\theta$, we need a definition for the gradient $\\nabla L(f(x, \\theta), y)$.\nFor logistic regression, the cross entropy [[Loss Function]] is\n$$L_{CE}(\\hat{y},y) = - [y \\log \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b) + \n(1-y) \\log (1 - \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b))]$$\n\nThe derivative of this function for one observation vector $x$ for a single weight $w_j$ is\n$$\\frac{\\delta L_{CE}(w,b)}{\\delta w_j} = [\\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b) - y]x_j$$\nI.e. the difference between the true $y$ and our estimate for $x$ multiplied by the\n corresponding input $x_j$.\n\nAverage loss:\n$$\\text{cost}(w,b) = \\frac{1}{m} \\sum_{i=1}^{m} L_{CE}(\\hat{y}^{(i)}, y^{i})$$\n$$= - \\frac{1}{m} \\sum_{i=1}^{m} y^{(i)} \\log \\sigma(w \\cdot x^{(i)} + b) + (1-y^{(i)})\n \\log (1-\\sigma(w \\cdot x^{(i)} + b))$$\nThis is what we want to minimize.\n\nThe loss for a batch of data or an entire data set is just the average loss over \nthe $m$ examples.\n\nThe gradient for multiple data points is the sum of the individual gradients:\n$$\\frac{\\delta \\text{cost}(w,b)}{\\delta w_j} = \\sum_{i=1}^{m} [\\sigma(\\boldsymbol{w}\n \\cdot x^{(i)} + b) - y^{(i)}]x_j^{(i)}$$\n\nExample\n1. ![[Pasted image 20211127154605.png]]\n2. ![[Pasted image 20211127154637.png]]\n3. ![[Pasted image 20211127154709.png]]\n\n---\n##### Mini-batch training\n**Stochastic** gradient descent chooses a **single random example** at a time and\n updates its weights on that example, therefore updates can fluctuate.\nInstead, **batch training** computes the gradient over the entire dataset which gives\n a much better estimate of which direction to move the weights, but it takes a long\n  time to compute.\nA compromise is **mini-batch training** where we train a small batch whose size is\n determined by computational resources. All examples in the batch can be processed\n  in parallel and the loss accumulated.\n\n---\n##### Regularization\n**Overfitting** is a problem in logistic regression: if a feature only occurs in\n one class it will get a high weight.\nRegularization penalises large weights by adding a term to the loss function:\n- Lasso regression uses L1 regularization\n- Ridge regression uses L2 regularization\n\n---\n##### Multinomial logistic regression\nOften want more than two (binary) classes and want to known probability $y$ for \neach class $c \\in C, p(y=c|x)$.\nTo get proper probability, we use a generalization of the sigmoid function called\n the **softmax function**:\n$$\\text{softmax}(z_i) = \\frac{e^{z_i}}{\\sum_{j=1}^{k}e^{z_j}}, 1 \\leq i \\leq k$$\n\nSoftmax takes in an input vector $z=[z_1,z_2,...,z_k]$ and outputs a vector of values\n normalized into probabilities.\n\n---\nNeural Networks\n\n##### Sigmoid neurons\nProblem: a small change in weights or bias of any single perceptron in the network\n can cause the output to completely flip from $0$ to $1$.\nSolution: sigmoid neuron.\n\nSmoothness of $\\sigma$ means small changes on the weights $w_j$ and bias $b$ will\n produce a small change in the output of the neuron.\n\n##### Activation functions\nThere are three commonly used non-linear functions used for the activation function $f$:\n- sigmoid function\n- tanh function\n- rectified linear unit (ReLU)\n\n##### Feed-forward Neural Network\nSimplest kind of NN. **Multilayer** network where all units are usually **fully-connected**\n and no cycles.\nThe outputs from each layer are passed to units in the next higher layer. No outputs\n are passed back to lower layers.\n\n---\n##### Training NN\nWant to learn best parameters for the NN to make its predictions $\\hat{y}$ as close\n as possible to the gold standard labels in the training data $y$. Require:\n- loss function: cross-entropy loss\n- optimization algorithm: gradient descent\n- a way to compute the gradient of the loss function: error propagation\n\n##### Cross-entropy loss\nIf the NN is a binary classifier with a sigmoid function at the final layer, the \n[[Loss Function]] is exactly the same as logistic regression.\n\nFor multinomial regression:\n$$L_{CE}(\\hat{y}, y) = - \\sum_{i=1}^{C} y_i \\log \\hat{y}_i$$\n\nIf there is only one correct answer, where the truth is $y_i=1$ then this simplifies to\n$$L_{CE}(\\hat{y}, y) = - \\log \\hat{y}_i$$\n\nPlugging into softmax:\n$$L_{CE}(\\hat{y}, y) = - \\log \\frac{e^{z_i}}{\\sum_{j=1}^{k}e^{z_j}}$$\n\n##### Computing the gradient\nLogistic regression can be through of as a network with just one weight layer and\n a sigmoid output. See [[Stochastic Gradient Descent]].\n\nBut these derivatives only give the correct updates for the last weight layer. For\n deeper networks, we need to look back through all earlier layers, even though loss\n  is only computed with respect to the output. Solution: error backpropagation algorithm.\n\n##### Computation graphs\nRelated to general **backward differentiation** procedure which depends on **computation graphs**\n - represents process of computing a mathematical expression and broken down into separate operations.\n  Each operation is a node in a graph - use **forward pass** to calculate.\n\n##### Backward differentiation\n**Backward pass** used to compute the derivatives needed for the weight update. Computing\n the derivative of the output function with respect to the inputs via the chain rule (from calculus).\n\n*Calculate partial derivative at each node and pass back.*\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 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "Neural Language Models\n",
        "\n",
        "Several advantages over n-gram LMs:\n",
        "1. Don't need smoothing\n",
        "2. Handle much longer histories\n",
        "3. Generalise over contexts of similar words\n",
        "4. Tend to have much higher predictive accuracy than n-grams LMs\n",
        "\n",
        "Disadvantage: slower to train.\n",
        "\n",
        "---\n",
        "How they work:\n",
        "1. Associate each words in the vocabulary with a vector-representation, thereby \n",
        "creating a notion of similarity between words\n",
        "2. Express the joint probability function of an input word sequence in terms of \n",
        "word vectors\n",
        "3. Learn the word vectors and parameters of the function\n",
        "\n",
        "Word vectors are low-dimensional (30 to 100) dense vectors.\n",
        "\n",
        "Probability function is expressed using the product of conditional probabilities \n",
        "of the next word given the previous word using multi-layer, feed forward neural \n",
        "networks.\n",
        "\n",
        "---\n",
        "Structure:\n",
        "**Input** = k-gram of words $w_{1:k}$.\n",
        "**Output** = probability distribution over the next word.\n",
        "The $k$ context words are treated as a word windows. Each word is associated with \n",
        "an embedding vector.\n",
        "Input vector $\\\\mathbf{x}$ concatenates $v(w)$ for each of the $k$ words:\n",
        "$$v(w) \\\\in \\\\mathbb{R}^{d_w}$$\n",
        "$$\\\\mathbf{x} = [v(w_1); v(w_2); ...; v(w_k)]$$\n",
        "\n",
        "---\n",
        "Training:\n",
        "Training examples are word k-grams from the corpus.\n",
        "The identities of the first $k-1$ words are features and the last word is the target\n",
        " label for the classification.\n",
        "Model is trained using cross-entropy loss.\n",
        "\n",
        "---\n",
        "N-grams construct tables to look up probability of seeing a word given a history. \n",
        "However, tables only store observed sequences. \n",
        "\n",
        "Problem arises when we have a new unseen combination of words. This was solved using\n",
        " back-off and smoothing/interpolation.\n",
        "\n",
        "Alternate idea: generalisation.\n",
        "Intuition: take a sentence and use it when assigning probabilities to similar sentences.\n",
        "\n",
        "1. Use a vector space model: words are vectors with real values $\\\\mathbb{r}^m$ with $d=30,\n",
        " 60, 100$ dimensional vector lengths. This computes word similarity.\n",
        "2. Define probability function that returns a joint probability of words in a sequence\n",
        " based on sequence of these vectors.\n",
        "3. Learns word representations and probability function from data at the same time.\n",
        "\n",
        "---\n",
        "Word embeddings: when the dimension of word vectors are reduced, the words group \n",
        "together intuitively.\n",
        "\n",
        "---\n",
        "Lexical Semantic Model\n",
        "\n",
        "##### Word Meaning\n",
        "In n-grams, words are represented as a string of letters or as an index in a vocabulary\n",
        " list.\n",
        "Ideally we want meaning representation to encode:\n",
        "- Synonyms\n",
        "- Antonyms\n",
        "- Connotations - words that are positive or negative\n",
        "- Semantic roles - words that are different parts of the same event and can portray\n",
        " the same meaning based on their position in a sentence\n",
        "- (Logical) entailment\n",
        "\n",
        "Entailment:\n",
        "Powerful machinery, but knowledge must come from somewhere else.\n",
        "E.g. WordNet is a lexical knowledge base created by researchers. Encodes synonyms\n",
        " for different meanings of a word and hypernym/holonyms - hyper is a generalization\n",
        "  (i.e. up the hierarchy) and holo is more specific (i.e. down the hierarchy).\n",
        "\n",
        "---\n",
        "Vector Space Model\n",
        "\n",
        "Vector space models do not allow for the same kind of operations as in a taxonomic model\n",
        " (e.g. WordNet), but they can scale and automatically extract knowledge about language from a corpus.\n",
        "\n",
        "Word similarity:\n",
        "Most words don't have many synonyms but they have a lot of similar words. Useful for\n",
        " applications like Q & A.\n",
        "\n",
        "Distributional hypothesis (Harris 1954):\n",
        "If words A and B have almost identical environments, we can define them as synonyms.\n",
        "\n",
        "Intuition of distributional word similarity:\n",
        "Humans can guess what a word means from its context. Therefore two words are similar\n",
        " if they have similar word contexts.\n",
        "\n",
        "---\n",
        "History of vector space models:\n",
        "Developed in the SMART information retrieval system (Salton 1971). Each document in\n",
        " a collection is represented as a point in a space (vector in vector space). A user's\n",
        "  query is a pseudo-document and is represented as a point in the same space. Perform\n",
        "   IR by retrieving documents whose vectors are close together in space to the query\n",
        "    vector.\n",
        "\n",
        "---\n",
        "##### Term-Document Matrix\n",
        "- Column vector is a document.\n",
        "- Row vector represents a term.\n",
        "- Cell is how often that term occurred in that document.\n",
        "\n",
        "Length of document vectors is the size of vocabulary. Document vectors can be sparse.\n",
        "\n",
        "Can compare similarity of **documents** by comparing their column vectors. Some \n",
        "common tasks include:\n",
        "- retrieving/searching similar docs\n",
        "- plagiarism detection\n",
        "\n",
        "Compare similarity of **words** by comparing their row vectors.\n",
        "\n",
        "Plotting vectors in space allows comparison of word similarity. Euclidean distance\n",
        " between points doesn't work as placement depends on word frequency! Therefore we use\n",
        "  vector L2 normalization:\n",
        "1. Calculate vector length (L2 norm):\n",
        "$$||u|| = \\\\sqrt{\\\\sum_{i=1}^{n} u^2_i}$$\n",
        "2. Divide each by vector by length (L2 norm)\n",
        "\n",
        "Take cosine of angle between vectors to measure distance. L2 normalization is \"built-in\":\n",
        "$$1-\\\\frac{\\\\sum_{i=1}^{n} u_i \\\\times v_i}{\\\\sqrt{\\\\sum_{i=1}^{n} u^2_i} \\\\times \\\\sqrt{\\\\sum_{i=1}^{n} v^2_i}}$$\n",
        "\n",
        "---\n",
        "##### Term-Term Matrix\n",
        "Also called term-context matrix.\n",
        "- Every word has a column *and* row vector.\n",
        "- Cell indicates how often word appears in a context window surrounding the other word.\n",
        "\n",
        "Length is now $|V|$ instead of number of docs.\n",
        "\n",
        "Context windows:\n",
        "Occur in windows of +/- 2 words, in same sentence and document. \n",
        "\n",
        "Instead, a window of words use more complex contexts since languages have long distance\n",
        " dependencies. Syntactic distributions used to define a word's context, e.g. similar words \n",
        "modified and act upon the same set of words. \n",
        "\n",
        "**Dependency parsing** can be used to define a word's context through its syntactic\n",
        " distribution. DIRT is one example from Google.\n",
        "\n",
        "Alternates to counts:\n",
        "Raw word frequency is not a great measure as it's skewed towards the most frequent\n",
        " words (e.g. the, and; follows the zipf distribution) that may not be the most informative\n",
        "  to a given context. Therefore common to transform vectors using:\n",
        "- TF-IDF\n",
        "Term frequency (word count) * inverse document frequency (1 / number of documents it\n",
        " occurred in)\n",
        "- or PPMI\n",
        "\n",
        "---\n",
        "Word Embedding\n",
        "\n",
        "Spare vs. dense vectors:\n",
        "Co-occurrence matrix (weighted by TF-IDF or mutual information)\n",
        "- long (length |V| = 50,000+)\n",
        "- sparse (most elements are 0)\n",
        "\n",
        "Alternative: learn vectors that are\n",
        "- short (length 200-1000)\n",
        "- dense (most elements are non-zero)\n",
        "\n",
        "Train a classifier!\n",
        "1. Treat target word and neighbouring context as positive examples\n",
        "2. Randomly sample other words to get negative samples\n",
        "3. Use logistic regression to train classifier to distinguish between these two cases\n",
        "4. Use weights as embeddings\n",
        "\n",
        "##### Word2Vec\n",
        "- Learn embeddings as part of the process of word prediction\n",
        "- Train classifier to predict neighbouring words\n",
        "- Inspired by neural net language models\n",
        "- Thus learn dense embeddings for the words in the training corpus\n",
        "\n",
        "Advantages: fast, easy to train (faster than SVD); available as package online\n",
        "\n",
        "Negative sampling:\n",
        "Want predictions of true surrounding words to be high; random noise words from vocabulary\n",
        " to be low.\n",
        "\n",
        "Training using logistic regression results in accurate embeddings (nearest neighbour words).\n",
        " Also captures relational meanings.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 40,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "650ef631-320f-4a42-a972-c8cfe13ef094"
      },
      "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": 41,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\nNeural Language Models\n\nSeveral advantages over n-gram LMs:\n1. Don't need smoothing\n2. Handle much longer histories\n3. Generalise over contexts of similar words\n4. Tend to have much higher predictive accuracy than n-grams LMs\n\nDisadvantage: slower to train.\n\n---\nHow they work:\n1. Associate each words in the vocabulary with a vector-representation, thereby \ncreating a notion of similarity between words\n2. Express the joint probability function of an input word sequence in terms of \nword vectors\n3. Learn the word vectors and parameters of the function\n\nWord vectors are low-dimensional (30 to 100) dense vectors.\n\nProbability function is expressed using the product of conditional probabilities \nof the next word given the previous word using multi-layer, feed forward neural \nnetworks.\n\n---\nStructure:\n**Input** = k-gram of words $w_{1:k}$.\n**Output** = probability distribution over the next word.\nThe $k$ context words are treated as a word windows. Each word is associated with \nan embedding vector.\nInput vector $\\mathbf{x}$ concatenates $v(w)$ for each of the $k$ words:\n$$v(w) \\in \\mathbb{R}^{d_w}$$\n$$\\mathbf{x} = [v(w_1); v(w_2); ...; v(w_k)]$$\n\n---\nTraining:\nTraining examples are word k-grams from the corpus.\nThe identities of the first $k-1$ words are features and the last word is the target\n label for the classification.\nModel is trained using cross-entropy loss.\n\n---\nN-grams construct tables to look up probability of seeing a word given a history. \nHowever, tables only store observed sequences. \n\nProblem arises when we have a new unseen combination of words. This was solved using\n back-off and smoothing/interpolation.\n\nAlternate idea: generalisation.\nIntuition: take a sentence and use it when assigning probabilities to similar sentences.\n\n1. Use a vector space model: words are vectors with real values $\\mathbb{r}^m$ with $d=30,\n 60, 100$ dimensional vector lengths. This computes word similarity.\n2. Define probability function that returns a joint probability of words in a sequence\n based on sequence of these vectors.\n3. Learns word representations and probability function from data at the same time.\n\n---\nWord embeddings: when the dimension of word vectors are reduced, the words group \ntogether intuitively.\n\n---\nLexical Semantic Model\n\n##### Word Meaning\nIn n-grams, words are represented as a string of letters or as an index in a vocabulary\n list.\nIdeally we want meaning representation to encode:\n- Synonyms\n- Antonyms\n- Connotations - words that are positive or negative\n- Semantic roles - words that are different parts of the same event and can portray\n the same meaning based on their position in a sentence\n- (Logical) entailment\n\nEntailment:\nPowerful machinery, but knowledge must come from somewhere else.\nE.g. WordNet is a lexical knowledge base created by researchers. Encodes synonyms\n for different meanings of a word and hypernym/holonyms - hyper is a generalization\n  (i.e. up the hierarchy) and holo is more specific (i.e. down the hierarchy).\n\n---\nVector Space Model\n\nVector space models do not allow for the same kind of operations as in a taxonomic model\n (e.g. WordNet), but they can scale and automatically extract knowledge about language from a corpus.\n\nWord similarity:\nMost words don't have many synonyms but they have a lot of similar words. Useful for\n applications like Q & A.\n\nDistributional hypothesis (Harris 1954):\nIf words A and B have almost identical environments, we can define them as synonyms.\n\nIntuition of distributional word similarity:\nHumans can guess what a word means from its context. Therefore two words are similar\n if they have similar word contexts.\n\n---\nHistory of vector space models:\nDeveloped in the SMART information retrieval system (Salton 1971). Each document in\n a collection is represented as a point in a space (vector in vector space). A user's\n  query is a pseudo-document and is represented as a point in the same space. Perform\n   IR by retrieving documents whose vectors are close together in space to the query\n    vector.\n\n---\n##### Term-Document Matrix\n- Column vector is a document.\n- Row vector represents a term.\n- Cell is how often that term occurred in that document.\n\nLength of document vectors is the size of vocabulary. Document vectors can be sparse.\n\nCan compare similarity of **documents** by comparing their column vectors. Some \ncommon tasks include:\n- retrieving/searching similar docs\n- plagiarism detection\n\nCompare similarity of **words** by comparing their row vectors.\n\nPlotting vectors in space allows comparison of word similarity. Euclidean distance\n between points doesn't work as placement depends on word frequency! Therefore we use\n  vector L2 normalization:\n1. Calculate vector length (L2 norm):\n$$||u|| = \\sqrt{\\sum_{i=1}^{n} u^2_i}$$\n2. Divide each by vector by length (L2 norm)\n\nTake cosine of angle between vectors to measure distance. L2 normalization is \"built-in\":\n$$1-\\frac{\\sum_{i=1}^{n} u_i \\times v_i}{\\sqrt{\\sum_{i=1}^{n} u^2_i} \\times \\sqrt{\\sum_{i=1}^{n} v^2_i}}$$\n\n---\n##### Term-Term Matrix\nAlso called term-context matrix.\n- Every word has a column *and* row vector.\n- Cell indicates how often word appears in a context window surrounding the other word.\n\nLength is now $|V|$ instead of number of docs.\n\nContext windows:\nOccur in windows of +/- 2 words, in same sentence and document. \n\nInstead, a window of words use more complex contexts since languages have long distance\n dependencies. Syntactic distributions used to define a word's context, e.g. similar words \nmodified and act upon the same set of words. \n\n**Dependency parsing** can be used to define a word's context through its syntactic\n distribution. DIRT is one example from Google.\n\nAlternates to counts:\nRaw word frequency is not a great measure as it's skewed towards the most frequent\n words (e.g. the, and; follows the zipf distribution) that may not be the most informative\n  to a given context. Therefore common to transform vectors using:\n- TF-IDF\nTerm frequency (word count) * inverse document frequency (1 / number of documents it\n occurred in)\n- or PPMI\n\n---\nWord Embedding\n\nSpare vs. dense vectors:\nCo-occurrence matrix (weighted by TF-IDF or mutual information)\n- long (length |V| = 50,000+)\n- sparse (most elements are 0)\n\nAlternative: learn vectors that are\n- short (length 200-1000)\n- dense (most elements are non-zero)\n\nTrain a classifier!\n1. Treat target word and neighbouring context as positive examples\n2. Randomly sample other words to get negative samples\n3. Use logistic regression to train classifier to distinguish between these two cases\n4. Use weights as embeddings\n\n##### Word2Vec\n- Learn embeddings as part of the process of word prediction\n- Train classifier to predict neighbouring words\n- Inspired by neural net language models\n- Thus learn dense embeddings for the words in the training corpus\n\nAdvantages: fast, easy to train (faster than SVD); available as package online\n\nNegative sampling:\nWant predictions of true surrounding words to be high; random noise words from vocabulary\n to be low.\n\nTraining using logistic regression results in accurate embeddings (nearest neighbour words).\n Also captures relational meanings.\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": {
        "id": "T3cm1WV542_a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9680ef9c-62dc-49a6-b8dc-7993fec0a523"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nDecision theory decides which action to choose based on the desirability of its immediate outcomes. An agent's preferences are captured by a utility function which assigns a numeric value to express desirability.\n\nThe MEU principle can be seen as a recipe for intelligent behaviour. It formalises the notion that an agent should do the right thing but doesn't operationalise it. Estimating the probability distribution over possible states of the world requires perception, learning, knowledge representation and inference; a model of the world. Utility functions may require further searching or planning to find the best state, and agent's acting on behalf of humans may not even know what the true utility function is!\n\nAn agent will achieve the highest possible performance score, averaged over all possible environments, if it acts to maximise a utility function that properly reflects its performance measure. The utility function thus internalises and guides an agent's \nactions (as opposed to a retrospective, external performance measure).\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nWe can derive the MEU principle from some constraints such as the agent preferring $A$ over $B$, is indifferent between them, or both. $A$ and $B$ could be states of the world or uncertainty about what's on offer. Its set of outcomes can be thought of as a lottery, with each action a ticket. Each outcome can either be an atomic state or another lottery.\n\nThe main concern for utility theory is how preferences between lotteries are related to preferences about their underlying states. There are six constraints that a preference relation must therefore obey (axioms of utility theory):\n- Orderability: exactly one of $(A \\succ B), (B \\succ A)$ or $(A \\sim B)$\n- Transitivity: $(A \\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C)$\n- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p,A;1-p,C]\\sim B$\n- Substitutability: if an agent is indifferent between lotteries $A$ and $B$ then it will be indifferent between two more complex lotteries that are the same other than $B$ being substituted for $A$, regardless of the probabilities. This also holds for preference instead of indifference.\n- Monotonicity: if an agent prefers $A$ to $B$ in two lotteries, then it prefers the lottery that has a higher probility for $A$.\n- Decomposability: compound lotteries can be reduced to simpler ones using probability laws.\n\nThe axioms derive the following consequences:\n- Existence of Utility Function: $U(A) > U(B)$ iff $A$ is preferred to $B$. $>$ can also be replaced with $\\sim$ when indifferent.\n- Expected Utility of Lottery: utility is the sum of the probability of each outcome multiplied by the outcome's utility\n\nOnce probabilities and utilities are specified for possible outcome states, the utility of a compound lottery involving those states is determined. The outcome of a nondeterministic action is a lottery so it follows an agent can act rationally by choosing actions that maximises its expected utility.\n\nUtility functions can be transformed and remain the same.\n\nRational behaviour can be generated in a number of ways, and an agent isn't necessarily maximising it's utility by itself. Observer's can also learn about an agent's utility function through observations about what it's trying to achieve.\n\n## AIMA Chapter 16.3 Utility Functions\nBuilding a decision-theoretic system that acts on behalf of a human or assists in making their decisions is achieved via preference elicitation.\n\nSince utilities can be transformed, there is no absolute scale, however fixing utilities of two particular outcomes can be helpful so they can be recorded and compared. This is typically done for the best and worst possible outcomes. Normalised utilities use a scale of 0 to 1.\n\nGiven a utility scale, the utility of any prize can be assessed by asking the agent to choose between it and a standard lottery. The probability is adjusted until the agent is indifferent between the two and this probability determines the utility.\n\nMoney is a candidate for a utility measure, provided by economics. An agent has a monotonic preference for more money. Accepting a gamble depends on the utility of accepting vs. declining. For example, someone with a high net worth is more likely to accept a gamble as their expected utility of accepting would be higher than declining.\n\nThe utility of money yields a kind of S-curve. Those in the positive part of the curve prefer the expected monetary value as a sure thing - they are risk-averse. On the other hand, behaviour is risk-seeking on the negative side. Small changes in wealth has a linear curve and is known as risk-neutral.\n\nIn reality models of probability are simplifications of the world or are too complex to calculate. Therefore we are working with estimates of the true expected utility. If estimates are unbiased, the expected value of the error is $0$ and the action chosen would be the best on average when executed. However, the real outcome is usually significantly worse than estimated as we favour overly optimistic estimates because of the optimizer's curse.\n\nPeople can act irrationally (i.e. Allais paradox). One explanation is due to the certainty effect. People may prefer to reduce their computational burden and distrust legitimacy of stated probabilities. People may also account for their emotional state as well as financial state. Other reasons include ambiguity aversion, the framing effect, and the anchoring effect. Preferences are however open to revision when choices are explained better. Evolutionary psychology questions human irrationality and suggest that we didn't evolve to solve word problems with probabilities and prizes stated as decimal numbers. Other representations, such as visuals, can be shown to increase rationality.\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nA **Markov decision process (MDP)** is a sequential decision problem for fully \nobservable, stochastic environments. It has a Markovian transition model, \nmeaning the probability of reaching $s'$ from $s$ depends only on $s$ and ignores\n the earlier history of getting there, and additive rewards from its environment \n history (i.e. its sequence of state-actions). An MDP consists of a set of states \n $s$, with initial state $s_0$, a set of actions $a$ in each state, a transition \n model $P(s' | s,a)$ and a reward function $R(s,a,s')$. Methods for solving usually \n involve dynamic programming using recursion.\n\nA **policy** $\\pi$ is a solution which specifies what an agent should do for any \nstate that it might reach. $\\pi(s)$ is the action recommended by the policy. \nFurthermore, an **optimal policy** $\\pi^*$* is a policy that generates the highest \nexpected utility. The agent then uses this policy at $s$ to decide which next action \nto take. Policies change based on the value of $R(s,a,s')$ at non-terminal states.\n\nIn decision making with a **finite horizon**, an optimal action in a given state \nmay depend on how much time is left. Policies that depend on the time are known \nas **nonstationary**. Conversely, a **stationary** policy with no fixed time limit, \nbehaviour would not change in the same state at different times.\n\n**Additive discounted rewards** are used to calculate the utility of state sequences. \n$\\gamma$ represents the **discount factor** which is a value between $0$ and $1$ \ninclusive. This shows the agent's preference for short-term rewards over long-term \nrewards.\nThe advantages of using this measure are:\n1. empirical; humans and animals value near-term rewards more highly\n2. economic; early rewards can be invested\n3. uncertainty; rewards may never arrive\n4. stationarity for preferences; only this measure can satisfy\n5. infinite horizons become finite:\n\t- if $\\gamma < 1$ and rewards are bounded by $\\pm R_{max}$, the utility becomes \n  finite\n\t- a **proper policy** is guaranteed to reach a terminal state (so $\\gamma = 1$ \n  allowed) whereas an **improper policy** never will <- need to use discounting\n\t- compare infinite sequences in terms of **average reward**\n\n$\\pi^*$ represents an optimal policy and the true utility of a state is written \nas $U(s)$.\n\nThe utility of a state is the expected reward for the next transition plus the \ndiscounted utility of the next state, assuming the agent chooses the optimal action: \n$U(s) = \\underset{a \\in A(s)}{max} \\underset{s'}\\sum P(s' | s,a) [R(s,a,s') + \n\\gamma U(s')]$\nThis is the **Bellman equation**.\n\nThe **action-utility function** or **Q-function** $Q(s,a)$ is the expected utility\n of taking a given action in a given state. We can develop a Bellman equation for \n Q-functions in a similar fashion:\n$Q(s,a) = \\underset{s'}\\sum P(s' | s,a) [R(s,a,s') + \\gamma ~\\underset{a'}{max} Q(s', a')]$\n\nThe scale of utilities is arbitrary and an affine transformation doesn't change \nthe optimal decision.\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n**Value iteration**\nThe Bellman equation is the basis for the algorithm. With $n$ possible states, there \nare $n$ Bellman equations. Systems of linear equations can be solved using linear \nalgebra; however this equation is nonlinear.\n\nWe use an iterative approach, starting with arbitrary initial utility values. The \n$i$th iteration is called a **Bellman update**:\n$U_{i+1}(s) \\leftarrow \\underset{a \\in A(s)}{max} \\underset{s'}{\\sum} P(s'|s,a)[R(s,a,s')\n + \\gamma U_i (s')]$\nApplying this infinitely often we will eventually reach an equilibrium (i.e. \nconvergence) in which we find the unique solutions to the Bellman equations. The \nresulting policy is optimal.\n\nThe value iteration algorithm propagates information through the state space via \nlocal updates.\n\n**Convergence of value iteration**\n**Contraction** generates two different outputs that are \"closer together\" when \ngiven some inputs, e.g. division by $2$. Contractions have one fixed point (e.g. \n$0$ in the previous example) and values move closer to the fixed point upon repeated \napplication.\n\nIn summary, the Bellman update is a contraction by a factor of $\\gamma$ on the \nspace of utility vectors, therefore value iteration converges to a unique solution \nof the Bellman equations when $\\gamma < 1$.\n\nThe number of iterations $N$ required to reach convergence is $\\gamma ^N$. Therefore\n convergence is exponential when $\\gamma$ is very small, but grows larger when it \n is closer to $1$. If $\\gamma$ is too small then the agent will have a shorter \n horizon and could miss the longer-term effects of its actions.\n\nIf an agent derives the policy $\\pi_i$ based on value iteration, its resulting \nbehaviour will be nearly as good as the optimal behaviour.\n\n**Policy iteration**\nThe algorithm alternates between two steps, beginning from an initial policy $\\pi_0$:\n- **Policy evaluation**: given a policy $\\pi_i$, calculate the utility of each state\n- **Policy improvement**: calculate a new policy $pi_{i+1}$ using one-step look-ahead\n based on the previous utility\nTerminates when policy improvement no longer changes the utilities.\n\nImplementing (approximate) policy evaluation (known as **modified policy iteration**)\n uses a simpler version of the Bellman equations: $U_{i+1}(s) \\leftarrow \\underset{s'}{\\sum} \n P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$\nThis is repeated several times to produce the next utility estimate.\n\nThe (exact) equations are linear so can be solved with linear algebra in $\\mathcal{O}(n^3)$\n (for $n$ states there are $n$ linear equations with $n$ unknowns).\n\n**Asynchronous policy iteration** updates subsets of states (rather than all states\n at once) and applies either value iteration or policy improvement; this can result \n in more efficient heuristic algorithms.\n\n**Linear programming** is a general approach for formulating constrained optimisation\n problems; an MDP can be solved with it. Dynamic programming methods can often be \n more efficient in practice.\n\n\n## Module 8 Lecture Notes\n\nMDP: type of non-deterministic search\n\n**Stochastic transition models**\nSearch algorithms so far had deterministic transition models where the outcome was \nguaranteed.\nIn the stochastic transition model, the transition function is given by $T(s, a, s')$ \nor as a probability $p(s' | s,a)$.\n\nWe ignore history of states up until the current state, therefore transitions are \nMarkovian. Probability only depends on $s$.\n\n**Reward function**\nRewards can be positive or negative but bounded by values.\nAgent receives an award at each step as defined by $R(s, a, s')$.\nRewards are additive and based on the sum of sequences of state-action pairs \n(environment history) that are executed.\n\n---\n**Markov Decision Process (MDP)**\n- sequential decision problems\n- for fully observable environments\n- has a stochastic transition model\n- and additive rewards\n\nTo find a solution, need to define:\n- set of states $s \\in S$\n- set of actions $a \\in A$\n- transition function $T(s, a, s')$\n\t- probability is $p(s' | s,a)$, known as the *model*\n- reward function $R(s, a, s')$\n\t- sometimes $R(s)$ or $R(s')$\n- initial state $s_0$\n- optionally: one or more terminal states\n\n**Solution == policy**\nIn search problems a solution had a shortest path of a sequence of actions.\nMDPs have a policy, mapping a state onto an action, defined as $\\pi(s) = a$. $\\pi^*$ \nindicates the most optimal policy.\n\n**Policies and rewards**\nNeed to compute the expected utility of all possible paths generated by a policy.\nReward function shapes optimal plan.\n\n**Sequence of rewards**\nPerformance of an agent is the sum of rewards of its transitions.\nAn agent would prefer more rewards overall and get them earlier rather than later.\n\n**Discounting**\nSolution to maximising sum of rewards and preferring them now is decaying values \nof rewards exponentially as time progresses.\n\nDiscount by multiplying the discount once per level in a tree.\nSooner rewards have higher utility than later rewards.\nAlgorithms converge to put a limit on search depth. Later rewards are diminishingly \nsmall so truncating early does not have a large effect.\n\n**Stationary preferences**\nTheorem: assuming stationary preferences:\n$[a_1, a_2,...] \\succ [b_1, b_2, ...]$\nAppending the same reward $r$ to both gives the same result\n$[r, a_1, a_2,...] \\succ [r, b_1, b_2, ...]$\n\nThen there are only two ways to define utilities:\nAdditive utility: $U([r_0, r_1. r_2,...]) = r_0 + r_1 + r_2 + ...$\nDiscounted utility: $U([r_0, r_1. r_2,...]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 + ...$\n\n**Infinite utilities**\nSolutions:\n- finite horizon: (similar to depth-limited search)\n\t- terminate episodes after a fixed number of steps (e.g. life)\n\t- gives non-stationary policies ($\\pi$ depends on time remaining)\n- discounting: (use $0 < \\gamma < 1$)\n\t- smaller $\\gamma$ means smaller horizon\n- absorbing state:\n\t- guarantee that for every policy a terminal state will eventually be reached \n  (e.g. \"overheating\" in racing games)\n\n---\n**MDP search trees**\nEach MDP state projects an expectimax-like search tree.\n\n**Optimal quantities**\nValue (utility) of a state $s$:\n$V^*(s)$ = expected utility starting in s and acting optimally\n\nValue (utility) of a q-state $(s,a)$:\n$Q^*(s,a)$ = expected utility starting out having taken action $a$ from state $s$\n and then acting optimally\n\nOptimal policy:\n$\\pi^*(s)$ = optimal action from state $s$\n\n**Value of states**\nFundamental operation: compute (expectimax) value of a state:\n- expected utility under optimal action\n- average sum of (discounted) rewards\n- what expectimax computed!\n\nRecursive definition of value:\n$Q^*(s, a) = \\sum_{s'}T(s,a,s')~[R(s,a,s')+ \\gamma V^*(s')]$\n(weighted average of all possible outcomes according to transition function)\nwhere\n$V^*(s) = {max}_a~Q^*(s,a)$\n\nThis is known as a **Bellman equation**.\n\nNeed to do a lot of work with expectimax:\n- states are repeated: only compute needed quantities once\n- tree goes on infinitely: do depth-limited computation until change is small (\n  deep levels don't contribute much if $\\gamma < 1$)\n\n---\nValue iteration:\n**Algorithm**\n- start with $V_0(s) = 0$: no steps left means an expected reward sum of zero\n- given vector $V_k(s)$ values, perform one ply of expectimax from each state: \n$V_{k+1}(s) = {max}_a~\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\gamma V_k(s')]$\n- repeat until convergence\n\nComplexity of each iteration: $\\mathcal{O}(s^2a)$ - worst case where a state is c\nonnected to every other state.\n\nTheorem: converges to unique optimal values.\n- approximations get refined towards optimal values\n- policy may converge long before values do\n\n**Convergence**\nCases of $V_k$ convergence:\n1. with maximum depth $M$, $V_M$ holds actual (untruncated) values\n2. discount $\\gamma < 1$ **review proof**\n\n---\nPolicy evaluation:\n**Policy methods**\nTo find the best policy, you can directly compare policies to one another and \ndecide which one is better.\n\nCalculate values given a policy.\n\n**Fixed policies**\nA fixed policy $\\pi(s)$ has a simpler tree as there is only one action per state.\nWe can compute the utility of $s$:\n- $V^{\\pi}(s)$ = expected total discounted rewards starting at $s$ and following $\\pi$\n- recursive relation: $V^{\\pi}(s) = \\sum_{s'}T(s,\\pi(s),s')~[R(s,\\pi(s),s') + \n\\gamma V^{\\pi}(s')]$\n\n**Policy evaluation**\nCalculating the values for a fixed policy $\\pi$ can be done:\n1. turn recursive Bellman equations into updates (like value iteration).\n\tefficiency is $\\mathcal{O}(s^2)$ per iteration - no need to decide actions as \n  it's provided by the policy\n2. without needing to find the maximum of an action, Bellman equations are a system \nof linear equations that can be solved directly\n\nOn the other hand, calculate policies given values.\n\n**Computing actions from values**\nNot obvious how to act.\n\nNeed to do a mini-expectimax of one step for each action that can be taken: \n$\\pi^*(s) = {max}_a~\\sum_{s'}T(s,a,s')~[R(s,a,s') + \\gamma V^*(s')]$\n\nKnown as **policy extraction** as it derives the policy implied by values.\n\n**Computing actions from q-values**\nTrivial to decide which action to take. Select maximum q-value: $\\pi^*(s) = {max}_a Q^*(s,a)$\n\n*Easier to select actions from q-values than values!*\n\n---\nProblems with value iteration:\n1. slow - $\\mathcal{O}(s^2a)$ per iteration\n2. the max at each stage of the Bellman equation rarely changes\n3. policy often converges long before values\n\n**Algorithm**\nSteps:\n1. **policy evaluation**: calculate utilities for some fixed (not optimal) policy until convergence:\n\t$V^{\\pi_i}_{k+1}(s) = \\sum_{s'}T(s,\\pi_i(s),s')~[R(s,\\pi_i(s),s') + \\gamma V^{\\pi_i}_{k}(s')]$\n2. **policy improvement**: update policy using one-step look-ahead with converged (not optimal) \nutilities as future values\n\t$\\pi_{i+1}(s) = {max}_a \\sum_{s'}T(s,a,s')~[R(s,a,s') + \\gamma V^{\\pi_i}(s')]$\n2. repeat until policy converges\n\nOptimal. Can converge faster under some conditions.\n\n**Comparison**\nBoth value and policy iteration achieve the same outcome: find optimal values, \napply policy extraction and derive optimal policy.\n\nValue iteration:\n- every iteration updates values and (implicitly) the policy\n- doesn't track policy, but taking the max over actions implicitly recomputes it\n\nPolicy iteration:\n- several passes that update utilities with a fixed policy - fast because it \nconsiders only a single action\n- after policy is evaluated, a new policy is chosen - slow like value iteration\n- new policy will be better (or it's finished)\n\nBoth are dynamic programs for solving MDPs.\n\n**Summary: MDP algorithms**\n- compute optimal values using value or policy iteration\n- compute values for a particular policy: use policy evaluation\n- turn values in a policy: use policy extraction (one-step look-ahead)\n\nAll very similar - variations of Bellman equations; all use one-step look-ahead \nexpectimax fragments; differ in whether we plug-in a fixed policy or max over actions.\n\n---\nPrinciple of maximum expected utility:\nA rational agent should choose the action that maximizes its expected utility, \ngiven its knowledge.\n\nFor worst-case minimax reasoning, terminal function scale doesn't matter; known as \n*insensitivity to monotonic transformations*.\nHowever, for average-case expectimax reasoning, magnitudes need to be meaningful - \ntransformations could affect the outcome.\n\n**Utilities**\n*Utilities are functions from outcomes (states) to real numbers that describe an \nagent's preferences.* They summarise an agen't goals.\n\nIn games: utilities may be simple (+1/-1 for win/lose).\n\nTheorem: any rational preference can be summarised by a utility function.\n\nBehaviours emerge from hard-coded utilities. We do not prescribe behaviours or let\n agents pick utilities to avoid unintended consequences.\n\n**Rational preferences**\nAxioms of rationality:\n- Transitivity: $(A \\succ B)~\\land~(B \\succ C) \\implies (A \\succ C)$\n- Orderability: $(A \\succ B)~\\lor~(B \\succ A) \\lor (A \\sim B)$\n- Continuity: $A \\succ B \\succ C \\implies \\exists_p~[p, A; 1-p, C] \\sim B$\n- Substitutability: $A \\sim B \\implies [p, A; 1-p, C] \\sim [p, B; 1-p, C]$\n- Monotonicity: $A \\succ B \\implies (p \\geq q \\Longleftrightarrow [p, A; 1-p, B] \\succeq [q, A; 1-q, B])$\nTheorem: rational preferences imply behaviour describable as maximum of expected utility.\n\n**MEU principle**\n*Theorem: given any preferences satisfying the constraints (axioms), there exists \na real-valued function $U$ such that*\n$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$\n$U([p_1, S_1; ...; p_n, S_n]) = \\sum_i p_i U(S_i)$\nThat is, *values assigned by $U$ preserve preferences of both prizes and lotteries*.\n\nMEU principle:\n- choose action that maximizes expected utility\n- (an agent can be rational (consistent with MEU) without ever representing/manipulating \nutilities and probabilities; e.g. can use a lookup table for some problems)\n\n**Utility scales**\n- normalised utilities: $u_+ = 1, u_- = 0$\n- micromorts: one-millionth chance of death\n- QALYs: quality-adjusted life years\n\nBehaviour is invariant under positive linear transformations: $U'(x) = k_1 U(x) + k_2$ \nwhere $k_1 > 0$\nWith deterministic prizes (i.e. no lottery choices), only ordinal utility can be \ndetermined, i.e. total order on prizes.\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nA one-armed bandit is a slot machine with one lever, and an **n-armed bandit** has \n$n$ levers.\n\nThere is a choice between **exploitation**, choosing the arm that has the best reward\nso far, and **exploration**, choosing the arm of an unknown state and action to \ngain new information.\n\nThere a several definitions of **bandit problems**, one is:\n- each arm $M_i$ is a **Markov reward process (MRP)**, i.e. an MDP with one action\n $a_i$. The arm defines a distribution over reward sequences.\n- the overall problem is an MDP: state space is Cartesian product $S = S_i x ... S_n$;\n actions are $a_1, ..., a_n$; transition model depends on arm $M_i$ selected; \n discount factor is $\\gamma$.\n\nThe **Gittins index** provides a simple optimal policy for any bandit problem: \npull the arm that has the highest index then update the Gittin indices. The index \nof arm $M_i$ depends only on its properties therefore an optimal decision on the \nfirst iteration can be made in $\\mathcal{O}(n)$ ($n$ being the number of arms) \nand subsequent decisions in $\\mathcal{O}(1)$ since their indices remain unchanged.\n\nThe value of the Gittins index is the maximum value attained from the ratio. Beyond \nthis point, $M_\\lambda$ is chosen by the optimal policy over $M$. \n\nThe Gittins index for an arm $M$ with state $s$ can be calculated by seeing that \na tipping point where an optimal policy is indifferent between $M$ and $M_\\lambda$, \nthe value of choosing $M$ is the same as choosing an infinite sequence of $\\lambda$-rewards.\n\n$M$ can be turned into an MDP whose optimal policy is the optimal stopping rule \nfor $M$. The type of MDP to solve this is called a **restart MDP** where the agent \nreturns to $M$'s initial state $s$, which is equivalent to deciding to quit and \nreceive infinite $\\lambda$-rewards.\n\nAny of the previous MDP algorithms can solve this MDP. The general result is the \nGittins index for $M$ in state $s$ is equal to the optimal policy of the restart \nMDP times $1-\\gamma$.\n\nThe **Bernoulli bandit** has arms $M_i$ that produce rewards $0$ or $1$ with fixed,\n unknown probability $\\mu_i$. The state of $M_i$ is defined by the counts success \n $s_i$ and failure $f_i$. The transition function for next outcome $1$ is $s_i / (s_i + f_i)$\n  and opposite for $0$.\n\n#### Approximately optimal bandit policies\nThe **upper confidence bound (UCB)** heuristic method samples each arm to find a\n confidence interval for the value of the arm, then the arm with the highest UCB is \n selected. This is strictly not a Gittins index since the total number of samples \n used is drawn across all arms, not just the arm in question.\n\n**Thompson sampling** chooses an arm randomly according to the probability the arm \nis optimal given samples so far.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nIn RL, an agent interacts with the world and receives rewards that reflect how well\n it's doing. The goal is to maximize the expected sum of rewards. The agent does not\n  know the transition model or reward function.\n\nThe main approaches to RL are:\n- **Model-based RL:** agent uses a transition model of environment to interpret \nreward signals and make decisions. The agent may need to learn the model from \nobserving the effects of its actions if it initially unknown, otherwise it may \nalready be known. Often learns from a utility function.\n- **Model-free RL:** the agent neither knows nor learns a transition model and \nlearns a more direct representation of how to behave. Two approaches:\n\t- **Action-utility learning:** most common is **Q-learning** which uses a **Q-function**\n   $Q(s,a)$ which denotes the sum of rewards from state $s$ onward if action $a$ is taken.\n\t- **Policy search:** the agent learns a policy $\\pi(s)$ that maps states to actions,\n   i.e. a reflex agent.\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n**Passive RL** is where an agent has a fixed policy $\\pi(s)$ and the task is to \nlearn the utilities of states (or state-action pairs) $U^{\\pi}(s)$. This is a \n**passive learning agent**.\n\nThe agent does not know the transition model or reward function. It executes a \nset of trials using $\\pi$ and the objective is to use information about rewards \nin each experienced transition to learn the expected utility associated with each \nnonterminal state $s$.\n\n---\n**Direct utility estimation** gives the utility of a state as the expected total \nreward from that state onward (known as the expected **reward-to-go**) and each \ntrial provides a sample for each of these states. In the limit, the sample average\n will converge to the true expectation.\n\nEach example becomes a (state, reward-to-go) pair. However, it ignores that the \nutility of a state is determined by the reward and expected utility of successor \nstates, i.e. it ignores connections between states. States learn nothing until \nthe end of a trial.\n\nHence, direct utility estimation includes functions that violate the Bellman equations\n (i.e. it views the space as much larger) so converges slowly.\n\n---\n**Adaptive dynamic programming (ADP)** agents learn the transition model that \nconnects states and solves the corresponding MDP with dynamic programming. For a\n passive learning agent, that means plugging in the learned transition model and \n observed rewards into the Bellman equation for expected utilities.\n\n**Modified policy iteration** can also be used with a simplified value iteration \nprocess to update utility estimates after each change to the learned model.\n\nLearning the transition model is simple as it uses the counts of a state transition\n to a new state to calculate the estimated transition probabilities.\n\n---\n**Temporal difference learning** is changing the estimate based on the difference\n between the observed current reward and reward expected based on what has been \n observed so far. Therefore we apply the following update:\n$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s,\\pi(s),s') + \\gamma U^{\\pi}(s') - \nU^{\\pi}(s)]$\nwhere $\\alpha$ is the **learning rate**.\nThe update is intended to reduce the error. Reducing $\\alpha$ as the number of times\n a state is visited increases eventually causes the utility to converge.\n\nTDL does not require a transition model to perform updates.\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nPassive learning agents have fixed policies that determine behaviour; active learning\n decides what actions to take.\n\n#### Exploration\nA **greedy agent** greedily takes the action that it believes to be optimal from\n a learned model, but this might not be optimal as the learned model may not be \n the same as the true environment. Sometimes it converges to the optimal, often not.\n\nActions do more than provide rewards, they also provide information about resulting\n states. An agent must decide between exploitation and exploration. \n\nAny scheme the agent follows should be greedy in the limit of infinite exploitation,\n or **GLIE**, meaning it must try each action in each state a number of times to \n avoid missing an optimal action.\n\nThere are several GLIE schemes:\n- agent chooses a random action at time step $t$ with probability $1/t$ and the \ngreedy option otherwise; simple but slow.\n- give weights to actions that haven't been tried very often while avoiding actions\n with low utilities. The exploration function $f(u,n)$ determines how greed is \n traded off against curiosity. Actions that lead toward unexplored regions are weighted\n  more highly, which are propagated back from further afield.\n\n#### Safe exploration\nMany actions are irreversible, i.e. no action can restore previous states. In the\n worst case we have an **absorbing state** where no actions have an affect and no\n  rewards are received.\n\nWe should choose a policy that works well for the whole range of models that stand\n a good chance of being the true model, even if it is suboptimal. These approaches are:\n- Bayesian RL: finds the optimal policy produced by the one with the highest expected utility.\n- Robust control theory: allows for a set of possible models without assigning \nprobabilities, and finds an optimal policy as one that gives the best outcome in \nthe worst case.\n\nHuman knowledge can keep a system safe by recording a set of actions by an experienced\n teacher and the system can improve from there. Another way is for a secondary program \n enforce constraints, for example taking control if the system gets close to an \n absorbing state.\n\n#### Temporal-difference Q-learning\nThe **Q-learning** doesn't require a transition model either for learning or action\n selection. However, it has no means of looking into the future so it can have \n difficulty with sparse rewards and long action sequences will be required.\n\n**SARSA** (state, action, reward, state, action) updates with the Q-value of the\n action $a'$ actually taken (rather than the best action). If exploration produces\n  a negative reward, it penalizes the action (Q-learning does not).\n\nQ-learning is **off-policy** (start acting according to best action policy) and \nSARSA is **on-policy** (stick with current policy).\n\nQ-learning is more flexible as it learns well with different exploration policies.\n SARSA is more appropriate if it's (partly) controlled by other agents or programs.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\nIntroduction to Reinforcement Learning\n\n#### Bandit Problems\nBandit problems came from slot machines with $>1$ levers.\nCan be solved as an MDP (offline planning), through value or policy iteration.\n\nWith reinforcement learning, you can't plan as you don't know the underlying probability\n distribution of actions therefore it can't be solved with just computation alone. \n You need to figure it out through observation of results and associated rewards \n (i.e. learning).\n\nKey terms:\n- **Exploration:** try unknown actions to get information\n- **Exploitation:** use what you know\n- **Regret:** even if you learn, mistakes happen\n- **Sampling:** there is chance so need to repeat actions\n- **Difficulty:** learning can be harder than solving known MDPs\n\n#### Reinforcement Learning\nBasic idea:\n- receive feedback in terms of rewards\n- utility is defined by reward function\n- must learn to maximize expected rewards\n- all learning based on sample of observed outcomes\n\nDescribing a problem is the same as an MDP, except the transition model and \nresulting reward are hidden so we don't know which states are good and must attempt\n actions to learn. Aim is still to find a good policy, $\\pi(s)$.\n\nMDPs are offline (compute/simulate plan) and RL is online (learn as you go).\n\n#### Model-Based Learning\nLearn an approximate model based on experiences and solve (with MDPs) for values\n as if the learned model was correct.\n\nSteps:\n1. Learn empirical MDP model\n\t1. count outcomes $s'$ for each $s, a$\n\t2. normalize to give an estimate $\\hat{T}(s,a,s')$\n\t3. discover each $\\hat{R}(s,a,s')$\n2. Solve the learned MDP\n\t1. Use, for example, value iteration (and policy extraction)\n\n---\nPassive Reinforcement Learning\n\n#### Model-Free Learning\nWe don't construct an explicit probability model to the transition function. Instead,\n for every action, compare the results to expected results. Then, adjust values when\n  result is different from expectation. We only keep track of values of interest \n  and not transition or reward functions.\n\n#### Passive RL\nTry policy provided to us. Don't attempt to act optimally, instead evaluate policy\n (i.e. policy iteration).\n\nSimplified task: policy evaluation:\n- input: fixed policy $\\pi(s)$\n- transition and reward functions are unknown\n- goal: learn state values\nThe learner is \"along for the ride\" and has no choice in which actions to take. \nThe agent executes the policy and learns from experience.\n\n**Direct evaluation**\nGoal is to compute values for each state under $\\pi$.\nIdea: average sum of observed sample values\n- act according to $\\pi$\n- at each state, record sum of discounted rewards\n- average samples\n\nAdvantages:\n- easy to understand\n- doesn't require knowledge of $T, R$\n- eventually computes correct average values using sample transitions\n\nDisadvantages:\n- discards information about state connections\n- each state learned separately\n- slow to learn!\n\nTherefore, use policy evaluation. However, need information about $T$ and $R$.\n\nIdea: take sample of outcomes $s'$ by taking the action and average over samples \n(removes the need for knowing the probability distribution). However, cannot gather\n repeated samples from state $s$ as there is no guarantee that we'll be at that \n $s$ several times.\n\n---\nTemporal Difference Learning\n\nBig idea: learn from every experience!\n- update $V(s)$ each time we experience a transition $(s,a,s')$\n- likely outcomes will contribute updates more often\n\nSample of $V(s)$: ${sample} = R(s, \\pi(s), s') + \\gamma V^{\\pi}(s')$\nUpdate to $V(s)$: $V^{\\pi}(s) \\leftarrow (1-\\alpha)V^{\\pi}(s) + \\alpha \\cdot {sample}$\nwhere $\\alpha$ is the learning rate which allows us to control how much weight we \nwant to apply current estimate vs. new sample estimate. This form is known as **interpolation**.\nThis can be re-written as $V^{\\pi}(s) \\leftarrow V^{\\pi}(s) + \\alpha({sample} - V^{\\pi}(s))$.\n\n**Exponential moving average**\nThe running interpolation update $\\bar{x}_n = (1-\\alpha)  \\cdot \\bar{x}_{n-1} + \n\\alpha \\cdot x_n$ makes recent examples more important, therefore forgetting about\n the past since distant values were inaccurate.\n\nDecreasing the learning rate $\\alpha$ converges averages over time.\n\n**TDL**\nModel-free way to do policy evaluation.\nHowever, it can't be turned into a new policy! We require Q-values, but for that,\n we need the transition model and reward.\n\nIdea: learn Q-values, not values. This makes action selection model-free too.\n\n---\nActive Reinforcement Learning (Q-Learning)\n\nFull RL: optimal policies (like value iteration).\nGoal: learn optimal policy and values.\n\nThe learner makes choices, and must decide between exploration and exploitation.\n This is not offline planning as we learn as actions are taken.\n\n#### Q-Value Learning\nQ-value iteration: [[MDP Examples]]\n\n**Q-learning**: sample-based Q-value iteration.\nLearn $Q(s,a)$ values as we go:\n- receive sample $(s,a,s',r)$\n- consider old estimate $Q(s,a)$\n- consider new sample estimate: ${sample} = R(s, a, s') + \\gamma~\\underset{a'}{max} Q(s',a')$\n- incorporate new estimate into running average: $Q(s,a) \\leftarrow (1-\\alpha)Q(s,a) + \\alpha \\cdot {sample}$\n\n**Q-Learning Properties**\nQ-learning converges to optimal policy, even when acting sub-optimally! This is \ncalled **off-policy learning**.\n\nCaveats:\n- need enough exploration\n- eventually make the learning rate $\\alpha$ small enough, but not decrease it \ntoo quickly\nIn the limit, it doesn't matter how actions are selected!\n\n---\nExploration vs Exploitation\n\nSeveral schemes for forcing exploration:\n**Simplest: random actions ($\\epsilon$-greedy)**\n- Idea: at every time step, flip a coin. With (small) probability $\\epsilon$, act\n randomly. Otherwise, with $1-\\epsilon$, act on current policy.\n- Problems: space is eventually explored, but it will keep thrashing around once\n learning is done. \n- Solutions: lower $\\epsilon$ over time; exploration functions.\n\t\n**Exploration Functions**\nCan explore at a fixed amount of randomness, or a better option is to explore \nareas whose 'badness' is not yet known then eventually stop exploring.\n\nDefine $f(u,n)=u+k/n$, where $u$ is a value estimate (i.e. current utility value),\n $n$ is a visit count, $k$ is a bonus and $f(u,n)$ is the returned optimistic utility.\n\nTherefore\nRegular Q-state: $Q(s,a) \\leftarrow \\alpha ( R(s, a, s') + \\gamma~\\underset{a'}{max}~Q(s',a') )$\nModified Q-state: $Q(s,a) \\leftarrow \\alpha ( R(s, a, s') + \\gamma~\\underset{a'}{max}~f(Q(s',a'), N(s',a')) )$\nThis also propagates the bonus back to states that lead to unknown states.\n\n**Regret**\nMeasures total cost of mistakes: difference between expected rewards, including \nyouthful sub-optimality, and optimal expected rewards.\n\nMinimizing regret goes beyond learning to be optimal - it is learning the optimal\n policy as quickly as is possible, i.e. optimally learning to be optimal.\n\nRandom exploration has higher regret than exploration functions.\n\n---\nApproximate Q-Learning\n\n#### Generalising across states\nBasic Q-learning keeps a table of all q-values. In realistic situations, we cannot\n learn about every single state as there are too many to visit and hold in memory.\n\nInstead, we want to generalise by learning about a small number of states from \nexperience and then applying that knowledge to new, similar situations.\n\nEvaluation functions score non-terminal states in depth-limited search. The ideal \nfunction would return the actual minimax value of a position, however in practice \nwe use a weighted linear sum of features, ${eval}(s) = w_1f_1(s)+...+w_nf_n(s)$.\n\nUsing feature representation, a Q-function or value function can be written for any state.\n- Advantage: experience is summed up in a few numbers\n- Disadvantage: states may share features, but actually have very different values\nGeneralisation depends on how well we represent states using features.\n\n$Q(s,a) = w_1f_1(s,a)+...+w_nf_n(s,a)$\n\n**Q-learning with linear Q-functions**\n${transition} = (s,a,s',r)$\n${difference} = [r + \\gamma~\\underset{a'}{max}~Q(s',a')] - Q(s,a)$\nExact Q's given by: $Q(s,a) + \\alpha[{difference}]$\nApproximate Q's given by: $w_i \\leftarrow w_i + \\alpha[{difference}]f_i(s,a)$\n\nIntuition: adjust weights of active features, i.e. blame features that lead to a\n bad action and 'disprefer' all states with that state's features\n\nFormal justification: online least squares (covered in future)\n\nDoes not *always* converge to the optimal policy.\n\n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nReview on Probabilities\n\n##### Uncertainty\nProbabilistic reasoning provides a framework:\n- observed variables (evidence) - things agent knows about the world (e.g. sensor \nreadings, symptoms)\n- unobserved variables (states) - things agent needs to reason about (e.g. where \nan object is, disease present)\n- model - agent knows something about how known variables relate to unknown variables\n\nSimilar to logical assertions, probabilities are about possible worlds, but also \nquantify how likely a possible world is.\n\nPossible worlds = **sample space**; they are **mutually exclusive** and **exhaustive**.\n\nA probability model associates a probability $P(w)$ with each world $w$.\n\n##### Random Variables\nSome aspect of the world which may have uncertainty. Denoted by capital letters.\n\n##### Axioms of Probability\nProbability of any possible world is between $0$ and $1$:\n$0 \\leq P(w) \\leq 1$ for every $w$.\n\nTotal probability of the set of all possible worlds is $1$:\n$\\underset{w \\in \\Omega}{\\sum} P(w) = 1$\n\n---\nDistributions\n\n##### Probability Distributions\nUnobserved R.V.s have distributions; a table of probabilities of values.\nA probability is a single number, e.g. $P(w = \\text{rain}) = 0.1$.\nMust adhere to axioms: [[Review on Probabilities]]\n\n##### Joint Distributions\nJoint distributions over a set of R.V.s $X_1, ..., X_n$ specifies a real number \nfor each assignment or outcome.\nE.g. $P(X_1 = x_1, ..., X_n = x_n) = P(x_1, ..., x_n)$.\nHas an associated probability distribution, e.g. $P(T,W)$ equals some value.\nAgain, must adhere to axioms: [[Review on Probabilities]]\n\nSize of distribution for $n$ variables with domain size $d$: $d^n$.\nImpractical to write out!\n\n##### Probabilistic Models\nProbabilistic models are a joint distribution over a set of R.V.s.\n- random variables with *domains*\n- assignments called *outcomes*\n- joint distributions say whether assignments are likely\n- *normalised* (sum to $1$)\n- ideally: most variables independent\n\n##### Events\nAn event is a set $E$ of outcomes:\n$P(E) = \\underset{x_1...x_n \\in E}{\\sum} P(x_1...x_n)$\nCan calculate probability of any event, e.g. probability that it's hot and sunny,\n hot or sunny, just sunny...\n\n##### Marginal Distributions\nTypically only care about partial assignments, e.g. $P(T=hot)$.\nMarginal distributions are sub-tables which eliminate variables. Marginalization:\n combine collapsed rows by summing:\n$P(t) = \\underset{s}{\\sum} P(t,s)$.\n\n##### Conditional Probabilities\nSimple relation between joint and conditional probabilities:\n$P(a | b) = \\frac{P(a,b)}{P(b)}$\n\n##### Conditional Distributions\nProbability distributions over some variables given fixed values of others.\nCan calculate a set of conditional distribution tables from a joint distribution\n table.\n\n ---\nProbabilistic Inference and Rules\n\n##### Probabilistic Inference\nCompute a desired probability from other known probabilities, e.g. conditional from joint.\n\nUsually we compute conditional probabilities - represent agent's beliefs given the evidence.\nProbabilities change with new evidence - causes beliefs to be updated.\n\n##### Inference by Enumeration\nStructure:\n-  evidence variables: $E_1...E_k = e_1...e_k$\n-  query variable: $Q$\n-  hidden variables: $H_1...H_r$\nThese together form all variables $X_1, X_2,...,X_n$\n\nCalculate: $P(Q | e_1...e_k)$\n\nSteps:\n1. select entries consistent with evidence, $e_i$\n2. sum out $H$ to find joint of query and evidence, $P(Q,e_1...e_k)=\\underset{h_1...h_r}{\\sum} P(Q, h_1...h_r, e_1...e_k)$\n3. normalize, multiply by $\\frac{1}{Z}$ where $Z=\\underset{q}{\\sum} P(Q, e_1...e_k)$\n\n##### The Product Rule\nOpposite of inference by enumeration: construct probability distribution given \nconditional probability.\n\n$P(y)P(x|y) = P(x,y)$\n\n##### The Chain Rule\nMore generally, can write any joint distribution as an incremental product of \nconditional distributions.\n\n$P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$\n$P(x_1,x_2,...x_n) = \\underset{i}{\\Pi}~P(x_i|x_1...x_{i-1})$\n\n##### Bayes' Rule\nTwo ways to factor a joint distribution over two variables:\n$P(x,y) = P(x|y)P(y) = P(y|x)P(x)$\nDividing gives:\n$P(x|y) = \\frac{P(y|x)}{P(y)} P(x)$\n\nReasons why it's helpful:\n- build one conditional from its reverse\n- one conditional may be difficult, the other simple\n- foundation of many systems, e.g. ASR, MT\n\n---\nProbabilistic Language Models\n\n##### Probabilistic Language Models\nOne goal: assign probability to a sentence or sequence of words\nE.g. keyboard auto-complete, machine translation, spelling correction, speech recognition\n\nRelated task: probability of upcoming word.\n\nModel that computes either is called a **language model (LM)**.\n\nComputing the probability of a given sentence (or probability of next word) can be\n accomplished through the chain rule.\n\nJoint probability of words in a sentence:\n$P(w_1,w_2,...w_n) = \\underset{i}{\\Pi}~P(w_i|w_1...w_{i-1})$\n\nEstimating these probabilities can be done by **maximum likelihood estimation (MLE)**:\n e.g. $P(\\text{won}|\\text{the underdog team}) = \\frac{\\text{count(the underdog team won)}}{\\text{count(the underdog team)}}$\n\nProblem is some sentences may never appear in a corpus. Needs huge datasets; inefficient.\n Many different ways of combining words.\n\nSimplifying assumption: **Markov assumption**. Only depends on previous $k$ words, \nnot entire context. Therefore $P(w_1,w_2,...w_n) \\approx \\overset{n} {\\underset{i}{\\Pi}}~P(w_i|w_{i-k}...w_{i-1})$.\nNow can use MLE.\n\nHistory count:\n- unigram: no history\n- bigram: 1 word as history\n- trigram: 2 words\n- 4-gram: 3 words\n- n-gram: n-1 words\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\nReview on Independence\n\nIn Bayes' Nets, we're making independence assumptions based on interaction of variables\n in a model.\n\nIndependence is given by:\n$\\forall x,y : P(x,y)=P(x)P(y)$, or $X \\perp Y$\n\nConditional independence is given by:\n$\\forall x,y,z : P(x,y|z)=P(x|z)P(y|z)$, or $X \\perp Y|Z$\nEquivalently:\n$\\forall x,y,z : P(x|z,y)=P(x|z)$\n\n---\nBayes Net Properties\n\n##### Bayes Nets Assumptions\nAssumptions we are required to make to define Bayes' nets when given a graph: $P(x_i|x_1...x_{i-1})\n = P(x_i|\\text{parents}(X_i))$\nThere are often additional conditional independences that can be read off the graph.\nWe must understand the assumptions made when choosing a graph.\n\n##### Casual Chain\nTo prove conditional independence in a **casual chain**, we can substitute our Bayes\n assumption into the re-written full joint probability equation.\nEvidence along a chain blocks the influence, i.e. the immediate cause is \"stronger\"\n than earlier causes.\n\n##### Common Cause\nSimilar to previous; must prove using substitution of assumption.\nObserving the cause blocks influence between effects. \nOn the other hand, *not knowing* the cause can give an effect an indication of the\n likelihood of the other effects.\n\n##### Common Effect\nCauses are not correlated so are independent, but still must prove. Not independent\n given the common effect because it puts the causes in *competition* with one another as explanation.\nThis is **backwards** from other two cases! Observing an effect activates influence\n between possible causes.\n\n---\nReachability & Path\n\nA BN can be broken into repetitions of the three cases in [[Bayes Net Properties]]\n to check independence.\n\nWe check if two variables are conditionally independent by their reachability \nand whether or not they are blocked by one of the three cases.\n\n\n##### Active vs. Inactive Paths\nA path if active if each triple is active:\n- Casual chain: $A \\rightarrow B \\rightarrow C$, where $B$ is *unobserved*\n- Common cause: $A \\leftarrow B \\rightarrow C$, where $B$ is *unobserved*\n- Common effect: $A \\rightarrow B \\leftarrow C$, where $B$ or one of its descendants\n is *observed*\n\nA single inactive segment can block a path.\n\nActive = dependence. Inactive = conditional independence.\n\n---\nD-Separation Algorithm\n\nIf a path is active, there are no guarantees about independence. On the other hand,\n an inactive path between variables is conditionally independent.\n\n**If all paths are inactive then independence is guaranteed.**\n\nRefer to diagram.\n\n---\nInference\n\nInference: calculating some useful quantity from a joint probability distribution.\n\nExamples: posterior probability; most likely explanation.\n\n---\nCan perform inference by enumeration on a Bayes' net, similar to [[Probabilistic \nInference and Rules]]. \n\nHowever, this is computationally expensive as the probabilities are exponential \nin the unobserved (hidden) variables; we need to join up the whole joint distribution\n before summing out hidden variables.\n\nAdvanced technique to solve this is variable elimination: interleave joining and \nmarginalization. Still NP-hard, but much faster.\n\n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\nClassification Task\n\n##### Machine Learning\nHow to acquire a model from data/experience:\n- learning parameters, e.g. probabilities\n- learning structures, e.g. Bayes nets\n- learning hidden concepts, e.g. clustering\n---\nFinite sets of classes are called classification. Real-numbered predictions are \ncalled regression.\n\nProblem: spam classification\n- input: email (labeled appropriately)\n- output: spam/not spam\nWant to learn a function that takes a new email and predicts a class. The email is \ntransformed into a vector of which elements correspond to a feature.\n\nProblem: digit recognition\n- input: images/pixels grids (labeled appropriately)\n- output: a digit of 0-9\nWant to learn a function that predicts labels of new, future digit images.\n\nTo summarise, classification: given inputs x, predict labels y\n\nExamples:\n- spam detection\n- OCR\n- medical diagnosis\n- essay grading\n- fraud detection\n- customer service email routing\n---\n##### Model-based Classification\nModel-based approach:\n- build a model (e.g. Bayes net) where both the label and features are random variables\n- instantiate observed features\n- query for the distribution of the label conditioned on the features \n\nChallenges:\n- structure of BN\n- learning parameters\n\nCan use a technique such as inference by enumeration or variable elimination to get\n information about query variable.\n\n---\nNaïve Bayes\n\n##### Naïve Bayes\nAssume all features are independent effects of the label.\n\nModel: $P(Y,F_{1}...F_{n}) = P(Y)~ \\underset{i}{\\Pi}~P(F_{i}|Y)$\nwhere $F_i$ is a feature representing the input.\n\nFull joint distribution would have $|Y| \\times |F|^n$ values ($n$ = number of \nfeatures, $|F|$ = domain of feature), whereas the NB model only has $n \\times |F| \n\\times |Y|$ parameters.\n\nAdvantages:\n- only need to specify how each feature depends on class\n- total number of parameters is *linear* in the number of features\n\nDisadvantages:\n- very simplistic (due to independence assumptions), but often works anyway!\n\n---\n##### Inference for NB\nGoal: compute posterior distribution over label variable Y: $P(Y|f_1...f_n)$\n\nInference method.\nSteps:\n1. get joint probability of label and evidence for each label\n$P(Y,f_1...f_n) = [P(y_1,f_1...f_n),..., P(y_k,f_1...f_n)] \\rightarrow [P(y_1)~ \n\\underset{i}{\\Pi}~P(f_i|y_1),..., P(y_k)~ \\underset{i}{\\Pi}~P(f_i|y_k)]$\n2. sum out classes in step 1 to get probability of evidence\n$P(f_1...f_n)$\n3. normalize by dividing step 1 by step 2\n$P(Y|f_1...f_n)$\n\n---\nEstimates of local conditional probability tables:\n- $P(Y)$ - prior over labels\n- $P(F_i|Y)$ for each feature - evidence variable\n- Collectively called parameters, $\\theta$\n\n---\nBasic Concepts on ML\n\nData: labeled instances, e.g. emails marked spam/ham\n- training set\n- held out set (also known as development set)\n- test set\n\nFeatures: attribute-value pairs which characterize each x\n\nExperimentation cycle:\n- learn parameters, e.g. model probabilities, on training set\n- (tune hyper-parameters on held-out set)\n- compute accuracy of test set\n- important: never peek at the test set!\n\nEvaluation:\n- accuracy: fraction of instances predicted correctly\n\nOverfitting and generalisation:\n- overfitting: fitting the training data very closely, but not generalising well\n- relative frequency parameters will overfit the training data\n- can't give unseen events $0$ probability\n- to generalise better: smooth or regularize estimates\n\n---\n##### Parameter Estimation\nEstimating the distribution of a random variable:\n- elicitation: ask a human expert\n- empirically: use training data\n\t- e.g. for each outcome x, look at the empirical rate of that value - maximum \n  likelihood estimation, $P_{\\text{ML}}(x) = \\frac{\\text{count}(x)}{\\text{total samples}}$\n\t\tAssignment of probabilities produces a $\\theta$.\n\t- this is the estimate that maximizes the likelihood of the data, $L(x,\\theta) = \\underset{i}{\\Pi} P_{\\theta}(x_i)$\n\n##### Maximum Likelihood\nRelative frequencies are the max likelihood estimates:\n$\\theta_{\\text{ML}} = \\underset{\\theta}{\\text{argmax}}P(X|\\theta) = \\underset{\\theta}{\\text{argmax}}~\\underset{i}{\\Pi}~P_\\theta(X_i)$ \n(where X is data)\n$\\rightarrow P_{\\text{ML}}(x) = \\frac{\\text{count}(x)}{\\text{total samples}}$\n\nProblem with this is unseen events.\n\n##### Laplace Smoothing\nLaplace's estimate: pretend you saw every outcome once more than you actually did\n$P_{\\text{LAP}}(x) = \\frac{c(x)+1}{\\sum_x[c(x)+1]} = \\frac{c(x)+1}{N+|X|}$\n\nLaplace's estimate (extended): pretend you saw every outcome $k$ more times than \nyou actually did\n$P_{\\text{LAP}}(x) = \\frac{c(x)+k}{N+k|X|}$\nand for conditionals:\n$$P_{\\text{LAP}}(x|y) = \\frac{c(x,y)+k}{c(y)+k|X|}$$\n\nSet $k$ to tune hyper-parameter.\n\n##### Linear Interpolation\nLaplace performs poorly for $P(X|Y)$ when $|X|$ or $|Y|$ are very large.\n\n$$P_{\\text{LIN}}(x|y) = \\alpha \\widehat{P}(x|y) + (1-\\alpha)\\widehat{P}(x)$$\n$\\widehat{P}$ is the observed max likelihood estimator.\n\nSet $\\alpha$ to tune hyper-parameter.\n\n##### Tuning\nNeed to set: \n- parameters: probabilities $P(X|Y), P(Y)$\n- hyper-parameters: the amount/type of smoothing, $\\alpha, k$\n\nLearn parameters from training data and for each value of the hyper-parameters, \ntrain and test on held-out data. Choose the best value and perform final test on test data.\n\n##### Features\nAdd more features if there are are errors in model.\n\n##### Baselines\nFirst step: get a baseline - simple \"straw man\" procedures help determine how hard\n the task is and how good accuracy is.\nWeak baseline: most frequent label classifier - gives all test instances whatever\n label was most common in training set; accuracy might be high if problem is skewed.\nReal research uses previous work as baseline.\n\n---\nPerceptron\n\n![[perceptron.png]]\n\nPerceptrons for decision making: device that makes decisions by weighing up evidence.\n\n**Notational changes**\n1. $$\\sum_j~w_jx_j \\equiv \\boldsymbol{w} \\cdot \\boldsymbol{x}$$\n\n2. $b \\equiv -\\text{threshold}$, therefore\n$$\\text{output} = \n\\begin{cases}\n0~\\text{if}~\\boldsymbol{w} \\cdot \\boldsymbol{x} + b \\leq 0 \\\n1~\\text{if}~\\boldsymbol{w} \\cdot \\boldsymbol{x} + b > 0\n\\end{cases}$$\nwhere $b$ is the bias. \n\nBias determines how easy it is for the perceptron to *fire*.\n\n---\n**Learning weights from examples**\nInputs can be thought of as *features* representing something we want to classify.\n Feature values for inputs are fixed, but we can choose different weight vectors, \n which change the classifier.\n\n---\n##### Learning: Binary Perceptron\n- start with weights $0$\nFor each training instance:\n- classify with current weights\n- if correct, i.e. $y=y*$, no change!\n- if wrong: adjust weight vector by adding or subtracting the feature vector. Subtract if $y* = -1$.\n- $\\boldsymbol{w} = \\boldsymbol{w} + \\boldsymbol{y^*} \\cdot \\boldsymbol{f}$\n\n---\n##### Multiclass Decision Rule\nIf we have multiple classes:\n- a weight vector for each class: $w_y$\n- score (activation) of class $y$: $w_y \\cdot f(x)$\n- prediction highest score wins: $y = \\text{argmax}_y~w_y \\cdot f(x)$\n\n##### Learning: Multiclass Perceptron\n- start with weights $0$\n- pick up training examples one by one\n- predict with current weights: $y = \\text{argmax}_y~w_y \\cdot f(x)$\n- if correct, no change!\n- if wrong, lower score of wrong answer: $w_y = w_y - f(x)$\nand raise score of right answer: $w_{y*} = w_{y*} + f(x)$\n\n---\nImprovements on Perceptrons and SVM\n\n##### Properties of Perceptrons\n- separability: true if some parameters get the training set perfectly correct\n- convergence: if the training is separable, perceptron will eventually converge (binary case)\n- mistake bound: the maximum number of mistakes (binary case) related to the *margin*\n or degree of separability $\\delta$: $\\text{mistakes} < \\frac{k}{\\delta^2}$\n\n##### Problems with Perceptrons\n- noise: if the data isn't separable, weights might thrash. Averaging weights over\n time can help (average perceptron)\n- mediocre generalization: finds a barely separating solution\n- overtraining (a type of overfitting): test/held-out accuracy usually rises, then\n falls - early-stopping can help\n\n##### Fixing Perceptrons\nIdea: adjust weight update to mitigate these effects\nMIRA = Margin Infused Relaxed Algorithm\nE.g. guessed $y$ instead of $y^*$ on example $x$ with features $f(x)$:\n$w_y = w'_y - \\tau f(x), w_{y^*} = w'_{y^*} + \\tau f(x)$\nChoose an update size that fixes current mistake, but minimises the change to $w$:\n$$\\tau = \\frac{(w'_y - w_{y^*} \\cdot f + 1)}{2f \\cdot f}$$\n\nIn practice, it's bad to make updates that are too large: example may be labeled\n incorrectly, may not have enough features.\nSolution: cap the max possible value of $\\tau$ with some constant $c$:\n$$\\tau^* = \\min \\left( \\frac{(w'_y - w_{y^*} \\cdot f + 1)}{2f \\cdot f}, c \\right)$$\nCorresponds to an optimization that assumes non-separable data, usually converges\n faster, and better on noisy data.\n\n---\n##### Support Vector Machines\nMax. the margin: good according to intuition, theory, practice.\nOnly support vectors matter; other training examples are ignorable.\n*Support vector machines (SVMs)* find the separator with max margin.\nSVMs are MIRA where you optimise over all examples at once.\n\n---\n##### Non-Linear Separators\nGeneral idea: original (linearly non-separable) feature space can always be mapped\n to some higher-dimensional feature space where the training set is separable:\n$\\Phi: x \\rightarrow \\phi(x)$\n(known as kernel trick)\n\n---\n##### Summary\nNaïve Bayes:\n- builds a model of training data\n- gives prediction probabilities\n- strong assumptions about feature independence\n- one pass through data (counting and smoothing)\n\nPerceptrons / MIRA:\n- makes less assumptions about data\n- mistake-driven learning\n- multiple passes through data (prediction)\n- often more accurate\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\nLogistic Regression\n\n**Logistic regression** is another type of classifier (supervised ML).\n\n##### Classifier Components\nClassifiers require a training corpus of $M$ observations of input/output pairs \n$(x^{(i)}, y^{(i)})$.\n1. **Feature representation** of the input - for each input observation $x^{(i)}$\n there is a vector of features $[x_1,x_2,...,x_n]$.\n2. **Classification function** - computes estimated class $\\hat{y}$ via $p(y|x)$.\n3. **Objective function** for learning - involves minimizing error on training examples.\n4. **Optimization** algorithm - optimize the objective function.\n\n##### Sentiment Classifier\nFor sentiment classification, consider a feature representation of an input. The\n classifier output can be $1$ (positive) or $0$ (negative). Want to estimate $P(Y=1|x)$.\nLogistic regression gives:\n$$z= \\sum_i w_i x_i + b$$\nwhich can also be written as:\n$$z = \\boldsymbol{w} \\cdot \\boldsymbol{x} + b$$\nwhere $b$ is bias.\n\n##### Sigmoid (logit) function \n$y=\\frac{1}{1+e^{-z}}$ is used to produce $z$ output between $0$ and $1$. Hence\n$$P(Y=1)=\\sigma (\\boldsymbol{w} \\cdot \\boldsymbol{x} + b)= \\frac{1}{1+e^{(\\boldsymbol{w}\n \\cdot \\boldsymbol{x} + b)}}$$\nTherefore in binary output, $P(Y=0) = 1 - \\sigma (\\boldsymbol{w} \\cdot \\boldsymbol{x} + b)$.\n\n##### Decision boundary\n$$\\hat{y} = \n\\begin{cases} \n1~\\text{if}~P(Y=1|x) > 0.5 \\\n0~\\text{otherwise}\n\\end{cases}$$\n\n##### Extracting features\nFeature engineering: select features that represent examples. E.g. count positive/negative\n lexicons, pronouns, binary features (!, \"no\"), word count.\n\nOnce feature values have been calculated, assign weight to importance of each.\n\nFinally, calculate $z$ and apply $\\sigma$.\n\n##### Learning in logistic regression\nRequire two components to learn weights and bias (parameters) of model:\n1. Objective / **loss function** that gives *distance* between system output and\n gold (human) output; will use **cross-entropy loss**.\n2. Algorithm for optimizing (minimizing) objective/loss function; will use \n**stochastic gradient descent**.\n\n---\nLoss Function\n\n##### Loss functions\nDetermine how close the classifier output $\\hat{y}$ for an observation $x$ is to \nthe correct output $y$.\n$$L(\\hat{y}, y) = \\text{how much}~\\hat{y}~\\text{differs from true}~y$$\nExample is mean squared error (not great for probabilistic classification as it \nis non-convex):\n$$L_{MSE}(\\hat{y}, y) = \\frac{1}{2} (\\hat{y}-y)^2$$\n\nBetter loss function for probabilistic classification:\n- prefers the correct (gold) class labels of the training example to be more likely.\n- conditional max likelihood estimation: choose parameters $w,b$ that max the (log)\n probabilities of the true (gold) labels in training data.\n- resulting loss function is the negative log likelihood loss, known as **cross entropy\n loss**.\n---\nFor observation $x$, want to max the probability of the correct label $p(y|x)$:\n$$p(y|x)= \\hat{y}^y(1-\\hat{y})^{1-y}$$\nIf $y=1$ then $p(y|x) = \\hat{y}$ <- as high as possible .\nIf $y=0$ then $p(y|x)= 1-\\hat{y}$ <- $\\hat{y}$ as low as possible.\n\nThen change to logs:\n$$\\log p(y|x)= \\log [\\hat{y}^y(1-\\hat{y})^{1-y}] = y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})$$\nThis maximizes the probability, but for loss functions we want to minimize so we \nchange the sign.\n\nHence the resulting cross-entropy loss:\n$$L_{CE}(\\hat{y}, y) = - \\log p(y|x)= - [y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})]$$\nFinally, plug in the definition for $\\hat{y}$:\n$$L_{CE}(\\hat{y}, y) = - [y \\log \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b) + \n(1-y) \\log (1 - \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b))]$$\n\nIf prediction is **correct**, then CE loss is **lower**.\nIf prediction is **incorrect**, then CE loss is **higher**.\n\n##### Loss on all training examples\n$$\\log p(\\text{training labels}) = \\log \\Pi_{i=1}^{m} p (y^{(i)}|x^{(i)}) \\ \n= \\sum_{i=1}^{m} \\log p (y^{(i)}|x^{(i)}) \\\n= - \\sum_{i=1}^{m} L_{CE} (\\hat{y}^{(i)}|y^{(i)})$$\n\n---\nStochastic Gradient Descent\n\nWe use gradient descent to find good settings for our weights and bias by min the \nloss function:\n$$\\hat{\\theta} = \\underset{\\theta}{\\text{argmin}}~\\frac{1}{m} \\sum_{i=1}^{m}~L_{CE}(y^{(i)}, x^{(i)}; \\theta)$$\n\n**Gradient descent** is a method that finds a min of a function by figuring out in \nwhich direction (in the space of parameters $\\theta$) the function's slope is rising the\n most steeply and moving in the opposite direction.\n\nFor logistic regression, this loss function is **convex** such that it only has one\n minimum so there is no local minima to get stuck in. Hence it is guaranteed to the\n  find the minimum.\n\nThe magnitude of the amount to move is the value of the slope weighted by a learning\n rate $\\eta$.\nA higher/faster learning rate means we should move $w$ more on each step.\n$$w^{t+1} = w^t - \\eta \\frac{d}{dw} f(x;w)$$\n---\n##### The Gradient\nTo update $\\theta$, we need a definition for the gradient $\\nabla L(f(x, \\theta), y)$.\nFor logistic regression, the cross entropy [[Loss Function]] is\n$$L_{CE}(\\hat{y},y) = - [y \\log \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b) + \n(1-y) \\log (1 - \\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b))]$$\n\nThe derivative of this function for one observation vector $x$ for a single weight $w_j$ is\n$$\\frac{\\delta L_{CE}(w,b)}{\\delta w_j} = [\\sigma(\\boldsymbol{w} \\cdot \\boldsymbol{x} + b) - y]x_j$$\nI.e. the difference between the true $y$ and our estimate for $x$ multiplied by the\n corresponding input $x_j$.\n\nAverage loss:\n$$\\text{cost}(w,b) = \\frac{1}{m} \\sum_{i=1}^{m} L_{CE}(\\hat{y}^{(i)}, y^{i})$$\n$$= - \\frac{1}{m} \\sum_{i=1}^{m} y^{(i)} \\log \\sigma(w \\cdot x^{(i)} + b) + (1-y^{(i)})\n \\log (1-\\sigma(w \\cdot x^{(i)} + b))$$\nThis is what we want to minimize.\n\nThe loss for a batch of data or an entire data set is just the average loss over \nthe $m$ examples.\n\nThe gradient for multiple data points is the sum of the individual gradients:\n$$\\frac{\\delta \\text{cost}(w,b)}{\\delta w_j} = \\sum_{i=1}^{m} [\\sigma(\\boldsymbol{w}\n \\cdot x^{(i)} + b) - y^{(i)}]x_j^{(i)}$$\n\nExample\n1. ![[Pasted image 20211127154605.png]]\n2. ![[Pasted image 20211127154637.png]]\n3. ![[Pasted image 20211127154709.png]]\n\n---\n##### Mini-batch training\n**Stochastic** gradient descent chooses a **single random example** at a time and\n updates its weights on that example, therefore updates can fluctuate.\nInstead, **batch training** computes the gradient over the entire dataset which gives\n a much better estimate of which direction to move the weights, but it takes a long\n  time to compute.\nA compromise is **mini-batch training** where we train a small batch whose size is\n determined by computational resources. All examples in the batch can be processed\n  in parallel and the loss accumulated.\n\n---\n##### Regularization\n**Overfitting** is a problem in logistic regression: if a feature only occurs in\n one class it will get a high weight.\nRegularization penalises large weights by adding a term to the loss function:\n- Lasso regression uses L1 regularization\n- Ridge regression uses L2 regularization\n\n---\n##### Multinomial logistic regression\nOften want more than two (binary) classes and want to known probability $y$ for \neach class $c \\in C, p(y=c|x)$.\nTo get proper probability, we use a generalization of the sigmoid function called\n the **softmax function**:\n$$\\text{softmax}(z_i) = \\frac{e^{z_i}}{\\sum_{j=1}^{k}e^{z_j}}, 1 \\leq i \\leq k$$\n\nSoftmax takes in an input vector $z=[z_1,z_2,...,z_k]$ and outputs a vector of values\n normalized into probabilities.\n\n---\nNeural Networks\n\n##### Sigmoid neurons\nProblem: a small change in weights or bias of any single perceptron in the network\n can cause the output to completely flip from $0$ to $1$.\nSolution: sigmoid neuron.\n\nSmoothness of $\\sigma$ means small changes on the weights $w_j$ and bias $b$ will\n produce a small change in the output of the neuron.\n\n##### Activation functions\nThere are three commonly used non-linear functions used for the activation function $f$:\n- sigmoid function\n- tanh function\n- rectified linear unit (ReLU)\n\n##### Feed-forward Neural Network\nSimplest kind of NN. **Multilayer** network where all units are usually **fully-connected**\n and no cycles.\nThe outputs from each layer are passed to units in the next higher layer. No outputs\n are passed back to lower layers.\n\n---\n##### Training NN\nWant to learn best parameters for the NN to make its predictions $\\hat{y}$ as close\n as possible to the gold standard labels in the training data $y$. Require:\n- loss function: cross-entropy loss\n- optimization algorithm: gradient descent\n- a way to compute the gradient of the loss function: error propagation\n\n##### Cross-entropy loss\nIf the NN is a binary classifier with a sigmoid function at the final layer, the \n[[Loss Function]] is exactly the same as logistic regression.\n\nFor multinomial regression:\n$$L_{CE}(\\hat{y}, y) = - \\sum_{i=1}^{C} y_i \\log \\hat{y}_i$$\n\nIf there is only one correct answer, where the truth is $y_i=1$ then this simplifies to\n$$L_{CE}(\\hat{y}, y) = - \\log \\hat{y}_i$$\n\nPlugging into softmax:\n$$L_{CE}(\\hat{y}, y) = - \\log \\frac{e^{z_i}}{\\sum_{j=1}^{k}e^{z_j}}$$\n\n##### Computing the gradient\nLogistic regression can be through of as a network with just one weight layer and\n a sigmoid output. See [[Stochastic Gradient Descent]].\n\nBut these derivatives only give the correct updates for the last weight layer. For\n deeper networks, we need to look back through all earlier layers, even though loss\n  is only computed with respect to the output. Solution: error backpropagation algorithm.\n\n##### Computation graphs\nRelated to general **backward differentiation** procedure which depends on **computation graphs**\n - represents process of computing a mathematical expression and broken down into separate operations.\n  Each operation is a node in a graph - use **forward pass** to calculate.\n\n##### Backward differentiation\n**Backward pass** used to compute the derivatives needed for the weight update. Computing\n the derivative of the output function with respect to the inputs via the chain rule (from calculus).\n\n*Calculate partial derivative at each node and pass back.*\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\nNeural Language Models\n\nSeveral advantages over n-gram LMs:\n1. Don't need smoothing\n2. Handle much longer histories\n3. Generalise over contexts of similar words\n4. Tend to have much higher predictive accuracy than n-grams LMs\n\nDisadvantage: slower to train.\n\n---\nHow they work:\n1. Associate each words in the vocabulary with a vector-representation, thereby \ncreating a notion of similarity between words\n2. Express the joint probability function of an input word sequence in terms of \nword vectors\n3. Learn the word vectors and parameters of the function\n\nWord vectors are low-dimensional (30 to 100) dense vectors.\n\nProbability function is expressed using the product of conditional probabilities \nof the next word given the previous word using multi-layer, feed forward neural \nnetworks.\n\n---\nStructure:\n**Input** = k-gram of words $w_{1:k}$.\n**Output** = probability distribution over the next word.\nThe $k$ context words are treated as a word windows. Each word is associated with \nan embedding vector.\nInput vector $\\mathbf{x}$ concatenates $v(w)$ for each of the $k$ words:\n$$v(w) \\in \\mathbb{R}^{d_w}$$\n$$\\mathbf{x} = [v(w_1); v(w_2); ...; v(w_k)]$$\n\n---\nTraining:\nTraining examples are word k-grams from the corpus.\nThe identities of the first $k-1$ words are features and the last word is the target\n label for the classification.\nModel is trained using cross-entropy loss.\n\n---\nN-grams construct tables to look up probability of seeing a word given a history. \nHowever, tables only store observed sequences. \n\nProblem arises when we have a new unseen combination of words. This was solved using\n back-off and smoothing/interpolation.\n\nAlternate idea: generalisation.\nIntuition: take a sentence and use it when assigning probabilities to similar sentences.\n\n1. Use a vector space model: words are vectors with real values $\\mathbb{r}^m$ with $d=30,\n 60, 100$ dimensional vector lengths. This computes word similarity.\n2. Define probability function that returns a joint probability of words in a sequence\n based on sequence of these vectors.\n3. Learns word representations and probability function from data at the same time.\n\n---\nWord embeddings: when the dimension of word vectors are reduced, the words group \ntogether intuitively.\n\n---\nLexical Semantic Model\n\n##### Word Meaning\nIn n-grams, words are represented as a string of letters or as an index in a vocabulary\n list.\nIdeally we want meaning representation to encode:\n- Synonyms\n- Antonyms\n- Connotations - words that are positive or negative\n- Semantic roles - words that are different parts of the same event and can portray\n the same meaning based on their position in a sentence\n- (Logical) entailment\n\nEntailment:\nPowerful machinery, but knowledge must come from somewhere else.\nE.g. WordNet is a lexical knowledge base created by researchers. Encodes synonyms\n for different meanings of a word and hypernym/holonyms - hyper is a generalization\n  (i.e. up the hierarchy) and holo is more specific (i.e. down the hierarchy).\n\n---\nVector Space Model\n\nVector space models do not allow for the same kind of operations as in a taxonomic model\n (e.g. WordNet), but they can scale and automatically extract knowledge about language from a corpus.\n\nWord similarity:\nMost words don't have many synonyms but they have a lot of similar words. Useful for\n applications like Q & A.\n\nDistributional hypothesis (Harris 1954):\nIf words A and B have almost identical environments, we can define them as synonyms.\n\nIntuition of distributional word similarity:\nHumans can guess what a word means from its context. Therefore two words are similar\n if they have similar word contexts.\n\n---\nHistory of vector space models:\nDeveloped in the SMART information retrieval system (Salton 1971). Each document in\n a collection is represented as a point in a space (vector in vector space). A user's\n  query is a pseudo-document and is represented as a point in the same space. Perform\n   IR by retrieving documents whose vectors are close together in space to the query\n    vector.\n\n---\n##### Term-Document Matrix\n- Column vector is a document.\n- Row vector represents a term.\n- Cell is how often that term occurred in that document.\n\nLength of document vectors is the size of vocabulary. Document vectors can be sparse.\n\nCan compare similarity of **documents** by comparing their column vectors. Some \ncommon tasks include:\n- retrieving/searching similar docs\n- plagiarism detection\n\nCompare similarity of **words** by comparing their row vectors.\n\nPlotting vectors in space allows comparison of word similarity. Euclidean distance\n between points doesn't work as placement depends on word frequency! Therefore we use\n  vector L2 normalization:\n1. Calculate vector length (L2 norm):\n$$||u|| = \\sqrt{\\sum_{i=1}^{n} u^2_i}$$\n2. Divide each by vector by length (L2 norm)\n\nTake cosine of angle between vectors to measure distance. L2 normalization is \"built-in\":\n$$1-\\frac{\\sum_{i=1}^{n} u_i \\times v_i}{\\sqrt{\\sum_{i=1}^{n} u^2_i} \\times \\sqrt{\\sum_{i=1}^{n} v^2_i}}$$\n\n---\n##### Term-Term Matrix\nAlso called term-context matrix.\n- Every word has a column *and* row vector.\n- Cell indicates how often word appears in a context window surrounding the other word.\n\nLength is now $|V|$ instead of number of docs.\n\nContext windows:\nOccur in windows of +/- 2 words, in same sentence and document. \n\nInstead, a window of words use more complex contexts since languages have long distance\n dependencies. Syntactic distributions used to define a word's context, e.g. similar words \nmodified and act upon the same set of words. \n\n**Dependency parsing** can be used to define a word's context through its syntactic\n distribution. DIRT is one example from Google.\n\nAlternates to counts:\nRaw word frequency is not a great measure as it's skewed towards the most frequent\n words (e.g. the, and; follows the zipf distribution) that may not be the most informative\n  to a given context. Therefore common to transform vectors using:\n- TF-IDF\nTerm frequency (word count) * inverse document frequency (1 / number of documents it\n occurred in)\n- or PPMI\n\n---\nWord Embedding\n\nSpare vs. dense vectors:\nCo-occurrence matrix (weighted by TF-IDF or mutual information)\n- long (length |V| = 50,000+)\n- sparse (most elements are 0)\n\nAlternative: learn vectors that are\n- short (length 200-1000)\n- dense (most elements are non-zero)\n\nTrain a classifier!\n1. Treat target word and neighbouring context as positive examples\n2. Randomly sample other words to get negative samples\n3. Use logistic regression to train classifier to distinguish between these two cases\n4. Use weights as embeddings\n\n##### Word2Vec\n- Learn embeddings as part of the process of word prediction\n- Train classifier to predict neighbouring words\n- Inspired by neural net language models\n- Thus learn dense embeddings for the words in the training corpus\n\nAdvantages: fast, easy to train (faster than SVD); available as package online\n\nNegative sampling:\nWant predictions of true surrounding words to be high; random noise words from vocabulary\n to be low.\n\nTraining using logistic regression results in accurate embeddings (nearest neighbour words).\n Also captures relational meanings.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}