{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 60,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "54580f1e-22eb-4657-8e14-104a615b6276"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 61,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "2cd4c8a2-805b-483a-8fae-409ce38e0560"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 62,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 63,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = \"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Decision theory refers to the idea of choosing among actions based on how desirable their\n",
        "immediate outcomes are. An agent's preferences are represented by a utility function $U(s)$. The expected utility of an action is\n",
        "the average utiltiy of the outcomes multiplied by the probability that particular outcome occurs. MEU formalizes that an inteeligent agent\n",
        "should do the right thing but does not acutllay execute that. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Think of the set of outcomes of an action as a lottery in which each action represents a ticket. Each lottery contains a \n",
        "set of possible outcomes all assigned specific probabilities. Each outcome is either a state or another lottery. With utility theory, the goal \n",
        "is to understand preferences with regards to complex lotteries and their relationships to the states within them. An agent that violates the \n",
        "axioms of utility theory will exhibit irrational behavior. We can represent a set of outcomes for each action as a lottery where each action is a\n",
        "ticket. A lottery L with outcomes $S_1, S_2, \\ldots, S_n$ with occurrence probabilites of $p_1, \\ldots, p_n$ looks like \n",
        "$$L = [p_1, S_1; p_2, S_2; \\ldots p_n, S_n]$$\n",
        "\n",
        "The utility of one action is greater than another only if the former is preferred to the latter. Similarly, the utilites are only equal if the agent\n",
        "is indifferent between the two. Note that just because a utility function exists, the agent is not necessarily maximizing the utility function\n",
        "on its own. \n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\" Utility functions are relevant for mapping the lotteries described above to real numbers. Using a process call preference \n",
        "eliciation, we can help design a system that can make decisions or act on behalf of a human. This process requires us to present choices to the \n",
        "human and decide by observing on the underlying utility function representing that person's preferences. Agents that are risk averse show a curve \n",
        "that for any lottery, the utility of getting the lottery is less than just the expected money of the lottery. On the opposite end are risk seeking.\n",
        "The rational way to choose the best action is usually to maximize the expected utility.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Sometimes decision making is stochastic such that when an agent makes a move, there is a probability that it will actually carry out \n",
        "that move as $P(s'|s, a)$. The utility function in this case depends on a sequence of states and actions known as the environment history where at each state\n",
        "the agent recieved some reward $R(s, a, s'). A solution to a problem defined as an MDP must specificy what the agent should for for any state that the agent might \n",
        "possibly reach. With a finite horizon an optimal action in a particular state depends on how much time is left which is called nonstationary policy. When there is no fixed\n",
        "time limit, there is no reason to change your policy in the same state at different times which means that the optimal action depends only on the current state. This is\n",
        "knowned as a stationary policy. The discount factor is close to 0 when rewards in the future are insignificant and close to 1 when the agent is more willing to wait for \n",
        "long term rewards. We use the discount factor to account for the fact that humans perfer near-term rewards more highly than rewards in the future. \n",
        "\n",
        "The expected utility is given by the following function: $E[\\sum_{t = 0} \\gamma ^ t R(S_t, \\pi(S_t), S_{t + 1})$$\n",
        "We want to select the arg max of that equation which becomes $\\pi_s*$. THe utility of some state $s$ is given by the max action of $Q$ over all possible actions for that \n",
        "state. WE can obtain the optimal policy from the Q-function by taking the argmax of $Q(s, a)$ over all actions for state $s$. \n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\" There are four different algorithms for solving MDPS: value iteration, policy iteration, and linear programming which create solutions offline. MonteCarolo planning \n",
        "is an online approximate algorithm.\n",
        "\n",
        "Value iteration is based significantly on the Bellman equation. If there are $n$ states, then there are $n$ Bellman equations for each state. The goal is to solve these equations \n",
        "to find the utilites. To do so, we try an diterative approach where we start with arbitrary values for the utilites to progressivly until we reach an equilibrium. Note that we are guaranteed \n",
        "to reach equilibrium. THe Bellman equation update is a contractation by a factor of $\\gamma$ on the set of utility vectors.\n",
        "\n",
        "Policy iteration alternates between policy evaluations where it finds the utility of each state is some policy $\\pi_i$ were to be executed and policy improvement\n",
        "which calculates the new MEU policy using a one-step look-ahead. The algorithm stops when policy improvement does not result in an updates to the utilites. It differs from \n",
        "value iteration in that the action is fixed by the policy. \n",
        "\n",
        "A simplified version of expectiminimax is an example of an online approximation algorithm. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"represents how desirable a state is\",\n",
        "\"expected utility\" : \"average utility value weighted by the probability outcome occurs\",\n",
        "\"maximum expected utility\": \"a rational agent should pick the action that maximizes EU (argmax)\",\n",
        "\"orderability\" : \"given two lotteries a rational agent must prefer one or think both are equal, must make a decision\",\n",
        "\"transitivity\" : \"if an agent prefers A to B and C to C then it prefers A to C\",\n",
        "\"continuity\" : \"if lottery B is between two others, the agent will be indifferent toward getting it or the other two\",\n",
        "\"substitutability\" : \"if indifferent between two choices, also indifferent if both are added to another lotter\",\n",
        "\"monotonicity\" : \"if outcomes are the same and agent prefers one lottery, it must prefer the one with the higher probability\",\n",
        "\"decomposability\" : \"lotteries can be reduced to smaller ones using probability laws\", \n",
        "\"value function/ordinal utility function\" : \"in deterministic game play, agent only needs preference ranking on the states invovled\", \n",
        "\"preference elicitation\" : \"how we determine what the human's utility function is\",\n",
        "\"normalized utilities\" : \"use a scale of 0 and 1 to assign utility to things\", \n",
        "\"certainty equivalent\" : \"value an agent accepts instead of a lottery\", \n",
        "\"optimizer's curse\" : \"overestimating the expected utility of best choice\", \n",
        "\"certainity effect\" : \"people prefer gains that are certain\",\n",
        "\"risk neutral\" : \"an agent with a linear utility curve\",\n",
        "\"sequential decision problems\" : \"the agent's utility depends on a sequence of actions\",\n",
        "\"Markovian\" : \"the probability of reach a state from another depends only on the first state and nothing else\",\n",
        "\"Markov decision process\" : \"fully observable, stochatic environemtn with Markovian transition model and rewards\",\n",
        "\"policy\" : \"denoted by $\\pi$ and $\\pi(s)$\",\n",
        "\"optimal policy\" : \"returns the highest expect utility given the different possibilities in that environment: $\\pi*$\",\n",
        "\"finite horizon\" : \"there is a fixed time $N$ after which the game is over\",\n",
        "\"additive discounted rewards\" : \"the utility of a history is the sum of the rewards multiplied by discounter factor\",\n",
        "\"discount factor\" : \"$\\gamma$ is a number between 1 and 0 which describes preferences for current rewards over future rewards\",\n",
        "\"additive rewards\" : \"when discount factor is exactly 1 where everything is purely additive\",\n",
        "\"proper policy\" : \"a policy that is guaranteed to reach a terminal state\",\n",
        "\"Bellman equation\" : \"utilites to states as teh expected utility of following states are teh solutions\",\n",
        "\"action-utility function/Q-function\" : \"expected utility of taking a given action in a given state is $Q(s, a)$\",\n",
        "\"contraction\" : \"function of one argument that applied to two inputs returns two outputs close together, used in convergence\",\n",
        "\"policy loss\" : \"the most an agent can lose by implementing something other than the optimal policy\",\n",
        "\"modified policy iteration\" : \"addresses space problem by running simplified value iteration and repeated several times\",\n",
        "\"linear programming\" : \"formulating constrained optimization problems\",\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 64,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 572
        },
        "id": "gYYeNcdM_maE",
        "outputId": "207ec42d-9028-4960-d00c-85836a9d5f16"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 8: Markov Decision Processes\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Decision theory refers to the idea of choosing among actions based on how desirable their\n",
              "immediate outcomes are. An agent's preferences are represented by a utility function $U(s)$. The expected utility of an action is\n",
              "the average utiltiy of the outcomes multiplied by the probability that particular outcome occurs. MEU formalizes that an inteeligent agent\n",
              "should do the right thing but does not acutllay execute that.  $P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Think of the set of outcomes of an action as a lottery in which each action represents a ticket. Each lottery contains a \n",
              "set of possible outcomes all assigned specific probabilities. Each outcome is either a state or another lottery. With utility theory, the goal \n",
              "is to understand preferences with regards to complex lotteries and their relationships to the states within them. An agent that violates the \n",
              "axioms of utility theory will exhibit irrational behavior. We can represent a set of outcomes for each action as a lottery where each action is a\n",
              "ticket. A lottery L with outcomes $S_1, S_2, \\ldots, S_n$ with occurrence probabilites of $p_1, \\ldots, p_n$ looks like \n",
              "$$L = [p_1, S_1; p_2, S_2; \\ldots p_n, S_n]$$\n",
              "\n",
              "The utility of one action is greater than another only if the former is preferred to the latter. Similarly, the utilites are only equal if the agent\n",
              "is indifferent between the two. Note that just because a utility function exists, the agent is not necessarily maximizing the utility function\n",
              "on its own. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Utility functions are relevant for mapping the lotteries described above to real numbers. Using a process call preference \n",
              "eliciation, we can help design a system that can make decisions or act on behalf of a human. This process requires us to present choices to the \n",
              "human and decide by observing on the underlying utility function representing that person's preferences. Agents that are risk averse show a curve \n",
              "that for any lottery, the utility of getting the lottery is less than just the expected money of the lottery. On the opposite end are risk seeking.\n",
              "The rational way to choose the best action is usually to maximize the expected utility.\n",
              "\n",
              "\n",
              "## AIMA Chapter 17.1 Sequential Decision Problems\n",
              " Sometimes decision making is stochastic such that when an agent makes a move, there is a probability that it will actually carry out \n",
              "that move as $P(s'|s, a)$. The utility function in this case depends on a sequence of states and actions known as the environment history where at each state\n",
              "the agent recieved some reward $R(s, a, s'). A solution to a problem defined as an MDP must specificy what the agent should for for any state that the agent might \n",
              "possibly reach. With a finite horizon an optimal action in a particular state depends on how much time is left which is called nonstationary policy. When there is no fixed\n",
              "time limit, there is no reason to change your policy in the same state at different times which means that the optimal action depends only on the current state. This is\n",
              "knowned as a stationary policy. The discount factor is close to 0 when rewards in the future are insignificant and close to 1 when the agent is more willing to wait for \n",
              "long term rewards. We use the discount factor to account for the fact that humans perfer near-term rewards more highly than rewards in the future. \n",
              "\n",
              "The expected utility is given by the following function: $E[\\sum_{t = 0} \\gamma ^ t R(S_t, \\pi(S_t), S_{t + 1})$$\n",
              "We want to select the arg max of that equation which becomes $\\pi_s*$. THe utility of some state $s$ is given by the max action of $Q$ over all possible actions for that \n",
              "state. WE can obtain the optimal policy from the Q-function by taking the argmax of $Q(s, a)$ over all actions for state $s$. \n",
              "\n",
              "\n",
              "## AIMA Chapter 17.2 Algorithms for MDPs\n",
              " There are four different algorithms for solving MDPS: value iteration, policy iteration, and linear programming which create solutions offline. MonteCarolo planning \n",
              "is an online approximate algorithm.\n",
              "\n",
              "Value iteration is based significantly on the Bellman equation. If there are $n$ states, then there are $n$ Bellman equations for each state. The goal is to solve these equations \n",
              "to find the utilites. To do so, we try an diterative approach where we start with arbitrary values for the utilites to progressivly until we reach an equilibrium. Note that we are guaranteed \n",
              "to reach equilibrium. THe Bellman equation update is a contractation by a factor of $\\gamma$ on the set of utility vectors.\n",
              "\n",
              "Policy iteration alternates between policy evaluations where it finds the utility of each state is some policy $\\pi_i$ were to be executed and policy improvement\n",
              "which calculates the new MEU policy using a one-step look-ahead. The algorithm stops when policy improvement does not result in an updates to the utilites. It differs from \n",
              "value iteration in that the action is fixed by the policy. \n",
              "\n",
              "A simplified version of expectiminimax is an example of an online approximation algorithm. \n",
              "\n",
              "## Module 8 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 8 Definitions\n",
              "* **Utility function** - represents how desirable a state is\n",
              "* **Expected utility** - average utility value weighted by the probability outcome occurs\n",
              "* **Maximum expected utility** - a rational agent should pick the action that maximizes EU (argmax)\n",
              "* **Orderability** - given two lotteries a rational agent must prefer one or think both are equal, must make a decision\n",
              "* **Transitivity** - if an agent prefers A to B and C to C then it prefers A to C\n",
              "* **Continuity** - if lottery B is between two others, the agent will be indifferent toward getting it or the other two\n",
              "* **Substitutability** - if indifferent between two choices, also indifferent if both are added to another lotter\n",
              "* **Monotonicity** - if outcomes are the same and agent prefers one lottery, it must prefer the one with the higher probability\n",
              "* **Decomposability** - lotteries can be reduced to smaller ones using probability laws\n",
              "* **Value function/ordinal utility function** - in deterministic game play, agent only needs preference ranking on the states invovled\n",
              "* **Preference elicitation** - how we determine what the human's utility function is\n",
              "* **Normalized utilities** - use a scale of 0 and 1 to assign utility to things\n",
              "* **Certainty equivalent** - value an agent accepts instead of a lottery\n",
              "* **Optimizer's curse** - overestimating the expected utility of best choice\n",
              "* **Certainity effect** - people prefer gains that are certain\n",
              "* **Risk neutral** - an agent with a linear utility curve\n",
              "* **Sequential decision problems** - the agent's utility depends on a sequence of actions\n",
              "* **Markovian** - the probability of reach a state from another depends only on the first state and nothing else\n",
              "* **Markov decision process** - fully observable, stochatic environemtn with Markovian transition model and rewards\n",
              "* **Policy** - denoted by $\\pi$ and $\\pi(s)$\n",
              "* **Optimal policy** - returns the highest expect utility given the different possibilities in that environment: $\\pi*$\n",
              "* **Finite horizon** - there is a fixed time $N$ after which the game is over\n",
              "* **Additive discounted rewards** - the utility of a history is the sum of the rewards multiplied by discounter factor\n",
              "* **Discount factor** - $\\gamma$ is a number between 1 and 0 which describes preferences for current rewards over future rewards\n",
              "* **Additive rewards** - when discount factor is exactly 1 where everything is purely additive\n",
              "* **Proper policy** - a policy that is guaranteed to reach a terminal state\n",
              "* **Bellman equation** - utilites to states as teh expected utility of following states are teh solutions\n",
              "* **Action-utility function/q-function** - expected utility of taking a given action in a given state is $Q(s, a)$\n",
              "* **Contraction** - function of one argument that applied to two inputs returns two outputs close together, used in convergence\n",
              "* **Policy loss** - the most an agent can lose by implementing something other than the optimal policy\n",
              "* **Modified policy iteration** - addresses space problem by running simplified value iteration and repeated several times\n",
              "* **Linear programming** - formulating constrained optimization problems\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 65,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" In the n-armed bandit problem, the gambler must choose which lever to play: either the one that has given the best payoff so far or an unexplored one. This is an example of \n",
        "the tradeoff between exploitation of the current best option and exploration of any unknown states to potentially discover a better policy in the long-run. There are many iterations of this game. It is often\n",
        "challenging to calculate the best policy so the there is a way to approximate policies such that they are nearly optimal using an uppre confidence bound heuristic. It essentially established a confidence interval\n",
        "for the value of the arm. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"Reinforcement learning is different than MDP because the agent is not given the MDP as a problme to solve but rather it already \n",
        "in the MDP. The agent might not know the transition model or the reward function and has to learn it by executing actions. \n",
        "\n",
        "Model-based reinforcement learning uses a transition model of teh environment to understand reward signals and make action decisions. The transition model\n",
        "is learned by observing the effects of the actions. This also is often coupled with learning a utility function $U(s)$. Model-free reinforcement learning consists \n",
        "of two different types. Action-utility learning's most common form is Q-learning where the agent learns a Q-function representing the sum of rewards from state\n",
        "$s$ and onward depending on if some action $a$ is selected. The other type is policy search which learns some policy $\\pi*$; this is also called a reflex agent.\"\"\"\n",
        "chapter22_2 =  \"\"\" A passive agent is already given a fixed policy $\\pi$ and wants to learn the utility function which is the total expected discounted reward if that policy is executed. This is similar to the\n",
        "policy evaluation task but here the agent does not know the transition model or the reward function. At each point in time, the agent executes a series of trials using the assigned policy and\n",
        "experiences a sequence of transitions until it reaches a terminal state. Direct utility estimation is helpful but ignores the connection between teh Bellman equation and states determined by the utility and reward\n",
        "of successor states.\"\"\"\n",
        "chapter22_3 =  \"\"\"An active reinforcement agent does not have a fixed policy, rather it decides what actions to take. This agent has to learn a complete transition model not just for one policy but for all possible\n",
        "actions. One way to do this is through a greedy algorithm where the agent finds the first policy that results in a positive reward and sticks with it to the detriment of never finding any possibly larger rewards.\n",
        "Oftentimes this does not result in the convergence toward the optimal policy. The main problem is taht the greedy agent overlooks the information that can be learned at any step. The agent has to make a tradeoff\n",
        "between exploration and exploitation. We can rememdy this with application of a GLIE scheme where each action in a state is tried an unbounded number of times to avoid missing an optimal action. An algorithm operating\n",
        "using maximum-likelihood estimation chooses a policy based solely on the estimated model so it will act like that model is always correct. Instead we should choose a policy that works pretty well for a range of models\n",
        "that are reasonable similar to the real model. There are three ways to do this: \n",
        "\n",
        "Bayesian Reinforcement Learning: assumes there is a prior probability over a set of hypotheses about what the true model is. If an agent decides to stop learning, the optimal policy is the one with currently the highest\n",
        "expected utility. In special cases, the optimal policy can be computer. However, if the agent continues learning, it becomes more more difficult because the agent has to think about the future in terms of its transition \n",
        "model. \n",
        "\n",
        "Second approach: uses robust control theory which allows for a set of possible models $H$ with no probabilites such that the optimal robust policy is the one that gives the best outcome in the worst case over $H$. This \n",
        "similar to minimax. The problem with this however it is that it results in overly conservative behavior. It does not account for risk-reward tradeoffs.\n",
        "\n",
        "The Q-Learning method avoids the need for a model by learning an action-utility function instead of just a utility function: $Q(s, a)$. Each value represents the expected reward if the agent takes that action and continues\n",
        "to act optimally. This allows the agent to just choose the argmax $Q(s, a)$ value without having to look ahead.\n",
        "$$Q(s, a) = Q(s, a) + \\alpha[R(s, a, s') + \\gamma max Q(s', a') - Q(s, a)]$$\n",
        "\n",
        "SARSA is a similar algorithm to Q-Learning where the Q-value is updated with the valye of the action $a'$ already taken.\n",
        "\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"This focuses on the idea of function approximation as the process of creating an approximation of the true utility function or Q-function. We can do this using features as a weight linear combination. \n",
        "This allows us to learn a subset of values rather than have to look at every single state in the model. However, this is often not sufficient. Thus, a lot of modern machine learning algorithms focus on deep learning or\n",
        "non linear methods.\"\"\"\n",
        "chapter22_5 =  \"\"\" Policy search is the final type of reinforcement learning. It keeps modifying policy as long as performance continues improving. We optimize this by using gradients which eventualy allow us to converge\n",
        "to a local optimum policy. It is much more challenging to do this when the policy is nondeterministic (ie includes probability of action in state)\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"supervised learning\" : \"learning by passively observing input/output pairs provided by external source\",\n",
        "\"reinforcement learning\" : \"an agent interacts with the world and occassionally receives rewards depending on how well it's doing\",\n",
        "\"passive reinforcement learning\" : \"agent's policy is fixed and agent needs to learn the utilites of state-action pairs\",\n",
        "\"active reinforcement learning\" : \"agent also has to figure out what to go through exploration\",\n",
        "\"n-armed bandit\" : \"has n levers behind each is a fixed/unknown probability of winnings\",\n",
        "\"Bernoulli bandit\" : \"each arm produces a reward of either 1 or 0 with an unknown probability\",\n",
        "\"selection problem\" : \"choosing the best option under some set of constraining conditions\",\n",
        "\"dominating policy\" : \"an optimal policy is unaffected by the opportunity cost\",\n",
        "\"direct utility estimation\" : \"utility of a state defined as expected total reward where each trial is a sample of possible reward\",\n",
        "\"adaptive dynamic programming\" : \"uses dynamic programming to solve the Markov decision process\",\n",
        "\"learning rate\" : \"$\\alpha\",\n",
        "\"temporal difference equation\" : \"update rule using teh difference in utilites between sucessive states\",\n",
        "\"GLIE\" : \"greedy in the limit of infinite exploration\",\n",
        "\"aborbing state\" : \"no actions have any effect and no rewards are given\",\n",
        "\"off-policy\" : \"Q-Learning; stop using current policy and act according to policy with best actions\",\n",
        "\"softmax\" : \"parameter \\beta modulates how close the max is to the hard max vs uniform random choice \",\n",
        "\"stochastic policy\" : \"representation of a policy that includes the probability of selecting action $a$ in state $s$\"\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 66,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 536
        },
        "id": "ydOK__lwWgdp",
        "outputId": "4707dfb3-647d-4ac6-9ce2-8249951a4723"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 9: Reinforcement Learning\n",
              "## AIMA Chapter 17.3 Bandit Problems\n",
              " In the n-armed bandit problem, the gambler must choose which lever to play: either the one that has given the best payoff so far or an unexplored one. This is an example of \n",
              "the tradeoff between exploitation of the current best option and exploration of any unknown states to potentially discover a better policy in the long-run. There are many iterations of this game. It is often\n",
              "challenging to calculate the best policy so the there is a way to approximate policies such that they are nearly optimal using an uppre confidence bound heuristic. It essentially established a confidence interval\n",
              "for the value of the arm. \n",
              "\n",
              "## AIMA Chapter 22.1 Learning from Rewards\n",
              "Reinforcement learning is different than MDP because the agent is not given the MDP as a problme to solve but rather it already \n",
              "in the MDP. The agent might not know the transition model or the reward function and has to learn it by executing actions. \n",
              "\n",
              "Model-based reinforcement learning uses a transition model of teh environment to understand reward signals and make action decisions. The transition model\n",
              "is learned by observing the effects of the actions. This also is often coupled with learning a utility function $U(s)$. Model-free reinforcement learning consists \n",
              "of two different types. Action-utility learning's most common form is Q-learning where the agent learns a Q-function representing the sum of rewards from state\n",
              "$s$ and onward depending on if some action $a$ is selected. The other type is policy search which learns some policy $\\pi*$; this is also called a reflex agent.\n",
              "\n",
              "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
              " A passive agent is already given a fixed policy $\\pi$ and wants to learn the utility function which is the total expected discounted reward if that policy is executed. This is similar to the\n",
              "policy evaluation task but here the agent does not know the transition model or the reward function. At each point in time, the agent executes a series of trials using the assigned policy and\n",
              "experiences a sequence of transitions until it reaches a terminal state. Direct utility estimation is helpful but ignores the connection between teh Bellman equation and states determined by the utility and reward\n",
              "of successor states.\n",
              "\n",
              "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
              "An active reinforcement agent does not have a fixed policy, rather it decides what actions to take. This agent has to learn a complete transition model not just for one policy but for all possible\n",
              "actions. One way to do this is through a greedy algorithm where the agent finds the first policy that results in a positive reward and sticks with it to the detriment of never finding any possibly larger rewards.\n",
              "Oftentimes this does not result in the convergence toward the optimal policy. The main problem is taht the greedy agent overlooks the information that can be learned at any step. The agent has to make a tradeoff\n",
              "between exploration and exploitation. We can rememdy this with application of a GLIE scheme where each action in a state is tried an unbounded number of times to avoid missing an optimal action. An algorithm operating\n",
              "using maximum-likelihood estimation chooses a policy based solely on the estimated model so it will act like that model is always correct. Instead we should choose a policy that works pretty well for a range of models\n",
              "that are reasonable similar to the real model. There are three ways to do this: \n",
              "\n",
              "Bayesian Reinforcement Learning: assumes there is a prior probability over a set of hypotheses about what the true model is. If an agent decides to stop learning, the optimal policy is the one with currently the highest\n",
              "expected utility. In special cases, the optimal policy can be computer. However, if the agent continues learning, it becomes more more difficult because the agent has to think about the future in terms of its transition \n",
              "model. \n",
              "\n",
              "Second approach: uses robust control theory which allows for a set of possible models $H$ with no probabilites such that the optimal robust policy is the one that gives the best outcome in the worst case over $H$. This \n",
              "similar to minimax. The problem with this however it is that it results in overly conservative behavior. It does not account for risk-reward tradeoffs.\n",
              "\n",
              "The Q-Learning method avoids the need for a model by learning an action-utility function instead of just a utility function: $Q(s, a)$. Each value represents the expected reward if the agent takes that action and continues\n",
              "to act optimally. This allows the agent to just choose the argmax $Q(s, a)$ value without having to look ahead.\n",
              "$$Q(s, a) = Q(s, a) + \u0007lpha[R(s, a, s') + \\gamma max Q(s', a') - Q(s, a)]$$\n",
              "\n",
              "SARSA is a similar algorithm to Q-Learning where the Q-value is updated with the valye of the action $a'$ already taken.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
              "This focuses on the idea of function approximation as the process of creating an approximation of the true utility function or Q-function. We can do this using features as a weight linear combination. \n",
              "This allows us to learn a subset of values rather than have to look at every single state in the model. However, this is often not sufficient. Thus, a lot of modern machine learning algorithms focus on deep learning or\n",
              "non linear methods.\n",
              "\n",
              "## AIMA Chapter 22.5 Policy Search\n",
              " Policy search is the final type of reinforcement learning. It keeps modifying policy as long as performance continues improving. We optimize this by using gradients which eventualy allow us to converge\n",
              "to a local optimum policy. It is much more challenging to do this when the policy is nondeterministic (ie includes probability of action in state)\n",
              "\n",
              "## Module 9 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 9 Definitions\n",
              "* **Supervised learning** - learning by passively observing input/output pairs provided by external source\n",
              "* **Reinforcement learning** - an agent interacts with the world and occassionally receives rewards depending on how well it's doing\n",
              "* **Passive reinforcement learning** - agent's policy is fixed and agent needs to learn the utilites of state-action pairs\n",
              "* **Active reinforcement learning** - agent also has to figure out what to go through exploration\n",
              "* **N-armed bandit** - has n levers behind each is a fixed/unknown probability of winnings\n",
              "* **Bernoulli bandit** - each arm produces a reward of either 1 or 0 with an unknown probability\n",
              "* **Selection problem** - choosing the best option under some set of constraining conditions\n",
              "* **Dominating policy** - an optimal policy is unaffected by the opportunity cost\n",
              "* **Direct utility estimation** - utility of a state defined as expected total reward where each trial is a sample of possible reward\n",
              "* **Adaptive dynamic programming** - uses dynamic programming to solve the Markov decision process\n",
              "* **Learning rate** - $\u0007lpha\n",
              "* **Temporal difference equation** - update rule using teh difference in utilites between sucessive states\n",
              "* **Glie** - greedy in the limit of infinite exploration\n",
              "* **Aborbing state** - no actions have any effect and no rewards are given\n",
              "* **Off-policy** - Q-Learning; stop using current policy and act according to policy with best actions\n",
              "* **Softmax** - parameter \beta modulates how close the max is to the hard max vs uniform random choice \n",
              "* **Stochastic policy** - representation of a policy that includes the probability of selecting action $a$ in state $s$\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 67,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"Agents have to be able to handle uncertainty. So far we know they can do so by keeping track of a belief state which is a represetation of all the possible world states that\n",
        "the agent might be in. It then generates a contigency plan to handle all possible outcomes. However, this method has drawbacks because it requires so much storage of every possible belief.\n",
        "Generally the rational decision depends on the relative importance of various goals and the likelihood that they can be achieved. Probability gives us a way to solve the qualification problem \n",
        "upon which even if we don't know for sure we can make a good guess based on data. \n",
        "\n",
        "To utilize the idea of probability, an agent must have preferences among the different possible outcomes. Utility theory can be used to represent this. \"\"\"\n",
        "chapter12_2 = \"\"\"See notation in module definitions \"\"\"\n",
        "chapter12_3 = \"\"\"Probabilistic interference refers to the way we can compute conditional probabilites given observed evidence. We use a full joint distribution as the knowledge base from which \n",
        "we can find the answer to all our queries.\"\"\"\n",
        "chapter12_4 = \"\"\"Independence refers to the idea that $P(a|b) = P(a)$ or $P(a \\land b) = P(a)P(b)$. They allow us to dramtically refuxe the size of the full joint distribution.\"\"\"\n",
        "chapter12_5 = \"\"\" Bayes rule refers to the following equation: \n",
        "$$P(b|a) = \\frac{P(a|b)P(b)}{P(a)}$$\n",
        "\n",
        "We use Bayes rules to compute the probabily of a fourth value if we have three numbers. It allows us to perceive as evidence the effect of some unknown clause: the probability of a cause given an effect\n",
        "This is the diagnostic direction versus the probability of an effect given a cause is the causal direction. \n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"A commonly occurring pattern is a single cause directly influencing a number of effects all of which are conditionally independent given the cause. This probability distribution is known \n",
        "as a naive Bayes model. The tuntime of calculating this probability is linear to the number of observed effects.\"\"\"\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 = \"\"\"In order to compute the probabilites of entire sequences we need to use the chain rule of probability which is as follows \n",
        "$$P(X_1 \\ldots X_n) = \\Pi_{k = 1}^{n}P(X_k|X_{1:k-1})$$\n",
        "\n",
        "However this is a challenging calculation to make with the n-gram model. We can instead approximate the history of a word by just the last few words rather than looking over its entire history. Note \n",
        "that with language model probabilities we use log probabilities to account for potential underflow of multiplying small numbers together.\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"In order to use intrinsic evaluation on our language models we need to have a training set which sets up the probabilities of our n-gram model and then a test set which is some\n",
        "set of unseen data upon which to test the performance of our n-gram. To fit the test set means that the model more accurately predicts the test set. We use perplexity as the metric which is also \n",
        "known as the weighted average branching factor of a language. The branching factor is the number of words possible that could follow some word. Note that an intrinsic improvement in perplexity \n",
        "does not necessary mean there will be an improvement in the performance of a language processing task\"\"\"\n",
        "SLP_chapter3_3 = \"\"\"An important way to visualize the type of knowledge in a language model is to sample from it which means choosing random points according to their probability.\"\"\"\n",
        "SLP_chapter3_4 = \"\"\"The n-gram model is dependent on its training corpus. We can try to ensure accuracy by keeping texts within the same genre as well as dialect/variety. Another problem that can \n",
        "arise is teh problem of words we have never seen before. The percentage of words that we've never seen before that appear in a test set is known as the OOV rate. We can address this by choosing a \n",
        "vocabulary list in advance, converting any word that is not known into an unknown word token, and estimating the probabilities for unknowns just like any other word.\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"Smoothing helps us to address words that are in our vocabulary but are being seen in our test set in a new context. In order to prevent our model from giving a 0, we can use \n",
        "smoothing.\n",
        "\n",
        "Laplace Smoothing: this algorithm just adds 1 to all the n-gram counts. A similar version is called add-$k$ smoothing where instead of adding 1 we add some fractional constant $k$ to the counts \n",
        "of every word. \n",
        "\n",
        "Another problem we can encounter if we are trying to compute some probability but only have part of it. Sometimes we can use less context to generalize more for contexts that our current model\n",
        "does not know that much about. If an n-gram we need has a count of 0, we would back down to the smaller n-gram model until it works.\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"Massive language models make many of the techniques mentioned here hard to implement. We can sometimes use bloom filters to build approximations as well as an algorithm called \n",
        "stupid backoff which gives up entirely on making the model a true probability distribution.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "Posterior probability: $P(Q|E_1 = e_1, \\ldots, E_k = e_k)$ also known as conditional probability\n",
        "\n",
        "Most Likely Explanation: argmax$P(Q = q|E_1 = e_1, \\ldots)$\n",
        "Laplace often performs poorly for conditional probabilities when the size of the random variables is quite large. We can use linear interpolation to fix this which is defined as follows: \n",
        "$$P(X|Y) = \\alpha \\hat{P}(X|Y) + (1 - \\alpha)\\hat{P}(X)$$\n",
        "This ensures that the estimate of $P(X|Y)$ isn't too different from $P(X)$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"decision theory\" : \"preferences as utilites and probabilites within rational decisions\",\n",
        "\"Product\" : \"$P(a \\land b) = P(a|b)P(b)\",\n",
        "\"Bernoulli distribution\" : \"when boolean variables are in the range of $\\{0, 1\\}\",\n",
        "\"probability density function\" : \"for continuous variables where each RV takes on a value as parameterized function\",\n",
        "\"inclusion exclusion principle\" : \"$P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\",\n",
        "\"marginalization\" : \"sum up the probabilites of each possible value thereby removing them from the equation\",\n",
        "\"conditioning\" : \"$P(Y) = \\sum_Z P(Y|Z)P(Z)$\",\n",
        "\"normilization\" : \"all probabilites add up to 1\",\n",
        "\"conditional independence\" : \"$P(X, Y|Z) = P(X|Z)P(Y|Z)$\",\n",
        "\"language models\" : \"assign probabilites to sequences of words\",\n",
        "\"n-gram\" : \"a sequence of n words\",\n",
        "\"Markov assumption\" : \"assume that the probability of a word depends only on the previous word\",\n",
        "\"relative frequency\" : \"dividing the observed frequency of a particular sequence by the observed frequency of a prefix \",\n",
        "\"extrinsic evaluation\" : \"embed the model in an application and see how much the application improves; very expensive\",\n",
        "\"intrinsic evaluation\" : \"measures the quality of a language model independent of an application\",\n",
        "\"perplexity\" : \"the inverse probability of the test set normalized by the number of words\",\n",
        "\"sparsity\" : \"corpus is limited so some good word sequences may be missing which means they will have probability of 0\",\n",
        "\"backoff\" : \"use trigram, otherwise bigram, otherwise unigram\",\n",
        "\"interpolation\" : \"mixing probability estimates for trigram, bigram, and unigram\",\n",
        "\"Katz backoff\" : \"backoff with discounting which saves probability mass for lower order n-grams\",\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 68,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "4fdba22e-1975-4df0-bcfc-2e257d6bae8b"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 10: Probabilies and Language Models\n",
              "## AIMA Chapter 12.1 Acting under Uncertainty\n",
              "Agents have to be able to handle uncertainty. So far we know they can do so by keeping track of a belief state which is a represetation of all the possible world states that\n",
              "the agent might be in. It then generates a contigency plan to handle all possible outcomes. However, this method has drawbacks because it requires so much storage of every possible belief.\n",
              "Generally the rational decision depends on the relative importance of various goals and the likelihood that they can be achieved. Probability gives us a way to solve the qualification problem \n",
              "upon which even if we don't know for sure we can make a good guess based on data. \n",
              "\n",
              "To utilize the idea of probability, an agent must have preferences among the different possible outcomes. Utility theory can be used to represent this. \n",
              "\n",
              "## AIMA Chapter 12.2 Basic Probability Notation\n",
              "See notation in module definitions \n",
              "\n",
              "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
              "Probabilistic interference refers to the way we can compute conditional probabilites given observed evidence. We use a full joint distribution as the knowledge base from which \n",
              "we can find the answer to all our queries.\n",
              "\n",
              "## AIMA Chapter 12.4 Independence\n",
              "Independence refers to the idea that $P(a|b) = P(a)$ or $P(a \\land b) = P(a)P(b)$. They allow us to dramtically refuxe the size of the full joint distribution.\n",
              "\n",
              "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
              " Bayes rule refers to the following equation: \n",
              "$$P(b|a) = \frac{P(a|b)P(b)}{P(a)}$$\n",
              "\n",
              "We use Bayes rules to compute the probabily of a fourth value if we have three numbers. It allows us to perceive as evidence the effect of some unknown clause: the probability of a cause given an effect\n",
              "This is the diagnostic direction versus the probability of an effect given a cause is the causal direction. \n",
              "\n",
              "\n",
              "## AIMA Chapter 12.6 Naive Bayes Models\n",
              "A commonly occurring pattern is a single cause directly influencing a number of effects all of which are conditionally independent given the cause. This probability distribution is known \n",
              "as a naive Bayes model. The tuntime of calculating this probability is linear to the number of observed effects.\n",
              "\n",
              "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.1 N-Grams\n",
              "In order to compute the probabilites of entire sequences we need to use the chain rule of probability which is as follows \n",
              "$$P(X_1 \\ldots X_n) = \\Pi_{k = 1}^{n}P(X_k|X_{1:k-1})$$\n",
              "\n",
              "However this is a challenging calculation to make with the n-gram model. We can instead approximate the history of a word by just the last few words rather than looking over its entire history. Note \n",
              "that with language model probabilities we use log probabilities to account for potential underflow of multiplying small numbers together.\n",
              "\n",
              "## SLP Chapter 3.2 Evaluating Language Models\n",
              "In order to use intrinsic evaluation on our language models we need to have a training set which sets up the probabilities of our n-gram model and then a test set which is some\n",
              "set of unseen data upon which to test the performance of our n-gram. To fit the test set means that the model more accurately predicts the test set. We use perplexity as the metric which is also \n",
              "known as the weighted average branching factor of a language. The branching factor is the number of words possible that could follow some word. Note that an intrinsic improvement in perplexity \n",
              "does not necessary mean there will be an improvement in the performance of a language processing task\n",
              "\n",
              "## SLP Chapter 3.3 Sampling sentences from a language model\n",
              "An important way to visualize the type of knowledge in a language model is to sample from it which means choosing random points according to their probability.\n",
              "\n",
              "## SLP Chapter 3.4 Generalization and Zeros\n",
              "The n-gram model is dependent on its training corpus. We can try to ensure accuracy by keeping texts within the same genre as well as dialect/variety. Another problem that can \n",
              "arise is teh problem of words we have never seen before. The percentage of words that we've never seen before that appear in a test set is known as the OOV rate. We can address this by choosing a \n",
              "vocabulary list in advance, converting any word that is not known into an unknown word token, and estimating the probabilities for unknowns just like any other word.\n",
              "\n",
              "## SLP Chapter 3.5 Smoothing\n",
              "Smoothing helps us to address words that are in our vocabulary but are being seen in our test set in a new context. In order to prevent our model from giving a 0, we can use \n",
              "smoothing.\n",
              "\n",
              "Laplace Smoothing: this algorithm just adds 1 to all the n-gram counts. A similar version is called add-$k$ smoothing where instead of adding 1 we add some fractional constant $k$ to the counts \n",
              "of every word. \n",
              "\n",
              "Another problem we can encounter if we are trying to compute some probability but only have part of it. Sometimes we can use less context to generalize more for contexts that our current model\n",
              "does not know that much about. If an n-gram we need has a count of 0, we would back down to the smaller n-gram model until it works.\n",
              "\n",
              "\n",
              "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
              "Massive language models make many of the techniques mentioned here hard to implement. We can sometimes use bloom filters to build approximations as well as an algorithm called \n",
              "stupid backoff which gives up entirely on making the model a true probability distribution.\n",
              "\n",
              "## Module 10 Lecture Notes\n",
              "\n",
              "Posterior probability: $P(Q|E_1 = e_1, \\ldots, E_k = e_k)$ also known as conditional probability\n",
              "\n",
              "Most Likely Explanation: argmax$P(Q = q|E_1 = e_1, \\ldots)$\n",
              "Laplace often performs poorly for conditional probabilities when the size of the random variables is quite large. We can use linear interpolation to fix this which is defined as follows: \n",
              "$$P(X|Y) = \u0007lpha \\hat{P}(X|Y) + (1 - \u0007lpha)\\hat{P}(X)$$\n",
              "This ensures that the estimate of $P(X|Y)$ isn't too different from $P(X)$\n",
              "\n",
              "\n",
              "## Module 10 Definitions\n",
              "* **Decision theory** - preferences as utilites and probabilites within rational decisions\n",
              "* **Product** - $P(a \\land b) = P(a|b)P(b)\n",
              "* **Bernoulli distribution** - when boolean variables are in the range of $\\{0, 1\\}\n",
              "* **Probability density function** - for continuous variables where each RV takes on a value as parameterized function\n",
              "* **Inclusion exclusion principle** - $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n",
              "* **Marginalization** - sum up the probabilites of each possible value thereby removing them from the equation\n",
              "* **Conditioning** - $P(Y) = \\sum_Z P(Y|Z)P(Z)$\n",
              "* **Normilization** - all probabilites add up to 1\n",
              "* **Conditional independence** - $P(X, Y|Z) = P(X|Z)P(Y|Z)$\n",
              "* **Language models** - assign probabilites to sequences of words\n",
              "* **N-gram** - a sequence of n words\n",
              "* **Markov assumption** - assume that the probability of a word depends only on the previous word\n",
              "* **Relative frequency** - dividing the observed frequency of a particular sequence by the observed frequency of a prefix \n",
              "* **Extrinsic evaluation** - embed the model in an application and see how much the application improves; very expensive\n",
              "* **Intrinsic evaluation** - measures the quality of a language model independent of an application\n",
              "* **Perplexity** - the inverse probability of the test set normalized by the number of words\n",
              "* **Sparsity** - corpus is limited so some good word sequences may be missing which means they will have probability of 0\n",
              "* **Backoff** - use trigram, otherwise bigram, otherwise unigram\n",
              "* **Interpolation** - mixing probability estimates for trigram, bigram, and unigram\n",
              "* **Katz backoff** - backoff with discounting which saves probability mass for lower order n-grams\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 69,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"We know that a full joint probability can answer many questions but it can become too large as we introduce more variables. Since we know that independence and conditional \n",
        "independence can reduce the number of variables we come up with the idea of a Bayesian network to represent dependencies among variables concisely. A Bayesian network consists of the following:\n",
        "1. each node is a random variable\n",
        "2. directed edge connect pairs of nodes where if an array goes from $X$ to $Y$, $X$ is said to be the parent. It is a DAG\n",
        "3. each node has associated probability information that determines the effect of the parents on the node\n",
        "\n",
        "Typically, we think of the arrows as one node having a direct influence on another node. \n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"The Bayesian network is a correct representation of a domain if each node is conditionally independent of its predecessors given its parents. We can guarantee this by first \n",
        "determining the set of variables and ordering them. For each node, choose a minimal set of parents such that the chain rule holds for the parents. For each parent insert a link from the parent to \n",
        "the current node and then write down the probability in the conditional probability table. The most common question asked of a Bayes net is whereht some set of nodes is conditionally independent\n",
        "of another set given a third set. This is known as whether one set d-separates two other sets. \n",
        "\n",
        "D-separation: \n",
        "1. consider the ancetral subgraph of all the involved nodes which includes all paths connecting them\n",
        "2. replace all directly links by undirected linked\n",
        "3. if some set blocks all paths between the two other sets, then it d-separates them and the conditional independence statement is true. Otherwise the original Bayes net did not require\n",
        "conditional independence \n",
        "\n",
        "Bayes nets can also handle continuous variables. This is often done by the process of discretization which divides up the possible values into a fixed set of intervals. We can also use a nonparametric\n",
        "representation which defines the conditional distribution implicitly with a collection of instances each with specific values. \"\"\"\n",
        "chapter13_3 = \"\"\"We want to be able to compute the posterior probability distribution for a set of query variables given some observed event. Generally to compute this using a Bayes net takes $O(n2^n)$\n",
        "but can be reduced to $O(2^n)$. We can use clustering algorithms to reduce the time to $O(n)$ which is why they are widely used. The basic idea is to join individual noes to form a cluster so that the\n",
        "resulting tree is a polytree.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"Inference refers to the idea of calculating some useful quantity from a joint probability distribution. \n",
        "\n",
        "Inference by enumeration refers to inference which breaks down the problem into evidence variables, query variables, and hidden variables. Note that we have to sum out the hidden variables to get\n",
        "what we want. With Naive Bayes, we only have to specify how each feature depends on a class. We assume all features are independent effects of the label. We train and test our models where training\n",
        "is done by humans to set standards and testing is an unseen data set to judge how well the training went. A problem that we can encounter in the process is overfitting which refers to when the model\n",
        "fits the training data too closely and cannot be generalized to the testing set. To avoid this, we don't want to give any value a 100% probability. \n",
        "\n",
        "Query: $Xi \\perp \\!\\!\\! \\perp Xj |{Xk1 , ..., Xkn }$\n",
        "1) Check all (undirected!) paths between and\n",
        "2) If one or more active, then independence not guaranteed\n",
        "3) Otherwise (i.e. if all paths are inactive), then independence is guaranteed\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"conditional probability table\" : \"local probability information for a Bayesian network; each row contains the conditional probability\",\n",
        "\"conditioning case\" : \"possible combination for parent nodes\",\n",
        "\"context specific independence\" : \"if a variable is conditional independent of some of its parents given certain values of others\",\n",
        "\"hybrid Bayesian network\" : \"contains both discrete and continuous variables\",   \n",
        "\"variable elimination algorithm\" : \"evaluates expressions from right to left, stores values and summations occur only for those that depend on the current variable\",\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 70,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 404
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "bb20c901-7476-453f-ca5d-5634317a6eef"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
              "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
              "We know that a full joint probability can answer many questions but it can become too large as we introduce more variables. Since we know that independence and conditional \n",
              "independence can reduce the number of variables we come up with the idea of a Bayesian network to represent dependencies among variables concisely. A Bayesian network consists of the following:\n",
              "1. each node is a random variable\n",
              "2. directed edge connect pairs of nodes where if an array goes from $X$ to $Y$, $X$ is said to be the parent. It is a DAG\n",
              "3. each node has associated probability information that determines the effect of the parents on the node\n",
              "\n",
              "Typically, we think of the arrows as one node having a direct influence on another node. \n",
              "\n",
              "\n",
              "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
              "The Bayesian network is a correct representation of a domain if each node is conditionally independent of its predecessors given its parents. We can guarantee this by first \n",
              "determining the set of variables and ordering them. For each node, choose a minimal set of parents such that the chain rule holds for the parents. For each parent insert a link from the parent to \n",
              "the current node and then write down the probability in the conditional probability table. The most common question asked of a Bayes net is whereht some set of nodes is conditionally independent\n",
              "of another set given a third set. This is known as whether one set d-separates two other sets. \n",
              "\n",
              "D-separation: \n",
              "1. consider the ancetral subgraph of all the involved nodes which includes all paths connecting them\n",
              "2. replace all directly links by undirected linked\n",
              "3. if some set blocks all paths between the two other sets, then it d-separates them and the conditional independence statement is true. Otherwise the original Bayes net did not require\n",
              "conditional independence \n",
              "\n",
              "Bayes nets can also handle continuous variables. This is often done by the process of discretization which divides up the possible values into a fixed set of intervals. We can also use a nonparametric\n",
              "representation which defines the conditional distribution implicitly with a collection of instances each with specific values. \n",
              "\n",
              "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
              "We want to be able to compute the posterior probability distribution for a set of query variables given some observed event. Generally to compute this using a Bayes net takes $O(n2^n)$\n",
              "but can be reduced to $O(2^n)$. We can use clustering algorithms to reduce the time to $O(n)$ which is why they are widely used. The basic idea is to join individual noes to form a cluster so that the\n",
              "resulting tree is a polytree.\n",
              "\n",
              "## Module 11 Lecture Notes\n",
              "Inference refers to the idea of calculating some useful quantity from a joint probability distribution. \n",
              "\n",
              "Inference by enumeration refers to inference which breaks down the problem into evidence variables, query variables, and hidden variables. Note that we have to sum out the hidden variables to get\n",
              "what we want. With Naive Bayes, we only have to specify how each feature depends on a class. We assume all features are independent effects of the label. We train and test our models where training\n",
              "is done by humans to set standards and testing is an unseen data set to judge how well the training went. A problem that we can encounter in the process is overfitting which refers to when the model\n",
              "fits the training data too closely and cannot be generalized to the testing set. To avoid this, we don't want to give any value a 100% probability. \n",
              "\n",
              "Query: $Xi \\perp \\!\\!\\! \\perp Xj |{Xk1 , ..., Xkn }$\n",
              "1) Check all (undirected!) paths between and\n",
              "2) If one or more active, then independence not guaranteed\n",
              "3) Otherwise (i.e. if all paths are inactive), then independence is guaranteed\n",
              "\n",
              "\n",
              "\n",
              "## Module 11 Definitions\n",
              "* **Conditional probability table** - local probability information for a Bayesian network; each row contains the conditional probability\n",
              "* **Conditioning case** - possible combination for parent nodes\n",
              "* **Context specific independence** - if a variable is conditional independent of some of its parents given certain values of others\n",
              "* **Hybrid bayesian network** - contains both discrete and continuous variables\n",
              "* **Variable elimination algorithm** - evaluates expressions from right to left, stores values and summations occur only for those that depend on the current variable\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 71,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"This chapter explores problems where the input is a factored representation which is a vector of \n",
        "attribute values. When the output is finite, the learning problme is called classification. When it is a number, it\n",
        "is called regression. \"\"\"\n",
        "chapter19_2 = \"\"\" Supervised learning is formally given a training set of example input-output pairs where each pair\n",
        "is created by an unknown function, discover the function $h$ that approximates the true function. We say that $h$ is \n",
        "a model o teh data drawn from the model class $H$ where the output $y_i$ is called the ground truth. In other words \n",
        "the true answer we are asking the model to predict. An $h$ generalizes well if it can accurately predict the output of \n",
        "a test set. Typically there is a bias-variance tradeoff where a choice is made between hypotheses that fit the training\n",
        "data well and ones that may generalize better.\"\"\"\n",
        "chapter19_3 = \"\"\"A decision tree performs a sequence of tests starting at the root and moves until a leaf is reached which\n",
        "represents its decision. Values and outputs that are either true or false are known as Boolean classification. Decision tree\n",
        "learning algorithm chooses the attribute with the highest importance. Importance is measured in terms of entropy or the \n",
        "uncertainty of a random variable. Overfitting becomes more likely as the number of attributes increases. Decision tree pruning \n",
        "can help reduce overfitting where nodes are elimnated that are not clearlyr relevant. Decision trees can address problems as\n",
        "varied as missing data, continuous/multivalued input attributes and contrinuous valued outputs. The problem with decision trees\n",
        "however is that they can have suboptimal accuracy and getting predictions can be epensive if the trees are very deep. They are \n",
        "also unstable in that adding an additional example can change the entire tree. \"\"\"\n",
        "chapter19_4 = \"\"\"In order to select a hypothesis that fits future examples, we need to assume that future examples will be like the\n",
        "past. The stationarity assumption assumes that each example has the same prior probability distribution and is independent of \n",
        "previous examples. In order to test a hypotheis we split our examples into two sets: a training set to produce the hypothesis \n",
        "and a test set to evaulate it. Because we often end up creating multiple hypotheses, we also have hyperparameters which are \n",
        "parameters of the model class and allow us to compare various things within one model. Overfitting starts to occur when the \n",
        "capacity approaches the point of interpolation. Rather than maximize utility directly, machine learning algorithms define a \n",
        "loss function $L(x, y, \\hat{y})$ which is the amount of utility lost by preduction $\\hat{y}$ instead of $y$. A learning problem is \n",
        "realizable if the hypothesis space does truly contain the true function. Hyperparameter tuning often requires hand-tuning which is \n",
        "guessing some parameter value based on past experience, training the model, analyzing results and then using intuition to suggest\n",
        "new parameter values. \"\"\"\n",
        "chapter19_5 = \"\"\"Computational learning theory says that any hypothesis that is seriously wrong will almost certainly be found\n",
        "with high probability because it will eventually make an incorrect prediction. This means that any hypothesis that is consistent\n",
        "with many examples is unlikely to be seriously wrong - this is known as probably approximately correct. Algorithms which return \n",
        "that type of solution are called PAC-learning algorithms.\"\"\"\n",
        "chapter19_6 = \"\"\"For univariate linear regression given by $y = w_1x + w_0$, we want to find the values of the weights $<w_0, w_1>$ \n",
        "that minimize empirical loss. Gradient descent represents a way to minimize loss no matter how complex the loss function. Gradient \n",
        "descent chooses any starting point in the weight space and then computes an estimate o the gradient, moving in the steepest downhill \n",
        "direction until we converge on the minimum loss. We move around the weight space using the step size $\\alpha$ also called learning rate.\n",
        "Stochastic gradient descent randomly selects a small number of training examples at each step and updates accordingly. This is faster. \n",
        "Often selects a minibatch of the examples which reduces computation and is faster. With the perceptron learning rule, if the output is \n",
        "correct, then the weights are not changed. If the correct is 1 but we predicted 0, $w_i$ is increased when the input is positive and \n",
        "decreased when the input is negative. If the correct is 0 but we predicted 1, we do the opposite.\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"The goal of classification is to take an observation, extract some useful features and then classify \n",
        "the observation into one of the set of a discrete classes. Most classification tasks are done by supervised machine learning. \n",
        "Generative classifiers like Naive Bayes build a model of how a class could create some input data. Discriminative classifiers\n",
        "like logistic regression learn what features are more useful to differentiate between different possible classes.  Since Naive\n",
        "Bayes is a probabilistic classifier, for some document, out of all the classes, the classifier will select the class $\\hat{c}$ \n",
        "that has the maximum posterior probability given the document. We can simplify the Bayesian inference formula into \n",
        "$\\hat{c} = $argmax $P(d|c)P(c)$ = argmax $P(c|d)$. We select a probable class by choosing the class with the highest product of \n",
        "two probabilities: the prior probability of the class and the likelihood of the document given the class. This is still too large\n",
        "of a computation because we would have to find the probability of every possible combination of features. To remedy this, we make two \n",
        "assumptions: first that position doesn't matter such that a word will have the same effect on classificiation no matter where in the document\n",
        "it appears. The second is called the naive Bayes assumption which says that all the conditional probabilities given class $c$ are independent. \n",
        "Note that typically these calculations are done in log space to increase speed and avoid underflow. \n",
        "\n",
        "Bayesian inference: $$P(x|y) = \\frac{P(y|x)P(x)}{P(y)}$$\n",
        " \"\"\"\n",
        "slp_chapter4_2 = \"\"\"Often times we can train Naive Bayes classifiers with maximum likelihood estimate of the probability. However,\n",
        "this can lead to problems when there are words which we have never seen before. This can lead to a 0 probability will will mean that the probability\n",
        "of the entire class will be 0 no matter the other evidence. This is remedied with Laplace smoothing. For unknown words or words that are not\n",
        "in our vocabulary, we ignore them by removing them from our document all together. Note that some systems completely ignore stop words as\n",
        "well which are words like \"the\" or \"a\". \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\"One way to increase efficiency is to better understand negation by appending NOT to every word that occurs after a token of \n",
        "logical negation. We also may hvae insufficently labeled training data. We can fix this by using sentiment lexicons which are lists of words\n",
        "that are preannotated with positive or negative sentiment.  \"\"\"\n",
        "slp_chapter4_5 = \"\"\"The most effective naive Bayes features are not words but character n-grams. This allows us to be more efficient by predefining \n",
        "likely sets of words or phrases as features rather than using all words as individual features. \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\"The development test set is used to tune parameters to decide what model is best. The idea of cross-validation allows ut\n",
        "to avoid the problem of having a test set that is not large enough to be representative. With cross-validation, we choose a number $k$ and partiton our\n",
        "data into $k$ disjoint subsets known as folds. We choose one of the folds as a test set and train the classifier on the rest, repeating the process $k$\n",
        "times.  \"\"\"\n",
        "slp_chapter4_9 = \"\"\"In NLP, we use two non-parametric tests called approximate randomization and bootstrap test to determine the significance of our results.\n",
        "The intuition behin dboostrapping is we can create many virtual test sets by repeatedly sample from observed.\"\"\"\n",
        "slp_chapter4_10 = \"\"\"This section addresses the possibility of harms that may arise from training a classifier. One of these is known as representational harms\n",
        "which are harms caused by a system that demeans a social group or reinforces negative stereotypes. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"Perceptrons consist of a set of features with weights where the dot product is summed. If it is above some threshold a specifc output value is returned. Usually perceptrons\n",
        "are more accurate than naive Bayes.\n",
        "\n",
        "Separability: if some parameter gets the training set perfectly correct\n",
        "\n",
        "Mistake bound: max number of mistakes related to the margine or degree of separability\n",
        "\n",
        "Noise: if the data isn't seaprable, weights might clash. We can fix this by averaging weight vectors over time. \n",
        "\n",
        "Margin infused relaxed algorithm (MIRA): choose an update size that fixes the current mistake but minimizes change to weight. Then multiple feature value by $\\Tau$\n",
        "\n",
        "Non-linear separators: original feature space can always be mapped to some higher dimensional feature space where the training set is separable \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"supervised learning\" : \"agent observes input-output pairs to learn a function mapping input to output\",  \n",
        "\"unsupervized learning\" : \"agent learns patterns in input without feedback\",  \n",
        "\"clustering\" : \"detecting useful clusters of input examples\",  \n",
        "\"eninforcement learning\" : \"learns from a series of reinforcements as rewards and punishments\",  \n",
        "\"hypothesis\" : \"the function $h$ that approximates the input-output function\",  \n",
        "\"consistent hypothesis\" : \"$h$ such that for each $x_i$, $h(x_i) = y_i$\",  \n",
        "\"bias\" : \"the tendency of a predictive hypothesis to deviate when averaged over different traningin sets\",  \n",
        "\"underfitting\" : \"when a hypothesis fails to find a pattern in the data\",  \n",
        "\"overfitting\" : \"when the hypothesis too closely models the training data\",  \n",
        "\"decision tree\" : \"representation of a function that maps attribute values to one output value\",  \n",
        "\"learning curve\" : \"evaluates the performance of a learning algorithm\",  \n",
        "\"model selection\" : \"choosing a good hypothesis space\",  \n",
        "\"optimization\" : \"finding best hypothesis in the space\",  \n",
        "\"interpolated\" : \"a model that exactly fits all the training data\",  \n",
        "\"regularization\" : \"penalizing complex hypotheses using a regularization function\",  \n",
        "\"approximately correct\" : \"error($h$) $\\le \\epsilon$\",  \n",
        "\"weight space\" : \"space defined by all possible settings of the weights\",  \n",
        "\"convex\" : \"all loss functions for every linear regression problem; no local minima\",  \n",
        "\"decision boundary\" : \"line or surface that separates two classes\",  \n",
        "\"linear separator\" : \"linear decision boundary that separates the data into classes\",  \n",
        "\"perceptron learning rule\" : \"$w_i = w_i + \\alpha (y - h(x)) \\cdot x_i\", \n",
        "\"binary multinomial naive Bayes\" : \"clip the word counts in each document at 1\",  \n",
        "\"precision\" : \"measures the percentage of items that the system labels properly\",  \n",
        "\"recall\" : \"measures percentage of items that were actually present that were correctly identified\", \n",
        "\"macroaveraging\" : \"performance for each class and then average over classes\",  \n",
        "\"microaveraging\" : \"collect the decisions for all classes and then compute values from them collectively\", \n",
        "\"\" : \"\",  \n",
        "\"\" : \"\", \n",
        "\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 72,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "368045f0-506c-4710-91cc-280458a3b324"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 12: Naive Bayes and Perceptrons\n",
              "## AIMA Chapter 19.1 Forms of Learning\n",
              "This chapter explores problems where the input is a factored representation which is a vector of \n",
              "attribute values. When the output is finite, the learning problme is called classification. When it is a number, it\n",
              "is called regression. \n",
              "\n",
              "## AIMA Chapter 19.2 Supervised Learning\n",
              " Supervised learning is formally given a training set of example input-output pairs where each pair\n",
              "is created by an unknown function, discover the function $h$ that approximates the true function. We say that $h$ is \n",
              "a model o teh data drawn from the model class $H$ where the output $y_i$ is called the ground truth. In other words \n",
              "the true answer we are asking the model to predict. An $h$ generalizes well if it can accurately predict the output of \n",
              "a test set. Typically there is a bias-variance tradeoff where a choice is made between hypotheses that fit the training\n",
              "data well and ones that may generalize better.\n",
              "\n",
              "## AIMA Chapter 19.3 Learning Decision Trees\n",
              "A decision tree performs a sequence of tests starting at the root and moves until a leaf is reached which\n",
              "represents its decision. Values and outputs that are either true or false are known as Boolean classification. Decision tree\n",
              "learning algorithm chooses the attribute with the highest importance. Importance is measured in terms of entropy or the \n",
              "uncertainty of a random variable. Overfitting becomes more likely as the number of attributes increases. Decision tree pruning \n",
              "can help reduce overfitting where nodes are elimnated that are not clearlyr relevant. Decision trees can address problems as\n",
              "varied as missing data, continuous/multivalued input attributes and contrinuous valued outputs. The problem with decision trees\n",
              "however is that they can have suboptimal accuracy and getting predictions can be epensive if the trees are very deep. They are \n",
              "also unstable in that adding an additional example can change the entire tree. \n",
              "\n",
              "## AIMA Chapter 19.4 Model Selection and Optimization\n",
              "In order to select a hypothesis that fits future examples, we need to assume that future examples will be like the\n",
              "past. The stationarity assumption assumes that each example has the same prior probability distribution and is independent of \n",
              "previous examples. In order to test a hypotheis we split our examples into two sets: a training set to produce the hypothesis \n",
              "and a test set to evaulate it. Because we often end up creating multiple hypotheses, we also have hyperparameters which are \n",
              "parameters of the model class and allow us to compare various things within one model. Overfitting starts to occur when the \n",
              "capacity approaches the point of interpolation. Rather than maximize utility directly, machine learning algorithms define a \n",
              "loss function $L(x, y, \\hat{y})$ which is the amount of utility lost by preduction $\\hat{y}$ instead of $y$. A learning problem is \n",
              "realizable if the hypothesis space does truly contain the true function. Hyperparameter tuning often requires hand-tuning which is \n",
              "guessing some parameter value based on past experience, training the model, analyzing results and then using intuition to suggest\n",
              "new parameter values. \n",
              "\n",
              "## AIMA Chapter 19.5 The Theory of Learning\n",
              "Computational learning theory says that any hypothesis that is seriously wrong will almost certainly be found\n",
              "with high probability because it will eventually make an incorrect prediction. This means that any hypothesis that is consistent\n",
              "with many examples is unlikely to be seriously wrong - this is known as probably approximately correct. Algorithms which return \n",
              "that type of solution are called PAC-learning algorithms.\n",
              "\n",
              "## AIMA Chapter 19.6 Linear Regression and Classification\n",
              "For univariate linear regression given by $y = w_1x + w_0$, we want to find the values of the weights $<w_0, w_1>$ \n",
              "that minimize empirical loss. Gradient descent represents a way to minimize loss no matter how complex the loss function. Gradient \n",
              "descent chooses any starting point in the weight space and then computes an estimate o the gradient, moving in the steepest downhill \n",
              "direction until we converge on the minimum loss. We move around the weight space using the step size $\u0007lpha$ also called learning rate.\n",
              "Stochastic gradient descent randomly selects a small number of training examples at each step and updates accordingly. This is faster. \n",
              "Often selects a minibatch of the examples which reduces computation and is faster. With the perceptron learning rule, if the output is \n",
              "correct, then the weights are not changed. If the correct is 1 but we predicted 0, $w_i$ is increased when the input is positive and \n",
              "decreased when the input is negative. If the correct is 0 but we predicted 1, we do the opposite.\n",
              "\n",
              "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
              "The goal of classification is to take an observation, extract some useful features and then classify \n",
              "the observation into one of the set of a discrete classes. Most classification tasks are done by supervised machine learning. \n",
              "Generative classifiers like Naive Bayes build a model of how a class could create some input data. Discriminative classifiers\n",
              "like logistic regression learn what features are more useful to differentiate between different possible classes.  Since Naive\n",
              "Bayes is a probabilistic classifier, for some document, out of all the classes, the classifier will select the class $\\hat{c}$ \n",
              "that has the maximum posterior probability given the document. We can simplify the Bayesian inference formula into \n",
              "$\\hat{c} = $argmax $P(d|c)P(c)$ = argmax $P(c|d)$. We select a probable class by choosing the class with the highest product of \n",
              "two probabilities: the prior probability of the class and the likelihood of the document given the class. This is still too large\n",
              "of a computation because we would have to find the probability of every possible combination of features. To remedy this, we make two \n",
              "assumptions: first that position doesn't matter such that a word will have the same effect on classificiation no matter where in the document\n",
              "it appears. The second is called the naive Bayes assumption which says that all the conditional probabilities given class $c$ are independent. \n",
              "Note that typically these calculations are done in log space to increase speed and avoid underflow. \n",
              "\n",
              "Bayesian inference: $$P(x|y) = \frac{P(y|x)P(x)}{P(y)}$$\n",
              " \n",
              "\n",
              "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
              "Often times we can train Naive Bayes classifiers with maximum likelihood estimate of the probability. However,\n",
              "this can lead to problems when there are words which we have never seen before. This can lead to a 0 probability will will mean that the probability\n",
              "of the entire class will be 0 no matter the other evidence. This is remedied with Laplace smoothing. For unknown words or words that are not\n",
              "in our vocabulary, we ignore them by removing them from our document all together. Note that some systems completely ignore stop words as\n",
              "well which are words like \"the\" or \"a\". \n",
              "\n",
              "## SLP Chapter 4.3 Worked Example\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
              "One way to increase efficiency is to better understand negation by appending NOT to every word that occurs after a token of \n",
              "logical negation. We also may hvae insufficently labeled training data. We can fix this by using sentiment lexicons which are lists of words\n",
              "that are preannotated with positive or negative sentiment.  \n",
              "\n",
              "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
              "The most effective naive Bayes features are not words but character n-grams. This allows us to be more efficient by predefining \n",
              "likely sets of words or phrases as features rather than using all words as individual features. \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",
              "The development test set is used to tune parameters to decide what model is best. The idea of cross-validation allows ut\n",
              "to avoid the problem of having a test set that is not large enough to be representative. With cross-validation, we choose a number $k$ and partiton our\n",
              "data into $k$ disjoint subsets known as folds. We choose one of the folds as a test set and train the classifier on the rest, repeating the process $k$\n",
              "times.  \n",
              "\n",
              "## SLP Chapter 4.9 Statistical Significance Testing\n",
              "In NLP, we use two non-parametric tests called approximate randomization and bootstrap test to determine the significance of our results.\n",
              "The intuition behin dboostrapping is we can create many virtual test sets by repeatedly sample from observed.\n",
              "\n",
              "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
              "This section addresses the possibility of harms that may arise from training a classifier. One of these is known as representational harms\n",
              "which are harms caused by a system that demeans a social group or reinforces negative stereotypes. \n",
              "\n",
              "## Module 12 Lecture Notes\n",
              "Perceptrons consist of a set of features with weights where the dot product is summed. If it is above some threshold a specifc output value is returned. Usually perceptrons\n",
              "are more accurate than naive Bayes.\n",
              "\n",
              "Separability: if some parameter gets the training set perfectly correct\n",
              "\n",
              "Mistake bound: max number of mistakes related to the margine or degree of separability\n",
              "\n",
              "Noise: if the data isn't seaprable, weights might clash. We can fix this by averaging weight vectors over time. \n",
              "\n",
              "Margin infused relaxed algorithm (MIRA): choose an update size that fixes the current mistake but minimizes change to weight. Then multiple feature value by $\\Tau$\n",
              "\n",
              "Non-linear separators: original feature space can always be mapped to some higher dimensional feature space where the training set is separable \n",
              "\n",
              "\n",
              "## Module 12 Definitions\n",
              "* **Supervised learning** - agent observes input-output pairs to learn a function mapping input to output\n",
              "* **Unsupervized learning** - agent learns patterns in input without feedback\n",
              "* **Clustering** - detecting useful clusters of input examples\n",
              "* **Eninforcement learning** - learns from a series of reinforcements as rewards and punishments\n",
              "* **Hypothesis** - the function $h$ that approximates the input-output function\n",
              "* **Consistent hypothesis** - $h$ such that for each $x_i$, $h(x_i) = y_i$\n",
              "* **Bias** - the tendency of a predictive hypothesis to deviate when averaged over different traningin sets\n",
              "* **Underfitting** - when a hypothesis fails to find a pattern in the data\n",
              "* **Overfitting** - when the hypothesis too closely models the training data\n",
              "* **Decision tree** - representation of a function that maps attribute values to one output value\n",
              "* **Learning curve** - evaluates the performance of a learning algorithm\n",
              "* **Model selection** - choosing a good hypothesis space\n",
              "* **Optimization** - finding best hypothesis in the space\n",
              "* **Interpolated** - a model that exactly fits all the training data\n",
              "* **Regularization** - penalizing complex hypotheses using a regularization function\n",
              "* **Approximately correct** - error($h$) $\\le \\epsilon$\n",
              "* **Weight space** - space defined by all possible settings of the weights\n",
              "* **Convex** - all loss functions for every linear regression problem; no local minima\n",
              "* **Decision boundary** - line or surface that separates two classes\n",
              "* **Linear separator** - linear decision boundary that separates the data into classes\n",
              "* **Perceptron learning rule** - $w_i = w_i + \u0007lpha (y - h(x)) \\cdot x_i\n",
              "* **Binary multinomial naive bayes** - clip the word counts in each document at 1\n",
              "* **Precision** - measures the percentage of items that the system labels properly\n",
              "* **Recall** - measures percentage of items that were actually present that were correctly identified\n",
              "* **Macroaveraging** - performance for each class and then average over classes\n",
              "* **Microaveraging** - collect the decisions for all classes and then compute values from them collectively\n",
              "* **** - \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 The Theory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 Linear Regression and Classification\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 73,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"A feature representation of the input: this\n",
        "will be a vector of features, A classification function that computes ˆy, the estimated class, via p(y|x) often using sigmoid\n",
        "or softmax, An objective function for learning, usually involving minimizing error on\n",
        "training examples (cross-entropy loss function) and An algorithm for optimizing the objective function (stochastic gradient descent algorithm).\n",
        "Logistic regression has two phases: training and test. It is represented by $z = w \\cdot x + b$ where $b$ is the bias term. The sigmoid\n",
        "function maps values between 0 and 1 where outlier values get pushed to 0 or 1. $z$ is fed into this function. Sigmoid is differentiable.\"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\"Cross Entropy Loss: \n",
        "$$L_{CE}(\\hat{y}, y) = −log p(y|x) = −[y log \\hat{y}+ (1−y)log(1−\\hat{y})]$$\n",
        "We can replace $\\hat{y}$ with $\\sigma(w \\cdot x + b)$. A perfect classifier would assign probability 1 to the correct outcome (y=1 or y=0) and\n",
        "probability 0 to the incorrect outcome. That means the higher $\\hat{y}$ (the closer it is\n",
        "to 1), the better the classifier; the lower $\\hat{y}$ is (the closer it is to 0), the worse the\n",
        "classifier.\"\"\"\n",
        "slp_chapter5_4 = \"\"\" The goal of gradient descent is to minimize the loss function defined above. This is a method to find the minimum in a functin\n",
        "by figuring out in which direction the function's slope is rising the most steeply and going the opposite direction. For logistic \n",
        "regressoin, the loss function is always convex so we are guaranteeds to find the minimum. The learning rate is a hyperparamter where if it is\n",
        "too high, we will overshoot the minimum and if it is too low, the learner will take too long to get to the minimum.\n",
        " \"\"\"\n",
        "slp_chapter5_5 = \"\"\"Regularization is used to penalize large weights. L2 regularization is quadatic and  L1 is linear function of the weight values \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Multinomial logistic regression is used when we have more than two classes. This uses a generalization of the sigmoid function called\n",
        "the softmax function.  The softmax function takes a vector of arbitrary values and maps them to a probability distribution, with each value in the range (0,1), \n",
        "and all the values summing to 1. The loss function is generalized for multinomial as a sum.\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Deep learning is called deep learning because there are often many layers of nets. a neural unit takes a weighted sum of its inputs, and adds\n",
        "a bias term. Neural networks apply a non-linear function to z\"\"\"\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 = \"\"\" Mini batch training is a compromise between stochastic gradient descent with single random example \n",
        "and batch training such that efficiency is preserved and resources are maximized. \n",
        "\n",
        "Neural networks have 3 non-linear functions: sigmoid function, tanh function, and rectified linear unit (ReLU). In a feed forward network, no output is passed back; they \n",
        "only move into unites in the next higher layer. The goal is to learn the best parameters to make predictions as close as possible to the gold standard. A loss function as well \n",
        "as optimization algorithm are used but we need an additional concept called error propogation which allows us to properly compute loss among all the layers. \n",
        "\n",
        "Backward differentiation: depends on notion of computation graphs which represent the process of computing mathematical expressions. Each operation is a separate node in the\n",
        "graph. Forward pass goes from left to right and is just carrying out the operations. Computing the derivative of the loss function takes place through backward pass\n",
        "where the derivative of the loss function with respect to the various individual variables is found. This gives us how much a smal change in a variable affects the final loss. \n",
        "We compute the derivates from right to left and multiply partial derivates until we get the final derivative we need. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"learning rate\" : \"given by $\\eta$\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 74,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "0f2b5c93-aa8c-423d-df56-f6e338176ded"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 13: Neural Networks\n",
              "## SLP Chapter 5.1 Classification: the sigmoid\n",
              "A feature representation of the input: this\n",
              "will be a vector of features, A classification function that computes ˆy, the estimated class, via p(y|x) often using sigmoid\n",
              "or softmax, An objective function for learning, usually involving minimizing error on\n",
              "training examples (cross-entropy loss function) and An algorithm for optimizing the objective function (stochastic gradient descent algorithm).\n",
              "Logistic regression has two phases: training and test. It is represented by $z = w \\cdot x + b$ where $b$ is the bias term. The sigmoid\n",
              "function maps values between 0 and 1 where outlier values get pushed to 0 or 1. $z$ is fed into this function. Sigmoid is differentiable.\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",
              "Cross Entropy Loss: \n",
              "$$L_{CE}(\\hat{y}, y) = −log p(y|x) = −[y log \\hat{y}+ (1−y)log(1−\\hat{y})]$$\n",
              "We can replace $\\hat{y}$ with $\\sigma(w \\cdot x + b)$. A perfect classifier would assign probability 1 to the correct outcome (y=1 or y=0) and\n",
              "probability 0 to the incorrect outcome. That means the higher $\\hat{y}$ (the closer it is\n",
              "to 1), the better the classifier; the lower $\\hat{y}$ is (the closer it is to 0), the worse the\n",
              "classifier.\n",
              "\n",
              "## SLP Chapter 5.4 Gradient Descent\n",
              " The goal of gradient descent is to minimize the loss function defined above. This is a method to find the minimum in a functin\n",
              "by figuring out in which direction the function's slope is rising the most steeply and going the opposite direction. For logistic \n",
              "regressoin, the loss function is always convex so we are guaranteeds to find the minimum. The learning rate is a hyperparamter where if it is\n",
              "too high, we will overshoot the minimum and if it is too low, the learner will take too long to get to the minimum.\n",
              " \n",
              "\n",
              "## SLP Chapter 5.5 Regularization\n",
              "Regularization is used to penalize large weights. L2 regularization is quadatic and  L1 is linear function of the weight values \n",
              "\n",
              "## SLP Chapter 5.6 Multinomial logistic regression\n",
              " Multinomial logistic regression is used when we have more than two classes. This uses a generalization of the sigmoid function called\n",
              "the softmax function.  The softmax function takes a vector of arbitrary values and maps them to a probability distribution, with each value in the range (0,1), \n",
              "and all the values summing to 1. The loss function is generalized for multinomial as a sum.\n",
              "\n",
              "## SLP Chapter 7.1 Units\n",
              " Deep learning is called deep learning because there are often many layers of nets. a neural unit takes a weighted sum of its inputs, and adds\n",
              "a bias term. Neural networks apply a non-linear function to z\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",
              " Mini batch training is a compromise between stochastic gradient descent with single random example \n",
              "and batch training such that efficiency is preserved and resources are maximized. \n",
              "\n",
              "Neural networks have 3 non-linear functions: sigmoid function, tanh function, and rectified linear unit (ReLU). In a feed forward network, no output is passed back; they \n",
              "only move into unites in the next higher layer. The goal is to learn the best parameters to make predictions as close as possible to the gold standard. A loss function as well \n",
              "as optimization algorithm are used but we need an additional concept called error propogation which allows us to properly compute loss among all the layers. \n",
              "\n",
              "Backward differentiation: depends on notion of computation graphs which represent the process of computing mathematical expressions. Each operation is a separate node in the\n",
              "graph. Forward pass goes from left to right and is just carrying out the operations. Computing the derivative of the loss function takes place through backward pass\n",
              "where the derivative of the loss function with respect to the various individual variables is found. This gives us how much a smal change in a variable affects the final loss. \n",
              "We compute the derivates from right to left and multiply partial derivates until we get the final derivative we need. \n",
              "\n",
              "\n",
              "## Module 13 Definitions\n",
              "* **Learning rate** - given by $\\eta$\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 75,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" We use perplexity to measure the quality of a language model \"\"\"\n",
        "slp_chapter9_2 = \"\"\" A recurrent neural network (RNN) is any network that contains a cycle within its\n",
        "network connections, meaning that the value of some unit is dependent on its own earlier outputs as an input. Note that feed \n",
        "forward networks do not have cycles. Forward inference however is nearly identical. \n",
        "\"\"\"\n",
        "slp_chapter9_3 = \"\"\"RNN language models  process the input sequence one word at\n",
        "a time, attempting to predict the next word from the current word and the previous\n",
        "hidden state. Unlike n-grams, they don't have to worry about the limited context problem. This means that the loss function is calculated\n",
        "slightly differently as follows for time $t$: $L_{CE}(\\hat{y}_t,y_t) = −log\\hat{y}_t[w_{t+1}]$  \"\"\"\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 = \"\"\" In the tf-idf model, the meaning of a word is defined by a simple function\n",
        "of the counts of nearby words. There is the word2vec model family for constructing short, dense vectors that have useful semantic properties. \n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Cosine is the standard way to use embeddings to compute semantic similarity. It is based on the dot product.\"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" \n",
        "Skip-gram/Word2Vec:\n",
        "1. Treat the target word and a neighboring context word as positive examples.\n",
        "2. Randomly sample other words in the lexicon to get negative samples.\n",
        "3. Use logistic regression to train a classifier to distinguish those two cases\n",
        "4. Use the learned weights as the embeddings. \n",
        "\n",
        "Skipgram with negative sampling creates k negative samples for each training instance, each consisting of the\n",
        "target word plus a noise word which is a random word from the lexicon, constrained not to be the target word w.\n",
        "\n",
        "\"\"\"\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 = \"\"\" TF-IDF = term frequency (how often the word occurred) * inverse document frequency (1 over the number of documents the word occured in)\n",
        "\n",
        "Context windows: given a window of about +/- two words to account for long distance dependencies\n",
        "\n",
        "Neural Language models > n-gram LMs:\n",
        "1. They don’t need smoothing\n",
        "2. They can handle much longer histories.\n",
        "3. They can generalize over contexts of similar words.\n",
        "4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs\n",
        "But they take longer to train than n-gram models.\n",
        "\n",
        "Neural LMs contain a k-gram of words as input, a probability distribution over the next work as output. The $k$ context words\n",
        "are treated as a word window where each word is associated with an embedding vector. The inpuyt is fed into a neural network with 1+ hidden\n",
        "layers. The advantages to this process include better results, larger orders of $n$ and they are more generalizable.\n",
        "\n",
        "In a term-document matrix, if two documents have similar words, the column vectors would be similar as well\n",
        "In a term-document matrix, what does a cell represent, a cell represents how often a word occurs. \n",
        "Each column represents a document and each row represents a term. The length of the document vectors is the size of the vocabulary. We \n",
        "can measure similarity of two documents by comparing their column vectors\n",
        "\n",
        "Short vectors may be easier to use as features in machine learning (fewer weights to tune) but dense vectors may generalize better than storing explicit counts\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"embeddings\" : \"vectors for representing words\", \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 76,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 930
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "02418688-7f1b-4a12-ac5e-d695d2403e0f"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 14: Natural Language Processing\n",
              "## SLP Chapter 9.1 Language Models Revisited\n",
              " We use perplexity to measure the quality of a language model \n",
              "\n",
              "## SLP Chapter 9.2 Recurrent Neural Networks\n",
              " A recurrent neural network (RNN) is any network that contains a cycle within its\n",
              "network connections, meaning that the value of some unit is dependent on its own earlier outputs as an input. Note that feed \n",
              "forward networks do not have cycles. Forward inference however is nearly identical. \n",
              "\n",
              "\n",
              "## SLP Chapter 9.3 RNNs as Language Models\n",
              "RNN language models  process the input sequence one word at\n",
              "a time, attempting to predict the next word from the current word and the previous\n",
              "hidden state. Unlike n-grams, they don't have to worry about the limited context problem. This means that the loss function is calculated\n",
              "slightly differently as follows for time $t$: $L_{CE}(\\hat{y}_t,y_t) = −log\\hat{y}_t[w_{t+1}]$  \n",
              "\n",
              "## SLP Chapter 6.1 Lexical Semantics\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.2 Vector Semantics\n",
              " In the tf-idf model, the meaning of a word is defined by a simple function\n",
              "of the counts of nearby words. There is the word2vec model family for constructing short, dense vectors that have useful semantic properties. \n",
              "\n",
              " \n",
              "\n",
              "## SLP Chapter 6.3 Words and Vectors\n",
              " Cosine is the standard way to use embeddings to compute semantic similarity. It is based on the dot product.\n",
              "\n",
              "## SLP Chapter 6.4 Cosine for measuring similarity\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.8 Word2vec\n",
              " \n",
              "Skip-gram/Word2Vec:\n",
              "1. Treat the target word and a neighboring context word as positive examples.\n",
              "2. Randomly sample other words in the lexicon to get negative samples.\n",
              "3. Use logistic regression to train a classifier to distinguish those two cases\n",
              "4. Use the learned weights as the embeddings. \n",
              "\n",
              "Skipgram with negative sampling creates k negative samples for each training instance, each consisting of the\n",
              "target word plus a noise word which is a random word from the lexicon, constrained not to be the target word w.\n",
              "\n",
              "\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 13 Lecture Notes\n",
              " Mini batch training is a compromise between stochastic gradient descent with single random example \n",
              "and batch training such that efficiency is preserved and resources are maximized. \n",
              "\n",
              "Neural networks have 3 non-linear functions: sigmoid function, tanh function, and rectified linear unit (ReLU). In a feed forward network, no output is passed back; they \n",
              "only move into unites in the next higher layer. The goal is to learn the best parameters to make predictions as close as possible to the gold standard. A loss function as well \n",
              "as optimization algorithm are used but we need an additional concept called error propogation which allows us to properly compute loss among all the layers. \n",
              "\n",
              "Backward differentiation: depends on notion of computation graphs which represent the process of computing mathematical expressions. Each operation is a separate node in the\n",
              "graph. Forward pass goes from left to right and is just carrying out the operations. Computing the derivative of the loss function takes place through backward pass\n",
              "where the derivative of the loss function with respect to the various individual variables is found. This gives us how much a smal change in a variable affects the final loss. \n",
              "We compute the derivates from right to left and multiply partial derivates until we get the final derivative we need. \n",
              "\n",
              "\n",
              "## Module 14 Definitions\n",
              "* **Embeddings** - vectors for representing words\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "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 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 77,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "6743ab4e-1890-4e40-9844-ed00f9cf2612"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 8: Markov Decision Processes\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Decision theory refers to the idea of choosing among actions based on how desirable their\n",
              "immediate outcomes are. An agent's preferences are represented by a utility function $U(s)$. The expected utility of an action is\n",
              "the average utiltiy of the outcomes multiplied by the probability that particular outcome occurs. MEU formalizes that an inteeligent agent\n",
              "should do the right thing but does not acutllay execute that.  $P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Think of the set of outcomes of an action as a lottery in which each action represents a ticket. Each lottery contains a \n",
              "set of possible outcomes all assigned specific probabilities. Each outcome is either a state or another lottery. With utility theory, the goal \n",
              "is to understand preferences with regards to complex lotteries and their relationships to the states within them. An agent that violates the \n",
              "axioms of utility theory will exhibit irrational behavior. We can represent a set of outcomes for each action as a lottery where each action is a\n",
              "ticket. A lottery L with outcomes $S_1, S_2, \\ldots, S_n$ with occurrence probabilites of $p_1, \\ldots, p_n$ looks like \n",
              "$$L = [p_1, S_1; p_2, S_2; \\ldots p_n, S_n]$$\n",
              "\n",
              "The utility of one action is greater than another only if the former is preferred to the latter. Similarly, the utilites are only equal if the agent\n",
              "is indifferent between the two. Note that just because a utility function exists, the agent is not necessarily maximizing the utility function\n",
              "on its own. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Utility functions are relevant for mapping the lotteries described above to real numbers. Using a process call preference \n",
              "eliciation, we can help design a system that can make decisions or act on behalf of a human. This process requires us to present choices to the \n",
              "human and decide by observing on the underlying utility function representing that person's preferences. Agents that are risk averse show a curve \n",
              "that for any lottery, the utility of getting the lottery is less than just the expected money of the lottery. On the opposite end are risk seeking.\n",
              "The rational way to choose the best action is usually to maximize the expected utility.\n",
              "\n",
              "\n",
              "## AIMA Chapter 17.1 Sequential Decision Problems\n",
              " Sometimes decision making is stochastic such that when an agent makes a move, there is a probability that it will actually carry out \n",
              "that move as $P(s'|s, a)$. The utility function in this case depends on a sequence of states and actions known as the environment history where at each state\n",
              "the agent recieved some reward $R(s, a, s'). A solution to a problem defined as an MDP must specificy what the agent should for for any state that the agent might \n",
              "possibly reach. With a finite horizon an optimal action in a particular state depends on how much time is left which is called nonstationary policy. When there is no fixed\n",
              "time limit, there is no reason to change your policy in the same state at different times which means that the optimal action depends only on the current state. This is\n",
              "knowned as a stationary policy. The discount factor is close to 0 when rewards in the future are insignificant and close to 1 when the agent is more willing to wait for \n",
              "long term rewards. We use the discount factor to account for the fact that humans perfer near-term rewards more highly than rewards in the future. \n",
              "\n",
              "The expected utility is given by the following function: $E[\\sum_{t = 0} \\gamma ^ t R(S_t, \\pi(S_t), S_{t + 1})$$\n",
              "We want to select the arg max of that equation which becomes $\\pi_s*$. THe utility of some state $s$ is given by the max action of $Q$ over all possible actions for that \n",
              "state. WE can obtain the optimal policy from the Q-function by taking the argmax of $Q(s, a)$ over all actions for state $s$. \n",
              "\n",
              "\n",
              "## AIMA Chapter 17.2 Algorithms for MDPs\n",
              " There are four different algorithms for solving MDPS: value iteration, policy iteration, and linear programming which create solutions offline. MonteCarolo planning \n",
              "is an online approximate algorithm.\n",
              "\n",
              "Value iteration is based significantly on the Bellman equation. If there are $n$ states, then there are $n$ Bellman equations for each state. The goal is to solve these equations \n",
              "to find the utilites. To do so, we try an diterative approach where we start with arbitrary values for the utilites to progressivly until we reach an equilibrium. Note that we are guaranteed \n",
              "to reach equilibrium. THe Bellman equation update is a contractation by a factor of $\\gamma$ on the set of utility vectors.\n",
              "\n",
              "Policy iteration alternates between policy evaluations where it finds the utility of each state is some policy $\\pi_i$ were to be executed and policy improvement\n",
              "which calculates the new MEU policy using a one-step look-ahead. The algorithm stops when policy improvement does not result in an updates to the utilites. It differs from \n",
              "value iteration in that the action is fixed by the policy. \n",
              "\n",
              "A simplified version of expectiminimax is an example of an online approximation algorithm. \n",
              "\n",
              "## Module 8 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 8 Definitions\n",
              "* **Utility function** - represents how desirable a state is\n",
              "* **Expected utility** - average utility value weighted by the probability outcome occurs\n",
              "* **Maximum expected utility** - a rational agent should pick the action that maximizes EU (argmax)\n",
              "* **Orderability** - given two lotteries a rational agent must prefer one or think both are equal, must make a decision\n",
              "* **Transitivity** - if an agent prefers A to B and C to C then it prefers A to C\n",
              "* **Continuity** - if lottery B is between two others, the agent will be indifferent toward getting it or the other two\n",
              "* **Substitutability** - if indifferent between two choices, also indifferent if both are added to another lotter\n",
              "* **Monotonicity** - if outcomes are the same and agent prefers one lottery, it must prefer the one with the higher probability\n",
              "* **Decomposability** - lotteries can be reduced to smaller ones using probability laws\n",
              "* **Value function/ordinal utility function** - in deterministic game play, agent only needs preference ranking on the states invovled\n",
              "* **Preference elicitation** - how we determine what the human's utility function is\n",
              "* **Normalized utilities** - use a scale of 0 and 1 to assign utility to things\n",
              "* **Certainty equivalent** - value an agent accepts instead of a lottery\n",
              "* **Optimizer's curse** - overestimating the expected utility of best choice\n",
              "* **Certainity effect** - people prefer gains that are certain\n",
              "* **Risk neutral** - an agent with a linear utility curve\n",
              "* **Sequential decision problems** - the agent's utility depends on a sequence of actions\n",
              "* **Markovian** - the probability of reach a state from another depends only on the first state and nothing else\n",
              "* **Markov decision process** - fully observable, stochatic environemtn with Markovian transition model and rewards\n",
              "* **Policy** - denoted by $\\pi$ and $\\pi(s)$\n",
              "* **Optimal policy** - returns the highest expect utility given the different possibilities in that environment: $\\pi*$\n",
              "* **Finite horizon** - there is a fixed time $N$ after which the game is over\n",
              "* **Additive discounted rewards** - the utility of a history is the sum of the rewards multiplied by discounter factor\n",
              "* **Discount factor** - $\\gamma$ is a number between 1 and 0 which describes preferences for current rewards over future rewards\n",
              "* **Additive rewards** - when discount factor is exactly 1 where everything is purely additive\n",
              "* **Proper policy** - a policy that is guaranteed to reach a terminal state\n",
              "* **Bellman equation** - utilites to states as teh expected utility of following states are teh solutions\n",
              "* **Action-utility function/q-function** - expected utility of taking a given action in a given state is $Q(s, a)$\n",
              "* **Contraction** - function of one argument that applied to two inputs returns two outputs close together, used in convergence\n",
              "* **Policy loss** - the most an agent can lose by implementing something other than the optimal policy\n",
              "* **Modified policy iteration** - addresses space problem by running simplified value iteration and repeated several times\n",
              "* **Linear programming** - formulating constrained optimization problems\n",
              "\n",
              "\n",
              "# Module 9: Reinforcement Learning\n",
              "## AIMA Chapter 17.3 Bandit Problems\n",
              " In the n-armed bandit problem, the gambler must choose which lever to play: either the one that has given the best payoff so far or an unexplored one. This is an example of \n",
              "the tradeoff between exploitation of the current best option and exploration of any unknown states to potentially discover a better policy in the long-run. There are many iterations of this game. It is often\n",
              "challenging to calculate the best policy so the there is a way to approximate policies such that they are nearly optimal using an uppre confidence bound heuristic. It essentially established a confidence interval\n",
              "for the value of the arm. \n",
              "\n",
              "## AIMA Chapter 22.1 Learning from Rewards\n",
              "Reinforcement learning is different than MDP because the agent is not given the MDP as a problme to solve but rather it already \n",
              "in the MDP. The agent might not know the transition model or the reward function and has to learn it by executing actions. \n",
              "\n",
              "Model-based reinforcement learning uses a transition model of teh environment to understand reward signals and make action decisions. The transition model\n",
              "is learned by observing the effects of the actions. This also is often coupled with learning a utility function $U(s)$. Model-free reinforcement learning consists \n",
              "of two different types. Action-utility learning's most common form is Q-learning where the agent learns a Q-function representing the sum of rewards from state\n",
              "$s$ and onward depending on if some action $a$ is selected. The other type is policy search which learns some policy $\\pi*$; this is also called a reflex agent.\n",
              "\n",
              "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
              " A passive agent is already given a fixed policy $\\pi$ and wants to learn the utility function which is the total expected discounted reward if that policy is executed. This is similar to the\n",
              "policy evaluation task but here the agent does not know the transition model or the reward function. At each point in time, the agent executes a series of trials using the assigned policy and\n",
              "experiences a sequence of transitions until it reaches a terminal state. Direct utility estimation is helpful but ignores the connection between teh Bellman equation and states determined by the utility and reward\n",
              "of successor states.\n",
              "\n",
              "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
              "An active reinforcement agent does not have a fixed policy, rather it decides what actions to take. This agent has to learn a complete transition model not just for one policy but for all possible\n",
              "actions. One way to do this is through a greedy algorithm where the agent finds the first policy that results in a positive reward and sticks with it to the detriment of never finding any possibly larger rewards.\n",
              "Oftentimes this does not result in the convergence toward the optimal policy. The main problem is taht the greedy agent overlooks the information that can be learned at any step. The agent has to make a tradeoff\n",
              "between exploration and exploitation. We can rememdy this with application of a GLIE scheme where each action in a state is tried an unbounded number of times to avoid missing an optimal action. An algorithm operating\n",
              "using maximum-likelihood estimation chooses a policy based solely on the estimated model so it will act like that model is always correct. Instead we should choose a policy that works pretty well for a range of models\n",
              "that are reasonable similar to the real model. There are three ways to do this: \n",
              "\n",
              "Bayesian Reinforcement Learning: assumes there is a prior probability over a set of hypotheses about what the true model is. If an agent decides to stop learning, the optimal policy is the one with currently the highest\n",
              "expected utility. In special cases, the optimal policy can be computer. However, if the agent continues learning, it becomes more more difficult because the agent has to think about the future in terms of its transition \n",
              "model. \n",
              "\n",
              "Second approach: uses robust control theory which allows for a set of possible models $H$ with no probabilites such that the optimal robust policy is the one that gives the best outcome in the worst case over $H$. This \n",
              "similar to minimax. The problem with this however it is that it results in overly conservative behavior. It does not account for risk-reward tradeoffs.\n",
              "\n",
              "The Q-Learning method avoids the need for a model by learning an action-utility function instead of just a utility function: $Q(s, a)$. Each value represents the expected reward if the agent takes that action and continues\n",
              "to act optimally. This allows the agent to just choose the argmax $Q(s, a)$ value without having to look ahead.\n",
              "$$Q(s, a) = Q(s, a) + \u0007lpha[R(s, a, s') + \\gamma max Q(s', a') - Q(s, a)]$$\n",
              "\n",
              "SARSA is a similar algorithm to Q-Learning where the Q-value is updated with the valye of the action $a'$ already taken.\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
              "This focuses on the idea of function approximation as the process of creating an approximation of the true utility function or Q-function. We can do this using features as a weight linear combination. \n",
              "This allows us to learn a subset of values rather than have to look at every single state in the model. However, this is often not sufficient. Thus, a lot of modern machine learning algorithms focus on deep learning or\n",
              "non linear methods.\n",
              "\n",
              "## AIMA Chapter 22.5 Policy Search\n",
              " Policy search is the final type of reinforcement learning. It keeps modifying policy as long as performance continues improving. We optimize this by using gradients which eventualy allow us to converge\n",
              "to a local optimum policy. It is much more challenging to do this when the policy is nondeterministic (ie includes probability of action in state)\n",
              "\n",
              "## Module 9 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 9 Definitions\n",
              "* **Supervised learning** - learning by passively observing input/output pairs provided by external source\n",
              "* **Reinforcement learning** - an agent interacts with the world and occassionally receives rewards depending on how well it's doing\n",
              "* **Passive reinforcement learning** - agent's policy is fixed and agent needs to learn the utilites of state-action pairs\n",
              "* **Active reinforcement learning** - agent also has to figure out what to go through exploration\n",
              "* **N-armed bandit** - has n levers behind each is a fixed/unknown probability of winnings\n",
              "* **Bernoulli bandit** - each arm produces a reward of either 1 or 0 with an unknown probability\n",
              "* **Selection problem** - choosing the best option under some set of constraining conditions\n",
              "* **Dominating policy** - an optimal policy is unaffected by the opportunity cost\n",
              "* **Direct utility estimation** - utility of a state defined as expected total reward where each trial is a sample of possible reward\n",
              "* **Adaptive dynamic programming** - uses dynamic programming to solve the Markov decision process\n",
              "* **Learning rate** - $\u0007lpha\n",
              "* **Temporal difference equation** - update rule using teh difference in utilites between sucessive states\n",
              "* **Glie** - greedy in the limit of infinite exploration\n",
              "* **Aborbing state** - no actions have any effect and no rewards are given\n",
              "* **Off-policy** - Q-Learning; stop using current policy and act according to policy with best actions\n",
              "* **Softmax** - parameter \beta modulates how close the max is to the hard max vs uniform random choice \n",
              "* **Stochastic policy** - representation of a policy that includes the probability of selecting action $a$ in state $s$\n",
              "\n",
              "\n",
              "# Module 10: Probabilies and Language Models\n",
              "## AIMA Chapter 12.1 Acting under Uncertainty\n",
              "Agents have to be able to handle uncertainty. So far we know they can do so by keeping track of a belief state which is a represetation of all the possible world states that\n",
              "the agent might be in. It then generates a contigency plan to handle all possible outcomes. However, this method has drawbacks because it requires so much storage of every possible belief.\n",
              "Generally the rational decision depends on the relative importance of various goals and the likelihood that they can be achieved. Probability gives us a way to solve the qualification problem \n",
              "upon which even if we don't know for sure we can make a good guess based on data. \n",
              "\n",
              "To utilize the idea of probability, an agent must have preferences among the different possible outcomes. Utility theory can be used to represent this. \n",
              "\n",
              "## AIMA Chapter 12.2 Basic Probability Notation\n",
              "See notation in module definitions \n",
              "\n",
              "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
              "Probabilistic interference refers to the way we can compute conditional probabilites given observed evidence. We use a full joint distribution as the knowledge base from which \n",
              "we can find the answer to all our queries.\n",
              "\n",
              "## AIMA Chapter 12.4 Independence\n",
              "Independence refers to the idea that $P(a|b) = P(a)$ or $P(a \\land b) = P(a)P(b)$. They allow us to dramtically refuxe the size of the full joint distribution.\n",
              "\n",
              "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
              " Bayes rule refers to the following equation: \n",
              "$$P(b|a) = \frac{P(a|b)P(b)}{P(a)}$$\n",
              "\n",
              "We use Bayes rules to compute the probabily of a fourth value if we have three numbers. It allows us to perceive as evidence the effect of some unknown clause: the probability of a cause given an effect\n",
              "This is the diagnostic direction versus the probability of an effect given a cause is the causal direction. \n",
              "\n",
              "\n",
              "## AIMA Chapter 12.6 Naive Bayes Models\n",
              "A commonly occurring pattern is a single cause directly influencing a number of effects all of which are conditionally independent given the cause. This probability distribution is known \n",
              "as a naive Bayes model. The tuntime of calculating this probability is linear to the number of observed effects.\n",
              "\n",
              "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.1 N-Grams\n",
              "In order to compute the probabilites of entire sequences we need to use the chain rule of probability which is as follows \n",
              "$$P(X_1 \\ldots X_n) = \\Pi_{k = 1}^{n}P(X_k|X_{1:k-1})$$\n",
              "\n",
              "However this is a challenging calculation to make with the n-gram model. We can instead approximate the history of a word by just the last few words rather than looking over its entire history. Note \n",
              "that with language model probabilities we use log probabilities to account for potential underflow of multiplying small numbers together.\n",
              "\n",
              "## SLP Chapter 3.2 Evaluating Language Models\n",
              "In order to use intrinsic evaluation on our language models we need to have a training set which sets up the probabilities of our n-gram model and then a test set which is some\n",
              "set of unseen data upon which to test the performance of our n-gram. To fit the test set means that the model more accurately predicts the test set. We use perplexity as the metric which is also \n",
              "known as the weighted average branching factor of a language. The branching factor is the number of words possible that could follow some word. Note that an intrinsic improvement in perplexity \n",
              "does not necessary mean there will be an improvement in the performance of a language processing task\n",
              "\n",
              "## SLP Chapter 3.3 Sampling sentences from a language model\n",
              "An important way to visualize the type of knowledge in a language model is to sample from it which means choosing random points according to their probability.\n",
              "\n",
              "## SLP Chapter 3.4 Generalization and Zeros\n",
              "The n-gram model is dependent on its training corpus. We can try to ensure accuracy by keeping texts within the same genre as well as dialect/variety. Another problem that can \n",
              "arise is teh problem of words we have never seen before. The percentage of words that we've never seen before that appear in a test set is known as the OOV rate. We can address this by choosing a \n",
              "vocabulary list in advance, converting any word that is not known into an unknown word token, and estimating the probabilities for unknowns just like any other word.\n",
              "\n",
              "## SLP Chapter 3.5 Smoothing\n",
              "Smoothing helps us to address words that are in our vocabulary but are being seen in our test set in a new context. In order to prevent our model from giving a 0, we can use \n",
              "smoothing.\n",
              "\n",
              "Laplace Smoothing: this algorithm just adds 1 to all the n-gram counts. A similar version is called add-$k$ smoothing where instead of adding 1 we add some fractional constant $k$ to the counts \n",
              "of every word. \n",
              "\n",
              "Another problem we can encounter if we are trying to compute some probability but only have part of it. Sometimes we can use less context to generalize more for contexts that our current model\n",
              "does not know that much about. If an n-gram we need has a count of 0, we would back down to the smaller n-gram model until it works.\n",
              "\n",
              "\n",
              "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
              "Massive language models make many of the techniques mentioned here hard to implement. We can sometimes use bloom filters to build approximations as well as an algorithm called \n",
              "stupid backoff which gives up entirely on making the model a true probability distribution.\n",
              "\n",
              "## Module 10 Lecture Notes\n",
              "\n",
              "Posterior probability: $P(Q|E_1 = e_1, \\ldots, E_k = e_k)$ also known as conditional probability\n",
              "\n",
              "Most Likely Explanation: argmax$P(Q = q|E_1 = e_1, \\ldots)$\n",
              "Laplace often performs poorly for conditional probabilities when the size of the random variables is quite large. We can use linear interpolation to fix this which is defined as follows: \n",
              "$$P(X|Y) = \u0007lpha \\hat{P}(X|Y) + (1 - \u0007lpha)\\hat{P}(X)$$\n",
              "This ensures that the estimate of $P(X|Y)$ isn't too different from $P(X)$\n",
              "\n",
              "\n",
              "## Module 10 Definitions\n",
              "* **Decision theory** - preferences as utilites and probabilites within rational decisions\n",
              "* **Product** - $P(a \\land b) = P(a|b)P(b)\n",
              "* **Bernoulli distribution** - when boolean variables are in the range of $\\{0, 1\\}\n",
              "* **Probability density function** - for continuous variables where each RV takes on a value as parameterized function\n",
              "* **Inclusion exclusion principle** - $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n",
              "* **Marginalization** - sum up the probabilites of each possible value thereby removing them from the equation\n",
              "* **Conditioning** - $P(Y) = \\sum_Z P(Y|Z)P(Z)$\n",
              "* **Normilization** - all probabilites add up to 1\n",
              "* **Conditional independence** - $P(X, Y|Z) = P(X|Z)P(Y|Z)$\n",
              "* **Language models** - assign probabilites to sequences of words\n",
              "* **N-gram** - a sequence of n words\n",
              "* **Markov assumption** - assume that the probability of a word depends only on the previous word\n",
              "* **Relative frequency** - dividing the observed frequency of a particular sequence by the observed frequency of a prefix \n",
              "* **Extrinsic evaluation** - embed the model in an application and see how much the application improves; very expensive\n",
              "* **Intrinsic evaluation** - measures the quality of a language model independent of an application\n",
              "* **Perplexity** - the inverse probability of the test set normalized by the number of words\n",
              "* **Sparsity** - corpus is limited so some good word sequences may be missing which means they will have probability of 0\n",
              "* **Backoff** - use trigram, otherwise bigram, otherwise unigram\n",
              "* **Interpolation** - mixing probability estimates for trigram, bigram, and unigram\n",
              "* **Katz backoff** - backoff with discounting which saves probability mass for lower order n-grams\n",
              "\n",
              "\n",
              "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
              "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
              "We know that a full joint probability can answer many questions but it can become too large as we introduce more variables. Since we know that independence and conditional \n",
              "independence can reduce the number of variables we come up with the idea of a Bayesian network to represent dependencies among variables concisely. A Bayesian network consists of the following:\n",
              "1. each node is a random variable\n",
              "2. directed edge connect pairs of nodes where if an array goes from $X$ to $Y$, $X$ is said to be the parent. It is a DAG\n",
              "3. each node has associated probability information that determines the effect of the parents on the node\n",
              "\n",
              "Typically, we think of the arrows as one node having a direct influence on another node. \n",
              "\n",
              "\n",
              "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
              "The Bayesian network is a correct representation of a domain if each node is conditionally independent of its predecessors given its parents. We can guarantee this by first \n",
              "determining the set of variables and ordering them. For each node, choose a minimal set of parents such that the chain rule holds for the parents. For each parent insert a link from the parent to \n",
              "the current node and then write down the probability in the conditional probability table. The most common question asked of a Bayes net is whereht some set of nodes is conditionally independent\n",
              "of another set given a third set. This is known as whether one set d-separates two other sets. \n",
              "\n",
              "D-separation: \n",
              "1. consider the ancetral subgraph of all the involved nodes which includes all paths connecting them\n",
              "2. replace all directly links by undirected linked\n",
              "3. if some set blocks all paths between the two other sets, then it d-separates them and the conditional independence statement is true. Otherwise the original Bayes net did not require\n",
              "conditional independence \n",
              "\n",
              "Bayes nets can also handle continuous variables. This is often done by the process of discretization which divides up the possible values into a fixed set of intervals. We can also use a nonparametric\n",
              "representation which defines the conditional distribution implicitly with a collection of instances each with specific values. \n",
              "\n",
              "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
              "We want to be able to compute the posterior probability distribution for a set of query variables given some observed event. Generally to compute this using a Bayes net takes $O(n2^n)$\n",
              "but can be reduced to $O(2^n)$. We can use clustering algorithms to reduce the time to $O(n)$ which is why they are widely used. The basic idea is to join individual noes to form a cluster so that the\n",
              "resulting tree is a polytree.\n",
              "\n",
              "## Module 11 Lecture Notes\n",
              "Inference refers to the idea of calculating some useful quantity from a joint probability distribution. \n",
              "\n",
              "Inference by enumeration refers to inference which breaks down the problem into evidence variables, query variables, and hidden variables. Note that we have to sum out the hidden variables to get\n",
              "what we want. With Naive Bayes, we only have to specify how each feature depends on a class. We assume all features are independent effects of the label. We train and test our models where training\n",
              "is done by humans to set standards and testing is an unseen data set to judge how well the training went. A problem that we can encounter in the process is overfitting which refers to when the model\n",
              "fits the training data too closely and cannot be generalized to the testing set. To avoid this, we don't want to give any value a 100% probability. \n",
              "\n",
              "Query: $Xi \\perp \\!\\!\\! \\perp Xj |{Xk1 , ..., Xkn }$\n",
              "1) Check all (undirected!) paths between and\n",
              "2) If one or more active, then independence not guaranteed\n",
              "3) Otherwise (i.e. if all paths are inactive), then independence is guaranteed\n",
              "\n",
              "\n",
              "\n",
              "## Module 11 Definitions\n",
              "* **Conditional probability table** - local probability information for a Bayesian network; each row contains the conditional probability\n",
              "* **Conditioning case** - possible combination for parent nodes\n",
              "* **Context specific independence** - if a variable is conditional independent of some of its parents given certain values of others\n",
              "* **Hybrid bayesian network** - contains both discrete and continuous variables\n",
              "* **Variable elimination algorithm** - evaluates expressions from right to left, stores values and summations occur only for those that depend on the current variable\n",
              "\n",
              "\n",
              "# Module 12: Naive Bayes and Perceptrons\n",
              "## AIMA Chapter 19.1 Forms of Learning\n",
              "This chapter explores problems where the input is a factored representation which is a vector of \n",
              "attribute values. When the output is finite, the learning problme is called classification. When it is a number, it\n",
              "is called regression. \n",
              "\n",
              "## AIMA Chapter 19.2 Supervised Learning\n",
              " Supervised learning is formally given a training set of example input-output pairs where each pair\n",
              "is created by an unknown function, discover the function $h$ that approximates the true function. We say that $h$ is \n",
              "a model o teh data drawn from the model class $H$ where the output $y_i$ is called the ground truth. In other words \n",
              "the true answer we are asking the model to predict. An $h$ generalizes well if it can accurately predict the output of \n",
              "a test set. Typically there is a bias-variance tradeoff where a choice is made between hypotheses that fit the training\n",
              "data well and ones that may generalize better.\n",
              "\n",
              "## AIMA Chapter 19.3 Learning Decision Trees\n",
              "A decision tree performs a sequence of tests starting at the root and moves until a leaf is reached which\n",
              "represents its decision. Values and outputs that are either true or false are known as Boolean classification. Decision tree\n",
              "learning algorithm chooses the attribute with the highest importance. Importance is measured in terms of entropy or the \n",
              "uncertainty of a random variable. Overfitting becomes more likely as the number of attributes increases. Decision tree pruning \n",
              "can help reduce overfitting where nodes are elimnated that are not clearlyr relevant. Decision trees can address problems as\n",
              "varied as missing data, continuous/multivalued input attributes and contrinuous valued outputs. The problem with decision trees\n",
              "however is that they can have suboptimal accuracy and getting predictions can be epensive if the trees are very deep. They are \n",
              "also unstable in that adding an additional example can change the entire tree. \n",
              "\n",
              "## AIMA Chapter 19.4 Model Selection and Optimization\n",
              "In order to select a hypothesis that fits future examples, we need to assume that future examples will be like the\n",
              "past. The stationarity assumption assumes that each example has the same prior probability distribution and is independent of \n",
              "previous examples. In order to test a hypotheis we split our examples into two sets: a training set to produce the hypothesis \n",
              "and a test set to evaulate it. Because we often end up creating multiple hypotheses, we also have hyperparameters which are \n",
              "parameters of the model class and allow us to compare various things within one model. Overfitting starts to occur when the \n",
              "capacity approaches the point of interpolation. Rather than maximize utility directly, machine learning algorithms define a \n",
              "loss function $L(x, y, \\hat{y})$ which is the amount of utility lost by preduction $\\hat{y}$ instead of $y$. A learning problem is \n",
              "realizable if the hypothesis space does truly contain the true function. Hyperparameter tuning often requires hand-tuning which is \n",
              "guessing some parameter value based on past experience, training the model, analyzing results and then using intuition to suggest\n",
              "new parameter values. \n",
              "\n",
              "## AIMA Chapter 19.5 The Theory of Learning\n",
              "Computational learning theory says that any hypothesis that is seriously wrong will almost certainly be found\n",
              "with high probability because it will eventually make an incorrect prediction. This means that any hypothesis that is consistent\n",
              "with many examples is unlikely to be seriously wrong - this is known as probably approximately correct. Algorithms which return \n",
              "that type of solution are called PAC-learning algorithms.\n",
              "\n",
              "## AIMA Chapter 19.6 Linear Regression and Classification\n",
              "For univariate linear regression given by $y = w_1x + w_0$, we want to find the values of the weights $<w_0, w_1>$ \n",
              "that minimize empirical loss. Gradient descent represents a way to minimize loss no matter how complex the loss function. Gradient \n",
              "descent chooses any starting point in the weight space and then computes an estimate o the gradient, moving in the steepest downhill \n",
              "direction until we converge on the minimum loss. We move around the weight space using the step size $\u0007lpha$ also called learning rate.\n",
              "Stochastic gradient descent randomly selects a small number of training examples at each step and updates accordingly. This is faster. \n",
              "Often selects a minibatch of the examples which reduces computation and is faster. With the perceptron learning rule, if the output is \n",
              "correct, then the weights are not changed. If the correct is 1 but we predicted 0, $w_i$ is increased when the input is positive and \n",
              "decreased when the input is negative. If the correct is 0 but we predicted 1, we do the opposite.\n",
              "\n",
              "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
              "The goal of classification is to take an observation, extract some useful features and then classify \n",
              "the observation into one of the set of a discrete classes. Most classification tasks are done by supervised machine learning. \n",
              "Generative classifiers like Naive Bayes build a model of how a class could create some input data. Discriminative classifiers\n",
              "like logistic regression learn what features are more useful to differentiate between different possible classes.  Since Naive\n",
              "Bayes is a probabilistic classifier, for some document, out of all the classes, the classifier will select the class $\\hat{c}$ \n",
              "that has the maximum posterior probability given the document. We can simplify the Bayesian inference formula into \n",
              "$\\hat{c} = $argmax $P(d|c)P(c)$ = argmax $P(c|d)$. We select a probable class by choosing the class with the highest product of \n",
              "two probabilities: the prior probability of the class and the likelihood of the document given the class. This is still too large\n",
              "of a computation because we would have to find the probability of every possible combination of features. To remedy this, we make two \n",
              "assumptions: first that position doesn't matter such that a word will have the same effect on classificiation no matter where in the document\n",
              "it appears. The second is called the naive Bayes assumption which says that all the conditional probabilities given class $c$ are independent. \n",
              "Note that typically these calculations are done in log space to increase speed and avoid underflow. \n",
              "\n",
              "Bayesian inference: $$P(x|y) = \frac{P(y|x)P(x)}{P(y)}$$\n",
              " \n",
              "\n",
              "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
              "Often times we can train Naive Bayes classifiers with maximum likelihood estimate of the probability. However,\n",
              "this can lead to problems when there are words which we have never seen before. This can lead to a 0 probability will will mean that the probability\n",
              "of the entire class will be 0 no matter the other evidence. This is remedied with Laplace smoothing. For unknown words or words that are not\n",
              "in our vocabulary, we ignore them by removing them from our document all together. Note that some systems completely ignore stop words as\n",
              "well which are words like \"the\" or \"a\". \n",
              "\n",
              "## SLP Chapter 4.3 Worked Example\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
              "One way to increase efficiency is to better understand negation by appending NOT to every word that occurs after a token of \n",
              "logical negation. We also may hvae insufficently labeled training data. We can fix this by using sentiment lexicons which are lists of words\n",
              "that are preannotated with positive or negative sentiment.  \n",
              "\n",
              "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
              "The most effective naive Bayes features are not words but character n-grams. This allows us to be more efficient by predefining \n",
              "likely sets of words or phrases as features rather than using all words as individual features. \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",
              "The development test set is used to tune parameters to decide what model is best. The idea of cross-validation allows ut\n",
              "to avoid the problem of having a test set that is not large enough to be representative. With cross-validation, we choose a number $k$ and partiton our\n",
              "data into $k$ disjoint subsets known as folds. We choose one of the folds as a test set and train the classifier on the rest, repeating the process $k$\n",
              "times.  \n",
              "\n",
              "## SLP Chapter 4.9 Statistical Significance Testing\n",
              "In NLP, we use two non-parametric tests called approximate randomization and bootstrap test to determine the significance of our results.\n",
              "The intuition behin dboostrapping is we can create many virtual test sets by repeatedly sample from observed.\n",
              "\n",
              "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
              "This section addresses the possibility of harms that may arise from training a classifier. One of these is known as representational harms\n",
              "which are harms caused by a system that demeans a social group or reinforces negative stereotypes. \n",
              "\n",
              "## Module 12 Lecture Notes\n",
              "Perceptrons consist of a set of features with weights where the dot product is summed. If it is above some threshold a specifc output value is returned. Usually perceptrons\n",
              "are more accurate than naive Bayes.\n",
              "\n",
              "Separability: if some parameter gets the training set perfectly correct\n",
              "\n",
              "Mistake bound: max number of mistakes related to the margine or degree of separability\n",
              "\n",
              "Noise: if the data isn't seaprable, weights might clash. We can fix this by averaging weight vectors over time. \n",
              "\n",
              "Margin infused relaxed algorithm (MIRA): choose an update size that fixes the current mistake but minimizes change to weight. Then multiple feature value by $\\Tau$\n",
              "\n",
              "Non-linear separators: original feature space can always be mapped to some higher dimensional feature space where the training set is separable \n",
              "\n",
              "\n",
              "## Module 12 Definitions\n",
              "* **Supervised learning** - agent observes input-output pairs to learn a function mapping input to output\n",
              "* **Unsupervized learning** - agent learns patterns in input without feedback\n",
              "* **Clustering** - detecting useful clusters of input examples\n",
              "* **Eninforcement learning** - learns from a series of reinforcements as rewards and punishments\n",
              "* **Hypothesis** - the function $h$ that approximates the input-output function\n",
              "* **Consistent hypothesis** - $h$ such that for each $x_i$, $h(x_i) = y_i$\n",
              "* **Bias** - the tendency of a predictive hypothesis to deviate when averaged over different traningin sets\n",
              "* **Underfitting** - when a hypothesis fails to find a pattern in the data\n",
              "* **Overfitting** - when the hypothesis too closely models the training data\n",
              "* **Decision tree** - representation of a function that maps attribute values to one output value\n",
              "* **Learning curve** - evaluates the performance of a learning algorithm\n",
              "* **Model selection** - choosing a good hypothesis space\n",
              "* **Optimization** - finding best hypothesis in the space\n",
              "* **Interpolated** - a model that exactly fits all the training data\n",
              "* **Regularization** - penalizing complex hypotheses using a regularization function\n",
              "* **Approximately correct** - error($h$) $\\le \\epsilon$\n",
              "* **Weight space** - space defined by all possible settings of the weights\n",
              "* **Convex** - all loss functions for every linear regression problem; no local minima\n",
              "* **Decision boundary** - line or surface that separates two classes\n",
              "* **Linear separator** - linear decision boundary that separates the data into classes\n",
              "* **Perceptron learning rule** - $w_i = w_i + \u0007lpha (y - h(x)) \\cdot x_i\n",
              "* **Binary multinomial naive bayes** - clip the word counts in each document at 1\n",
              "* **Precision** - measures the percentage of items that the system labels properly\n",
              "* **Recall** - measures percentage of items that were actually present that were correctly identified\n",
              "* **Macroaveraging** - performance for each class and then average over classes\n",
              "* **Microaveraging** - collect the decisions for all classes and then compute values from them collectively\n",
              "* **** - \n",
              "\n",
              "\n",
              "# Module 13: Neural Networks\n",
              "## SLP Chapter 5.1 Classification: the sigmoid\n",
              "A feature representation of the input: this\n",
              "will be a vector of features, A classification function that computes ˆy, the estimated class, via p(y|x) often using sigmoid\n",
              "or softmax, An objective function for learning, usually involving minimizing error on\n",
              "training examples (cross-entropy loss function) and An algorithm for optimizing the objective function (stochastic gradient descent algorithm).\n",
              "Logistic regression has two phases: training and test. It is represented by $z = w \\cdot x + b$ where $b$ is the bias term. The sigmoid\n",
              "function maps values between 0 and 1 where outlier values get pushed to 0 or 1. $z$ is fed into this function. Sigmoid is differentiable.\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",
              "Cross Entropy Loss: \n",
              "$$L_{CE}(\\hat{y}, y) = −log p(y|x) = −[y log \\hat{y}+ (1−y)log(1−\\hat{y})]$$\n",
              "We can replace $\\hat{y}$ with $\\sigma(w \\cdot x + b)$. A perfect classifier would assign probability 1 to the correct outcome (y=1 or y=0) and\n",
              "probability 0 to the incorrect outcome. That means the higher $\\hat{y}$ (the closer it is\n",
              "to 1), the better the classifier; the lower $\\hat{y}$ is (the closer it is to 0), the worse the\n",
              "classifier.\n",
              "\n",
              "## SLP Chapter 5.4 Gradient Descent\n",
              " The goal of gradient descent is to minimize the loss function defined above. This is a method to find the minimum in a functin\n",
              "by figuring out in which direction the function's slope is rising the most steeply and going the opposite direction. For logistic \n",
              "regressoin, the loss function is always convex so we are guaranteeds to find the minimum. The learning rate is a hyperparamter where if it is\n",
              "too high, we will overshoot the minimum and if it is too low, the learner will take too long to get to the minimum.\n",
              " \n",
              "\n",
              "## SLP Chapter 5.5 Regularization\n",
              "Regularization is used to penalize large weights. L2 regularization is quadatic and  L1 is linear function of the weight values \n",
              "\n",
              "## SLP Chapter 5.6 Multinomial logistic regression\n",
              " Multinomial logistic regression is used when we have more than two classes. This uses a generalization of the sigmoid function called\n",
              "the softmax function.  The softmax function takes a vector of arbitrary values and maps them to a probability distribution, with each value in the range (0,1), \n",
              "and all the values summing to 1. The loss function is generalized for multinomial as a sum.\n",
              "\n",
              "## SLP Chapter 7.1 Units\n",
              " Deep learning is called deep learning because there are often many layers of nets. a neural unit takes a weighted sum of its inputs, and adds\n",
              "a bias term. Neural networks apply a non-linear function to z\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",
              " Mini batch training is a compromise between stochastic gradient descent with single random example \n",
              "and batch training such that efficiency is preserved and resources are maximized. \n",
              "\n",
              "Neural networks have 3 non-linear functions: sigmoid function, tanh function, and rectified linear unit (ReLU). In a feed forward network, no output is passed back; they \n",
              "only move into unites in the next higher layer. The goal is to learn the best parameters to make predictions as close as possible to the gold standard. A loss function as well \n",
              "as optimization algorithm are used but we need an additional concept called error propogation which allows us to properly compute loss among all the layers. \n",
              "\n",
              "Backward differentiation: depends on notion of computation graphs which represent the process of computing mathematical expressions. Each operation is a separate node in the\n",
              "graph. Forward pass goes from left to right and is just carrying out the operations. Computing the derivative of the loss function takes place through backward pass\n",
              "where the derivative of the loss function with respect to the various individual variables is found. This gives us how much a smal change in a variable affects the final loss. \n",
              "We compute the derivates from right to left and multiply partial derivates until we get the final derivative we need. \n",
              "\n",
              "\n",
              "## Module 13 Definitions\n",
              "* **Learning rate** - given by $\\eta$\n",
              "\n",
              "\n",
              "# Module 14: Natural Language Processing\n",
              "## SLP Chapter 9.1 Language Models Revisited\n",
              " We use perplexity to measure the quality of a language model \n",
              "\n",
              "## SLP Chapter 9.2 Recurrent Neural Networks\n",
              " A recurrent neural network (RNN) is any network that contains a cycle within its\n",
              "network connections, meaning that the value of some unit is dependent on its own earlier outputs as an input. Note that feed \n",
              "forward networks do not have cycles. Forward inference however is nearly identical. \n",
              "\n",
              "\n",
              "## SLP Chapter 9.3 RNNs as Language Models\n",
              "RNN language models  process the input sequence one word at\n",
              "a time, attempting to predict the next word from the current word and the previous\n",
              "hidden state. Unlike n-grams, they don't have to worry about the limited context problem. This means that the loss function is calculated\n",
              "slightly differently as follows for time $t$: $L_{CE}(\\hat{y}_t,y_t) = −log\\hat{y}_t[w_{t+1}]$  \n",
              "\n",
              "## SLP Chapter 6.1 Lexical Semantics\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.2 Vector Semantics\n",
              " In the tf-idf model, the meaning of a word is defined by a simple function\n",
              "of the counts of nearby words. There is the word2vec model family for constructing short, dense vectors that have useful semantic properties. \n",
              "\n",
              " \n",
              "\n",
              "## SLP Chapter 6.3 Words and Vectors\n",
              " Cosine is the standard way to use embeddings to compute semantic similarity. It is based on the dot product.\n",
              "\n",
              "## SLP Chapter 6.4 Cosine for measuring similarity\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.8 Word2vec\n",
              " \n",
              "Skip-gram/Word2Vec:\n",
              "1. Treat the target word and a neighboring context word as positive examples.\n",
              "2. Randomly sample other words in the lexicon to get negative samples.\n",
              "3. Use logistic regression to train a classifier to distinguish those two cases\n",
              "4. Use the learned weights as the embeddings. \n",
              "\n",
              "Skipgram with negative sampling creates k negative samples for each training instance, each consisting of the\n",
              "target word plus a noise word which is a random word from the lexicon, constrained not to be the target word w.\n",
              "\n",
              "\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 13 Lecture Notes\n",
              " Mini batch training is a compromise between stochastic gradient descent with single random example \n",
              "and batch training such that efficiency is preserved and resources are maximized. \n",
              "\n",
              "Neural networks have 3 non-linear functions: sigmoid function, tanh function, and rectified linear unit (ReLU). In a feed forward network, no output is passed back; they \n",
              "only move into unites in the next higher layer. The goal is to learn the best parameters to make predictions as close as possible to the gold standard. A loss function as well \n",
              "as optimization algorithm are used but we need an additional concept called error propogation which allows us to properly compute loss among all the layers. \n",
              "\n",
              "Backward differentiation: depends on notion of computation graphs which represent the process of computing mathematical expressions. Each operation is a separate node in the\n",
              "graph. Forward pass goes from left to right and is just carrying out the operations. Computing the derivative of the loss function takes place through backward pass\n",
              "where the derivative of the loss function with respect to the various individual variables is found. This gives us how much a smal change in a variable affects the final loss. \n",
              "We compute the derivates from right to left and multiply partial derivates until we get the final derivative we need. \n",
              "\n",
              "\n",
              "## Module 14 Definitions\n",
              "* **Embeddings** - vectors for representing words\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.9.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
