{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other materials 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": "3f39916b-67c7-4658-e3eb-7bfed9dbe80f"
      },
      "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": 19,
      "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": "0fa72d0e-dd1c-47b8-d9b5-f1aaad60aadb"
      },
      "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": 20,
      "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": 21,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = r\"\"\"\n",
        "A decision-theoretic agent assigns a continuous range of values to goals and states so that it can pick \n",
        "a state even when no best state is available. \n",
        "\n",
        " $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n",
        " * $P(s'|s,a)$ = Probability that action a in state s reaches state s'\n",
        " * $P(\\textnormal{RESULT}(a)=s')$ = Probability of reaching s' by doing action a in the curent state\n",
        " * $P(s)$ = Probability of state s\n",
        "\n",
        "\n",
        " $EU(a) = sum_{s'}P(\\textnormal{RESULT}(a)=s')U(s')$\n",
        "\n",
        " Principle of Maximum Expected Utility = rational agent should choose the action that maximizes the agents's expected utility \n",
        " * $action = argmax_a EU(a)$\n",
        "\n",
        "\n",
        " The MEU Principle formulizes the notion that an intelligent agent should do the right now but not how to operationalize that notion. \n",
        " Estimating the probability distribution P(s) requires perception, learning, knowledge representation, and infernece. To get $P(\\textnormal{RESULT}(a)=s')$ \n",
        " you need to know a casual model of the world. Computing the utilities (U(s')) requires searching or planning since an agent doesn't know how good that future \n",
        " state might be until to knows where it can get to from that state. There might be some uncertainty about the utility function if the computer does \n",
        " not know the human's true utility function. Decision theory might not be the end all to AI, but it provides the beginnings of the general mathematical \n",
        " framework to define the AI problem. MEU has a clear relation to the idea of performance measures. \n",
        "\n",
        " *If an agent acts so that it maximizes a utility function that reflects the performance measure, then the agent will achieve the highest possible performance score \n",
        " (averaged over all possible environments)*\n",
        "\n",
        " Performance measure gives a score for history (sequence of states). Utility function applies to the next state and can be used to guide actions step by step. \n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 =  \"\"\"\n",
        "Axioms of Utility Theory\n",
        "* Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equality preferable. (Deciding cannot be avoided.)\n",
        " * Exactly one of $(A>B), (B>A)$ or $(A~B)$ holds\n",
        "* Transitivity: Given any three lotteries, if an agent prefernece A to B and prefers B to C, then the agent must prefer A to C.\n",
        " * $(A>B) \\lor (B>C) \\implies (A>C)$\n",
        "* Continuity:If some lottery B is between A and C in preference, then there is some probability p where the rational agent will be indifferent between getting B \n",
        "for sure and the lottery that yields A with probability p and C with probability 1-p.\n",
        " * $A>B>C \\implies \\exists p [p, A; 1-p, C]~B$\n",
        "* Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same \n",
        "expect that B is substituted for A in one of them. \n",
        " * $A~B \\implies [p, A; 1-p, C] ~ [p, B; 1-p, C]$\n",
        "* Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then it must prefer the lotter with the higher \n",
        "probability for A.\n",
        " * A>B \\implies (p>q \\iff [p, A; 1-p, B] > [q, A; 1-q, B])\n",
        "* Decomposability: Compound lotteries can be reduced so simplier ones using laws of probability. (aka. \"no fun in gambling\" rule)\n",
        " * $[p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C]$\n",
        "\n",
        "\n",
        "If an agent violates any of the axioms of Utility Theory, then it can be proved they are irrational. \n",
        "These are really axioms of preferences, they don't say anything about a utility function.\n",
        "\n",
        "From the axioms of utility, the following consequences can be derived:\n",
        "* Existence of Utility Function:If an agent's preference obey the axioms of utility, then there exists a function U such that U(A)>U(B) iff A is preferred to B, \n",
        "and U(A)=(B) iff the agent is indifferent between A and B.\n",
        "** $U(A)>U(B) \\iff A>B$ and $U(A)=U(B) \\iff A~B$\n",
        "* Expected Utility of a Lottery: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n",
        "** $U([p1, S1; ...; pn, Sn]) = \\sum_i{piU(Si)}$\n",
        "** The utility of a compound lottery involving possible outcome states is completely determined once the probabilities and utilities of the outcome states are specified, . \n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "First we need to work out what the human's utility function is. We can use preference elicitation to do this. Establish a scale to use for comparison of utility values by \n",
        "fixing the utilities of any two outcomes (same idea as setting the temp for boiling and freezing). Usually we fix the best possible prize ($U(S)= u_\\perp$) and worst possible catastrophe \n",
        "($U(S)= u_\\bot$) with finite values. Then, using a standard lottery, we find at what point probability p needs to be at where the agent is indifferent between S and the standard \n",
        "lottery. Example: Want to find out how much a fan values getting to the semi-final and losing. Compare standard lottery with probability p of winning the trophy to probability 1-p \n",
        "to fail to quality. If indifference is at 0.3, this is the value of reaching the semi-final and losing.   \n",
        "\n",
        "It is helpful to establish some scale that utilities can be recorded and compared for a problem. A scale can be established by fixing utilities of any \\\n",
        "two particular outcomes. Typically this is the (finite) utility for a best possible price and worst possible catastrophe. We would ask the agent to \\\n",
        "choose between S and a standard lottery and adjust the probability until the agent is indifferent between them. Tehn we can determine the prizes for all \\\n",
        "lotteries involved. These values can be used to put value and decide on tolerants for risk. Aircraft are not serviced after every flight, analysis for \\\n",
        "deciding the value of a childs life vs removing asbestos from the school. \n",
        "\n",
        "Utility theory has roots in economics. Say if you had 1mil you could take now vs flipping a coin and you get 2.5mil if it is tails and nothing if it is \\\n",
        "heads. The EMV would benefit the coin flip, but that isn't necessarily the best decision. It would be dependent on your current financial wealth. A \\\n",
        "millionnaire would most likely have a utility function that is linear over a range of a couple million and would be more likely to take the gamble. \\\n",
        "The utility of money is almost exactly proportional to the log of the amount. Most people would accept \\$400 (certainty equivalent) in lieu of a chance at \\\n",
        "\\$1000 or \\$0, even though the EMV is \\$500. Difference between EMV and certainty equivalent is the insurance premium. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "If a fully observable environment were deterministic, the solution would be straightfoward, but actions are unreliable in a stochastic environment. The outcome \n",
        "of the transsition model is stochastic, so it is represented as a probability $P(s'|s,a)$ and transitions are assumed to be Markovian. The decision problem is \n",
        "sequential so the utility function will depend on the environment history instead of a single state. For every transsition, the agent will receive a reward $R(s,a,s')$. \n",
        "Reward may be positive or negative. This problem is known as a Markov Decision Process (MDP). These consist of...\n",
        "* set of states (with initial state s0)\n",
        "* set of ACTIONS(s) for each state\n",
        "* transition model $P(s'|s,a)$\n",
        "* reward function $R(s,a,s')$\n",
        "\n",
        "\n",
        "Methods for solving MDPs using invovle dynamic programming. Since there cannot be a single solution to the problem, the solution is a policy. The agent will know what \n",
        "to do based on what the policy says. Given an optimal policy, the agent decides what to do based on their current percept (defining their current state) and then executes \n",
        "the actions provided from $\\pi*(s)$. The policy represents the agent function explicitly, resulting in a simple reflex agent. For a state, there can be multiple optimal \n",
        "policies. The balance of risk and reward is determined by the rewards from the transition function as the agent moves to non-terminal states. Since MDPs include uncertainty, \n",
        "they are closer to real world problems than deterministic search problems. \n",
        "\n",
        "Policies for infinite horizon cases are simplier than for finite horizons since they do not have to act differently depending on the time.\n",
        "\n",
        "If $\\gamma$ is close to 0, rewards in the distant future are insignificant; if $\\gamma$ is close to 1, agent can wait for more long-term rewards. If $\\gamma=1$, then rewards \n",
        "are purely additive. Additive rewards make sense since living beings tend to prefer now instead of later. For money, it is better to get it sooner than later because gains \n",
        "can be reinvested. There is also uncertainty about true rewards in the future, they might not come for some reason. Discounted rewards allows us to make the utility of an \n",
        "infinite sequence finite and bounded by a maximum, that way we are not trying to compare two $+\\inf$ utilities.  \n",
        "\n",
        "\n",
        "The Bellman Equation: $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n",
        "* the utility of a state is the expected reward for the next transistion plus the discounted utility of the next state, assuming that the agent chooses the optimal action\n",
        "\n",
        "\n",
        "Action-utility function (Q-function): $U(s)=max_a Q(s,a)$ where $Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q(s',a')]$\n",
        "* Q(s,a) is the expected utility of taking a given action in a given state\n",
        "\n",
        "\n",
        "The simplest way to represent P(s'|s,a) and R(s,a,s') is with 3D tables of size $|S|^2|A|$. This is OK for small problems. Tables can be sparse.\n",
        "\"\"\"\n",
        "chapter17_2 =  r\"\"\"\n",
        "Value Iteration\n",
        "* Solving systems of nonlinear equations with an iterative approach. Bellman Update is applied simultaneously to \n",
        "all states at each iteration. If we apply the Bellman update infinitely often, we are guranteed to reach convergence where the final utility values is the soution to the Bellman \n",
        "equations. \n",
        "* Contraction is a function when applied to two different inputs during separate turns, they produce two output values that are \"closer together by some constant factor than the \n",
        "original inputs. Contractions have only one fixed point. If there were two points, they would not get closer when the function is applied. When the function is applied, the value \n",
        "must get closer to the fixed point, so repeated application of the contration would continue to get closer to the fixed point (like sqrt).\n",
        "* The Bellman update is a contraction by a factor of $\\gamma$ on the space of utility vectors.\n",
        "* Value iteration converages exponentially fast. Number of iterations to convergence = $N = \\lceil log(2R_{max}/\\epsilon (1-\\gamma))/log(1/\\gamma) \\rceil$. Since convergence is \n",
        "exponentially fast, it does not rely much on the ratio of $\\epsilon/R_{max}$, but N can grow rapidly as $\\gamma$ gets closer to 1. We can get fast convergence if $\\gamma$ is small, \n",
        "but then we risk missing out on any long term effects of the agents actions since the event horizon would be short.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "Policy Iteration\n",
        "* Previously, we observed that it is possible to get an optimal policy even when the utility function estimate is inaccurate. If one action is clearly better than the others, the \n",
        "accuracy of the value of the others does not really matter. Thus there can be another way to find the optimal policy using policy iteration. It is broken into two steps, policy \n",
        "evaluation and improvement.\n",
        "* Algorithm terminates then the policy improvement steps yields no changes in the utility values. Then we know that the utility function is a fixed point in the Bellman update, \n",
        "therefore a solution to the Bellman equations and an optimal policy. \n",
        "* To implement, it is simpler than solving the standard Bellman equations like value iteration does since the action in each state is fixed by the policy. This gives us a simplified \n",
        "version of the Bellman equation: $U_i(s) =  \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$. Since the max operation is removed, all the equations are linear. \n",
        "* If we have n states, there are n linear equations with n unknowns, solvable in $O(n^3)$ time. If the transition model is sparse (states transition to only a few other states), \n",
        "the process can be even faster. For small state spaces, exact solutions with policy evaluation is the most efficient approach, but for large state spaces, $O(n^3)$ might be too \n",
        "much. \n",
        "* We do not have to update all of the utilities/policies for all states at once, instead we can use asynchronous policy iteration.  Given certain conditions on the initial policy \n",
        "and initial utility function, this is guaranteed to converge to an optimal policy. \n",
        "\n",
        "\n",
        "Linear Programming\n",
        "* General approach for fomulating constrained optimization problems. A MDP can be reduced to solving a suitably formulated linear program since it involves a lot of sums and maxes. \n",
        "Consider the variables in the LP to be the utilities for each state. The utilities for an optimal policy are the highest utilities attainable that are consistent with the Bellman \n",
        "equations. This means we want to minimize U(s) for all states; $U(s) \\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$ for every state s and action a.\n",
        "* Linear programming is solvable in polynomial time, therefore this means that MDPs can be solved in time polynomial in the number of states anda ction and bits required to specify \n",
        "the model. In practice, it turns out that LPs solvers are seldomly more efficient than dynamic programming. Even though polynomial time might sound good, the number of states is \n",
        "usually large. \n",
        "\n",
        "\n",
        "Value iteration and policy iteration are both offline algorithms like A*.  Because of state sizes, \n",
        "exact offline solutions are often not possible, even in polynomial time. Therefore, it needs to be approximated. Instead we should use online algorithms. Options include a simplifed \n",
        "version of EXPECTIMINIMAX, Real-time Dynamic Programming (RTDP), reinforcement learning, Monte Carlo approach, UCT (Upper Confidence bounds applied to Trees) algorithm.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"decision-theoretic agent\" : \"an agent that makes rational decisions based on what it believes and what it wants\",\n",
        "\"utility function, U(s)\" : \"assigns a number to express the desirability of a state, captures the agent's preferences. Maps lotteries to real numbers. \",\n",
        "\"expected utility, EU(a)\" : \"the average utility value of the outcomes, weighted by the probability that the outcome occurs\",\n",
        "\"lottery\": \"set of outcomes for each action, $L = {p1, S1; p2, S2; ...; pn, Sn}$\",\n",
        "\"value function or ordinal utility function\" : \"an agent only needs a preference ranking on states in a deterministic environment\",\n",
        "\"preference elicitation\" : \"the process of figuring out the utility function by presenting choices to humans and using the preferences to make the utility function\",\n",
        "\"normalized utilities\" : \"uses scale for 0 to 1 for best and worst outcomes.\",\n",
        "\"standard lottery\" : \"e.g. $[p, u \\perp; (1-p), u \\bot]$\",\n",
        "\"micromort\" : \"one million chance at death\",\n",
        "\"monotonic preference\": \"given everything else is equal, the preference will always be A over B (e.g. prefer more money over less)\",\n",
        "\"expected monetary value\": \"(EMV), sum of probabilities times value\",\n",
        "\"risk-adverse\": \"prefer a sure thing over a gamble\",\n",
        "\"certainty equivalent\": \"amount someone would accept in lieu of the gamble\",\n",
        "\"sequential decision problems\" : \"agent's utility depends on a sequence of decisions, incorporating utilities, uncertainty, sensing, and search/planning problems (special cases)\",\n",
        "\"Markovian\" : \"probability of reaching a state s' depends only on current state s, not on any previous history\",\n",
        "\"environment history\" : \"sequence of states and actions\", \n",
        "\"Markov Decision Process (MDP)\" : \"sequential decision problem for a fully observable, stochastic environement with a Markovian transition model and additive rewards\",\n",
        "\"dynamic programming\" : \"recursively breaks down a problem into smaller pieces and rembers the optimal solutions to the pieces.\",\n",
        "\"policy\" : \"solution that specifies what the agent might do at any state. denoted by $\\pi(s)$ for the policy for state s. \",\n",
        "\"optimal policy\" : \"policy that yields the highest expected utility, $\\pi*$\",\n",
        "\"finite horizon\": \"fixed time N after which nothing matters, e.g. the game is over\",\n",
        "\"nonstationary\" : \"policy that depends on time\",\n",
        "\"stationary\" : \"optimal action only depends on current state, does not have to react differently depending on the time\",\n",
        "\"additive discount rewards\" : \"$U_h([s0,a0,s1,a1,s2...])=R(s0,a0,s1)+\\gamma R(s1,a1,s2)+\\gamma^2R(s2,a2,s3)+...$\",\n",
        "\"discount factor\" : \"$0>\\gamma>1$, preference for current rewards over future rewards.\",\n",
        "\"proper policy\" : \"guaranteed to reach a terminal state\",\n",
        "\"Dynamic decision networks (DDNs)\" : \"decision, reward, utility nodes\",\n",
        "\"contraction\" : \"basic concept used to show that value iteration converages\",\n",
        "\"max norm\" : \"maximum value of the absolute value, 'length' of the vector, $||U|| = max_s |U(s)|$\",\n",
        "\"policy loss\" : \"the most the agent can lose by executing a policy instead of the optimal policy, $||U^{\\pi_i}-U||$\",\n",
        "\"Bellman Update\" : \"Iteration step called the Bellman update, using the Bellman equation.\",\n",
        "\"Policy evaluation\" : \"given a policy, calcualte the utility of each state if the policy was executed\",\n",
        "\"Policy improvement\" : \"calculate a new MEU policy using one-step look-ahead based on the utilities calculated in policy evaluation.\",\n",
        "\"modified policy iteration\" : \"You don't have to do exact policy evaluation, instead some simplified value iteration steps can be performed to give a good approximation of the utilities.\", \n",
        "\"asynchronous policy iteration\" : \"Instead we can pick a subset of states and apply either policy improvement or simpilfied value iteration to them.\",\n",
        "\"offline algorithms\" : \"They generate an optimal solution for the problem and then it is executed by the agent.\",\n",
        "\"online algorithms\" : \"like we used for game playing, where the agent does computations at each decision point rather than using precomputed information. \",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 22,
      "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": "475a4fbb-b9fb-42ea-f9d4-a8202264f4f3"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nA decision-theoretic agent assigns a continuous range of values to goals and states so that it can pick \na state even when no best state is available. \n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n * $P(s'|s,a)$ = Probability that action a in state s reaches state s'\n * $P(\\textnormal{RESULT}(a)=s')$ = Probability of reaching s' by doing action a in the curent state\n * $P(s)$ = Probability of state s\n\n\n $EU(a) = sum_{s'}P(\\textnormal{RESULT}(a)=s')U(s')$\n\n Principle of Maximum Expected Utility = rational agent should choose the action that maximizes the agents's expected utility \n * $action = argmax_a EU(a)$\n\n\n The MEU Principle formulizes the notion that an intelligent agent should do the right now but not how to operationalize that notion. \n Estimating the probability distribution P(s) requires perception, learning, knowledge representation, and infernece. To get $P(\\textnormal{RESULT}(a)=s')$ \n you need to know a casual model of the world. Computing the utilities (U(s')) requires searching or planning since an agent doesn't know how good that future \n state might be until to knows where it can get to from that state. There might be some uncertainty about the utility function if the computer does \n not know the human's true utility function. Decision theory might not be the end all to AI, but it provides the beginnings of the general mathematical \n framework to define the AI problem. MEU has a clear relation to the idea of performance measures. \n\n *If an agent acts so that it maximizes a utility function that reflects the performance measure, then the agent will achieve the highest possible performance score \n (averaged over all possible environments)*\n\n Performance measure gives a score for history (sequence of states). Utility function applies to the next state and can be used to guide actions step by step. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nAxioms of Utility Theory\n* Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equality preferable. (Deciding cannot be avoided.)\n * Exactly one of $(A>B), (B>A)$ or $(A~B)$ holds\n* Transitivity: Given any three lotteries, if an agent prefernece A to B and prefers B to C, then the agent must prefer A to C.\n * $(A>B) \\lor (B>C) \\implies (A>C)$\n* Continuity:If some lottery B is between A and C in preference, then there is some probability p where the rational agent will be indifferent between getting B \nfor sure and the lottery that yields A with probability p and C with probability 1-p.\n * $A>B>C \\implies \\exists p [p, A; 1-p, C]~B$\n* Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same \nexpect that B is substituted for A in one of them. \n * $A~B \\implies [p, A; 1-p, C] ~ [p, B; 1-p, C]$\n* Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then it must prefer the lotter with the higher \nprobability for A.\n * A>B \\implies (p>q \\iff [p, A; 1-p, B] > [q, A; 1-q, B])\n* Decomposability: Compound lotteries can be reduced so simplier ones using laws of probability. (aka. \"no fun in gambling\" rule)\n * $[p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C]$\n\n\nIf an agent violates any of the axioms of Utility Theory, then it can be proved they are irrational. \nThese are really axioms of preferences, they don't say anything about a utility function.\n\nFrom the axioms of utility, the following consequences can be derived:\n* Existence of Utility Function:If an agent's preference obey the axioms of utility, then there exists a function U such that U(A)>U(B) iff A is preferred to B, \nand U(A)=(B) iff the agent is indifferent between A and B.\n** $U(A)>U(B) \\iff A>B$ and $U(A)=U(B) \\iff A~B$\n* Expected Utility of a Lottery: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n** $U([p1, S1; ...; pn, Sn]) = \\sum_i{piU(Si)}$\n** The utility of a compound lottery involving possible outcome states is completely determined once the probabilities and utilities of the outcome states are specified, . \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nFirst we need to work out what the human's utility function is. We can use preference elicitation to do this. Establish a scale to use for comparison of utility values by \nfixing the utilities of any two outcomes (same idea as setting the temp for boiling and freezing). Usually we fix the best possible prize ($U(S)= u_\\perp$) and worst possible catastrophe \n($U(S)= u_\bot$) with finite values. Then, using a standard lottery, we find at what point probability p needs to be at where the agent is indifferent between S and the standard \nlottery. Example: Want to find out how much a fan values getting to the semi-final and losing. Compare standard lottery with probability p of winning the trophy to probability 1-p \nto fail to quality. If indifference is at 0.3, this is the value of reaching the semi-final and losing.   \n\nIt is helpful to establish some scale that utilities can be recorded and compared for a problem. A scale can be established by fixing utilities of any two particular outcomes. Typically this is the (finite) utility for a best possible price and worst possible catastrophe. We would ask the agent to choose between S and a standard lottery and adjust the probability until the agent is indifferent between them. Tehn we can determine the prizes for all lotteries involved. These values can be used to put value and decide on tolerants for risk. Aircraft are not serviced after every flight, analysis for deciding the value of a childs life vs removing asbestos from the school. \n\nUtility theory has roots in economics. Say if you had 1mil you could take now vs flipping a coin and you get 2.5mil if it is tails and nothing if it is heads. The EMV would benefit the coin flip, but that isn't necessarily the best decision. It would be dependent on your current financial wealth. A millionnaire would most likely have a utility function that is linear over a range of a couple million and would be more likely to take the gamble. The utility of money is almost exactly proportional to the log of the amount. Most people would accept \\$400 (certainty equivalent) in lieu of a chance at \\$1000 or \\$0, even though the EMV is \\$500. Difference between EMV and certainty equivalent is the insurance premium. \n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nIf a fully observable environment were deterministic, the solution would be straightfoward, but actions are unreliable in a stochastic environment. The outcome \nof the transsition model is stochastic, so it is represented as a probability $P(s'|s,a)$ and transitions are assumed to be Markovian. The decision problem is \nsequential so the utility function will depend on the environment history instead of a single state. For every transsition, the agent will receive a reward $R(s,a,s')$. \nReward may be positive or negative. This problem is known as a Markov Decision Process (MDP). These consist of...\n* set of states (with initial state s0)\n* set of ACTIONS(s) for each state\n* transition model $P(s'|s,a)$\n* reward function $R(s,a,s')$\n\n\nMethods for solving MDPs using invovle dynamic programming. Since there cannot be a single solution to the problem, the solution is a policy. The agent will know what \nto do based on what the policy says. Given an optimal policy, the agent decides what to do based on their current percept (defining their current state) and then executes \nthe actions provided from $\\pi*(s)$. The policy represents the agent function explicitly, resulting in a simple reflex agent. For a state, there can be multiple optimal \npolicies. The balance of risk and reward is determined by the rewards from the transition function as the agent moves to non-terminal states. Since MDPs include uncertainty, \nthey are closer to real world problems than deterministic search problems. \n\nPolicies for infinite horizon cases are simplier than for finite horizons since they do not have to act differently depending on the time.\n\nIf $\\gamma$ is close to 0, rewards in the distant future are insignificant; if $\\gamma$ is close to 1, agent can wait for more long-term rewards. If $\\gamma=1$, then rewards \nare purely additive. Additive rewards make sense since living beings tend to prefer now instead of later. For money, it is better to get it sooner than later because gains \ncan be reinvested. There is also uncertainty about true rewards in the future, they might not come for some reason. Discounted rewards allows us to make the utility of an \ninfinite sequence finite and bounded by a maximum, that way we are not trying to compare two $+\\inf$ utilities.  \n\n\nThe Bellman Equation: $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n* the utility of a state is the expected reward for the next transistion plus the discounted utility of the next state, assuming that the agent chooses the optimal action\n\n\nAction-utility function (Q-function): $U(s)=max_a Q(s,a)$ where $Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q(s',a')]$\n* Q(s,a) is the expected utility of taking a given action in a given state\n\n\nThe simplest way to represent P(s'|s,a) and R(s,a,s') is with 3D tables of size $|S|^2|A|$. This is OK for small problems. Tables can be sparse.\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nValue Iteration\n* Solving systems of nonlinear equations with an iterative approach. Bellman Update is applied simultaneously to \nall states at each iteration. If we apply the Bellman update infinitely often, we are guranteed to reach convergence where the final utility values is the soution to the Bellman \nequations. \n* Contraction is a function when applied to two different inputs during separate turns, they produce two output values that are \"closer together by some constant factor than the \noriginal inputs. Contractions have only one fixed point. If there were two points, they would not get closer when the function is applied. When the function is applied, the value \nmust get closer to the fixed point, so repeated application of the contration would continue to get closer to the fixed point (like sqrt).\n* The Bellman update is a contraction by a factor of $\\gamma$ on the space of utility vectors.\n* Value iteration converages exponentially fast. Number of iterations to convergence = $N = \\lceil log(2R_{max}/\\epsilon (1-\\gamma))/log(1/\\gamma) \\rceil$. Since convergence is \nexponentially fast, it does not rely much on the ratio of $\\epsilon/R_{max}$, but N can grow rapidly as $\\gamma$ gets closer to 1. We can get fast convergence if $\\gamma$ is small, \nbut then we risk missing out on any long term effects of the agents actions since the event horizon would be short.\n\n\n\n## Module 8 Lecture Notes\n\nPolicy Iteration\n* Previously, we observed that it is possible to get an optimal policy even when the utility function estimate is inaccurate. If one action is clearly better than the others, the \naccuracy of the value of the others does not really matter. Thus there can be another way to find the optimal policy using policy iteration. It is broken into two steps, policy \nevaluation and improvement.\n* Algorithm terminates then the policy improvement steps yields no changes in the utility values. Then we know that the utility function is a fixed point in the Bellman update, \ntherefore a solution to the Bellman equations and an optimal policy. \n* To implement, it is simpler than solving the standard Bellman equations like value iteration does since the action in each state is fixed by the policy. This gives us a simplified \nversion of the Bellman equation: $U_i(s) =  \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$. Since the max operation is removed, all the equations are linear. \n* If we have n states, there are n linear equations with n unknowns, solvable in $O(n^3)$ time. If the transition model is sparse (states transition to only a few other states), \nthe process can be even faster. For small state spaces, exact solutions with policy evaluation is the most efficient approach, but for large state spaces, $O(n^3)$ might be too \nmuch. \n* We do not have to update all of the utilities/policies for all states at once, instead we can use asynchronous policy iteration.  Given certain conditions on the initial policy \nand initial utility function, this is guaranteed to converge to an optimal policy. \n\n\nLinear Programming\n* General approach for fomulating constrained optimization problems. A MDP can be reduced to solving a suitably formulated linear program since it involves a lot of sums and maxes. \nConsider the variables in the LP to be the utilities for each state. The utilities for an optimal policy are the highest utilities attainable that are consistent with the Bellman \nequations. This means we want to minimize U(s) for all states; $U(s) \\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$ for every state s and action a.\n* Linear programming is solvable in polynomial time, therefore this means that MDPs can be solved in time polynomial in the number of states anda ction and bits required to specify \nthe model. In practice, it turns out that LPs solvers are seldomly more efficient than dynamic programming. Even though polynomial time might sound good, the number of states is \nusually large. \n\n\nValue iteration and policy iteration are both offline algorithms like A*.  Because of state sizes, \nexact offline solutions are often not possible, even in polynomial time. Therefore, it needs to be approximated. Instead we should use online algorithms. Options include a simplifed \nversion of EXPECTIMINIMAX, Real-time Dynamic Programming (RTDP), reinforcement learning, Monte Carlo approach, UCT (Upper Confidence bounds applied to Trees) algorithm.\n\n\n\n## Module 8 Definitions\n* **Decision-theoretic agent** - an agent that makes rational decisions based on what it believes and what it wants\n* **Utility function, u(s)** - assigns a number to express the desirability of a state, captures the agent's preferences. Maps lotteries to real numbers. \n* **Expected utility, eu(a)** - the average utility value of the outcomes, weighted by the probability that the outcome occurs\n* **Lottery** - set of outcomes for each action, $L = {p1, S1; p2, S2; ...; pn, Sn}$\n* **Value function or ordinal utility function** - an agent only needs a preference ranking on states in a deterministic environment\n* **Preference elicitation** - the process of figuring out the utility function by presenting choices to humans and using the preferences to make the utility function\n* **Normalized utilities** - uses scale for 0 to 1 for best and worst outcomes.\n* **Standard lottery** - e.g. $[p, u \\perp; (1-p), u \bot]$\n* **Micromort** - one million chance at death\n* **Monotonic preference** - given everything else is equal, the preference will always be A over B (e.g. prefer more money over less)\n* **Expected monetary value** - (EMV), sum of probabilities times value\n* **Risk-adverse** - prefer a sure thing over a gamble\n* **Certainty equivalent** - amount someone would accept in lieu of the gamble\n* **Sequential decision problems** - agent's utility depends on a sequence of decisions, incorporating utilities, uncertainty, sensing, and search/planning problems (special cases)\n* **Markovian** - probability of reaching a state s' depends only on current state s, not on any previous history\n* **Environment history** - sequence of states and actions\n* **Markov decision process (mdp)** - sequential decision problem for a fully observable, stochastic environement with a Markovian transition model and additive rewards\n* **Dynamic programming** - recursively breaks down a problem into smaller pieces and rembers the optimal solutions to the pieces.\n* **Policy** - solution that specifies what the agent might do at any state. denoted by $\\pi(s)$ for the policy for state s. \n* **Optimal policy** - policy that yields the highest expected utility, $\\pi*$\n* **Finite horizon** - fixed time N after which nothing matters, e.g. the game is over\n* **Nonstationary** - policy that depends on time\n* **Stationary** - optimal action only depends on current state, does not have to react differently depending on the time\n* **Additive discount rewards** - $U_h([s0,a0,s1,a1,s2...])=R(s0,a0,s1)+\\gamma R(s1,a1,s2)+\\gamma^2R(s2,a2,s3)+...$\n* **Discount factor** - $0>\\gamma>1$, preference for current rewards over future rewards.\n* **Proper policy** - guaranteed to reach a terminal state\n* **Dynamic decision networks (ddns)** - decision, reward, utility nodes\n* **Contraction** - basic concept used to show that value iteration converages\n* **Max norm** - maximum value of the absolute value, 'length' of the vector, $||U|| = max_s |U(s)|$\n* **Policy loss** - the most the agent can lose by executing a policy instead of the optimal policy, $||U^{\\pi_i}-U||$\n* **Bellman update** - Iteration step called the Bellman update, using the Bellman equation.\n* **Policy evaluation** - given a policy, calcualte the utility of each state if the policy was executed\n* **Policy improvement** - calculate a new MEU policy using one-step look-ahead based on the utilities calculated in policy evaluation.\n* **Modified policy iteration** - You don't have to do exact policy evaluation, instead some simplified value iteration steps can be performed to give a good approximation of the utilities.\n* **Asynchronous policy iteration** - Instead we can pick a subset of states and apply either policy improvement or simpilfied value iteration to them.\n* **Offline algorithms** - They generate an optimal solution for the problem and then it is executed by the agent.\n* **Online algorithms** - like we used for game playing, where the agent does computations at each decision point rather than using precomputed information. \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 =  r\"\"\"\n",
        "A gambler must choose which lever to play for each turn for an n-armed bandit. They need to decide if they should try something they has already \n",
        "paid off the best or something new. This is a tradeoff between exploitation and exploration. Examples of n-bandit problems include: \"which of n \n",
        "possible investments to put your saving into\", \"which of n possible adverts to show a user when they visit a particular page\". At first, scientists \n",
        "tried to prove statements about n-armed bandit problems that were actually false, such as the optimal policy would settle on the best arms, but there \n",
        "is a finite probability it will setting on a suboptimal arm. \n",
        "\n",
        "Definition of a bandit problem:\n",
        "* Each arm is a Markov reward process. Rewards are random variables. \n",
        "* Overall bandit problem is an MDP. \n",
        "* Arms are independent. Agent can only work one arm at a time.\n",
        "\n",
        "\n",
        "Gittin index of an arm only depends on the properties of the arm. The optional deciion on the first iteram can be calcualted in O(n) time (n=number of arms). \n",
        "Each decision after the first one can be calculated in O(1) since the GIttin indicies of the unselected arms remain unchanged. \n",
        "* $\\lambda = max_{T>0} \\frac{E(\\sum_{t=0}^{T-1}\\gamma^t R_t)}{E(\\sum_{t=0}^{T-1} \\gamma^t)}$\n",
        "\n",
        "\n",
        "A Bernoulli bandit has infinitely many states, but we can approximate the solution with a truncated MDP with states of $successes_i+failures_i=100$ and $\\gamma=0.9$. \n",
        "Results depict that arms with higher payoff probabilities are preferred and there is an exploration bonus associated with arms that been tried sedomly. \n",
        "\n",
        "It is rarely easy to calculate Gittins indicies for realistic problems. But the creation of simple polies turn out to be nearly as good as optimal policies. \n",
        " * upper confidence bound (UCB) heristic: uses samples from each arm to establish a confidence interval  for he value of the arm, then chooses the arm with the highest \n",
        " upper bound. A UCB policy picks the arm with the highest UCB value.\n",
        " * Thompson Sampling: chooses an arm at random according to the probability that the arm is optimal, given the samples so far. Simple way to implement Thompson's is to \n",
        " generate one sample from each P and then pick the best. This has a regret that grows as O(logN).\n",
        "\n",
        " Bandit problems originally came up because there was a serious cost for failing, we didn't want to fail. If instead we just wanted to find out which 'arm' performs the best, \n",
        " with no or little cost of failing, then we have a selection problem. Selection problems are similar to bandit problems but with different mathematical properties, e.g. they \n",
        " have no index function. \n",
        "\n",
        "Examples of BSPs include multitasking. The global optimal policy might include suboptimal actions compared to the POV of the constituent MDP. We solve BSPs by using the loose \n",
        "interation between the arms and modeling with an opportunity cost.  \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "Reinforcement learning goal is the same as MDP, maximize the expected sum of rewards. But it is diffeent because the agent is not given an MDP problem to solve, it is \n",
        "IN the MDP. It does not know the transition model or reward function, it has to do things in order to learn more. Reinforcement learning benefits from being simplier to \n",
        "code, we don't need to be experts and we only need to code either it gets a reward or not. But a little bit of expertise can go a long way. \n",
        "\n",
        "* Model-based reinforcement learning: Agent uses a transistion model to interpret reward signals and to make decisions on how to act. The model may start as unknown and \n",
        "the agent will learn it from its actions or it might be known. They often learn a utility function.  \n",
        "* Model-free reinforcement learning: Agent neither knows nor leanrs a transition model. Instead it learns a more direct representation on how to behave. \n",
        " * Action-utility learning: Most common form is Q-learning; agent learns a Q-function (quality function) which is the sum of rewards from state s onward if action a is taken. \n",
        " The agent can choose what to do in the current state by finding the action with the highest Q-value. \n",
        " * Policy search: Agent learns a policy that maps directly from state to actions. Same as a reflex agent. \n",
        "\"\"\"\n",
        "chapter22_2 =  r\"\"\" \n",
        "Passive Learning Agent (PLA): Consider a fully observable env with small number of actions and states, agent had a fixed policy that determines its actions and is trying to learn \n",
        "the utility function. PLA is similiar to policy evaluation task, but we do not know the transition \n",
        "model or reward function. \n",
        "\n",
        "Direct utility estimation: utility of a state is defined as the expected total reward from that state onward (expected reward-to-go). Each trial provides a sample of this quantity \n",
        "for each state visited. This reduces reinforcement learning to supervised learning, but it ignores the constraint that the utility of a state is determined by the reward and the \n",
        "expected utility of the successor states. Ignoring this connection, it misses the opportunities for learning and converges slowly.\n",
        "\n",
        "Adaptive Dynamic Programming (ADP): agent takes advantage of the constraints amoung the utilties by learning the transition model that connects them and solves the corresponding MDP \n",
        "during dynamic programming. For a PLA, we can take the learned transition model and observed rewards to calcuate the utilities of states using \n",
        "$U_i(s) = \\sum_{s'} P(s'|s,\\pi_i(s))[R(s, \\pi_i(s), s')+\\gamma U_i(s')]$. This can be solved using linear algebra. Alternatively, we can use modified policy iteration. The model \n",
        "usually only changes slightly with each observation, value iteration can use previous utility estimates as initial values and can converage quickly. Since the env is \n",
        "fully observable, learning the transition model is easy. ADP agent is only limited by its ability to learn the transition model. But it is not good in large state spaces since it has \n",
        "equal number of equations to solve as unknowns. Heuristics can help approx. ADPs learn as fast as full ADPs. \n",
        "\n",
        "Temporal-difference learning (TD): Uses observed transitions to adjust the utilities of the observed states so that they agree with the constraint equations. Update to utilities = \n",
        "$U^\\pi(s) \\leftarrow U^\\pi(s) + \\alpha [R(s, \\pi(s), s') +\\gamma U^\\pi(s')-U^\\pi(s)]$. $\\alpha = $ learning rate. All TD methods work by adjusting the utility estimates \n",
        "towards the ideal equilibrium that holds locally when the utility estimates are correct. The update only invovles successor s'. This will not result in changing U drastically for an \n",
        "extremely rare event, 1. because it is rare and 2. because the avg value will still converge. If we turn $\\alpha$ in to a function that dec over time, the utility will converge \n",
        "to the correct value. TD will not learn as fast as ADP, but it is simpler and requires less computation per observation. There is no need for a transition model to perform the updates. \n",
        "Instead, it will use the connection between neighboring states from observed transitions. TD will adjust a state to agree with its observed successor, ADP will adjust the state to agree \n",
        "with ALL the successors that have already occurred, weighed by probab. Over a large number of transitions, this diff disappears.    \n",
        "\"\"\"\n",
        "chapter22_3 =  r\"\"\"\n",
        "Active learning agent can take a modified ADP approach. It will need to learn a complete transisiotn model with outcome probs for all actions. The agent has a choice of actions and the utitlies \n",
        "will need to be defined by the optimal policy by using the Bellman Equations to solve for the utility function using value iteration or policy iteration. Since now the agent will have a utility \n",
        "function, it can exact an optimal action looking one step ahead to maximize the expected utilities. But is this the best approach to take?\n",
        "\n",
        "This approach is narrow and could result in the agent not learning the true utilities or true optimal policy. The agent needs to utilize that the actions provide rewards and information. Just like \n",
        "the bandits, there is a tradeoff between exploitation and exploration. GLIE schemes must try each action and unbounded number of times so that it doesnt miss an optimal action. The true transition \n",
        "model will eventually be learned and then the agent can operate under exploitation. Options are choose an action at random (converges slowly) or weight the actions (better).\n",
        "\n",
        "\n",
        "Exploration function: $f(u,n) = \\begin{cases}\n",
        "  R^+ \\textnormal{ if } n<N_e  \\\\    \n",
        "  u \\textnormal{ otherwise}    \n",
        "\\end{cases}$\n",
        "\n",
        "where $R^+$ is an optimistic estimate of the best possible reward obtainable in any state and $N_e$ is a fixed parameter.\n",
        "\n",
        "\n",
        "We have assumed that the agent can explore and failure has no lasting consequences, but this is not the case in most realistic scenarios. We need to be able to explore safely. We can end up in bad \n",
        "states because the model is unknown and we choose to explore is a direction that turns out to be bad, or  because the model is incorrect and we don't know the action is bad. If acting with a policy \n",
        "with an estimated model, it acts as if the model is correct, which can be bad. Better would be to use a policy that works reasonably well for all models, even if it is suboptimal. \n",
        "\n",
        "For TD learning, the Q-learning method learns an action-utility function (Q(a,s)), avoiding the need for a model. Note that the TD Q-learning agent does not need a transition model for learning or \n",
        "action selection. But they have no means to look into the future, so may struggle when rewards are sparse or long action sequences are need to reach rewards. \n",
        "\n",
        "SARSA update rule is similar to Q-learning update rule: $Q(s,a) \\leftarrow Q(s,a) + \\alpha [R(s,a,s') + \\gamma Q(s',a')-Q(s,a)]$. SARSA waits until an action is taken and backs up the Q-value for \n",
        "that action. If the agent is greedy, Q-Learning and SARSA are identical. Q-learning is off-policy, SARSA is on-policy. Q-learning and SARSA are both slower than ADP since local updates do not enforce \n",
        "consistency.\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\n",
        "Tabular form works for state spaces up to about $10^6$. For the real-world, this would be too slow. Function approximation allows for utility or Q functions to be represented in larger state spaces. \n",
        "It also allows for inductive generalization. \n",
        "\n",
        "Direct utility estimation generates trajectories in the state space and extracts the sum of rewards received from that state onward until termination. We can use the Widrow-Hoff rule (delta rule) \n",
        "to get update rules for the approximator. Changing the parameters also changes the utilities, therefore this approximation can allow the reinforcement learner to generalize from its experiences. \n",
        "The agent can learn faster with a function approximator. \n",
        "\n",
        "Similar approximation ideas can be applied to TD as well. The parameters need to be adjusted to reduce the TD between successive states. This will work if the function approximator is linear, but \n",
        "can result in infinity if it is not. But this has a risk of catastrophic forgetting. A solution is experience replay. Learning modesl for observable environments for supervised learning problems \n",
        "is easier since it can look ahead compared to partially observable environments. \n",
        "\n",
        "We need to go beyond linear function approximators for utility and Q functions because there might be no good linear function or we might not be able to invent the necessary features, particularly in new \n",
        "domains. Deep neural networks can be used as nonlinear function approximators, it can discover the features for itself and, if the last layer is linear, then build its own linear function approximator. \n",
        "Even though it can get good results, it can be difficult since the trained system can behave unpredictably if the environment differs from the training data.   \n",
        "\n",
        "We can use reward shaping to give additional \"pseudorewards\" for actions to help speed up learning, but need to make sure the agent does not try to maximize these rewards rather than the true rewards. \n",
        "\n",
        "A HRL agent starts with a partial program that outlines the hierarchial structure for the agent's behavior. HRL is based on the concept of joint state space. The machine state is the internal state \n",
        "of the program. HRL can be good for learning complex behaviors. \n",
        "\"\"\"\n",
        "chapter22_5 =  r\"\"\"\n",
        "Q-functions could be linear or nonlinear. Policy search adjusts the parameters to improve the policy. If the policy relies on Q-functions, then it will result in a process where it learns the Q-functions. \n",
        "This process is different than Q-learning. Q-learning finds parameters that gets close to optimal Q-function, whereas policy search finds parameters that result in good performance. If actions are discrete \n",
        "then the policy is a discontinuous function of the parameters. There might be values of the parameters where if there is a reallly small change, it might cause the policy to switch from one action to another. \n",
        "This would make gradient search difficult if the policy is changing discontinuously. Policy search needs to use a stochastic policy representation that speciflies the probablity of selecting action a in state s. \n",
        "An example is the softmax function: $\\pi_\\theta (s,a) \\frac{e^{\\beta \\hat{Q}_{\\theta}(s,a)}}{\\sum_{a'}e^{\\beta \\hat{Q}_{\\theta}(s,a')}}$. $\\beta$ controls the softness of softmax, large values approach a hard max, \n",
        "close to zero approaches a uniform rancom choise among actions. Correlated sampling can be applied to policy search. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = r\"\"\"\n",
        "Direct evaluation: compute values for each state under \\pi where we average together observed sample values and act according to the policy $\\pi$. \n",
        "Every time you visit a state, write down the sum of discounted rewards and avereage the samples. Direct evaluation doesn't require knowlege of T and R. \n",
        "But it takes a long time to learn since each state needs to be learned separately and it wastes information about state connections. \n",
        "\n",
        "We can use policy evaluation but we need T and R. We can take a weighted average without knowing the weights by taking samples of outcomes s' by doing \n",
        "the action and then average using samples. \n",
        "\n",
        "In Temporal Difference Learning (TD), the idea is that we can learn from every experience. We will update the weights every time we transition. Likely outcomes \n",
        "will constribute updates more often. The policy is still fixed. We can use an exponential moving average to learn. $\\alpha$ learning rates that decrease can give \n",
        "convering averages. \n",
        "$V^{\\pi}(s) \\leftarrow (1-\\alpha) V^{\\pi}(s) + \\alpha [R(s,\\pi(s),s')+ \\gamma V^{\\pi} (s')]$ \n",
        "\n",
        "TD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages. If we want to turn values into a new policy, \n",
        "it is not possible because we have to work with a fixed policy. We need to learn Q-values not just values and make the action selections model-free too through reinforcement \n",
        "learning. We allow the learner to make the choices and have to deal with a tradeoff between exploration and exploitation. We do not know the transistions or rewards beforehand, \n",
        "we will learn the optimal policies and values along the way as the agent chooses and complete the actions. This is online planning. \n",
        "\n",
        "Q learning uses value iteration to find successive (depth limited) Q-values with the state and action. These Q values will be learned as the agent goes, take a sample estimate \n",
        "and incorporate it into a running average. $sample=R(s,a,s')+\\gamma max_{a'}Q(s',a')$; $Q(s,a)\\leftarrow (a-\\alpha)Q(s,a)+(\\alpha)[sample]$. \n",
        "Q-learning converages to optimal policy, even if the agent is acting suboptimally. This is off-policy learning. But you have to explore enough and eventually make the learning \n",
        "rate small enough over time (but don't decrease it too quickly). Therefore, it doesn't matter how actions are selected. To explore, we can choose randon actions ($\\epsilon-greedy$). \n",
        "$\\epsilon$ being small, there is a small probability that it will act randomly, so then $1-\\epsilon$ to act on current policy. With random actions, you explore the space eventually \n",
        "but a lot of thrashing around is done. So you could lower the epsilon value over time or use exploration functions. Exploration functions will focus the agent on areas were the badness \n",
        "has not yet been established, and as areas are found, the agent will eventually stop exploring. The agent will make mistakes, totally in a mistake cost called regret. Mistake cost is \n",
        "the $(expected rewards - optimal rewards)$. Minimizing regret requires optimal learning to be optimal, random exploration has higher regret. Approximate Q-learning generalizes by learning \n",
        "about some small number of training states from experience. The model will generalize the experience to new, similiar situations.  \n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"n-armed bandit\" : \"slot machine with n levers. each lever has a fixed but unknown probability distribution for winnings\",\n",
        "\"exploitation\" : \"using the current action to get rewards\",\n",
        "\"exploration\" : \"continuing on to gather more information about unknown states and actions, which could lead to a better policy and better rewards\",\n",
        "\"regret\" : \"making mistakes while learning\",\n",
        "\"sampling\" : \"trying things repeatedly because of chance\",\n",
        "\"difficulty\" : \"learning can be much harder than solving a known MDP\",\n",
        "\"Markov reward process\" : \"MRP, an MDP with only one possible action, with states, transition model, and reward. The arm defines a distribution over sequences of rewards\",\n",
        "\"Gittins index\" : \"$\\lambda$, provides a simple potimal policy for any bandit problem, pull the arm with the highest Gittins index, then update the indicies.\",\n",
        "\"Restart MDP\" : \"MDP whose optimal value is equivalent to the optimal value of the initial state, and is indifferent between them. Therefore it should just restart.\",\n",
        "\"Bernoulli bandit\" : \"each arm produces a 0<reward<1 with fixed but unknown probability\",\n",
        "\"bandit superprocess\" : \"BSP, each arm is a full Markov decision process instead of just a Markov reward process with only one possible action.\",\n",
        "\"opportunity cost\" : \"how much utility is given up per time step by not devoting that time to another arm\",\n",
        "\"dominating policy\" : \"optimal policy of an arm that is unaffected by the opportunity cost.\",\n",
        "\"reinforcement learning\" : \"the agent interacts with the world and recieves rewards (aka reinforcement) along the way that reflect how well it is doing\",\n",
        "\"sparse rewards\" : \"vast majority of the state give no informative reward signal\",\n",
        "\"passive reinforcement learning\" : \"agent's policy is fixed, needs to learn the utilities of states (or state-action pairs).\",\n",
        "\"active reinforcement learning\" : \"agent also needs to figure out what to do\",\n",
        "\"exploration\" : \"agent experiencing as much as possible from the environment to learn how to behave in it\",\n",
        "\"pseudoexperience\" : \"Extend TD by creating transitions that might happen\",\n",
        "\"prioritized sweeping\" : \"heuristic makes adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\",\n",
        "\"utility function\" : \"(the expected total discounted reward if policy is executed)\",\n",
        "\"passive learning agent\" : \"has a fixed policy that determines its behavior, learner is along for the ride\",\n",
        "\"active learning agent\" : \"gets to decide what actions to take\",\n",
        "\"GLIE\" : \"Greedy in the limit of infinite exploration\",\n",
        "\"absorbing state\" : \"actions have no effect and rewards are not received\",\n",
        "\"Bayesian reinforcement learning\" : \"assumes a prior prob P(h) over hypotheses h, posterior P(h|e) is obtained using Bayes rule given observations to date\",\n",
        "\"SARSA\" : \"state, action, reward, state, action\",\n",
        "\"off-policy\" : \"learns Q-values based on if the agent stops using its current policy and switches to a policy that chooses the best actions based on estimates\",\n",
        "\"on-policy\" : \"learns Q-values based on if the agent continues using its current policy\",\n",
        "\"function approximation\" : \"process of constructing a compact approximation of the true utility function or Q-function\",\n",
        "\"inductive generalization\" : \"agent can generalize from states it has visited to states it has not visited\",\n",
        "\"catastrophic forgetting\" : \"learns the safe areas too well and forgets the dangerous areas. \",\n",
        "\"experience replay\" : \"replay failures at a regular interval\",\n",
        "\"deep reinforcement learning system\" : \"uses a deep network as a function approximator\",\n",
        "\"credit assignment problem\" : \"working out what a model did wrong after many commands for many variables\",\n",
        "\"reward shaping\" : \"supplying the agent with additional rewards (psuedorewards) for making progress\",\n",
        "\"hierarchical reinforcement learning (HRL)\" : \"breaking up long action sequences into smaller pieces to make learning easier\",\n",
        "\"joint state space\" : \"each state (s,m) is composed of a physical state s and machine state m\",\n",
        "\"choice state\" : \"program counter for m is at a choice point for the agent program. decisions are not made in between choice states.\",\n",
        "\"policy search\" : \"keep updating the policy as long as its performance improves, then stop\",\n",
        "\"correlated sampling\" : \"using the same inputs during trials to eliminate the measure error due to differences\"\n",
        "}"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d554eaf0-8845-47d0-d1b7-44d04902ead7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"AIMA Chapter 22.5 Policy Search\", chapter22_5),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nA gambler must choose which lever to play for each turn for an n-armed bandit. They need to decide if they should try something they has already \npaid off the best or something new. This is a tradeoff between exploitation and exploration. Examples of n-bandit problems include: \"which of n \npossible investments to put your saving into\", \"which of n possible adverts to show a user when they visit a particular page\". At first, scientists \ntried to prove statements about n-armed bandit problems that were actually false, such as the optimal policy would settle on the best arms, but there \nis a finite probability it will setting on a suboptimal arm. \n\nDefinition of a bandit problem:\n* Each arm is a Markov reward process. Rewards are random variables. \n* Overall bandit problem is an MDP. \n* Arms are independent. Agent can only work one arm at a time.\n\n\nGittin index of an arm only depends on the properties of the arm. The optional deciion on the first iteram can be calcualted in O(n) time (n=number of arms). \nEach decision after the first one can be calculated in O(1) since the GIttin indicies of the unselected arms remain unchanged. \n* $\\lambda = max_{T>0} \\frac{E(\\sum_{t=0}^{T-1}\\gamma^t R_t)}{E(\\sum_{t=0}^{T-1} \\gamma^t)}$\n\n\nA Bernoulli bandit has infinitely many states, but we can approximate the solution with a truncated MDP with states of $successes_i+failures_i=100$ and $\\gamma=0.9$. \nResults depict that arms with higher payoff probabilities are preferred and there is an exploration bonus associated with arms that been tried sedomly. \n\nIt is rarely easy to calculate Gittins indicies for realistic problems. But the creation of simple polies turn out to be nearly as good as optimal policies. \n * upper confidence bound (UCB) heristic: uses samples from each arm to establish a confidence interval  for he value of the arm, then chooses the arm with the highest \n upper bound. A UCB policy picks the arm with the highest UCB value.\n * Thompson Sampling: chooses an arm at random according to the probability that the arm is optimal, given the samples so far. Simple way to implement Thompson's is to \n generate one sample from each P and then pick the best. This has a regret that grows as O(logN).\n\n Bandit problems originally came up because there was a serious cost for failing, we didn't want to fail. If instead we just wanted to find out which 'arm' performs the best, \n with no or little cost of failing, then we have a selection problem. Selection problems are similar to bandit problems but with different mathematical properties, e.g. they \n have no index function. \n\nExamples of BSPs include multitasking. The global optimal policy might include suboptimal actions compared to the POV of the constituent MDP. We solve BSPs by using the loose \ninteration between the arms and modeling with an opportunity cost.  \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nReinforcement learning goal is the same as MDP, maximize the expected sum of rewards. But it is diffeent because the agent is not given an MDP problem to solve, it is \nIN the MDP. It does not know the transition model or reward function, it has to do things in order to learn more. Reinforcement learning benefits from being simplier to \ncode, we don't need to be experts and we only need to code either it gets a reward or not. But a little bit of expertise can go a long way. \n\n* Model-based reinforcement learning: Agent uses a transistion model to interpret reward signals and to make decisions on how to act. The model may start as unknown and \nthe agent will learn it from its actions or it might be known. They often learn a utility function.  \n* Model-free reinforcement learning: Agent neither knows nor leanrs a transition model. Instead it learns a more direct representation on how to behave. \n * Action-utility learning: Most common form is Q-learning; agent learns a Q-function (quality function) which is the sum of rewards from state s onward if action a is taken. \n The agent can choose what to do in the current state by finding the action with the highest Q-value. \n * Policy search: Agent learns a policy that maps directly from state to actions. Same as a reflex agent. \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nPassive Learning Agent (PLA): Consider a fully observable env with small number of actions and states, agent had a fixed policy that determines its actions and is trying to learn \nthe utility function. PLA is similiar to policy evaluation task, but we do not know the transition \nmodel or reward function. \n\nDirect utility estimation: utility of a state is defined as the expected total reward from that state onward (expected reward-to-go). Each trial provides a sample of this quantity \nfor each state visited. This reduces reinforcement learning to supervised learning, but it ignores the constraint that the utility of a state is determined by the reward and the \nexpected utility of the successor states. Ignoring this connection, it misses the opportunities for learning and converges slowly.\n\nAdaptive Dynamic Programming (ADP): agent takes advantage of the constraints amoung the utilties by learning the transition model that connects them and solves the corresponding MDP \nduring dynamic programming. For a PLA, we can take the learned transition model and observed rewards to calcuate the utilities of states using \n$U_i(s) = \\sum_{s'} P(s'|s,\\pi_i(s))[R(s, \\pi_i(s), s')+\\gamma U_i(s')]$. This can be solved using linear algebra. Alternatively, we can use modified policy iteration. The model \nusually only changes slightly with each observation, value iteration can use previous utility estimates as initial values and can converage quickly. Since the env is \nfully observable, learning the transition model is easy. ADP agent is only limited by its ability to learn the transition model. But it is not good in large state spaces since it has \nequal number of equations to solve as unknowns. Heuristics can help approx. ADPs learn as fast as full ADPs. \n\nTemporal-difference learning (TD): Uses observed transitions to adjust the utilities of the observed states so that they agree with the constraint equations. Update to utilities = \n$U^\\pi(s) \\leftarrow U^\\pi(s) + \\alpha [R(s, \\pi(s), s') +\\gamma U^\\pi(s')-U^\\pi(s)]$. $\\alpha = $ learning rate. All TD methods work by adjusting the utility estimates \ntowards the ideal equilibrium that holds locally when the utility estimates are correct. The update only invovles successor s'. This will not result in changing U drastically for an \nextremely rare event, 1. because it is rare and 2. because the avg value will still converge. If we turn $\\alpha$ in to a function that dec over time, the utility will converge \nto the correct value. TD will not learn as fast as ADP, but it is simpler and requires less computation per observation. There is no need for a transition model to perform the updates. \nInstead, it will use the connection between neighboring states from observed transitions. TD will adjust a state to agree with its observed successor, ADP will adjust the state to agree \nwith ALL the successors that have already occurred, weighed by probab. Over a large number of transitions, this diff disappears.    \n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nActive learning agent can take a modified ADP approach. It will need to learn a complete transisiotn model with outcome probs for all actions. The agent has a choice of actions and the utitlies \nwill need to be defined by the optimal policy by using the Bellman Equations to solve for the utility function using value iteration or policy iteration. Since now the agent will have a utility \nfunction, it can exact an optimal action looking one step ahead to maximize the expected utilities. But is this the best approach to take?\n\nThis approach is narrow and could result in the agent not learning the true utilities or true optimal policy. The agent needs to utilize that the actions provide rewards and information. Just like \nthe bandits, there is a tradeoff between exploitation and exploration. GLIE schemes must try each action and unbounded number of times so that it doesnt miss an optimal action. The true transition \nmodel will eventually be learned and then the agent can operate under exploitation. Options are choose an action at random (converges slowly) or weight the actions (better).\n\n\nExploration function: $f(u,n) = \\begin{cases}\n  R^+ \\textnormal{ if } n<N_e  \\\\    \n  u \\textnormal{ otherwise}    \n\\end{cases}$\n\nwhere $R^+$ is an optimistic estimate of the best possible reward obtainable in any state and $N_e$ is a fixed parameter.\n\n\nWe have assumed that the agent can explore and failure has no lasting consequences, but this is not the case in most realistic scenarios. We need to be able to explore safely. We can end up in bad \nstates because the model is unknown and we choose to explore is a direction that turns out to be bad, or  because the model is incorrect and we don't know the action is bad. If acting with a policy \nwith an estimated model, it acts as if the model is correct, which can be bad. Better would be to use a policy that works reasonably well for all models, even if it is suboptimal. \n\nFor TD learning, the Q-learning method learns an action-utility function (Q(a,s)), avoiding the need for a model. Note that the TD Q-learning agent does not need a transition model for learning or \naction selection. But they have no means to look into the future, so may struggle when rewards are sparse or long action sequences are need to reach rewards. \n\nSARSA update rule is similar to Q-learning update rule: $Q(s,a) \\leftarrow Q(s,a) + \\alpha [R(s,a,s') + \\gamma Q(s',a')-Q(s,a)]$. SARSA waits until an action is taken and backs up the Q-value for \nthat action. If the agent is greedy, Q-Learning and SARSA are identical. Q-learning is off-policy, SARSA is on-policy. Q-learning and SARSA are both slower than ADP since local updates do not enforce \nconsistency.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\nTabular form works for state spaces up to about $10^6$. For the real-world, this would be too slow. Function approximation allows for utility or Q functions to be represented in larger state spaces. \nIt also allows for inductive generalization. \n\nDirect utility estimation generates trajectories in the state space and extracts the sum of rewards received from that state onward until termination. We can use the Widrow-Hoff rule (delta rule) \nto get update rules for the approximator. Changing the parameters also changes the utilities, therefore this approximation can allow the reinforcement learner to generalize from its experiences. \nThe agent can learn faster with a function approximator. \n\nSimilar approximation ideas can be applied to TD as well. The parameters need to be adjusted to reduce the TD between successive states. This will work if the function approximator is linear, but \ncan result in infinity if it is not. But this has a risk of catastrophic forgetting. A solution is experience replay. Learning modesl for observable environments for supervised learning problems \nis easier since it can look ahead compared to partially observable environments. \n\nWe need to go beyond linear function approximators for utility and Q functions because there might be no good linear function or we might not be able to invent the necessary features, particularly in new \ndomains. Deep neural networks can be used as nonlinear function approximators, it can discover the features for itself and, if the last layer is linear, then build its own linear function approximator. \nEven though it can get good results, it can be difficult since the trained system can behave unpredictably if the environment differs from the training data.   \n\nWe can use reward shaping to give additional \"pseudorewards\" for actions to help speed up learning, but need to make sure the agent does not try to maximize these rewards rather than the true rewards. \n\nA HRL agent starts with a partial program that outlines the hierarchial structure for the agent's behavior. HRL is based on the concept of joint state space. The machine state is the internal state \nof the program. HRL can be good for learning complex behaviors. \n\n\n## AIMA Chapter 22.5 Policy Search\n\nQ-functions could be linear or nonlinear. Policy search adjusts the parameters to improve the policy. If the policy relies on Q-functions, then it will result in a process where it learns the Q-functions. \nThis process is different than Q-learning. Q-learning finds parameters that gets close to optimal Q-function, whereas policy search finds parameters that result in good performance. If actions are discrete \nthen the policy is a discontinuous function of the parameters. There might be values of the parameters where if there is a reallly small change, it might cause the policy to switch from one action to another. \nThis would make gradient search difficult if the policy is changing discontinuously. Policy search needs to use a stochastic policy representation that speciflies the probablity of selecting action a in state s. \nAn example is the softmax function: $\\pi_\\theta (s,a) \\frac{e^{\\beta \\hat{Q}_{\\theta}(s,a)}}{\\sum_{a'}e^{\\beta \\hat{Q}_{\\theta}(s,a')}}$. $\\beta$ controls the softness of softmax, large values approach a hard max, \nclose to zero approaches a uniform rancom choise among actions. Correlated sampling can be applied to policy search. \n\n\n## Module 9 Lecture Notes\n\nDirect evaluation: compute values for each state under \\pi where we average together observed sample values and act according to the policy $\\pi$. \nEvery time you visit a state, write down the sum of discounted rewards and avereage the samples. Direct evaluation doesn't require knowlege of T and R. \nBut it takes a long time to learn since each state needs to be learned separately and it wastes information about state connections. \n\nWe can use policy evaluation but we need T and R. We can take a weighted average without knowing the weights by taking samples of outcomes s' by doing \nthe action and then average using samples. \n\nIn Temporal Difference Learning (TD), the idea is that we can learn from every experience. We will update the weights every time we transition. Likely outcomes \nwill constribute updates more often. The policy is still fixed. We can use an exponential moving average to learn. $\\alpha$ learning rates that decrease can give \nconvering averages. \n$V^{\\pi}(s) \\leftarrow (1-\\alpha) V^{\\pi}(s) + \\alpha [R(s,\\pi(s),s')+ \\gamma V^{\\pi} (s')]$ \n\nTD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages. If we want to turn values into a new policy, \nit is not possible because we have to work with a fixed policy. We need to learn Q-values not just values and make the action selections model-free too through reinforcement \nlearning. We allow the learner to make the choices and have to deal with a tradeoff between exploration and exploitation. We do not know the transistions or rewards beforehand, \nwe will learn the optimal policies and values along the way as the agent chooses and complete the actions. This is online planning. \n\nQ learning uses value iteration to find successive (depth limited) Q-values with the state and action. These Q values will be learned as the agent goes, take a sample estimate \nand incorporate it into a running average. $sample=R(s,a,s')+\\gamma max_{a'}Q(s',a')$; $Q(s,a)\\leftarrow (a-\\alpha)Q(s,a)+(\\alpha)[sample]$. \nQ-learning converages to optimal policy, even if the agent is acting suboptimally. This is off-policy learning. But you have to explore enough and eventually make the learning \nrate small enough over time (but don't decrease it too quickly). Therefore, it doesn't matter how actions are selected. To explore, we can choose randon actions ($\\epsilon-greedy$). \n$\\epsilon$ being small, there is a small probability that it will act randomly, so then $1-\\epsilon$ to act on current policy. With random actions, you explore the space eventually \nbut a lot of thrashing around is done. So you could lower the epsilon value over time or use exploration functions. Exploration functions will focus the agent on areas were the badness \nhas not yet been established, and as areas are found, the agent will eventually stop exploring. The agent will make mistakes, totally in a mistake cost called regret. Mistake cost is \nthe $(expected rewards - optimal rewards)$. Minimizing regret requires optimal learning to be optimal, random exploration has higher regret. Approximate Q-learning generalizes by learning \nabout some small number of training states from experience. The model will generalize the experience to new, similiar situations.  \n\n\n## Module 9 Definitions\n* **N-armed bandit** - slot machine with n levers. each lever has a fixed but unknown probability distribution for winnings\n* **Exploitation** - using the current action to get rewards\n* **Exploration** - agent experiencing as much as possible from the environment to learn how to behave in it\n* **Regret** - making mistakes while learning\n* **Sampling** - trying things repeatedly because of chance\n* **Difficulty** - learning can be much harder than solving a known MDP\n* **Markov reward process** - MRP, an MDP with only one possible action, with states, transition model, and reward. The arm defines a distribution over sequences of rewards\n* **Gittins index** - $\\lambda$, provides a simple potimal policy for any bandit problem, pull the arm with the highest Gittins index, then update the indicies.\n* **Restart mdp** - MDP whose optimal value is equivalent to the optimal value of the initial state, and is indifferent between them. Therefore it should just restart.\n* **Bernoulli bandit** - each arm produces a 0<reward<1 with fixed but unknown probability\n* **Bandit superprocess** - BSP, each arm is a full Markov decision process instead of just a Markov reward process with only one possible action.\n* **Opportunity cost** - how much utility is given up per time step by not devoting that time to another arm\n* **Dominating policy** - optimal policy of an arm that is unaffected by the opportunity cost.\n* **Reinforcement learning** - the agent interacts with the world and recieves rewards (aka reinforcement) along the way that reflect how well it is doing\n* **Sparse rewards** - vast majority of the state give no informative reward signal\n* **Passive reinforcement learning** - agent's policy is fixed, needs to learn the utilities of states (or state-action pairs).\n* **Active reinforcement learning** - agent also needs to figure out what to do\n* **Pseudoexperience** - Extend TD by creating transitions that might happen\n* **Prioritized sweeping** - heuristic makes adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n* **Utility function** - (the expected total discounted reward if policy is executed)\n* **Passive learning agent** - has a fixed policy that determines its behavior, learner is along for the ride\n* **Active learning agent** - gets to decide what actions to take\n* **Glie** - Greedy in the limit of infinite exploration\n* **Absorbing state** - actions have no effect and rewards are not received\n* **Bayesian reinforcement learning** - assumes a prior prob P(h) over hypotheses h, posterior P(h|e) is obtained using Bayes rule given observations to date\n* **Sarsa** - state, action, reward, state, action\n* **Off-policy** - learns Q-values based on if the agent stops using its current policy and switches to a policy that chooses the best actions based on estimates\n* **On-policy** - learns Q-values based on if the agent continues using its current policy\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n* **Inductive generalization** - agent can generalize from states it has visited to states it has not visited\n* **Catastrophic forgetting** - learns the safe areas too well and forgets the dangerous areas. \n* **Experience replay** - replay failures at a regular interval\n* **Deep reinforcement learning system** - uses a deep network as a function approximator\n* **Credit assignment problem** - working out what a model did wrong after many commands for many variables\n* **Reward shaping** - supplying the agent with additional rewards (psuedorewards) for making progress\n* **Hierarchical reinforcement learning (hrl)** - breaking up long action sequences into smaller pieces to make learning easier\n* **Joint state space** - each state (s,m) is composed of a physical state s and machine state m\n* **Choice state** - program counter for m is at a choice point for the agent program. decisions are not made in between choice states.\n* **Policy search** - keep updating the policy as long as its performance improves, then stop\n* **Correlated sampling** - using the same inputs during trials to eliminate the measure error due to differences\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 = r\"\"\"\n",
        "One approach is to create a logically exhaustive solution, but this is not possible because it is too much work to list all the rules, there might not be complete domain knowledge, and not \n",
        "all the information that needs to be known is known. We can deal with degrees of believe through probability theory. \n",
        "\"\"\"\n",
        "chapter12_2 = r\"\"\" \n",
        "* Conditional probability: $P(a|b) = \\frac{P(a \\land b)}{P(b)}$\n",
        "* Product Rule: $P(a \\land b) = P(a|b)P(b)$\n",
        "* axioms of probability\n",
        " * inclusion-exclusion principle: $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n",
        " * $0 \\leq P(\\omega) \\leq \\textnormal{ for every } \\omega \\textnormal{ and } \\sum_{\\omega \\in \\Omega}P(\\omega)=1$ --> for all probabilities between 0 and 1, the sum of the probabilities equals 1\n",
        " * full joint probability distribution: often not possible to build out the full table becuase it is too large to create and use. \n",
        " \"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "* marginalization or summing out: $P(Y)=\\sum_z P(Y, Z=z)$ --> sum up the probabilties for each possible value of the other variables\n",
        "* conditioning: $\\sum_z P(Y|z)P(z)$\n",
        " \"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        "* independence: $P(a|b) = P(a)$, $P(b|a)=P(b)$, $P(a \\land b) = P(a)P(b)$. Independence assertion can simplify the size of the domain representation and complexity of the inference problem, \n",
        "but they are usually quite rare.  \n",
        "\"\"\"\n",
        "chapter12_5 = r\"\"\" \n",
        "* Bayes' Rule: $P(b|a) = \\frac{P(a|b)P(b)}{P(a)}$ or P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}\n",
        " * P(effect|cause) quantifies the relationship in the casual direction\n",
        " * P(cause|effect) quantifies the relationship in the diagnostic direction\n",
        "* Conditional Independence: $P(X,Y|Z)=P(X|Z)P(Y|Z)$\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "* Naive Bayes Model: $P(Cause, Effect_1, ..., Effect_n)=P(Cause)\\Pi_iP(Effect_i|Cause)$\n",
        " * 'naive' because it is often used in cases where the effect variable is not strictly independent given the cause variable (we are using it to simplify)\n",
        "\n",
        "\n",
        "We can use Naive Bayes' for text classification, given text, decide which predefined set of classes or categories it should belong to. \n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\"\n",
        "* Chain Rule of Probability: $P(X_1, ..., X_n)=P(X_1)P(X_2|X_1)P(X_3|X_{1:2}...P(X_n|X_{1:n-1})=\\Pi_{k=1}^{n}P(X_k|X_{1:k-1})$\n",
        "* bigram approximates the probability of a word given all previous words by using only the conditional probability of the preceding word\n",
        "* Markov assumption: predict the probability of some future unit without looking too far into the past. A bigram is an example of a Markov assumption.\n",
        "* Maximum Likelihood estimation (MLE): get counts from a corpus and normalize the counts so they lie between 0 and 1.\n",
        "* relative frequency: divide the observed frequency of a sequence by the observed frequency of a prefix. Used in MLE. \n",
        "\n",
        "It is more common to use trigram, 4, or 5-gram models where there is sufficient training data. For larger grams, the sentences will need more padding. \n",
        "To make the math easier, use log probabilities since we can sum them. This allows solves the problem of multiplying lots of small numbers together to \n",
        "get an even smaller number.\n",
        "* $p1 * p2 * p3 * p4 = exp(logp1 + logp2 + logp3 + logp4) $\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = r\"\"\"\n",
        "Extrinsic evaluation is the only way to know if a particular improvement in a component is going to help the task. But this can be expensive to run \n",
        "big NLP systems end to end, therefore we most often test it intrinsically with a test set. The model is trained on a training set (training corpus) \n",
        "and tested with unseen data with a test set that was held out from the training data. When comparing models, whichever model has the highest probabiliity \n",
        "(it more accurately predicted the tests set) is the better model. Sometimes we need to implicitly tune the model first. We give it a initial test set \n",
        "called the development test set or devset. Usually we divide the data into 80% training, 10% development, and 10% test. \n",
        "\n",
        "Perplexity: $PP(W) = \\sqrt[N]{\\Pi_{i=1}^{N} \\frac{1}{P(w_i|w_{i-1})}}$\n",
        "* We can also think about perplexity as the weighted average branching factor of a language.  \n",
        "* When computing perplexities, the n-gram model must be constructed without any knowledge of the test set or of the vocabulary of the test set. If it is, \n",
        "the perplexity can end up artificially low. The higher the conditional probability of the word sequence, the lower the perplexity. We want to minimize the \n",
        "perplexity which is equivalent to maximizing the probability.\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "When training models for n-grams, we need to stay in the simplier genre as the question we are trying to answer. Combining genre's for more data will result \n",
        "in outputs that are not relevant. This also includes getting the corpus in the correct dialect/variety. Modeling might still have the problem of sparsity in \n",
        "the corpus, resulting in \"zero probability n-grams\" where the model will not know that n-gram from the test set is actually possible since it didnt see it in \n",
        "the training set. These are a problem because they underestimate the probability of other words that might occur, which hurts the performance of the application, \n",
        "and because if it is zero, then the entire probability of the test set is 0. THen we can't compute perplexity because we are not allowed to divide by zero. \n",
        "\n",
        "We will need to know how to deal with these unknown words. We can train with an open vocabulary using the pseudoword <UNK>.\n",
        "* Option 1: Turn the problem back into a closed vocabulary by choosing a fixed vocabulary in advance\n",
        " * Choose a vocabulary fixed in advanced\n",
        " * Convert any word in the training set that is not in the vocab to the unknown word token\n",
        " * Estimate the prob for <UNK> from its counts like any other word\n",
        "* Option 2: If we don't have a prior vocab, create one implicitly, replace words in training data with <UNK> based on their frequency. \n",
        " * For example, replace all words that occur fewer times than n with <UNK>. Then proceed as above. \n",
        "\n",
        "\n",
        "UNK does not have any effect on perplexity. For this reason, perlexities should only be compared across language models with same vocabs. \n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "What do we do if the words appear in the vocabulary but then appear in the test data in an unseen context? In order to not assign zero probability, \n",
        "we need to modify with smoothing or discounting. This is were we take some probability from more frequent events and give it to events we have never seen. \n",
        "* Laplace smoothing: add one to all n-gram counts before normalizing them into probabilities. All counts would at least be one and there would be no zero \n",
        "counts. This does not perform well enough to be used in modern n-gram models. \n",
        "* Add-k smoothing: add a fractional count k to each count. This requires a method for choosing k, which could be done by optimizing on a devset. Still doesnt \n",
        "work well, generates counts with poor variances and inappropriate discounts. \n",
        "* Backoff: using less context to generalize for more. For example, we can use the trigram if evidence is sufficent, otherwise use a bigram or unigram accordingly. \n",
        "Only backoff to a lower order n-gram if there is zero evidence for a higher order one. \n",
        "* Interpolation: mix the probability estimates from all n-gram estimators, weighing and combining the counts and linearly interpolate them with constants $\\lambda$. \n",
        "The $\\lambda$ values can be learned from a held-out corpus to learn these hyperparameters.   \n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "stupid backoff: gives up the idea of trying to make a language model a true probability distribution. No discounting of higher order probabilities. If a higher order \n",
        "n-gram has a zero count, simply backoff to a lower order and weight it by a fixed (context independent) weight. This does not produce a probability distribution. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"belief state\" : \"representation of the set of all possible worlds states that the agent might be in\",\n",
        "\"utility\" : \"the quality of being useful\",\n",
        "\"decision theory\" : \"= probability theory + utility theory\",\n",
        "\"maximum utility theory\" : \"an agent is rational iff it chooses the action yielding highest expected utility, averaged over all possible outcomes of the action\",\n",
        "\"unconditional or prior probabilities\" : \"degrees of belief in proposition in the absense of any other information\",\n",
        "\"conditional or posterior probability\" : \"probability given another piece of information\",\n",
        "\"probability density function\" : \"for continuous variables, function that determines the probability from some value x\",\n",
        "\"probabilistic inference\" : \"computation of posterial probabilties for query propositions given observed evidence\",\n",
        "\"normalization\" : \"constant to allow the probability distribution to add up to 1, $\\alpha$\",\n",
        "\"full joint probability distribution\" : \"specifies the probability of each complete assignment of values to random variables (usually in tabular form)\",\n",
        "\"(absolute) independence\" : \"based on knowledge domain, two variables have no relationship and do not impact one another\",\n",
        "\"language model\" : \"models that are assigned probabilities to sequence of words\",\n",
        "\"n-gram\" : \"sequence of n words (bigram, trigram)\",\n",
        "\"extrinsic evaluation\" : \"embedding a model into an application and measure how well the application improves\",\n",
        "\"intrinsic evaluation\" : \"measures the quality of a model independent of any application\",\n",
        "\"perplexity\" : \"variant of probability, inverse probability of the test set, normalized by the number of words\",\n",
        "\"weighted average branching factor\" : \"number of possible next words that can follow any word\",\n",
        "\"sampling\" : \"choosing random points according to their likelihood\",\n",
        "\"closed vocabulary\" : \"test set only contains words from this vocabulary, there are no unknown words\",\n",
        "\"out of vocabulary\" : \"using unknown words (OOV)\",\n",
        "\"OOV rate\" : \"percentage of words that appear in the test set that are OOV\",\n",
        "\"open vocabulary\" : \"model these potential unknow words in the test set by adding a psuedoword <UNK>\",\n",
        "\"held-out corpus\" : \"additional training corpus\",\n",
        "\"discounting\" : \"lowering some non-zero counts to get probabiliby mass to assign to zero-counts\",\n",
        "}"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b56b9770-20e5-439b-8375-a7f9e4dc9706"
      },
      "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": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\nOne approach is to create a logically exhaustive solution, but this is not possible because it is too much work to list all the rules, there might not be complete domain knowledge, and not \nall the information that needs to be known is known. We can deal with degrees of believe through probability theory. \n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n* Conditional probability: $P(a|b) = \\frac{P(a \\land b)}{P(b)}$\n* Product Rule: $P(a \\land b) = P(a|b)P(b)$\n* axioms of probability\n * inclusion-exclusion principle: $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n * $0 \\leq P(\\omega) \\leq \\textnormal{ for every } \\omega \\textnormal{ and } \\sum_{\\omega \\in \\Omega}P(\\omega)=1$ --> for all probabilities between 0 and 1, the sum of the probabilities equals 1\n * full joint probability distribution: often not possible to build out the full table becuase it is too large to create and use. \n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n* marginalization or summing out: $P(Y)=\\sum_z P(Y, Z=z)$ --> sum up the probabilties for each possible value of the other variables\n* conditioning: $\\sum_z P(Y|z)P(z)$\n \n\n## AIMA Chapter 12.4 Independence\n \n* independence: $P(a|b) = P(a)$, $P(b|a)=P(b)$, $P(a \\land b) = P(a)P(b)$. Independence assertion can simplify the size of the domain representation and complexity of the inference problem, \nbut they are usually quite rare.  \n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n* Bayes' Rule: $P(b|a) = \\frac{P(a|b)P(b)}{P(a)}$ or P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}\n * P(effect|cause) quantifies the relationship in the casual direction\n * P(cause|effect) quantifies the relationship in the diagnostic direction\n* Conditional Independence: $P(X,Y|Z)=P(X|Z)P(Y|Z)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n* Naive Bayes Model: $P(Cause, Effect_1, ..., Effect_n)=P(Cause)\\Pi_iP(Effect_i|Cause)$\n * 'naive' because it is often used in cases where the effect variable is not strictly independent given the cause variable (we are using it to simplify)\n\n\nWe can use Naive Bayes' for text classification, given text, decide which predefined set of classes or categories it should belong to. \n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n\n* Chain Rule of Probability: $P(X_1, ..., X_n)=P(X_1)P(X_2|X_1)P(X_3|X_{1:2}...P(X_n|X_{1:n-1})=\\Pi_{k=1}^{n}P(X_k|X_{1:k-1})$\n* bigram approximates the probability of a word given all previous words by using only the conditional probability of the preceding word\n* Markov assumption: predict the probability of some future unit without looking too far into the past. A bigram is an example of a Markov assumption.\n* Maximum Likelihood estimation (MLE): get counts from a corpus and normalize the counts so they lie between 0 and 1.\n* relative frequency: divide the observed frequency of a sequence by the observed frequency of a prefix. Used in MLE. \n\nIt is more common to use trigram, 4, or 5-gram models where there is sufficient training data. For larger grams, the sentences will need more padding. \nTo make the math easier, use log probabilities since we can sum them. This allows solves the problem of multiplying lots of small numbers together to \nget an even smaller number.\n* $p1 * p2 * p3 * p4 = exp(logp1 + logp2 + logp3 + logp4) $\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nExtrinsic evaluation is the only way to know if a particular improvement in a component is going to help the task. But this can be expensive to run \nbig NLP systems end to end, therefore we most often test it intrinsically with a test set. The model is trained on a training set (training corpus) \nand tested with unseen data with a test set that was held out from the training data. When comparing models, whichever model has the highest probabiliity \n(it more accurately predicted the tests set) is the better model. Sometimes we need to implicitly tune the model first. We give it a initial test set \ncalled the development test set or devset. Usually we divide the data into 80% training, 10% development, and 10% test. \n\nPerplexity: $PP(W) = \\sqrt[N]{\\Pi_{i=1}^{N} \\frac{1}{P(w_i|w_{i-1})}}$\n* We can also think about perplexity as the weighted average branching factor of a language.  \n* When computing perplexities, the n-gram model must be constructed without any knowledge of the test set or of the vocabulary of the test set. If it is, \nthe perplexity can end up artificially low. The higher the conditional probability of the word sequence, the lower the perplexity. We want to minimize the \nperplexity which is equivalent to maximizing the probability.\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n\nWhen training models for n-grams, we need to stay in the simplier genre as the question we are trying to answer. Combining genre's for more data will result \nin outputs that are not relevant. This also includes getting the corpus in the correct dialect/variety. Modeling might still have the problem of sparsity in \nthe corpus, resulting in \"zero probability n-grams\" where the model will not know that n-gram from the test set is actually possible since it didnt see it in \nthe training set. These are a problem because they underestimate the probability of other words that might occur, which hurts the performance of the application, \nand because if it is zero, then the entire probability of the test set is 0. THen we can't compute perplexity because we are not allowed to divide by zero. \n\nWe will need to know how to deal with these unknown words. We can train with an open vocabulary using the pseudoword <UNK>.\n* Option 1: Turn the problem back into a closed vocabulary by choosing a fixed vocabulary in advance\n * Choose a vocabulary fixed in advanced\n * Convert any word in the training set that is not in the vocab to the unknown word token\n * Estimate the prob for <UNK> from its counts like any other word\n* Option 2: If we don't have a prior vocab, create one implicitly, replace words in training data with <UNK> based on their frequency. \n * For example, replace all words that occur fewer times than n with <UNK>. Then proceed as above. \n\n\nUNK does not have any effect on perplexity. For this reason, perlexities should only be compared across language models with same vocabs. \n\n\n## SLP Chapter 3.5 Smoothing\n\nWhat do we do if the words appear in the vocabulary but then appear in the test data in an unseen context? In order to not assign zero probability, \nwe need to modify with smoothing or discounting. This is were we take some probability from more frequent events and give it to events we have never seen. \n* Laplace smoothing: add one to all n-gram counts before normalizing them into probabilities. All counts would at least be one and there would be no zero \ncounts. This does not perform well enough to be used in modern n-gram models. \n* Add-k smoothing: add a fractional count k to each count. This requires a method for choosing k, which could be done by optimizing on a devset. Still doesnt \nwork well, generates counts with poor variances and inappropriate discounts. \n* Backoff: using less context to generalize for more. For example, we can use the trigram if evidence is sufficent, otherwise use a bigram or unigram accordingly. \nOnly backoff to a lower order n-gram if there is zero evidence for a higher order one. \n* Interpolation: mix the probability estimates from all n-gram estimators, weighing and combining the counts and linearly interpolate them with constants $\\lambda$. \nThe $\\lambda$ values can be learned from a held-out corpus to learn these hyperparameters.   \n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\nstupid backoff: gives up the idea of trying to make a language model a true probability distribution. No discounting of higher order probabilities. If a higher order \nn-gram has a zero count, simply backoff to a lower order and weight it by a fixed (context independent) weight. This does not produce a probability distribution. \n\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - representation of the set of all possible worlds states that the agent might be in\n* **Utility** - the quality of being useful\n* **Decision theory** - = probability theory + utility theory\n* **Maximum utility theory** - an agent is rational iff it chooses the action yielding highest expected utility, averaged over all possible outcomes of the action\n* **Unconditional or prior probabilities** - degrees of belief in proposition in the absense of any other information\n* **Conditional or posterior probability** - probability given another piece of information\n* **Probability density function** - for continuous variables, function that determines the probability from some value x\n* **Probabilistic inference** - computation of posterial probabilties for query propositions given observed evidence\n* **Normalization** - constant to allow the probability distribution to add up to 1, $\u0007lpha$\n* **Full joint probability distribution** - specifies the probability of each complete assignment of values to random variables (usually in tabular form)\n* **(absolute) independence** - based on knowledge domain, two variables have no relationship and do not impact one another\n* **Language model** - models that are assigned probabilities to sequence of words\n* **N-gram** - sequence of n words (bigram, trigram)\n* **Extrinsic evaluation** - embedding a model into an application and measure how well the application improves\n* **Intrinsic evaluation** - measures the quality of a model independent of any application\n* **Perplexity** - variant of probability, inverse probability of the test set, normalized by the number of words\n* **Weighted average branching factor** - number of possible next words that can follow any word\n* **Sampling** - choosing random points according to their likelihood\n* **Closed vocabulary** - test set only contains words from this vocabulary, there are no unknown words\n* **Out of vocabulary** - using unknown words (OOV)\n* **Oov rate** - percentage of words that appear in the test set that are OOV\n* **Open vocabulary** - model these potential unknow words in the test set by adding a psuedoword <UNK>\n* **Held-out corpus** - additional training corpus\n* **Discounting** - lowering some non-zero counts to get probabiliby mass to assign to zero-counts\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 = r\"\"\"\n",
        "Bayes' net (network) is a technique for describing complex joint distributions (aka models) using simple, local distributions (aka conditional probabilities). \n",
        "These are graphical models that describe how variables locally interact. \n",
        "* Nodes: variables (with domains) that are observed (assigned) or unobserved (unassigned)\n",
        "* Arcs: interations indicating direct influence between variables and encode condiation independence. \n",
        "Direction of the arrow could mean causation. e.g. rain --> (causes) traffic but actually mean correlation and encode conditional independence.\n",
        "\n",
        "\n",
        "Bayes' nets are directed acyclic graphs and the graphs can be turned into a conditional probability table (CPT) \n",
        "* P(X|A1...An) for all nodes An that are pointing to X\n",
        "\n",
        "\n",
        "Bayes' nets implicitly encode join distributions, which are a product of local conditional distributions. But not every BN can represent every join distribution. \n",
        "For N boolean variables, BNs are of size $2^N$. An N-node net with k parents is $O(N*2)^{k+1}$. With both of these nets, we can calculate probability but BNs give \n",
        "a huge space savings and are easier to elicit local CPTs. $\\perp \\!\\!\\! \\perp$ means independent (X is independent of Y)\n",
        "* X and Y are independent if $\\forall x,y  P(x,y)=P(x)P(y) \\leftarrow X \\perp \\!\\!\\! \\perp Y$\n",
        "* X and Y are conditionally independent given Z if $\\forall x,y,z  P(x,y|z) =P((x|z)P(y|z) \\leftarrow X \\perp \\!\\!\\! \\perp Y|Z$\n",
        "\n",
        "\n",
        "BNs contains independence assumptions that need to be understood when modeling with a BN.\n",
        "We can break BNs into descendents using D-separation, breaking it down into triples. \n",
        "We can use BNs to analyze casual chains and common causes to determine independence with three variables. If the path is blocked, they are not conditionally independent. \n",
        "* what are all the paths/triples between the variables? \n",
        "* are they inactive or active triples? if a variable is given, then shaded it. Then compare the triple to the picture. \n",
        "* if all the paths are inactive, then independece is guranteed. \n",
        "* path is active if all triples in the path is active. if one is not active, then the path is inactive and conditional independence is guranteed.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 771
        },
        "cellView": "form",
        "outputId": "e3c5a6b0-eb2d-4c90-e12e-13c1c7759680"
      },
      "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": 29,
      "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\nBayes' net (network) is a technique for describing complex joint distributions (aka models) using simple, local distributions (aka conditional probabilities). \nThese are graphical models that describe how variables locally interact. \n* Nodes: variables (with domains) that are observed (assigned) or unobserved (unassigned)\n* Arcs: interations indicating direct influence between variables and encode condiation independence. \nDirection of the arrow could mean causation. e.g. rain --> (causes) traffic but actually mean correlation and encode conditional independence.\n\n\nBayes' nets are directed acyclic graphs and the graphs can be turned into a conditional probability table (CPT) \n* P(X|A1...An) for all nodes An that are pointing to X\n\n\nBayes' nets implicitly encode join distributions, which are a product of local conditional distributions. But not every BN can represent every join distribution. \nFor N boolean variables, BNs are of size $2^N$. An N-node net with k parents is $O(N*2)^{k+1}$. With both of these nets, we can calculate probability but BNs give \na huge space savings and are easier to elicit local CPTs. $\\perp \\!\\!\\! \\perp$ means independent (X is independent of Y)\n* X and Y are independent if $\\forall x,y  P(x,y)=P(x)P(y) \\leftarrow X \\perp \\!\\!\\! \\perp Y$\n* X and Y are conditionally independent given Z if $\\forall x,y,z  P(x,y|z) =P((x|z)P(y|z) \\leftarrow X \\perp \\!\\!\\! \\perp Y|Z$\n\n\nBNs contains independence assumptions that need to be understood when modeling with a BN.\nWe can break BNs into descendents using D-separation, breaking it down into triples. \nWe can use BNs to analyze casual chains and common causes to determine independence with three variables. If the path is blocked, they are not conditionally independent. \n* what are all the paths/triples between the variables? \n* are they inactive or active triples? if a variable is given, then shaded it. Then compare the triple to the picture. \n* if all the paths are inactive, then independece is guranteed. \n* path is active if all triples in the path is active. if one is not active, then the path is inactive and conditional independence is guranteed.\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 = r\"\"\"\n",
        "Model-Based Classification - build a model, like a Bayes' Net where both the label and the features are random variables. \n",
        "Instantiate any observed features and query for the distribution of the label conditioned on the features. Query variable \n",
        "is random variable that we want to make an inference on. One approach we \n",
        "could use is Naive Bayes where we assume all the features are independent. The features are determined to be either on or \n",
        "off (1 or 0). We are trying to learn the labels for the features. To use Naive Bayes, we need \n",
        "* Inference: start with a bunch of probabilities, calculate the standard inference.\n",
        "* Estimates of local conditional probability tables: these probabilities are called the parameters $\\theta$ of the model. \n",
        "These are determined from the training data counts. \n",
        "\n",
        "We are trying to learn all the probability tables. The prior probability times the probability of all of the features given \n",
        "the label. For digits, the prior probability would be 1/10 since there are 10 digits. Size is the number of classes we have \n",
        "times number of features to n. With Naive Bayes, this would change to n*F*Y. Since we are making strong indepenence assumptions, \n",
        "it does not perfectly capture reality but it will do ok and work quickly. \n",
        "* get the prob of y given all the features. get join prob of label and evidence for each label. \n",
        "* sum over the probabiliy of the labels after naive bayes\n",
        "* divide step 1 by step 2\n",
        "* we need to learn the feature values\n",
        "\n",
        "Bag-of-words Naive Bayes: \n",
        "* represent a text document as a \"bag-of-words\" that are an unordered set of words, keeping only their frequency. \n",
        "\n",
        "\n",
        "If we are giving relative frequencies with zero probabilities, we run the risk of overfitting the data, which will result in \n",
        "incorrect classification. We can use smoothing and parameter estimation for this. \n",
        "* elicitation based - ask a human, domain knowledge\n",
        "* empirically - learn using data (P = count of x /total samples)\n",
        "  * if we have two probability possibilities, the best is the one that maximizes the likelihood of the data. $L(x, \\theta_1) = 2/3* 2/3* 1/3 = 0.148$ vs $L(x, \\theta_2) = 1/2* 1/2* 1/2=0.125$ \n",
        "  this gives the best fit for the data.\n",
        "\n",
        "\n",
        "But what do we do with unseen events? Laplace smoothing can add 1. Or some other number with a hyperparameter. Another option \n",
        "is linear interpolation with value $\\alpha$. Learn prob from training data set, train the hyperparamters from the heldout set. \n",
        "Other options to improve is to add more features. If the model is getting good accuracy, we need a baseline to compare it to. \n",
        "What is the best model accuracy for the current approaches for the same problem? Did it beat it?  \n",
        "\n",
        "\n",
        "Perceptron is a different classifer for making decisions. The features are representing something we want to classify. \n",
        "Their values are fixed but we can choose different weight vectors. Depending on the weigh vector chosen, we will get a different classifier. \n",
        "In the space of feature vectors, each of the examples are points and a weight vector is a hyperplane. For a binary perceptron, the weights \n",
        "will start at 0, if the label is correct, dont change the weight, but if it is not, then adjust the value of the weight vector. The highest \n",
        "value would be determined to be the label. \n",
        "\n",
        "If data is not separable, then we loose accuracy. Perceptrons can also have problems with drawing the line between classes so that it barely \n",
        "separates the data. It also can overtrain, similar to overfitting. \n",
        "* One approach is to adjust the weights to mitigate these effects with an approach like MIRA (Margin Infused Relaxed Algorithm). \n",
        "* Another could be to maximize the step size so that you are not making too big of an \n",
        "update at one time. \n",
        "* Support Vector Machines allow us to maximize the margin or space between the data so that the separating line is in the \n",
        "middle between them. SVMs are similar to MIRA where you optimize over all examples at once.\n",
        "* Non-linear separators take the data and map it to a higher dimensional space where it can be separable\n",
        "\n",
        "\n",
        "Activation Functions:\n",
        "\n",
        "We can apply a non-linear function in order to add dimensionality to the model.\n",
        "* sigmoid function\n",
        "* tanh function\n",
        "* rectified linear unit ReLU\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"classification\" : \"given inputs x, predict labels y\",    \n",
        "\"separability\" : \"true if some parameters get the training set perfectly correct, such as with the hyperplane\",\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 or degree of separability\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b81b63cf-c572-44aa-b283-3bdfca8aac06"
      },
      "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": 31,
      "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\nModel-Based Classification - build a model, like a Bayes' Net where both the label and the features are random variables. \nInstantiate any observed features and query for the distribution of the label conditioned on the features. Query variable \nis random variable that we want to make an inference on. One approach we \ncould use is Naive Bayes where we assume all the features are independent. The features are determined to be either on or \noff (1 or 0). We are trying to learn the labels for the features. To use Naive Bayes, we need \n* Inference: start with a bunch of probabilities, calculate the standard inference.\n* Estimates of local conditional probability tables: these probabilities are called the parameters $\\theta$ of the model. \nThese are determined from the training data counts. \n\nWe are trying to learn all the probability tables. The prior probability times the probability of all of the features given \nthe label. For digits, the prior probability would be 1/10 since there are 10 digits. Size is the number of classes we have \ntimes number of features to n. With Naive Bayes, this would change to n*F*Y. Since we are making strong indepenence assumptions, \nit does not perfectly capture reality but it will do ok and work quickly. \n* get the prob of y given all the features. get join prob of label and evidence for each label. \n* sum over the probabiliy of the labels after naive bayes\n* divide step 1 by step 2\n* we need to learn the feature values\n\nBag-of-words Naive Bayes: \n* represent a text document as a \"bag-of-words\" that are an unordered set of words, keeping only their frequency. \n\n\nIf we are giving relative frequencies with zero probabilities, we run the risk of overfitting the data, which will result in \nincorrect classification. We can use smoothing and parameter estimation for this. \n* elicitation based - ask a human, domain knowledge\n* empirically - learn using data (P = count of x /total samples)\n  * if we have two probability possibilities, the best is the one that maximizes the likelihood of the data. $L(x, \\theta_1) = 2/3* 2/3* 1/3 = 0.148$ vs $L(x, \\theta_2) = 1/2* 1/2* 1/2=0.125$ \n  this gives the best fit for the data.\n\n\nBut what do we do with unseen events? Laplace smoothing can add 1. Or some other number with a hyperparameter. Another option \nis linear interpolation with value $\\alpha$. Learn prob from training data set, train the hyperparamters from the heldout set. \nOther options to improve is to add more features. If the model is getting good accuracy, we need a baseline to compare it to. \nWhat is the best model accuracy for the current approaches for the same problem? Did it beat it?  \n\n\nPerceptron is a different classifer for making decisions. The features are representing something we want to classify. \nTheir values are fixed but we can choose different weight vectors. Depending on the weigh vector chosen, we will get a different classifier. \nIn the space of feature vectors, each of the examples are points and a weight vector is a hyperplane. For a binary perceptron, the weights \nwill start at 0, if the label is correct, dont change the weight, but if it is not, then adjust the value of the weight vector. The highest \nvalue would be determined to be the label. \n\nIf data is not separable, then we loose accuracy. Perceptrons can also have problems with drawing the line between classes so that it barely \nseparates the data. It also can overtrain, similar to overfitting. \n* One approach is to adjust the weights to mitigate these effects with an approach like MIRA (Margin Infused Relaxed Algorithm). \n* Another could be to maximize the step size so that you are not making too big of an \nupdate at one time. \n* Support Vector Machines allow us to maximize the margin or space between the data so that the separating line is in the \nmiddle between them. SVMs are similar to MIRA where you optimize over all examples at once.\n* Non-linear separators take the data and map it to a higher dimensional space where it can be separable\n\n\nActivation Functions:\n\nWe can apply a non-linear function in order to add dimensionality to the model.\n* sigmoid function\n* tanh function\n* rectified linear unit ReLU\n\n\n## Module 12 Definitions\n* **Classification** - given inputs x, predict labels y\n* **Separability** - true if some parameters get the training set perfectly correct, such as with the hyperplane\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 or degree of separability\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 = r\"\"\"\n",
        "Just like the last module, we are working with classifiers:\n",
        "* Feature representation: vector of features x\n",
        "* classification function: computers our predictions $\\hat{y}$ from the probabilities\n",
        "* objective function: NEW, also known as a loss function, this allows us to learn and usually involves trying to minimize the error on the training examples\n",
        "* some algorithm for optimizing the objective function, updates the parameters, (e.g. stochasic gradient descent)\n",
        "\n",
        "\n",
        "learning with the dot product of weights $z = w \\cdot x + b$\n",
        "\n",
        "We will squish the value z with the sigmoid function (logrithmic function). $P = \\sigma (w \\cdot x + b)$. \n",
        "What is the threshold for pos vs neg class? This is easy for binary because it is 1 if >0.5 and 0 otherwise. \n",
        "Feature engineering is the process of creating features that we can use to classify the review. The weights \n",
        "can be given to us to how important that feature is to classify the statement. Then take the product of value * weight \n",
        "and add them together and that gives the z value. Then we can apply the sigmoid ($y=1/(1+e^{-z})$) to squish it into the range for a \n",
        "probability. \n",
        "\n",
        "But usually the weights are not given to us, so we need to learn them. \n",
        "* objective function or loss function that gives us the distance between the system output and the gold \n",
        "output. for this we will use cross-entropy loss\n",
        "* we will use stochastic gradient descent to minimize (aka optimize) the loss function. \n",
        "\n",
        "Loss Functions:\n",
        "\n",
        "How close is the classifer to the correct output. How much does $\\hat{y}$ different from true y.\n",
        "$L_{MSE}(\\hat{y}, y)=1/2(\\hat{y}-y)^2$. The loss function prefers that correct class labels of \n",
        "the training example to be more likely. Using conditional maximum likelihood estimateion, we choose \n",
        "parameters for w, b that maximizes the (log) probabilities of the true labels inthe training data. \n",
        "the resulting loss function is the negative log likeihood loss, called the *cross entropy loss*. \n",
        "When trying maximize the probability, we want y_hat as high as possible when y is supposed to equal 1, \n",
        "and for y_hat to be as low as possible (near to zero) when y is supposed to equal 0. \n",
        "$L_{CE}(\\hat{y},y)=-[y log \\theta (w \\cdot x +b) +(1-y) log (1- \\theta (w \\cdot x +b)]$ \n",
        "If y=1 the second term would drop out and we would only need to compute the first term because \n",
        "of math. If y=0, then the first term would drop and we would only compute the second term. \n",
        "The log values will get smaller and smaller if the values are getting closer to the truth. \n",
        "So we want to minimize the loss of all labels in the training set. \n",
        "\n",
        "To find good parameters, we can use Gradient Descent to find a minimum function by figuring out in \n",
        "which direction (in the space of parameters theta) the function's scope is rising the most steeply \n",
        "and moving in the opposite direction. For logistic regression, the loss function is convex, so we \n",
        "need to look for the one minimum, gradient descent will help to find the minimum by comparing the slopes. \n",
        "We need to do this across many dimensions. \n",
        "\n",
        "Stochastic gradient descent chooses a single random example at a time and updates its weights. Because \n",
        "of this randomness, the updates can fluctuate. An alternative is bath training which compute the gradient \n",
        "over the entire dataset, but this takes a long time, even though it gives a better estiamte. A compromise \n",
        "is mini-batch training. The size of the batch is selected based on computational resources so that all examples \n",
        "in the mini-batch can run in parallel. Afterwards, the loss is accumulated. \n",
        "\n",
        "Overfitting is a problem with many ML models. This is a result of poor generalization and performance on \n",
        "an unseen test set. In log regression, if a feature only occurs in one class then it gets a high \n",
        "weight. If we are modeling noisy factors, they can accidently correlate with the class which can \n",
        "mess with the weights. Regularization is a way to penalize large weights. This is a term used to add to \n",
        "the loss function. \n",
        "* Lasso regresssion = L1 regularization \n",
        "* Ridge regression = L2 regularization\n",
        "\n",
        "If we want more than two classes, we need a generalization of the sigmoid function called the \n",
        "softmax function: $softmax(z_i)=\\frac{e^{z_j}}{\\sum_{j=1}^{k}e^{z_j}} 1 \\geq i \\geq k$. The \n",
        "softmax function takes an input vector z and outputs a vector of normalized probabilities for \n",
        "each of the classes. \n",
        "\n",
        "\n",
        "Neural Networks:\n",
        "\n",
        "A single computations unit is the building block of NN. THe simpliest kind of NN is the \n",
        "Feed-Forward Neural Network. This is a multilayered network where all units are fully connected \n",
        "and there are no cycles. Outputs are passed from each layer and every passed back down. \n",
        "* multiple the weight maxtrix by the input vector x\n",
        "* adding the bias vector b \n",
        "* applying the activation function g (such as sigmoid)\n",
        "\n",
        "The output of the hidden layer ($h=\\sigma (Wx+b$) is passed to the output layer ($z=Uh$) where \n",
        "U is the weight matrix and z is the output). Output z is then passed to softmax to compute the final \n",
        "probability distribution to normalize the output. \n",
        "\n",
        "To train a NN, we need \n",
        "* loss function - cross entropy loss \n",
        "* optimization algorithm - gradient descent \n",
        "* computing the gradient of the loss function - error propagation \n",
        "\n",
        "\n",
        "For deep networks, we need to compute the gradient by looking back through all the earilier layers \n",
        "in the network. To do this, we can use error backpropagation.  \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a1c02676-2124-404d-b671-e99d823cdb37"
      },
      "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": 33,
      "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\nJust like the last module, we are working with classifiers:\n* Feature representation: vector of features x\n* classification function: computers our predictions $\\hat{y}$ from the probabilities\n* objective function: NEW, also known as a loss function, this allows us to learn and usually involves trying to minimize the error on the training examples\n* some algorithm for optimizing the objective function, updates the parameters, (e.g. stochasic gradient descent)\n\n\nlearning with the dot product of weights $z = w \\cdot x + b$\n\nWe will squish the value z with the sigmoid function (logrithmic function). $P = \\sigma (w \\cdot x + b)$. \nWhat is the threshold for pos vs neg class? This is easy for binary because it is 1 if >0.5 and 0 otherwise. \nFeature engineering is the process of creating features that we can use to classify the review. The weights \ncan be given to us to how important that feature is to classify the statement. Then take the product of value * weight \nand add them together and that gives the z value. Then we can apply the sigmoid ($y=1/(1+e^{-z})$) to squish it into the range for a \nprobability. \n\nBut usually the weights are not given to us, so we need to learn them. \n* objective function or loss function that gives us the distance between the system output and the gold \noutput. for this we will use cross-entropy loss\n* we will use stochastic gradient descent to minimize (aka optimize) the loss function. \n\nLoss Functions:\n\nHow close is the classifer to the correct output. How much does $\\hat{y}$ different from true y.\n$L_{MSE}(\\hat{y}, y)=1/2(\\hat{y}-y)^2$. The loss function prefers that correct class labels of \nthe training example to be more likely. Using conditional maximum likelihood estimateion, we choose \nparameters for w, b that maximizes the (log) probabilities of the true labels inthe training data. \nthe resulting loss function is the negative log likeihood loss, called the *cross entropy loss*. \nWhen trying maximize the probability, we want y_hat as high as possible when y is supposed to equal 1, \nand for y_hat to be as low as possible (near to zero) when y is supposed to equal 0. \n$L_{CE}(\\hat{y},y)=-[y log \\theta (w \\cdot x +b) +(1-y) log (1- \\theta (w \\cdot x +b)]$ \nIf y=1 the second term would drop out and we would only need to compute the first term because \nof math. If y=0, then the first term would drop and we would only compute the second term. \nThe log values will get smaller and smaller if the values are getting closer to the truth. \nSo we want to minimize the loss of all labels in the training set. \n\nTo find good parameters, we can use Gradient Descent to find a minimum function by figuring out in \nwhich direction (in the space of parameters theta) the function's scope is rising the most steeply \nand moving in the opposite direction. For logistic regression, the loss function is convex, so we \nneed to look for the one minimum, gradient descent will help to find the minimum by comparing the slopes. \nWe need to do this across many dimensions. \n\nStochastic gradient descent chooses a single random example at a time and updates its weights. Because \nof this randomness, the updates can fluctuate. An alternative is bath training which compute the gradient \nover the entire dataset, but this takes a long time, even though it gives a better estiamte. A compromise \nis mini-batch training. The size of the batch is selected based on computational resources so that all examples \nin the mini-batch can run in parallel. Afterwards, the loss is accumulated. \n\nOverfitting is a problem with many ML models. This is a result of poor generalization and performance on \nan unseen test set. In log regression, if a feature only occurs in one class then it gets a high \nweight. If we are modeling noisy factors, they can accidently correlate with the class which can \nmess with the weights. Regularization is a way to penalize large weights. This is a term used to add to \nthe loss function. \n* Lasso regresssion = L1 regularization \n* Ridge regression = L2 regularization\n\nIf we want more than two classes, we need a generalization of the sigmoid function called the \nsoftmax function: $softmax(z_i)=\\frac{e^{z_j}}{\\sum_{j=1}^{k}e^{z_j}} 1 \\geq i \\geq k$. The \nsoftmax function takes an input vector z and outputs a vector of normalized probabilities for \neach of the classes. \n\n\nNeural Networks:\n\nA single computations unit is the building block of NN. THe simpliest kind of NN is the \nFeed-Forward Neural Network. This is a multilayered network where all units are fully connected \nand there are no cycles. Outputs are passed from each layer and every passed back down. \n* multiple the weight maxtrix by the input vector x\n* adding the bias vector b \n* applying the activation function g (such as sigmoid)\n\nThe output of the hidden layer ($h=\\sigma (Wx+b$) is passed to the output layer ($z=Uh$) where \nU is the weight matrix and z is the output). Output z is then passed to softmax to compute the final \nprobability distribution to normalize the output. \n\nTo train a NN, we need \n* loss function - cross entropy loss \n* optimization algorithm - gradient descent \n* computing the gradient of the loss function - error propagation \n\n\nFor deep networks, we need to compute the gradient by looking back through all the earilier layers \nin the network. To do this, we can use error backpropagation.  \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 = r\"\"\"\n",
        "In Vector Space Models, each document in the collection is represented as a point in space \n",
        "(a vector in a vector space). The user's query is a pseudo-document and joins the other \n",
        "documents in the same space. Information retrieval (IR) was performed by selecting the vectors \n",
        "that are close together in the space to the query vector. \n",
        "\n",
        "Term-Document Matrix:\n",
        "* Each column vector represents a document \n",
        "* Each row vector represents a term \n",
        "* The value in a cell is based on how often that term occured in the document \n",
        "* the length of the document vectors (y-axis) is the size of the vocab\n",
        "* the width of the matrix (x-axis) is the number of documents in the collection\n",
        "* document vectors can be sparse (most values 0)\n",
        "* we can measure how similar two documents are by comparing their column vectors\n",
        "\n",
        "Term-document maxtrices are good for identifying plagarism. Comparing two row vectors let's \n",
        "us see how close words are to each other. We can normalize the data with Vector L2 (length) \n",
        "normalization ($||u||= \\sqrt{\\sum_{i=1}^{n}u_i^2}$) then divide the vector by the L2 length u \n",
        "to get the normalized values which will take care of discrepancies for highly used words. Cosine \n",
        "distance can also be used to compare similarities based on the cosine angle between them. \n",
        "\n",
        "\n",
        "Term-Term Matrix:\n",
        "* aka Term-context matrix\n",
        "* the length of the row vector is now |V| (vocabulary, words) instead of number of documents. \n",
        "so now both axises are the words. \n",
        "* the value in a cell indicates how often the word appears in a context window of the other word. \n",
        "* we need to pick a context window, such as +/-2 words to either side of the target word. \n",
        "\n",
        "\n",
        "\n",
        "Another option is that we can use syntax to define a word's context instead of the surrounding words. \n",
        "Alternatives to raw counts are transforming vectors with methods such as TF-IDF (Term frequency 'how \n",
        "often a word occurs in a document' * inverse document frequency '1 over the number of documents that \n",
        "the word occurs in' ) or PPMI. Co-occurnace matrix (such as weighed by TF-IDF) are long and sparse. \n",
        "An alternative is that we could learn vectors that are short and dense. \n",
        "\n",
        "\n",
        "In Language modeling, we are trying to learn a function that returns the join probability for the words. \n",
        "This is usually hard because there are too many parameters (aka curse of dimensionality) and in n-gram \n",
        "based models, we fail to generalize to related words/word sequences that we already have observed. Neural \n",
        "Language models have several advantages over n-gram LMs. \n",
        "* dont need smoothing \n",
        "* handle longer histories \n",
        "* can generalize over contexts of similar words\n",
        "* have higher predictive accuracy\n",
        "* BUT they are slower to train \n",
        "\n",
        "To do this, we need to... \n",
        "* Associate each word in the vocab with a vector representation, create a notion of similiarity between words \n",
        "* Express joint prob function of a word sequence in terms of the word vectors for the words in that sequence \n",
        "* Simultaneously learn the word vectors and the parameters of the function \n",
        "\n",
        "We can use a multilayer, feed forward neural network to get a prob function that expresses the product \n",
        "of conditional probabilities of the next word given the previous word. \n",
        "* input: k-gram of words\n",
        "* output: prob distribution over next word\n",
        "* k context words is treated as a word window. Each word is associated with an embedding vector.\n",
        "\n",
        "Just like before, training examples are just word k-grams from the corpus. Identidies of the first k-1 words are used \n",
        "as features and the last word is the target label for the classification (the new word we are trying to predict that \n",
        "might come after the words in the k-gram). The model can be trained using cross entropy loss. \n",
        "* NN LMs achieve better perplexity scores\n",
        "* they can scale to larger n-grams because the parameters are associated only with individual words instead of n-gram combinations \n",
        "* they can generalize across contexts, seeing that all color words live in the same context, for example\n",
        "* A by-product of trainings are word embeddings\n",
        "\n",
        "Word Embeddings are discovered when we take multidimentsional vectors and project it to 2 dimensions. Similar \n",
        "words are clustered together. \n",
        "* Embeddings can capture relational meanings, like man -> woman, uncle -> aunt \n",
        "\n",
        "We can train a classifier to get dense vectors. This is also the same approach as Word2Vec \n",
        "\"skip-gram with negative sampling\" (SGNS). \n",
        "* Treat the target word and a neighboring context word as positive examples\n",
        "* Randomly sample other words in the vocab to get negative samples\n",
        "* Use log regression to train a classifier to distinguide the pos and neg cases \n",
        "* Use the weights as the embeddings\n",
        "* This is similar to what Word2Vec does. Train a classifier on a binary prediction task (is w likely to show up near 'apricot'?)\n",
        "\n",
        "We want dense vectors because the shorter vectors may be easier to use as features themselves (fewer weights to tune). \n",
        "Dense vectors may generalize better than storing explicit counts and may be better at capturing synonymy. \n",
        "\n",
        "We need the probability (target, context):\n",
        "* $P(+|t,c) = \\frac{1}{1+e^{-t \\cdot c}}$\n",
        "* $P(-|t,c) = 1-P(-|t,c)= \\frac{e^{-t \\cdot c}}{1+e^{-t \\cdot c}}$\n",
        "\n",
        "Now that we can compute the probabilities (take the log to actually do the math) Word2Vec \n",
        "can learn the embeddings automatically. It starts with an initial set of embedding vectors and iteratively shifts the \n",
        "embedding of each word to be more like the embeddings of words that occur in nearby text and less like the ones that \n",
        "are not close by.\n",
        "\n",
        "To chose 'noise words' to serve as negative examples, could pick them according to their unigram frequency. \n",
        "But it is more common to chose according to $p_{\\alpha}(w) = \\frac{count(w)^{\\alpha}}{\\sum_w count(w)^{\\alpha}}$. \n",
        "$\\alpha=3/4$ works well because it gives rare noise words with slightly higher probability.\n",
        "\n",
        "We can start with initial weights of zero or random values. we will adjust the word vectors so that we are \n",
        "maximizing the similiary of the (t,c) pairs from the positive data and minimizing the similiary of the (t,c) \n",
        "paids from the negative data. If we use gradient descent to train, we would result in learning two separate \n",
        "embedding matrices. We can throw one away or merge them for the final result. Embeddings need to be evaluated \n",
        "based on human input on whether they are accurate or not. Pairs of words that are similar are concordant and \n",
        "dissimilar are discordant. Correlation can be computed as $(N(N-1)/2)/total pairs$. \n",
        "\n",
        "Depending on the window size chosen, the embeddings will change too. We can solve analogies with embeddings by \n",
        "comparing the vectors. a:a* as b:b* where b* is a hidden vector; b* = b-a+a*. We can optimize analogies by solving \n",
        "$argmax_{b* \\in V}( \\cos(b*, b-a+a*))$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "454400f2-18c6-4cd1-cbf7-0d75dc65c218"
      },
      "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": 35,
      "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\nIn Vector Space Models, each document in the collection is represented as a point in space \n(a vector in a vector space). The user's query is a pseudo-document and joins the other \ndocuments in the same space. Information retrieval (IR) was performed by selecting the vectors \nthat are close together in the space to the query vector. \n\nTerm-Document Matrix:\n* Each column vector represents a document \n* Each row vector represents a term \n* The value in a cell is based on how often that term occured in the document \n* the length of the document vectors (y-axis) is the size of the vocab\n* the width of the matrix (x-axis) is the number of documents in the collection\n* document vectors can be sparse (most values 0)\n* we can measure how similar two documents are by comparing their column vectors\n\nTerm-document maxtrices are good for identifying plagarism. Comparing two row vectors let's \nus see how close words are to each other. We can normalize the data with Vector L2 (length) \nnormalization ($||u||= \\sqrt{\\sum_{i=1}^{n}u_i^2}$) then divide the vector by the L2 length u \nto get the normalized values which will take care of discrepancies for highly used words. Cosine \ndistance can also be used to compare similarities based on the cosine angle between them. \n\n\nTerm-Term Matrix:\n* aka Term-context matrix\n* the length of the row vector is now |V| (vocabulary, words) instead of number of documents. \nso now both axises are the words. \n* the value in a cell indicates how often the word appears in a context window of the other word. \n* we need to pick a context window, such as +/-2 words to either side of the target word. \n\n\n\nAnother option is that we can use syntax to define a word's context instead of the surrounding words. \nAlternatives to raw counts are transforming vectors with methods such as TF-IDF (Term frequency 'how \noften a word occurs in a document' * inverse document frequency '1 over the number of documents that \nthe word occurs in' ) or PPMI. Co-occurnace matrix (such as weighed by TF-IDF) are long and sparse. \nAn alternative is that we could learn vectors that are short and dense. \n\n\nIn Language modeling, we are trying to learn a function that returns the join probability for the words. \nThis is usually hard because there are too many parameters (aka curse of dimensionality) and in n-gram \nbased models, we fail to generalize to related words/word sequences that we already have observed. Neural \nLanguage models have several advantages over n-gram LMs. \n* dont need smoothing \n* handle longer histories \n* can generalize over contexts of similar words\n* have higher predictive accuracy\n* BUT they are slower to train \n\nTo do this, we need to... \n* Associate each word in the vocab with a vector representation, create a notion of similiarity between words \n* Express joint prob function of a word sequence in terms of the word vectors for the words in that sequence \n* Simultaneously learn the word vectors and the parameters of the function \n\nWe can use a multilayer, feed forward neural network to get a prob function that expresses the product \nof conditional probabilities of the next word given the previous word. \n* input: k-gram of words\n* output: prob distribution over next word\n* k context words is treated as a word window. Each word is associated with an embedding vector.\n\nJust like before, training examples are just word k-grams from the corpus. Identidies of the first k-1 words are used \nas features and the last word is the target label for the classification (the new word we are trying to predict that \nmight come after the words in the k-gram). The model can be trained using cross entropy loss. \n* NN LMs achieve better perplexity scores\n* they can scale to larger n-grams because the parameters are associated only with individual words instead of n-gram combinations \n* they can generalize across contexts, seeing that all color words live in the same context, for example\n* A by-product of trainings are word embeddings\n\nWord Embeddings are discovered when we take multidimentsional vectors and project it to 2 dimensions. Similar \nwords are clustered together. \n* Embeddings can capture relational meanings, like man -> woman, uncle -> aunt \n\nWe can train a classifier to get dense vectors. This is also the same approach as Word2Vec \n\"skip-gram with negative sampling\" (SGNS). \n* Treat the target word and a neighboring context word as positive examples\n* Randomly sample other words in the vocab to get negative samples\n* Use log regression to train a classifier to distinguide the pos and neg cases \n* Use the weights as the embeddings\n* This is similar to what Word2Vec does. Train a classifier on a binary prediction task (is w likely to show up near 'apricot'?)\n\nWe want dense vectors because the shorter vectors may be easier to use as features themselves (fewer weights to tune). \nDense vectors may generalize better than storing explicit counts and may be better at capturing synonymy. \n\nWe need the probability (target, context):\n* $P(+|t,c) = \\frac{1}{1+e^{-t \\cdot c}}$\n* $P(-|t,c) = 1-P(-|t,c)= \\frac{e^{-t \\cdot c}}{1+e^{-t \\cdot c}}$\n\nNow that we can compute the probabilities (take the log to actually do the math) Word2Vec \ncan learn the embeddings automatically. It starts with an initial set of embedding vectors and iteratively shifts the \nembedding of each word to be more like the embeddings of words that occur in nearby text and less like the ones that \nare not close by.\n\nTo chose 'noise words' to serve as negative examples, could pick them according to their unigram frequency. \nBut it is more common to chose according to $p_{\\alpha}(w) = \\frac{count(w)^{\\alpha}}{\\sum_w count(w)^{\\alpha}}$. \n$\\alpha=3/4$ works well because it gives rare noise words with slightly higher probability.\n\nWe can start with initial weights of zero or random values. we will adjust the word vectors so that we are \nmaximizing the similiary of the (t,c) pairs from the positive data and minimizing the similiary of the (t,c) \npaids from the negative data. If we use gradient descent to train, we would result in learning two separate \nembedding matrices. We can throw one away or merge them for the final result. Embeddings need to be evaluated \nbased on human input on whether they are accurate or not. Pairs of words that are similar are concordant and \ndissimilar are discordant. Correlation can be computed as $(N(N-1)/2)/total pairs$. \n\nDepending on the window size chosen, the embeddings will change too. We can solve analogies with embeddings by \ncomparing the vectors. a:a* as b:b* where b* is a hidden vector; b* = b-a+a*. We can optimize analogies by solving \n$argmax_{b* \\in V}( \\cos(b*, b-a+a*))$\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "d3fa2b65-4dce-45e7-c32a-6795b88093bc"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nA decision-theoretic agent assigns a continuous range of values to goals and states so that it can pick \na state even when no best state is available. \n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n * $P(s'|s,a)$ = Probability that action a in state s reaches state s'\n * $P(\\textnormal{RESULT}(a)=s')$ = Probability of reaching s' by doing action a in the curent state\n * $P(s)$ = Probability of state s\n\n\n $EU(a) = sum_{s'}P(\\textnormal{RESULT}(a)=s')U(s')$\n\n Principle of Maximum Expected Utility = rational agent should choose the action that maximizes the agents's expected utility \n * $action = argmax_a EU(a)$\n\n\n The MEU Principle formulizes the notion that an intelligent agent should do the right now but not how to operationalize that notion. \n Estimating the probability distribution P(s) requires perception, learning, knowledge representation, and infernece. To get $P(\\textnormal{RESULT}(a)=s')$ \n you need to know a casual model of the world. Computing the utilities (U(s')) requires searching or planning since an agent doesn't know how good that future \n state might be until to knows where it can get to from that state. There might be some uncertainty about the utility function if the computer does \n not know the human's true utility function. Decision theory might not be the end all to AI, but it provides the beginnings of the general mathematical \n framework to define the AI problem. MEU has a clear relation to the idea of performance measures. \n\n *If an agent acts so that it maximizes a utility function that reflects the performance measure, then the agent will achieve the highest possible performance score \n (averaged over all possible environments)*\n\n Performance measure gives a score for history (sequence of states). Utility function applies to the next state and can be used to guide actions step by step. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nAxioms of Utility Theory\n* Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equality preferable. (Deciding cannot be avoided.)\n * Exactly one of $(A>B), (B>A)$ or $(A~B)$ holds\n* Transitivity: Given any three lotteries, if an agent prefernece A to B and prefers B to C, then the agent must prefer A to C.\n * $(A>B) \\lor (B>C) \\implies (A>C)$\n* Continuity:If some lottery B is between A and C in preference, then there is some probability p where the rational agent will be indifferent between getting B \nfor sure and the lottery that yields A with probability p and C with probability 1-p.\n * $A>B>C \\implies \\exists p [p, A; 1-p, C]~B$\n* Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same \nexpect that B is substituted for A in one of them. \n * $A~B \\implies [p, A; 1-p, C] ~ [p, B; 1-p, C]$\n* Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then it must prefer the lotter with the higher \nprobability for A.\n * A>B \\implies (p>q \\iff [p, A; 1-p, B] > [q, A; 1-q, B])\n* Decomposability: Compound lotteries can be reduced so simplier ones using laws of probability. (aka. \"no fun in gambling\" rule)\n * $[p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C]$\n\n\nIf an agent violates any of the axioms of Utility Theory, then it can be proved they are irrational. \nThese are really axioms of preferences, they don't say anything about a utility function.\n\nFrom the axioms of utility, the following consequences can be derived:\n* Existence of Utility Function:If an agent's preference obey the axioms of utility, then there exists a function U such that U(A)>U(B) iff A is preferred to B, \nand U(A)=(B) iff the agent is indifferent between A and B.\n** $U(A)>U(B) \\iff A>B$ and $U(A)=U(B) \\iff A~B$\n* Expected Utility of a Lottery: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n** $U([p1, S1; ...; pn, Sn]) = \\sum_i{piU(Si)}$\n** The utility of a compound lottery involving possible outcome states is completely determined once the probabilities and utilities of the outcome states are specified, . \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nFirst we need to work out what the human's utility function is. We can use preference elicitation to do this. Establish a scale to use for comparison of utility values by \nfixing the utilities of any two outcomes (same idea as setting the temp for boiling and freezing). Usually we fix the best possible prize ($U(S)= u_\\perp$) and worst possible catastrophe \n($U(S)= u_\bot$) with finite values. Then, using a standard lottery, we find at what point probability p needs to be at where the agent is indifferent between S and the standard \nlottery. Example: Want to find out how much a fan values getting to the semi-final and losing. Compare standard lottery with probability p of winning the trophy to probability 1-p \nto fail to quality. If indifference is at 0.3, this is the value of reaching the semi-final and losing.   \n\nIt is helpful to establish some scale that utilities can be recorded and compared for a problem. A scale can be established by fixing utilities of any two particular outcomes. Typically this is the (finite) utility for a best possible price and worst possible catastrophe. We would ask the agent to choose between S and a standard lottery and adjust the probability until the agent is indifferent between them. Tehn we can determine the prizes for all lotteries involved. These values can be used to put value and decide on tolerants for risk. Aircraft are not serviced after every flight, analysis for deciding the value of a childs life vs removing asbestos from the school. \n\nUtility theory has roots in economics. Say if you had 1mil you could take now vs flipping a coin and you get 2.5mil if it is tails and nothing if it is heads. The EMV would benefit the coin flip, but that isn't necessarily the best decision. It would be dependent on your current financial wealth. A millionnaire would most likely have a utility function that is linear over a range of a couple million and would be more likely to take the gamble. The utility of money is almost exactly proportional to the log of the amount. Most people would accept \\$400 (certainty equivalent) in lieu of a chance at \\$1000 or \\$0, even though the EMV is \\$500. Difference between EMV and certainty equivalent is the insurance premium. \n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nIf a fully observable environment were deterministic, the solution would be straightfoward, but actions are unreliable in a stochastic environment. The outcome \nof the transsition model is stochastic, so it is represented as a probability $P(s'|s,a)$ and transitions are assumed to be Markovian. The decision problem is \nsequential so the utility function will depend on the environment history instead of a single state. For every transsition, the agent will receive a reward $R(s,a,s')$. \nReward may be positive or negative. This problem is known as a Markov Decision Process (MDP). These consist of...\n* set of states (with initial state s0)\n* set of ACTIONS(s) for each state\n* transition model $P(s'|s,a)$\n* reward function $R(s,a,s')$\n\n\nMethods for solving MDPs using invovle dynamic programming. Since there cannot be a single solution to the problem, the solution is a policy. The agent will know what \nto do based on what the policy says. Given an optimal policy, the agent decides what to do based on their current percept (defining their current state) and then executes \nthe actions provided from $\\pi*(s)$. The policy represents the agent function explicitly, resulting in a simple reflex agent. For a state, there can be multiple optimal \npolicies. The balance of risk and reward is determined by the rewards from the transition function as the agent moves to non-terminal states. Since MDPs include uncertainty, \nthey are closer to real world problems than deterministic search problems. \n\nPolicies for infinite horizon cases are simplier than for finite horizons since they do not have to act differently depending on the time.\n\nIf $\\gamma$ is close to 0, rewards in the distant future are insignificant; if $\\gamma$ is close to 1, agent can wait for more long-term rewards. If $\\gamma=1$, then rewards \nare purely additive. Additive rewards make sense since living beings tend to prefer now instead of later. For money, it is better to get it sooner than later because gains \ncan be reinvested. There is also uncertainty about true rewards in the future, they might not come for some reason. Discounted rewards allows us to make the utility of an \ninfinite sequence finite and bounded by a maximum, that way we are not trying to compare two $+\\inf$ utilities.  \n\n\nThe Bellman Equation: $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n* the utility of a state is the expected reward for the next transistion plus the discounted utility of the next state, assuming that the agent chooses the optimal action\n\n\nAction-utility function (Q-function): $U(s)=max_a Q(s,a)$ where $Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q(s',a')]$\n* Q(s,a) is the expected utility of taking a given action in a given state\n\n\nThe simplest way to represent P(s'|s,a) and R(s,a,s') is with 3D tables of size $|S|^2|A|$. This is OK for small problems. Tables can be sparse.\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nValue Iteration\n* Solving systems of nonlinear equations with an iterative approach. Bellman Update is applied simultaneously to \nall states at each iteration. If we apply the Bellman update infinitely often, we are guranteed to reach convergence where the final utility values is the soution to the Bellman \nequations. \n* Contraction is a function when applied to two different inputs during separate turns, they produce two output values that are \"closer together by some constant factor than the \noriginal inputs. Contractions have only one fixed point. If there were two points, they would not get closer when the function is applied. When the function is applied, the value \nmust get closer to the fixed point, so repeated application of the contration would continue to get closer to the fixed point (like sqrt).\n* The Bellman update is a contraction by a factor of $\\gamma$ on the space of utility vectors.\n* Value iteration converages exponentially fast. Number of iterations to convergence = $N = \\lceil log(2R_{max}/\\epsilon (1-\\gamma))/log(1/\\gamma) \\rceil$. Since convergence is \nexponentially fast, it does not rely much on the ratio of $\\epsilon/R_{max}$, but N can grow rapidly as $\\gamma$ gets closer to 1. We can get fast convergence if $\\gamma$ is small, \nbut then we risk missing out on any long term effects of the agents actions since the event horizon would be short.\n\n\n\n## Module 8 Lecture Notes\n\nPolicy Iteration\n* Previously, we observed that it is possible to get an optimal policy even when the utility function estimate is inaccurate. If one action is clearly better than the others, the \naccuracy of the value of the others does not really matter. Thus there can be another way to find the optimal policy using policy iteration. It is broken into two steps, policy \nevaluation and improvement.\n* Algorithm terminates then the policy improvement steps yields no changes in the utility values. Then we know that the utility function is a fixed point in the Bellman update, \ntherefore a solution to the Bellman equations and an optimal policy. \n* To implement, it is simpler than solving the standard Bellman equations like value iteration does since the action in each state is fixed by the policy. This gives us a simplified \nversion of the Bellman equation: $U_i(s) =  \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$. Since the max operation is removed, all the equations are linear. \n* If we have n states, there are n linear equations with n unknowns, solvable in $O(n^3)$ time. If the transition model is sparse (states transition to only a few other states), \nthe process can be even faster. For small state spaces, exact solutions with policy evaluation is the most efficient approach, but for large state spaces, $O(n^3)$ might be too \nmuch. \n* We do not have to update all of the utilities/policies for all states at once, instead we can use asynchronous policy iteration.  Given certain conditions on the initial policy \nand initial utility function, this is guaranteed to converge to an optimal policy. \n\n\nLinear Programming\n* General approach for fomulating constrained optimization problems. A MDP can be reduced to solving a suitably formulated linear program since it involves a lot of sums and maxes. \nConsider the variables in the LP to be the utilities for each state. The utilities for an optimal policy are the highest utilities attainable that are consistent with the Bellman \nequations. This means we want to minimize U(s) for all states; $U(s) \\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$ for every state s and action a.\n* Linear programming is solvable in polynomial time, therefore this means that MDPs can be solved in time polynomial in the number of states anda ction and bits required to specify \nthe model. In practice, it turns out that LPs solvers are seldomly more efficient than dynamic programming. Even though polynomial time might sound good, the number of states is \nusually large. \n\n\nValue iteration and policy iteration are both offline algorithms like A*.  Because of state sizes, \nexact offline solutions are often not possible, even in polynomial time. Therefore, it needs to be approximated. Instead we should use online algorithms. Options include a simplifed \nversion of EXPECTIMINIMAX, Real-time Dynamic Programming (RTDP), reinforcement learning, Monte Carlo approach, UCT (Upper Confidence bounds applied to Trees) algorithm.\n\n\n\n## Module 8 Definitions\n* **Decision-theoretic agent** - an agent that makes rational decisions based on what it believes and what it wants\n* **Utility function, u(s)** - assigns a number to express the desirability of a state, captures the agent's preferences. Maps lotteries to real numbers. \n* **Expected utility, eu(a)** - the average utility value of the outcomes, weighted by the probability that the outcome occurs\n* **Lottery** - set of outcomes for each action, $L = {p1, S1; p2, S2; ...; pn, Sn}$\n* **Value function or ordinal utility function** - an agent only needs a preference ranking on states in a deterministic environment\n* **Preference elicitation** - the process of figuring out the utility function by presenting choices to humans and using the preferences to make the utility function\n* **Normalized utilities** - uses scale for 0 to 1 for best and worst outcomes.\n* **Standard lottery** - e.g. $[p, u \\perp; (1-p), u \bot]$\n* **Micromort** - one million chance at death\n* **Monotonic preference** - given everything else is equal, the preference will always be A over B (e.g. prefer more money over less)\n* **Expected monetary value** - (EMV), sum of probabilities times value\n* **Risk-adverse** - prefer a sure thing over a gamble\n* **Certainty equivalent** - amount someone would accept in lieu of the gamble\n* **Sequential decision problems** - agent's utility depends on a sequence of decisions, incorporating utilities, uncertainty, sensing, and search/planning problems (special cases)\n* **Markovian** - probability of reaching a state s' depends only on current state s, not on any previous history\n* **Environment history** - sequence of states and actions\n* **Markov decision process (mdp)** - sequential decision problem for a fully observable, stochastic environement with a Markovian transition model and additive rewards\n* **Dynamic programming** - recursively breaks down a problem into smaller pieces and rembers the optimal solutions to the pieces.\n* **Policy** - solution that specifies what the agent might do at any state. denoted by $\\pi(s)$ for the policy for state s. \n* **Optimal policy** - policy that yields the highest expected utility, $\\pi*$\n* **Finite horizon** - fixed time N after which nothing matters, e.g. the game is over\n* **Nonstationary** - policy that depends on time\n* **Stationary** - optimal action only depends on current state, does not have to react differently depending on the time\n* **Additive discount rewards** - $U_h([s0,a0,s1,a1,s2...])=R(s0,a0,s1)+\\gamma R(s1,a1,s2)+\\gamma^2R(s2,a2,s3)+...$\n* **Discount factor** - $0>\\gamma>1$, preference for current rewards over future rewards.\n* **Proper policy** - guaranteed to reach a terminal state\n* **Dynamic decision networks (ddns)** - decision, reward, utility nodes\n* **Contraction** - basic concept used to show that value iteration converages\n* **Max norm** - maximum value of the absolute value, 'length' of the vector, $||U|| = max_s |U(s)|$\n* **Policy loss** - the most the agent can lose by executing a policy instead of the optimal policy, $||U^{\\pi_i}-U||$\n* **Bellman update** - Iteration step called the Bellman update, using the Bellman equation.\n* **Policy evaluation** - given a policy, calcualte the utility of each state if the policy was executed\n* **Policy improvement** - calculate a new MEU policy using one-step look-ahead based on the utilities calculated in policy evaluation.\n* **Modified policy iteration** - You don't have to do exact policy evaluation, instead some simplified value iteration steps can be performed to give a good approximation of the utilities.\n* **Asynchronous policy iteration** - Instead we can pick a subset of states and apply either policy improvement or simpilfied value iteration to them.\n* **Offline algorithms** - They generate an optimal solution for the problem and then it is executed by the agent.\n* **Online algorithms** - like we used for game playing, where the agent does computations at each decision point rather than using precomputed information. \n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nA gambler must choose which lever to play for each turn for an n-armed bandit. They need to decide if they should try something they has already \npaid off the best or something new. This is a tradeoff between exploitation and exploration. Examples of n-bandit problems include: \"which of n \npossible investments to put your saving into\", \"which of n possible adverts to show a user when they visit a particular page\". At first, scientists \ntried to prove statements about n-armed bandit problems that were actually false, such as the optimal policy would settle on the best arms, but there \nis a finite probability it will setting on a suboptimal arm. \n\nDefinition of a bandit problem:\n* Each arm is a Markov reward process. Rewards are random variables. \n* Overall bandit problem is an MDP. \n* Arms are independent. Agent can only work one arm at a time.\n\n\nGittin index of an arm only depends on the properties of the arm. The optional deciion on the first iteram can be calcualted in O(n) time (n=number of arms). \nEach decision after the first one can be calculated in O(1) since the GIttin indicies of the unselected arms remain unchanged. \n* $\\lambda = max_{T>0} \\frac{E(\\sum_{t=0}^{T-1}\\gamma^t R_t)}{E(\\sum_{t=0}^{T-1} \\gamma^t)}$\n\n\nA Bernoulli bandit has infinitely many states, but we can approximate the solution with a truncated MDP with states of $successes_i+failures_i=100$ and $\\gamma=0.9$. \nResults depict that arms with higher payoff probabilities are preferred and there is an exploration bonus associated with arms that been tried sedomly. \n\nIt is rarely easy to calculate Gittins indicies for realistic problems. But the creation of simple polies turn out to be nearly as good as optimal policies. \n * upper confidence bound (UCB) heristic: uses samples from each arm to establish a confidence interval  for he value of the arm, then chooses the arm with the highest \n upper bound. A UCB policy picks the arm with the highest UCB value.\n * Thompson Sampling: chooses an arm at random according to the probability that the arm is optimal, given the samples so far. Simple way to implement Thompson's is to \n generate one sample from each P and then pick the best. This has a regret that grows as O(logN).\n\n Bandit problems originally came up because there was a serious cost for failing, we didn't want to fail. If instead we just wanted to find out which 'arm' performs the best, \n with no or little cost of failing, then we have a selection problem. Selection problems are similar to bandit problems but with different mathematical properties, e.g. they \n have no index function. \n\nExamples of BSPs include multitasking. The global optimal policy might include suboptimal actions compared to the POV of the constituent MDP. We solve BSPs by using the loose \ninteration between the arms and modeling with an opportunity cost.  \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nReinforcement learning goal is the same as MDP, maximize the expected sum of rewards. But it is diffeent because the agent is not given an MDP problem to solve, it is \nIN the MDP. It does not know the transition model or reward function, it has to do things in order to learn more. Reinforcement learning benefits from being simplier to \ncode, we don't need to be experts and we only need to code either it gets a reward or not. But a little bit of expertise can go a long way. \n\n* Model-based reinforcement learning: Agent uses a transistion model to interpret reward signals and to make decisions on how to act. The model may start as unknown and \nthe agent will learn it from its actions or it might be known. They often learn a utility function.  \n* Model-free reinforcement learning: Agent neither knows nor leanrs a transition model. Instead it learns a more direct representation on how to behave. \n * Action-utility learning: Most common form is Q-learning; agent learns a Q-function (quality function) which is the sum of rewards from state s onward if action a is taken. \n The agent can choose what to do in the current state by finding the action with the highest Q-value. \n * Policy search: Agent learns a policy that maps directly from state to actions. Same as a reflex agent. \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nPassive Learning Agent (PLA): Consider a fully observable env with small number of actions and states, agent had a fixed policy that determines its actions and is trying to learn \nthe utility function. PLA is similiar to policy evaluation task, but we do not know the transition \nmodel or reward function. \n\nDirect utility estimation: utility of a state is defined as the expected total reward from that state onward (expected reward-to-go). Each trial provides a sample of this quantity \nfor each state visited. This reduces reinforcement learning to supervised learning, but it ignores the constraint that the utility of a state is determined by the reward and the \nexpected utility of the successor states. Ignoring this connection, it misses the opportunities for learning and converges slowly.\n\nAdaptive Dynamic Programming (ADP): agent takes advantage of the constraints amoung the utilties by learning the transition model that connects them and solves the corresponding MDP \nduring dynamic programming. For a PLA, we can take the learned transition model and observed rewards to calcuate the utilities of states using \n$U_i(s) = \\sum_{s'} P(s'|s,\\pi_i(s))[R(s, \\pi_i(s), s')+\\gamma U_i(s')]$. This can be solved using linear algebra. Alternatively, we can use modified policy iteration. The model \nusually only changes slightly with each observation, value iteration can use previous utility estimates as initial values and can converage quickly. Since the env is \nfully observable, learning the transition model is easy. ADP agent is only limited by its ability to learn the transition model. But it is not good in large state spaces since it has \nequal number of equations to solve as unknowns. Heuristics can help approx. ADPs learn as fast as full ADPs. \n\nTemporal-difference learning (TD): Uses observed transitions to adjust the utilities of the observed states so that they agree with the constraint equations. Update to utilities = \n$U^\\pi(s) \\leftarrow U^\\pi(s) + \\alpha [R(s, \\pi(s), s') +\\gamma U^\\pi(s')-U^\\pi(s)]$. $\\alpha = $ learning rate. All TD methods work by adjusting the utility estimates \ntowards the ideal equilibrium that holds locally when the utility estimates are correct. The update only invovles successor s'. This will not result in changing U drastically for an \nextremely rare event, 1. because it is rare and 2. because the avg value will still converge. If we turn $\\alpha$ in to a function that dec over time, the utility will converge \nto the correct value. TD will not learn as fast as ADP, but it is simpler and requires less computation per observation. There is no need for a transition model to perform the updates. \nInstead, it will use the connection between neighboring states from observed transitions. TD will adjust a state to agree with its observed successor, ADP will adjust the state to agree \nwith ALL the successors that have already occurred, weighed by probab. Over a large number of transitions, this diff disappears.    \n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nActive learning agent can take a modified ADP approach. It will need to learn a complete transisiotn model with outcome probs for all actions. The agent has a choice of actions and the utitlies \nwill need to be defined by the optimal policy by using the Bellman Equations to solve for the utility function using value iteration or policy iteration. Since now the agent will have a utility \nfunction, it can exact an optimal action looking one step ahead to maximize the expected utilities. But is this the best approach to take?\n\nThis approach is narrow and could result in the agent not learning the true utilities or true optimal policy. The agent needs to utilize that the actions provide rewards and information. Just like \nthe bandits, there is a tradeoff between exploitation and exploration. GLIE schemes must try each action and unbounded number of times so that it doesnt miss an optimal action. The true transition \nmodel will eventually be learned and then the agent can operate under exploitation. Options are choose an action at random (converges slowly) or weight the actions (better).\n\n\nExploration function: $f(u,n) = \\begin{cases}\n  R^+ \\textnormal{ if } n<N_e  \\\\    \n  u \\textnormal{ otherwise}    \n\\end{cases}$\n\nwhere $R^+$ is an optimistic estimate of the best possible reward obtainable in any state and $N_e$ is a fixed parameter.\n\n\nWe have assumed that the agent can explore and failure has no lasting consequences, but this is not the case in most realistic scenarios. We need to be able to explore safely. We can end up in bad \nstates because the model is unknown and we choose to explore is a direction that turns out to be bad, or  because the model is incorrect and we don't know the action is bad. If acting with a policy \nwith an estimated model, it acts as if the model is correct, which can be bad. Better would be to use a policy that works reasonably well for all models, even if it is suboptimal. \n\nFor TD learning, the Q-learning method learns an action-utility function (Q(a,s)), avoiding the need for a model. Note that the TD Q-learning agent does not need a transition model for learning or \naction selection. But they have no means to look into the future, so may struggle when rewards are sparse or long action sequences are need to reach rewards. \n\nSARSA update rule is similar to Q-learning update rule: $Q(s,a) \\leftarrow Q(s,a) + \\alpha [R(s,a,s') + \\gamma Q(s',a')-Q(s,a)]$. SARSA waits until an action is taken and backs up the Q-value for \nthat action. If the agent is greedy, Q-Learning and SARSA are identical. Q-learning is off-policy, SARSA is on-policy. Q-learning and SARSA are both slower than ADP since local updates do not enforce \nconsistency.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\nTabular form works for state spaces up to about $10^6$. For the real-world, this would be too slow. Function approximation allows for utility or Q functions to be represented in larger state spaces. \nIt also allows for inductive generalization. \n\nDirect utility estimation generates trajectories in the state space and extracts the sum of rewards received from that state onward until termination. We can use the Widrow-Hoff rule (delta rule) \nto get update rules for the approximator. Changing the parameters also changes the utilities, therefore this approximation can allow the reinforcement learner to generalize from its experiences. \nThe agent can learn faster with a function approximator. \n\nSimilar approximation ideas can be applied to TD as well. The parameters need to be adjusted to reduce the TD between successive states. This will work if the function approximator is linear, but \ncan result in infinity if it is not. But this has a risk of catastrophic forgetting. A solution is experience replay. Learning modesl for observable environments for supervised learning problems \nis easier since it can look ahead compared to partially observable environments. \n\nWe need to go beyond linear function approximators for utility and Q functions because there might be no good linear function or we might not be able to invent the necessary features, particularly in new \ndomains. Deep neural networks can be used as nonlinear function approximators, it can discover the features for itself and, if the last layer is linear, then build its own linear function approximator. \nEven though it can get good results, it can be difficult since the trained system can behave unpredictably if the environment differs from the training data.   \n\nWe can use reward shaping to give additional \"pseudorewards\" for actions to help speed up learning, but need to make sure the agent does not try to maximize these rewards rather than the true rewards. \n\nA HRL agent starts with a partial program that outlines the hierarchial structure for the agent's behavior. HRL is based on the concept of joint state space. The machine state is the internal state \nof the program. HRL can be good for learning complex behaviors. \n\n\n## AIMA Chapter 22.5 Policy Search\n\nQ-functions could be linear or nonlinear. Policy search adjusts the parameters to improve the policy. If the policy relies on Q-functions, then it will result in a process where it learns the Q-functions. \nThis process is different than Q-learning. Q-learning finds parameters that gets close to optimal Q-function, whereas policy search finds parameters that result in good performance. If actions are discrete \nthen the policy is a discontinuous function of the parameters. There might be values of the parameters where if there is a reallly small change, it might cause the policy to switch from one action to another. \nThis would make gradient search difficult if the policy is changing discontinuously. Policy search needs to use a stochastic policy representation that speciflies the probablity of selecting action a in state s. \nAn example is the softmax function: $\\pi_\\theta (s,a) \\frac{e^{\\beta \\hat{Q}_{\\theta}(s,a)}}{\\sum_{a'}e^{\\beta \\hat{Q}_{\\theta}(s,a')}}$. $\\beta$ controls the softness of softmax, large values approach a hard max, \nclose to zero approaches a uniform rancom choise among actions. Correlated sampling can be applied to policy search. \n\n\n## Module 9 Lecture Notes\n\nDirect evaluation: compute values for each state under \\pi where we average together observed sample values and act according to the policy $\\pi$. \nEvery time you visit a state, write down the sum of discounted rewards and avereage the samples. Direct evaluation doesn't require knowlege of T and R. \nBut it takes a long time to learn since each state needs to be learned separately and it wastes information about state connections. \n\nWe can use policy evaluation but we need T and R. We can take a weighted average without knowing the weights by taking samples of outcomes s' by doing \nthe action and then average using samples. \n\nIn Temporal Difference Learning (TD), the idea is that we can learn from every experience. We will update the weights every time we transition. Likely outcomes \nwill constribute updates more often. The policy is still fixed. We can use an exponential moving average to learn. $\\alpha$ learning rates that decrease can give \nconvering averages. \n$V^{\\pi}(s) \\leftarrow (1-\\alpha) V^{\\pi}(s) + \\alpha [R(s,\\pi(s),s')+ \\gamma V^{\\pi} (s')]$ \n\nTD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages. If we want to turn values into a new policy, \nit is not possible because we have to work with a fixed policy. We need to learn Q-values not just values and make the action selections model-free too through reinforcement \nlearning. We allow the learner to make the choices and have to deal with a tradeoff between exploration and exploitation. We do not know the transistions or rewards beforehand, \nwe will learn the optimal policies and values along the way as the agent chooses and complete the actions. This is online planning. \n\nQ learning uses value iteration to find successive (depth limited) Q-values with the state and action. These Q values will be learned as the agent goes, take a sample estimate \nand incorporate it into a running average. $sample=R(s,a,s')+\\gamma max_{a'}Q(s',a')$; $Q(s,a)\\leftarrow (a-\\alpha)Q(s,a)+(\\alpha)[sample]$. \nQ-learning converages to optimal policy, even if the agent is acting suboptimally. This is off-policy learning. But you have to explore enough and eventually make the learning \nrate small enough over time (but don't decrease it too quickly). Therefore, it doesn't matter how actions are selected. To explore, we can choose randon actions ($\\epsilon-greedy$). \n$\\epsilon$ being small, there is a small probability that it will act randomly, so then $1-\\epsilon$ to act on current policy. With random actions, you explore the space eventually \nbut a lot of thrashing around is done. So you could lower the epsilon value over time or use exploration functions. Exploration functions will focus the agent on areas were the badness \nhas not yet been established, and as areas are found, the agent will eventually stop exploring. The agent will make mistakes, totally in a mistake cost called regret. Mistake cost is \nthe $(expected rewards - optimal rewards)$. Minimizing regret requires optimal learning to be optimal, random exploration has higher regret. Approximate Q-learning generalizes by learning \nabout some small number of training states from experience. The model will generalize the experience to new, similiar situations.  \n\n\n## Module 9 Definitions\n* **N-armed bandit** - slot machine with n levers. each lever has a fixed but unknown probability distribution for winnings\n* **Exploitation** - using the current action to get rewards\n* **Exploration** - agent experiencing as much as possible from the environment to learn how to behave in it\n* **Regret** - making mistakes while learning\n* **Sampling** - trying things repeatedly because of chance\n* **Difficulty** - learning can be much harder than solving a known MDP\n* **Markov reward process** - MRP, an MDP with only one possible action, with states, transition model, and reward. The arm defines a distribution over sequences of rewards\n* **Gittins index** - $\\lambda$, provides a simple potimal policy for any bandit problem, pull the arm with the highest Gittins index, then update the indicies.\n* **Restart mdp** - MDP whose optimal value is equivalent to the optimal value of the initial state, and is indifferent between them. Therefore it should just restart.\n* **Bernoulli bandit** - each arm produces a 0<reward<1 with fixed but unknown probability\n* **Bandit superprocess** - BSP, each arm is a full Markov decision process instead of just a Markov reward process with only one possible action.\n* **Opportunity cost** - how much utility is given up per time step by not devoting that time to another arm\n* **Dominating policy** - optimal policy of an arm that is unaffected by the opportunity cost.\n* **Reinforcement learning** - the agent interacts with the world and recieves rewards (aka reinforcement) along the way that reflect how well it is doing\n* **Sparse rewards** - vast majority of the state give no informative reward signal\n* **Passive reinforcement learning** - agent's policy is fixed, needs to learn the utilities of states (or state-action pairs).\n* **Active reinforcement learning** - agent also needs to figure out what to do\n* **Pseudoexperience** - Extend TD by creating transitions that might happen\n* **Prioritized sweeping** - heuristic makes adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n* **Utility function** - (the expected total discounted reward if policy is executed)\n* **Passive learning agent** - has a fixed policy that determines its behavior, learner is along for the ride\n* **Active learning agent** - gets to decide what actions to take\n* **Glie** - Greedy in the limit of infinite exploration\n* **Absorbing state** - actions have no effect and rewards are not received\n* **Bayesian reinforcement learning** - assumes a prior prob P(h) over hypotheses h, posterior P(h|e) is obtained using Bayes rule given observations to date\n* **Sarsa** - state, action, reward, state, action\n* **Off-policy** - learns Q-values based on if the agent stops using its current policy and switches to a policy that chooses the best actions based on estimates\n* **On-policy** - learns Q-values based on if the agent continues using its current policy\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n* **Inductive generalization** - agent can generalize from states it has visited to states it has not visited\n* **Catastrophic forgetting** - learns the safe areas too well and forgets the dangerous areas. \n* **Experience replay** - replay failures at a regular interval\n* **Deep reinforcement learning system** - uses a deep network as a function approximator\n* **Credit assignment problem** - working out what a model did wrong after many commands for many variables\n* **Reward shaping** - supplying the agent with additional rewards (psuedorewards) for making progress\n* **Hierarchical reinforcement learning (hrl)** - breaking up long action sequences into smaller pieces to make learning easier\n* **Joint state space** - each state (s,m) is composed of a physical state s and machine state m\n* **Choice state** - program counter for m is at a choice point for the agent program. decisions are not made in between choice states.\n* **Policy search** - keep updating the policy as long as its performance improves, then stop\n* **Correlated sampling** - using the same inputs during trials to eliminate the measure error due to differences\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\nOne approach is to create a logically exhaustive solution, but this is not possible because it is too much work to list all the rules, there might not be complete domain knowledge, and not \nall the information that needs to be known is known. We can deal with degrees of believe through probability theory. \n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n* Conditional probability: $P(a|b) = \\frac{P(a \\land b)}{P(b)}$\n* Product Rule: $P(a \\land b) = P(a|b)P(b)$\n* axioms of probability\n * inclusion-exclusion principle: $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n * $0 \\leq P(\\omega) \\leq \\textnormal{ for every } \\omega \\textnormal{ and } \\sum_{\\omega \\in \\Omega}P(\\omega)=1$ --> for all probabilities between 0 and 1, the sum of the probabilities equals 1\n * full joint probability distribution: often not possible to build out the full table becuase it is too large to create and use. \n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n* marginalization or summing out: $P(Y)=\\sum_z P(Y, Z=z)$ --> sum up the probabilties for each possible value of the other variables\n* conditioning: $\\sum_z P(Y|z)P(z)$\n \n\n## AIMA Chapter 12.4 Independence\n \n* independence: $P(a|b) = P(a)$, $P(b|a)=P(b)$, $P(a \\land b) = P(a)P(b)$. Independence assertion can simplify the size of the domain representation and complexity of the inference problem, \nbut they are usually quite rare.  \n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n* Bayes' Rule: $P(b|a) = \\frac{P(a|b)P(b)}{P(a)}$ or P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}\n * P(effect|cause) quantifies the relationship in the casual direction\n * P(cause|effect) quantifies the relationship in the diagnostic direction\n* Conditional Independence: $P(X,Y|Z)=P(X|Z)P(Y|Z)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n* Naive Bayes Model: $P(Cause, Effect_1, ..., Effect_n)=P(Cause)\\Pi_iP(Effect_i|Cause)$\n * 'naive' because it is often used in cases where the effect variable is not strictly independent given the cause variable (we are using it to simplify)\n\n\nWe can use Naive Bayes' for text classification, given text, decide which predefined set of classes or categories it should belong to. \n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n\n* Chain Rule of Probability: $P(X_1, ..., X_n)=P(X_1)P(X_2|X_1)P(X_3|X_{1:2}...P(X_n|X_{1:n-1})=\\Pi_{k=1}^{n}P(X_k|X_{1:k-1})$\n* bigram approximates the probability of a word given all previous words by using only the conditional probability of the preceding word\n* Markov assumption: predict the probability of some future unit without looking too far into the past. A bigram is an example of a Markov assumption.\n* Maximum Likelihood estimation (MLE): get counts from a corpus and normalize the counts so they lie between 0 and 1.\n* relative frequency: divide the observed frequency of a sequence by the observed frequency of a prefix. Used in MLE. \n\nIt is more common to use trigram, 4, or 5-gram models where there is sufficient training data. For larger grams, the sentences will need more padding. \nTo make the math easier, use log probabilities since we can sum them. This allows solves the problem of multiplying lots of small numbers together to \nget an even smaller number.\n* $p1 * p2 * p3 * p4 = exp(logp1 + logp2 + logp3 + logp4) $\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nExtrinsic evaluation is the only way to know if a particular improvement in a component is going to help the task. But this can be expensive to run \nbig NLP systems end to end, therefore we most often test it intrinsically with a test set. The model is trained on a training set (training corpus) \nand tested with unseen data with a test set that was held out from the training data. When comparing models, whichever model has the highest probabiliity \n(it more accurately predicted the tests set) is the better model. Sometimes we need to implicitly tune the model first. We give it a initial test set \ncalled the development test set or devset. Usually we divide the data into 80% training, 10% development, and 10% test. \n\nPerplexity: $PP(W) = \\sqrt[N]{\\Pi_{i=1}^{N} \\frac{1}{P(w_i|w_{i-1})}}$\n* We can also think about perplexity as the weighted average branching factor of a language.  \n* When computing perplexities, the n-gram model must be constructed without any knowledge of the test set or of the vocabulary of the test set. If it is, \nthe perplexity can end up artificially low. The higher the conditional probability of the word sequence, the lower the perplexity. We want to minimize the \nperplexity which is equivalent to maximizing the probability.\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n\nWhen training models for n-grams, we need to stay in the simplier genre as the question we are trying to answer. Combining genre's for more data will result \nin outputs that are not relevant. This also includes getting the corpus in the correct dialect/variety. Modeling might still have the problem of sparsity in \nthe corpus, resulting in \"zero probability n-grams\" where the model will not know that n-gram from the test set is actually possible since it didnt see it in \nthe training set. These are a problem because they underestimate the probability of other words that might occur, which hurts the performance of the application, \nand because if it is zero, then the entire probability of the test set is 0. THen we can't compute perplexity because we are not allowed to divide by zero. \n\nWe will need to know how to deal with these unknown words. We can train with an open vocabulary using the pseudoword <UNK>.\n* Option 1: Turn the problem back into a closed vocabulary by choosing a fixed vocabulary in advance\n * Choose a vocabulary fixed in advanced\n * Convert any word in the training set that is not in the vocab to the unknown word token\n * Estimate the prob for <UNK> from its counts like any other word\n* Option 2: If we don't have a prior vocab, create one implicitly, replace words in training data with <UNK> based on their frequency. \n * For example, replace all words that occur fewer times than n with <UNK>. Then proceed as above. \n\n\nUNK does not have any effect on perplexity. For this reason, perlexities should only be compared across language models with same vocabs. \n\n\n## SLP Chapter 3.5 Smoothing\n\nWhat do we do if the words appear in the vocabulary but then appear in the test data in an unseen context? In order to not assign zero probability, \nwe need to modify with smoothing or discounting. This is were we take some probability from more frequent events and give it to events we have never seen. \n* Laplace smoothing: add one to all n-gram counts before normalizing them into probabilities. All counts would at least be one and there would be no zero \ncounts. This does not perform well enough to be used in modern n-gram models. \n* Add-k smoothing: add a fractional count k to each count. This requires a method for choosing k, which could be done by optimizing on a devset. Still doesnt \nwork well, generates counts with poor variances and inappropriate discounts. \n* Backoff: using less context to generalize for more. For example, we can use the trigram if evidence is sufficent, otherwise use a bigram or unigram accordingly. \nOnly backoff to a lower order n-gram if there is zero evidence for a higher order one. \n* Interpolation: mix the probability estimates from all n-gram estimators, weighing and combining the counts and linearly interpolate them with constants $\\lambda$. \nThe $\\lambda$ values can be learned from a held-out corpus to learn these hyperparameters.   \n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\nstupid backoff: gives up the idea of trying to make a language model a true probability distribution. No discounting of higher order probabilities. If a higher order \nn-gram has a zero count, simply backoff to a lower order and weight it by a fixed (context independent) weight. This does not produce a probability distribution. \n\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - representation of the set of all possible worlds states that the agent might be in\n* **Utility** - the quality of being useful\n* **Decision theory** - = probability theory + utility theory\n* **Maximum utility theory** - an agent is rational iff it chooses the action yielding highest expected utility, averaged over all possible outcomes of the action\n* **Unconditional or prior probabilities** - degrees of belief in proposition in the absense of any other information\n* **Conditional or posterior probability** - probability given another piece of information\n* **Probability density function** - for continuous variables, function that determines the probability from some value x\n* **Probabilistic inference** - computation of posterial probabilties for query propositions given observed evidence\n* **Normalization** - constant to allow the probability distribution to add up to 1, $\u0007lpha$\n* **Full joint probability distribution** - specifies the probability of each complete assignment of values to random variables (usually in tabular form)\n* **(absolute) independence** - based on knowledge domain, two variables have no relationship and do not impact one another\n* **Language model** - models that are assigned probabilities to sequence of words\n* **N-gram** - sequence of n words (bigram, trigram)\n* **Extrinsic evaluation** - embedding a model into an application and measure how well the application improves\n* **Intrinsic evaluation** - measures the quality of a model independent of any application\n* **Perplexity** - variant of probability, inverse probability of the test set, normalized by the number of words\n* **Weighted average branching factor** - number of possible next words that can follow any word\n* **Sampling** - choosing random points according to their likelihood\n* **Closed vocabulary** - test set only contains words from this vocabulary, there are no unknown words\n* **Out of vocabulary** - using unknown words (OOV)\n* **Oov rate** - percentage of words that appear in the test set that are OOV\n* **Open vocabulary** - model these potential unknow words in the test set by adding a psuedoword <UNK>\n* **Held-out corpus** - additional training corpus\n* **Discounting** - lowering some non-zero counts to get probabiliby mass to assign to zero-counts\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\nBayes' net (network) is a technique for describing complex joint distributions (aka models) using simple, local distributions (aka conditional probabilities). \nThese are graphical models that describe how variables locally interact. \n* Nodes: variables (with domains) that are observed (assigned) or unobserved (unassigned)\n* Arcs: interations indicating direct influence between variables and encode condiation independence. \nDirection of the arrow could mean causation. e.g. rain --> (causes) traffic but actually mean correlation and encode conditional independence.\n\n\nBayes' nets are directed acyclic graphs and the graphs can be turned into a conditional probability table (CPT) \n* P(X|A1...An) for all nodes An that are pointing to X\n\n\nBayes' nets implicitly encode join distributions, which are a product of local conditional distributions. But not every BN can represent every join distribution. \nFor N boolean variables, BNs are of size $2^N$. An N-node net with k parents is $O(N*2)^{k+1}$. With both of these nets, we can calculate probability but BNs give \na huge space savings and are easier to elicit local CPTs. $\\perp \\!\\!\\! \\perp$ means independent (X is independent of Y)\n* X and Y are independent if $\\forall x,y  P(x,y)=P(x)P(y) \\leftarrow X \\perp \\!\\!\\! \\perp Y$\n* X and Y are conditionally independent given Z if $\\forall x,y,z  P(x,y|z) =P((x|z)P(y|z) \\leftarrow X \\perp \\!\\!\\! \\perp Y|Z$\n\n\nBNs contains independence assumptions that need to be understood when modeling with a BN.\nWe can break BNs into descendents using D-separation, breaking it down into triples. \nWe can use BNs to analyze casual chains and common causes to determine independence with three variables. If the path is blocked, they are not conditionally independent. \n* what are all the paths/triples between the variables? \n* are they inactive or active triples? if a variable is given, then shaded it. Then compare the triple to the picture. \n* if all the paths are inactive, then independece is guranteed. \n* path is active if all triples in the path is active. if one is not active, then the path is inactive and conditional independence is guranteed.\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\nModel-Based Classification - build a model, like a Bayes' Net where both the label and the features are random variables. \nInstantiate any observed features and query for the distribution of the label conditioned on the features. Query variable \nis random variable that we want to make an inference on. One approach we \ncould use is Naive Bayes where we assume all the features are independent. The features are determined to be either on or \noff (1 or 0). We are trying to learn the labels for the features. To use Naive Bayes, we need \n* Inference: start with a bunch of probabilities, calculate the standard inference.\n* Estimates of local conditional probability tables: these probabilities are called the parameters $\\theta$ of the model. \nThese are determined from the training data counts. \n\nWe are trying to learn all the probability tables. The prior probability times the probability of all of the features given \nthe label. For digits, the prior probability would be 1/10 since there are 10 digits. Size is the number of classes we have \ntimes number of features to n. With Naive Bayes, this would change to n*F*Y. Since we are making strong indepenence assumptions, \nit does not perfectly capture reality but it will do ok and work quickly. \n* get the prob of y given all the features. get join prob of label and evidence for each label. \n* sum over the probabiliy of the labels after naive bayes\n* divide step 1 by step 2\n* we need to learn the feature values\n\nBag-of-words Naive Bayes: \n* represent a text document as a \"bag-of-words\" that are an unordered set of words, keeping only their frequency. \n\n\nIf we are giving relative frequencies with zero probabilities, we run the risk of overfitting the data, which will result in \nincorrect classification. We can use smoothing and parameter estimation for this. \n* elicitation based - ask a human, domain knowledge\n* empirically - learn using data (P = count of x /total samples)\n  * if we have two probability possibilities, the best is the one that maximizes the likelihood of the data. $L(x, \\theta_1) = 2/3* 2/3* 1/3 = 0.148$ vs $L(x, \\theta_2) = 1/2* 1/2* 1/2=0.125$ \n  this gives the best fit for the data.\n\n\nBut what do we do with unseen events? Laplace smoothing can add 1. Or some other number with a hyperparameter. Another option \nis linear interpolation with value $\\alpha$. Learn prob from training data set, train the hyperparamters from the heldout set. \nOther options to improve is to add more features. If the model is getting good accuracy, we need a baseline to compare it to. \nWhat is the best model accuracy for the current approaches for the same problem? Did it beat it?  \n\n\nPerceptron is a different classifer for making decisions. The features are representing something we want to classify. \nTheir values are fixed but we can choose different weight vectors. Depending on the weigh vector chosen, we will get a different classifier. \nIn the space of feature vectors, each of the examples are points and a weight vector is a hyperplane. For a binary perceptron, the weights \nwill start at 0, if the label is correct, dont change the weight, but if it is not, then adjust the value of the weight vector. The highest \nvalue would be determined to be the label. \n\nIf data is not separable, then we loose accuracy. Perceptrons can also have problems with drawing the line between classes so that it barely \nseparates the data. It also can overtrain, similar to overfitting. \n* One approach is to adjust the weights to mitigate these effects with an approach like MIRA (Margin Infused Relaxed Algorithm). \n* Another could be to maximize the step size so that you are not making too big of an \nupdate at one time. \n* Support Vector Machines allow us to maximize the margin or space between the data so that the separating line is in the \nmiddle between them. SVMs are similar to MIRA where you optimize over all examples at once.\n* Non-linear separators take the data and map it to a higher dimensional space where it can be separable\n\n\nActivation Functions:\n\nWe can apply a non-linear function in order to add dimensionality to the model.\n* sigmoid function\n* tanh function\n* rectified linear unit ReLU\n\n\n## Module 12 Definitions\n* **Classification** - given inputs x, predict labels y\n* **Separability** - true if some parameters get the training set perfectly correct, such as with the hyperplane\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 or degree of separability\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\nJust like the last module, we are working with classifiers:\n* Feature representation: vector of features x\n* classification function: computers our predictions $\\hat{y}$ from the probabilities\n* objective function: NEW, also known as a loss function, this allows us to learn and usually involves trying to minimize the error on the training examples\n* some algorithm for optimizing the objective function, updates the parameters, (e.g. stochasic gradient descent)\n\n\nlearning with the dot product of weights $z = w \\cdot x + b$\n\nWe will squish the value z with the sigmoid function (logrithmic function). $P = \\sigma (w \\cdot x + b)$. \nWhat is the threshold for pos vs neg class? This is easy for binary because it is 1 if >0.5 and 0 otherwise. \nFeature engineering is the process of creating features that we can use to classify the review. The weights \ncan be given to us to how important that feature is to classify the statement. Then take the product of value * weight \nand add them together and that gives the z value. Then we can apply the sigmoid ($y=1/(1+e^{-z})$) to squish it into the range for a \nprobability. \n\nBut usually the weights are not given to us, so we need to learn them. \n* objective function or loss function that gives us the distance between the system output and the gold \noutput. for this we will use cross-entropy loss\n* we will use stochastic gradient descent to minimize (aka optimize) the loss function. \n\nLoss Functions:\n\nHow close is the classifer to the correct output. How much does $\\hat{y}$ different from true y.\n$L_{MSE}(\\hat{y}, y)=1/2(\\hat{y}-y)^2$. The loss function prefers that correct class labels of \nthe training example to be more likely. Using conditional maximum likelihood estimateion, we choose \nparameters for w, b that maximizes the (log) probabilities of the true labels inthe training data. \nthe resulting loss function is the negative log likeihood loss, called the *cross entropy loss*. \nWhen trying maximize the probability, we want y_hat as high as possible when y is supposed to equal 1, \nand for y_hat to be as low as possible (near to zero) when y is supposed to equal 0. \n$L_{CE}(\\hat{y},y)=-[y log \\theta (w \\cdot x +b) +(1-y) log (1- \\theta (w \\cdot x +b)]$ \nIf y=1 the second term would drop out and we would only need to compute the first term because \nof math. If y=0, then the first term would drop and we would only compute the second term. \nThe log values will get smaller and smaller if the values are getting closer to the truth. \nSo we want to minimize the loss of all labels in the training set. \n\nTo find good parameters, we can use Gradient Descent to find a minimum function by figuring out in \nwhich direction (in the space of parameters theta) the function's scope is rising the most steeply \nand moving in the opposite direction. For logistic regression, the loss function is convex, so we \nneed to look for the one minimum, gradient descent will help to find the minimum by comparing the slopes. \nWe need to do this across many dimensions. \n\nStochastic gradient descent chooses a single random example at a time and updates its weights. Because \nof this randomness, the updates can fluctuate. An alternative is bath training which compute the gradient \nover the entire dataset, but this takes a long time, even though it gives a better estiamte. A compromise \nis mini-batch training. The size of the batch is selected based on computational resources so that all examples \nin the mini-batch can run in parallel. Afterwards, the loss is accumulated. \n\nOverfitting is a problem with many ML models. This is a result of poor generalization and performance on \nan unseen test set. In log regression, if a feature only occurs in one class then it gets a high \nweight. If we are modeling noisy factors, they can accidently correlate with the class which can \nmess with the weights. Regularization is a way to penalize large weights. This is a term used to add to \nthe loss function. \n* Lasso regresssion = L1 regularization \n* Ridge regression = L2 regularization\n\nIf we want more than two classes, we need a generalization of the sigmoid function called the \nsoftmax function: $softmax(z_i)=\\frac{e^{z_j}}{\\sum_{j=1}^{k}e^{z_j}} 1 \\geq i \\geq k$. The \nsoftmax function takes an input vector z and outputs a vector of normalized probabilities for \neach of the classes. \n\n\nNeural Networks:\n\nA single computations unit is the building block of NN. THe simpliest kind of NN is the \nFeed-Forward Neural Network. This is a multilayered network where all units are fully connected \nand there are no cycles. Outputs are passed from each layer and every passed back down. \n* multiple the weight maxtrix by the input vector x\n* adding the bias vector b \n* applying the activation function g (such as sigmoid)\n\nThe output of the hidden layer ($h=\\sigma (Wx+b$) is passed to the output layer ($z=Uh$) where \nU is the weight matrix and z is the output). Output z is then passed to softmax to compute the final \nprobability distribution to normalize the output. \n\nTo train a NN, we need \n* loss function - cross entropy loss \n* optimization algorithm - gradient descent \n* computing the gradient of the loss function - error propagation \n\n\nFor deep networks, we need to compute the gradient by looking back through all the earilier layers \nin the network. To do this, we can use error backpropagation.  \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\nIn Vector Space Models, each document in the collection is represented as a point in space \n(a vector in a vector space). The user's query is a pseudo-document and joins the other \ndocuments in the same space. Information retrieval (IR) was performed by selecting the vectors \nthat are close together in the space to the query vector. \n\nTerm-Document Matrix:\n* Each column vector represents a document \n* Each row vector represents a term \n* The value in a cell is based on how often that term occured in the document \n* the length of the document vectors (y-axis) is the size of the vocab\n* the width of the matrix (x-axis) is the number of documents in the collection\n* document vectors can be sparse (most values 0)\n* we can measure how similar two documents are by comparing their column vectors\n\nTerm-document maxtrices are good for identifying plagarism. Comparing two row vectors let's \nus see how close words are to each other. We can normalize the data with Vector L2 (length) \nnormalization ($||u||= \\sqrt{\\sum_{i=1}^{n}u_i^2}$) then divide the vector by the L2 length u \nto get the normalized values which will take care of discrepancies for highly used words. Cosine \ndistance can also be used to compare similarities based on the cosine angle between them. \n\n\nTerm-Term Matrix:\n* aka Term-context matrix\n* the length of the row vector is now |V| (vocabulary, words) instead of number of documents. \nso now both axises are the words. \n* the value in a cell indicates how often the word appears in a context window of the other word. \n* we need to pick a context window, such as +/-2 words to either side of the target word. \n\n\n\nAnother option is that we can use syntax to define a word's context instead of the surrounding words. \nAlternatives to raw counts are transforming vectors with methods such as TF-IDF (Term frequency 'how \noften a word occurs in a document' * inverse document frequency '1 over the number of documents that \nthe word occurs in' ) or PPMI. Co-occurnace matrix (such as weighed by TF-IDF) are long and sparse. \nAn alternative is that we could learn vectors that are short and dense. \n\n\nIn Language modeling, we are trying to learn a function that returns the join probability for the words. \nThis is usually hard because there are too many parameters (aka curse of dimensionality) and in n-gram \nbased models, we fail to generalize to related words/word sequences that we already have observed. Neural \nLanguage models have several advantages over n-gram LMs. \n* dont need smoothing \n* handle longer histories \n* can generalize over contexts of similar words\n* have higher predictive accuracy\n* BUT they are slower to train \n\nTo do this, we need to... \n* Associate each word in the vocab with a vector representation, create a notion of similiarity between words \n* Express joint prob function of a word sequence in terms of the word vectors for the words in that sequence \n* Simultaneously learn the word vectors and the parameters of the function \n\nWe can use a multilayer, feed forward neural network to get a prob function that expresses the product \nof conditional probabilities of the next word given the previous word. \n* input: k-gram of words\n* output: prob distribution over next word\n* k context words is treated as a word window. Each word is associated with an embedding vector.\n\nJust like before, training examples are just word k-grams from the corpus. Identidies of the first k-1 words are used \nas features and the last word is the target label for the classification (the new word we are trying to predict that \nmight come after the words in the k-gram). The model can be trained using cross entropy loss. \n* NN LMs achieve better perplexity scores\n* they can scale to larger n-grams because the parameters are associated only with individual words instead of n-gram combinations \n* they can generalize across contexts, seeing that all color words live in the same context, for example\n* A by-product of trainings are word embeddings\n\nWord Embeddings are discovered when we take multidimentsional vectors and project it to 2 dimensions. Similar \nwords are clustered together. \n* Embeddings can capture relational meanings, like man -> woman, uncle -> aunt \n\nWe can train a classifier to get dense vectors. This is also the same approach as Word2Vec \n\"skip-gram with negative sampling\" (SGNS). \n* Treat the target word and a neighboring context word as positive examples\n* Randomly sample other words in the vocab to get negative samples\n* Use log regression to train a classifier to distinguide the pos and neg cases \n* Use the weights as the embeddings\n* This is similar to what Word2Vec does. Train a classifier on a binary prediction task (is w likely to show up near 'apricot'?)\n\nWe want dense vectors because the shorter vectors may be easier to use as features themselves (fewer weights to tune). \nDense vectors may generalize better than storing explicit counts and may be better at capturing synonymy. \n\nWe need the probability (target, context):\n* $P(+|t,c) = \\frac{1}{1+e^{-t \\cdot c}}$\n* $P(-|t,c) = 1-P(-|t,c)= \\frac{e^{-t \\cdot c}}{1+e^{-t \\cdot c}}$\n\nNow that we can compute the probabilities (take the log to actually do the math) Word2Vec \ncan learn the embeddings automatically. It starts with an initial set of embedding vectors and iteratively shifts the \nembedding of each word to be more like the embeddings of words that occur in nearby text and less like the ones that \nare not close by.\n\nTo chose 'noise words' to serve as negative examples, could pick them according to their unigram frequency. \nBut it is more common to chose according to $p_{\\alpha}(w) = \\frac{count(w)^{\\alpha}}{\\sum_w count(w)^{\\alpha}}$. \n$\\alpha=3/4$ works well because it gives rare noise words with slightly higher probability.\n\nWe can start with initial weights of zero or random values. we will adjust the word vectors so that we are \nmaximizing the similiary of the (t,c) pairs from the positive data and minimizing the similiary of the (t,c) \npaids from the negative data. If we use gradient descent to train, we would result in learning two separate \nembedding matrices. We can throw one away or merge them for the final result. Embeddings need to be evaluated \nbased on human input on whether they are accurate or not. Pairs of words that are similar are concordant and \ndissimilar are discordant. Correlation can be computed as $(N(N-1)/2)/total pairs$. \n\nDepending on the window size chosen, the embeddings will change too. We can solve analogies with embeddings by \ncomparing the vectors. a:a* as b:b* where b* is a hidden vector; b* = b-a+a*. We can optimize analogies by solving \n$argmax_{b* \\in V}( \\cos(b*, b-a+a*))$\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}