{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1c8b8a13-c6b2-404d-c50e-11aded260f4f"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5207bcd9-7e0c-4ddf-edcc-25f6c553ee8e"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "- environment assumed to be episodic in decision making theory\n",
        "- non deterministic, partially observable environments\n",
        "- Agent might not know current state so we let Result(a), be a random variable whos outcomes\n",
        "are all possible states\n",
        "- Probability of outcome s given action a and observation e is P(s | a, e)\n",
        "- Epected utility of an action is average utility over all outcomes weighted by thier probability\n",
        "\"\"\"\n",
        "chapter16_2 =  \"\"\"\n",
        "- A lottery with outcomes $S_1, S_2, ..., S_n$ and probablities of ouctomes $p_1, p_2, ..., p_n$ can be written as $L = [S_1, p_1, S2_, p2, ..., S_n, p_n]$\n",
        "- An outcome $S_i$ can be an atomic state or another lottery\n",
        "- Reasonal preference should obey six axioms\n",
        "\n",
        "- Orderability: $A \\geq B$, $A \\leq B$ or $A = B$ must hold\n",
        "- Transitivity: If $A > B$ and $B>C$ then it must be $A > C$\n",
        "- Continuity: If some lottery B is between A and C in preference, then there is some\n",
        "probability p for which the rational agent will be indifferent between getting B for sure\n",
        "and the lottery that yields A with probability p and C with probability 1 − p. In other words\n",
        "\n",
        "$$A \\geq B \\geq C \\implies [A, p, C, 1-p] = B$$\n",
        "\n",
        "- Substitutability: If an agent is indiferent between two lotteries A and B then the agent is indifferent,\n",
        " between two more complex lotteries that are the same except that B is substituted in one of them \n",
        "\n",
        " $$A = B \\implies [A, p, C, 1-p] = [B, p, C, 1-p]$$\n",
        "\n",
        " - Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B.\n",
        "If an agent prefers A to B, then the agent must prefer the lottery that has a higher\n",
        "probability for A (and vice versa)\n",
        "\n",
        "$$A > B \\implies [A, p, B, 1-p] > [A, q, B, 1-q], p \\geq q $$\n",
        "\n",
        "- Decomposability: Compounded loterries can be resolved into simpler ones using the law of probability \n",
        "\n",
        "- If these axioms are violated by an agent then it can be shown that this agent is not rational\n",
        "\n",
        "- If an agents preferences obey the axioms of utility then there exits a utility function the represent the preferences\n",
        "of that agent\n",
        "\n",
        "- Expected utility of lottery L is the sum of each outcomes utility weighted by the probability it occurs\n",
        "\n",
        "$$U(L) = \\sum_iU(S_i) *p_i$$\n",
        "\n",
        "- Expected utility of compounded lotteries can be copmuted through decomposability \n",
        "\n",
        "- Multiple utility functions exist that can capture there preferences of an agent\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "- usually there is no scale for utility function but we can make one by fixing the values of the worst and best outcomes\n",
        "- Let $u_b$ be the expected utility in the best case, let $u_w$ be the expected utility of the worst possible outcome\n",
        "- A normalized utility scale has $u_b = 1$ and $u_w = 0$ \n",
        "- We can asses the utility of some other state $S$ by asking the agent to choose between S and $[u_b, p, u_w, 1-p]\n",
        "- If utilities are normalized, the utility of S is given by p\n",
        "- we are really working with estimates EU(a|e) of the true expected utility. We will assume, kindly perhaps, that the\n",
        "UNBIASED estimates are unbiased, that is, the expected value of the error, E(EU!(a|e) − EU (a|e))) =0\n",
        "- real outcome will usually be significantly worse than estimated even though estimator is unbiased \n",
        "- This is because we favor overestimates so this creates bias. As more utilities are considered bias grows\n",
        "- The phenomenon above is known as optimizers curse\n",
        "- framing effect, the wording of a decision probelm can have a great impact on agent preferences\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "- we need to consider utility in sequential decision probelms\n",
        "- quality of a policy is measured by expected utility of the possible environment histories generated by that policy\n",
        "- optimal policy for a finite horizon is non stationary\n",
        "- With no fixed time limit no reason to behave differently in the same state at different times\n",
        "- Optimal action depends only on the current state, and the optimal policy is stationary\n",
        "- Assume agent's preferences between state sequences are stationary\n",
        "- ie. if there are two sequences $[s_1, s_2, ..., s_n]$ and $[s'_1, s'_2, ..., s'_n]$ and $s_1 = s'_1$, then the two sequences should be preference ordered\n",
        "the same way as $[s_2, ..., s_n]$ and $[s'_2, ..., s'_n]$ \n",
        "- Stationarity leads to a few important conclusions\n",
        "- Additive rewards: utility of a state sequence $[s_1, s_2, ..., s_n]$ is $R(s_0) + R(s_1) + ... R(s_n)$\n",
        "- Discounted rewards: Utility of a state sequence $[s_1, s_2, ..., s_n]$ is $R(s_0) + yR(s_1) + ... y^{n-1}R(s_n)$. Where $y$ is a discount factor between 0 and 1. If $y$ is \n",
        "close to zero then future rewards matter less and less to the current reward\n",
        "- This leads to to two further conclusions:\n",
        "- With discounted rewards, the utility of infinite sequence is finite and is further bounded by $R_{max}$\n",
        "$$U([s_1, s_2, ..., s_n]) = \\sum_{t=0}y^tR(s_t) \\leq \\sum_{t=0}y^t R_{max} = R_{max}/(1-y)$$\n",
        "- infinite series can be compared based on average reward per time step\n",
        "- Compare policies based on the expected utility from executing them\n",
        "- The optimal policy is therefore \n",
        "\n",
        "$$\\pi^* = argmax_{\\pi}U^{\\pi}(s)$$\n",
        "- This is the optimal policy starting at state $s$\n",
        "- Discounted utilities with infinite horizons means that the optimal policy is independnet of starting state\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "- The Bellman Equation is Defined as \n",
        "$$U(s) = R(s) + max_{a \\in A}\\sum_{s'}P(s'; a, s) * U(s')$$\n",
        "\n",
        "- From this equation we can infer the value iteration algorithm \n",
        "- The iteration step, called the Bellman update, is as follows:\n",
        "\n",
        "$$U_{i+1} = R(s) + max_{a \\in A}\\sum_{s'}P(s'; a, s) * U_i(s')$$\n",
        "- The value iteration algorithm is shown in extra hand notes\n",
        "- If we apply the Bellman update infinitely, we are garanteed to reach equilibrium, the solutions are unique\n",
        "- This algorithm propagates information through stae space\n",
        "- Value iteration can be shown to converge through contraction - a function of one argument that, when applied to\n",
        "two different inputs in turn, produces two output values that are “closer together\" (example of this is division by 2)\n",
        "- A contraction has only one fixed point; if there were two fixed points they would not\n",
        "get closer together when the function was applied, so it would not be a contraction.\n",
        "- When the function is applied to any argument, the value must get closer to the fixed\n",
        "point so repeated application of a contraction always reaches the fixed point in the limit.\n",
        "- Bellman update is a contraction by a factor of γ on the space of utility vectors. Therefore Bellman iteration always converges to a unique solution when y< 1\n",
        "- Value iteration also converges exponenentially in $y$\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "MDP needs:\n",
        "- A set of states $s \\in S$\n",
        "- A set of actions $a \\in A$\n",
        "- A transition function $T(s, a, s’)$\n",
        "- Probability that executing action a in s will lead to s’ $P(s’ | s, a)$\n",
        "- The probability is called the model\n",
        "- A reward function $R(s, a, s’)$\n",
        "- An initial state $s0$\n",
        "\n",
        "- Time complexity of each value iteration is O(S^2 * A)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"Decision theory\" : \"choosing among actions based on the desirability of their immediate outcomes\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "\"utility function\": \"assigns a single value to capture the desirability of a state\",\n",
        "\"principle of Maximum Expected Utility MEU\": \"rational agent should choose action that maximizes expected uitlity\",\n",
        "\"Lottery\" : \"set of outcomes for each action\",\n",
        "\"value function/ ordinal utilty\": \" We care about the ordering of outcomes in terms of preference not the number\",\n",
        "\"utility function\": \"maps lotteries to real numbers\",\n",
        "\"preference elicitation\": \"presenting choices to an agent to determine preferences\",\n",
        "\"Normalized utilities\": \"Use a scale from 0 to 1\",\n",
        "\"normative theory\": \"describes how agent should act\",\n",
        "\"descriptive theory\": \"describes how agents should act\",\n",
        "\"certainty effect\": \"people are attracted to gains that are certain\",\n",
        "\"markovian\": \"probability of reaching next state only depends on current state\",\n",
        "\"environment history\": \"sequence of states the agent was in\",\n",
        "\"Markov decision process\": \"sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\",\n",
        "\"policy\": \"a specification of what an agent should do at any state of an MDP\",\n",
        "\"optimal policy\": \"policy that yeilds the highest expected utility\",\n",
        "\"proper policy\": \"policy garanteed to reach a terminal state\",\n",
        "\"value iteration\": \"algorithm for calculating optimal policy\",\n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "30b7fa4a-0dfa-49f9-a0a2-062b4a276cce"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- environment assumed to be episodic in decision making theory\n- non deterministic, partially observable environments\n- Agent might not know current state so we let Result(a), be a random variable whos outcomes\nare all possible states\n- Probability of outcome s given action a and observation e is P(s | a, e)\n- Epected utility of an action is average utility over all outcomes weighted by thier probability\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- A lottery with outcomes $S_1, S_2, ..., S_n$ and probablities of ouctomes $p_1, p_2, ..., p_n$ can be written as $L = [S_1, p_1, S2_, p2, ..., S_n, p_n]$\n- An outcome $S_i$ can be an atomic state or another lottery\n- Reasonal preference should obey six axioms\n\n- Orderability: $A \\geq B$, $A \\leq B$ or $A = B$ must hold\n- Transitivity: If $A > B$ and $B>C$ then it must be $A > C$\n- Continuity: If some lottery B is between A and C in preference, then there is some\nprobability p for which the rational agent will be indifferent between getting B for sure\nand the lottery that yields A with probability p and C with probability 1 − p. In other words\n\n$$A \\geq B \\geq C \\implies [A, p, C, 1-p] = B$$\n\n- Substitutability: If an agent is indiferent between two lotteries A and B then the agent is indifferent,\n between two more complex lotteries that are the same except that B is substituted in one of them \n\n $$A = B \\implies [A, p, C, 1-p] = [B, p, C, 1-p]$$\n\n - Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B.\nIf an agent prefers A to B, then the agent must prefer the lottery that has a higher\nprobability for A (and vice versa)\n\n$$A > B \\implies [A, p, B, 1-p] > [A, q, B, 1-q], p \\geq q $$\n\n- Decomposability: Compounded loterries can be resolved into simpler ones using the law of probability \n\n- If these axioms are violated by an agent then it can be shown that this agent is not rational\n\n- If an agents preferences obey the axioms of utility then there exits a utility function the represent the preferences\nof that agent\n\n- Expected utility of lottery L is the sum of each outcomes utility weighted by the probability it occurs\n\n$$U(L) = \\sum_iU(S_i) *p_i$$\n\n- Expected utility of compounded lotteries can be copmuted through decomposability \n\n- Multiple utility functions exist that can capture there preferences of an agent\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- usually there is no scale for utility function but we can make one by fixing the values of the worst and best outcomes\n- Let $u_b$ be the expected utility in the best case, let $u_w$ be the expected utility of the worst possible outcome\n- A normalized utility scale has $u_b = 1$ and $u_w = 0$ \n- We can asses the utility of some other state $S$ by asking the agent to choose between S and $[u_b, p, u_w, 1-p]\n- If utilities are normalized, the utility of S is given by p\n- we are really working with estimates EU(a|e) of the true expected utility. We will assume, kindly perhaps, that the\nUNBIASED estimates are unbiased, that is, the expected value of the error, E(EU!(a|e) − EU (a|e))) =0\n- real outcome will usually be significantly worse than estimated even though estimator is unbiased \n- This is because we favor overestimates so this creates bias. As more utilities are considered bias grows\n- The phenomenon above is known as optimizers curse\n- framing effect, the wording of a decision probelm can have a great impact on agent preferences\n\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- we need to consider utility in sequential decision probelms\n- quality of a policy is measured by expected utility of the possible environment histories generated by that policy\n- optimal policy for a finite horizon is non stationary\n- With no fixed time limit no reason to behave differently in the same state at different times\n- Optimal action depends only on the current state, and the optimal policy is stationary\n- Assume agent's preferences between state sequences are stationary\n- ie. if there are two sequences $[s_1, s_2, ..., s_n]$ and $[s'_1, s'_2, ..., s'_n]$ and $s_1 = s'_1$, then the two sequences should be preference ordered\nthe same way as $[s_2, ..., s_n]$ and $[s'_2, ..., s'_n]$ \n- Stationarity leads to a few important conclusions\n- Additive rewards: utility of a state sequence $[s_1, s_2, ..., s_n]$ is $R(s_0) + R(s_1) + ... R(s_n)$\n- Discounted rewards: Utility of a state sequence $[s_1, s_2, ..., s_n]$ is $R(s_0) + yR(s_1) + ... y^{n-1}R(s_n)$. Where $y$ is a discount factor between 0 and 1. If $y$ is \nclose to zero then future rewards matter less and less to the current reward\n- This leads to to two further conclusions:\n- With discounted rewards, the utility of infinite sequence is finite and is further bounded by $R_{max}$\n$$U([s_1, s_2, ..., s_n]) = \\sum_{t=0}y^tR(s_t) \\leq \\sum_{t=0}y^t R_{max} = R_{max}/(1-y)$$\n- infinite series can be compared based on average reward per time step\n- Compare policies based on the expected utility from executing them\n- The optimal policy is therefore \n\n$$\\pi^* = argmax_{\\pi}U^{\\pi}(s)$$\n- This is the optimal policy starting at state $s$\n- Discounted utilities with infinite horizons means that the optimal policy is independnet of starting state\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- The Bellman Equation is Defined as \n$$U(s) = R(s) + max_{a \\in A}\\sum_{s'}P(s'; a, s) * U(s')$$\n\n- From this equation we can infer the value iteration algorithm \n- The iteration step, called the Bellman update, is as follows:\n\n$$U_{i+1} = R(s) + max_{a \\in A}\\sum_{s'}P(s'; a, s) * U_i(s')$$\n- The value iteration algorithm is shown in extra hand notes\n- If we apply the Bellman update infinitely, we are garanteed to reach equilibrium, the solutions are unique\n- This algorithm propagates information through stae space\n- Value iteration can be shown to converge through contraction - a function of one argument that, when applied to\ntwo different inputs in turn, produces two output values that are “closer together\" (example of this is division by 2)\n- A contraction has only one fixed point; if there were two fixed points they would not\nget closer together when the function was applied, so it would not be a contraction.\n- When the function is applied to any argument, the value must get closer to the fixed\npoint so repeated application of a contraction always reaches the fixed point in the limit.\n- Bellman update is a contraction by a factor of γ on the space of utility vectors. Therefore Bellman iteration always converges to a unique solution when y< 1\n- Value iteration also converges exponenentially in $y$\n\n\n## Module 8 Lecture Notes\n\nMDP needs:\n- A set of states $s \\in S$\n- A set of actions $a \\in A$\n- A transition function $T(s, a, s’)$\n- Probability that executing action a in s will lead to s’ $P(s’ | s, a)$\n- The probability is called the model\n- A reward function $R(s, a, s’)$\n- An initial state $s0$\n\n- Time complexity of each value iteration is O(S^2 * A)\n\n\n\n## Module 8 Definitions\n* **Decision theory** - choosing among actions based on the desirability of their immediate outcomes\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n* **Utility function** - maps lotteries to real numbers\n* **Principle of maximum expected utility meu** - rational agent should choose action that maximizes expected uitlity\n* **Lottery** - set of outcomes for each action\n* **Value function/ ordinal utilty** -  We care about the ordering of outcomes in terms of preference not the number\n* **Preference elicitation** - presenting choices to an agent to determine preferences\n* **Normalized utilities** - Use a scale from 0 to 1\n* **Normative theory** - describes how agent should act\n* **Descriptive theory** - describes how agents should act\n* **Certainty effect** - people are attracted to gains that are certain\n* **Markovian** - probability of reaching next state only depends on current state\n* **Environment history** - sequence of states the agent was in\n* **Markov decision process** - sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\n* **Policy** - a specification of what an agent should do at any state of an MDP\n* **Optimal policy** - policy that yeilds the highest expected utility\n* **Proper policy** - policy garanteed to reach a terminal state\n* **Value iteration** - algorithm for calculating optimal policy\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "- Want to create policy iteration algorithm. Intuition is that if one action is better than all others, than the magnitute by which it differs need not precise\n",
        "- Policy iterationa algorithm works with two steps:\n",
        "1) Policy evaluation: given a policy $\\pi_i$, calculate $Ui = U^{\\pi_i}$ , the utility of each state if πi POLICY EVALUATION\n",
        "were to be executed.\n",
        "2) Policy imporovement: Calculate a new MEU policy $\\pi_{i+1}$, using one-step look-ahead  based on $U_i$\n",
        "- Algorithm terminates when policy imporvement yeilds no changes in the utilities\n",
        "- This structure simplifies the Bellman equation to\n",
        "\n",
        "$$U_i(s) = R(s) + \\sum_{s'}P(s'; \\pi_i(s), s) * U(s')$$\n",
        "- Since max operator is removed, the equations are now linear and the Utility update can be solved in O(N^3) time where n is the number of states\n",
        "- Policy iteration algorithm is in the doc\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "- A utility-based agent learns a utility function on states and uses it to select actions that\n",
        "maximize the expected outcome utility.\n",
        "- A Q-learning agent learns an action-utility function, or Q-function, giving the exQ-FUNCTION pected utility of taking a given action in a given state.\n",
        "- A reflex agent learns a policy that maps directly from states to actions.\n",
        "- \n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "- Direct Evaluation. Sample in the space by doing trial runs and calculate the utility of a state through discounting. In the end avaerage all samples to estimate \n",
        "utility for a particular state. With infinite samples this approaches the true value\n",
        "- Direct Evaluation converges very slowsly because it doesn't take advanatage of the relationship between state and actions\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "- policy search: keep altering the policy while performance improves and then stop\n",
        "- the output of policy search is not always optimal (it focuses on achieveing good agent performance)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "- Offline planning: determine all quantities through computation. Need to know the details of the MDP. Do not actually play the game!\n",
        "- Online learning: we don't plan the future\n",
        "- Reinforcement learning : Receive feedback in the form of rewards. Agent’s utility is defined by the reward function and act so as to maximize expected rewards\n",
        "- Context: Assume an MDP where we dont know T (the transition model) and R the rewards\n",
        "- So we first start exploring with a fixed policy $\\pi$ - this is online learning we are actually taking actions in the environment\n",
        "\n",
        "- Direct Evaluation: Act according to $\\pi$. Every time you visit a state, write down what the sum of discounted rewards turned out to be\n",
        "Average those samples.\n",
        "- Direct Evaluation eventually computes correct average values, but is ineffcient and needs to be run individually for everys state\n",
        "- Use Policy Iteration instead of Direct Evaluation!!!\n",
        "$$V_{k+1}^{\\pi} = \\sum_{s'}T(s, \\pi(s), s')[R(s, \\pi(s), s') + V_k^{\\pi}(s')]$$\n",
        "$$V_{0}^{\\pi} = 0$$\n",
        "\n",
        "- But we dont know the transition model and rewards so we can take samples and average them.\n",
        "$$sample= R(s, a, s') + yV(s')$$\n",
        "$$V^{\\pi}(s) = (1-a)V^{\\pi}(s) + a*sample$$\n",
        "$$V^{\\pi}(s) = V^{\\pi}(s) + (sample - V^{\\pi}(s))$$\n",
        "\n",
        "- This form of update results in an exponential moving average:\n",
        "\n",
        "$$x_n^{mean} = (1-a)x_{n-1}^{mean} + ax_n$$\n",
        "$$x_n^{mean} = \\\\frac{x_n + (1-a)x_{n-1} + (1-a)^2x_{n-2} + ...}{1 + (1-a) + (1-a)^2 + ...}$$\n",
        "\n",
        "- decreasing leraning rate gives converging averages\n",
        "- This is great but we don't have the transition model (probability of ending up in s' by taking action a from state s). So we need another approach.\n",
        "Solution is to infer Q values instead of actual values (values of Q states ) to make things model free\n",
        "\n",
        "- How do we do Q learning. The equation mirrors the bellman update\n",
        "\n",
        "$$Q_{k+1}(s,a) = \\sum_{s'}T(s, a, s')[R(s, a, s') + max_a'Q_k(s', a')]$$\n",
        "\n",
        "- This can be learned by sampling \n",
        "- 1. Recieve a sample (s, a, s', r)\n",
        "- 2. Define the sample estimate to be $sample = R(s,a,s') + y * max_a(Q(s',a))$\n",
        "- 3. Update Q value: $Q_{i+1}(s,a) = (1-a)Q_i(s,a) + a * sample$\n",
        "\n",
        "- The optimal policy ends up being $\\pi*(s) = argmax_a Q(s,a)$\n",
        "\n",
        "- Q learning converges to optimal policy even if acting suboptimally (but you have to explore enough and make the learning rate a small enough)\n",
        " \n",
        "- In order to sample well so we must incorporate exploration. Therefore with some probability e choose a random action in a state\n",
        "- But this is not best because it might be better to explore areas who' badness is not established \n",
        "- Define $f(u,n) = u + \\\\frac{k}{n}$ where k is a constant, n is the nunber of times visited and u is the utility \n",
        "- Agument the q values by factor $Q(s,a)' = f(Q(s,a), n)$. This means that the modified Q update is \n",
        "\n",
        "$$Q_i(s,a) = R(s,a s')$$\n",
        "\n",
        "- Regret caputures the idea that we are \"optimally\" learning (ie. not wasting time making mistakes)\n",
        "- Regret can be defined as the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n",
        "- Random exploration has a higher regre than other exploration functions\n",
        "\n",
        "- Aproximate Q Learning: In a realistic environment we cannot know every single state (example driving a car)\n",
        "- So we want to generalize by learning about a small subset of states and applying to new situations\n",
        "- We can write a Q function to estimate the Q value based on some percepts from the environment\n",
        "\n",
        "$$Q(s,a) = w_1*f_1(s) + w_2*f_2(s) + ... + w_k*f_k(s)$$\n",
        "\n",
        "- Without applying any Neural Net to this, we can reformat Q Learning to be:\n",
        "- 1. transition = (s, a, s', r)\n",
        "- 2. difference $[r + max_{a'}Q(s',a')] - Q(s,a)$\n",
        "- 3. update: $Q(s,a) = Q(s,a) - a*difference$\n",
        "- 4. update: $w_i = w_i + a * difference * f_i(s,a)$\n",
        "\n",
        "- The intutiion is :  if something unexpectedly bad happens, blame the features that were on:\n",
        "disprefer all states with that state’s features\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"reinforcement\" : \"signal to tell agent how they are doing\",\n",
        "\"passive learning\": \"agent’s policy is fixed and the task is to learn the utilities of states\",\n",
        "\"active learning\": \"agent learns wht to do (some policy)\",\n",
        "\"off policy learning\": \"can achieve optimal policy regardless of the agents actions\",\n",
        "\"regret\": \"measure of the total mistake cost\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "92ebdaec-b923-4f64-e8bd-432d96d52984"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- Want to create policy iteration algorithm. Intuition is that if one action is better than all others, than the magnitute by which it differs need not precise\n- Policy iterationa algorithm works with two steps:\n1) Policy evaluation: given a policy $\\pi_i$, calculate $Ui = U^{\\pi_i}$ , the utility of each state if πi POLICY EVALUATION\nwere to be executed.\n2) Policy imporovement: Calculate a new MEU policy $\\pi_{i+1}$, using one-step look-ahead  based on $U_i$\n- Algorithm terminates when policy imporvement yeilds no changes in the utilities\n- This structure simplifies the Bellman equation to\n\n$$U_i(s) = R(s) + \\sum_{s'}P(s'; \\pi_i(s), s) * U(s')$$\n- Since max operator is removed, the equations are now linear and the Utility update can be solved in O(N^3) time where n is the number of states\n- Policy iteration algorithm is in the doc\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- A utility-based agent learns a utility function on states and uses it to select actions that\nmaximize the expected outcome utility.\n- A Q-learning agent learns an action-utility function, or Q-function, giving the exQ-FUNCTION pected utility of taking a given action in a given state.\n- A reflex agent learns a policy that maps directly from states to actions.\n- \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n- Direct Evaluation. Sample in the space by doing trial runs and calculate the utility of a state through discounting. In the end avaerage all samples to estimate \nutility for a particular state. With infinite samples this approaches the true value\n- Direct Evaluation converges very slowsly because it doesn't take advanatage of the relationship between state and actions\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n- Offline planning: determine all quantities through computation. Need to know the details of the MDP. Do not actually play the game!\n- Online learning: we don't plan the future\n- Reinforcement learning : Receive feedback in the form of rewards. Agent’s utility is defined by the reward function and act so as to maximize expected rewards\n- Context: Assume an MDP where we dont know T (the transition model) and R the rewards\n- So we first start exploring with a fixed policy $\\pi$ - this is online learning we are actually taking actions in the environment\n\n- Direct Evaluation: Act according to $\\pi$. Every time you visit a state, write down what the sum of discounted rewards turned out to be\nAverage those samples.\n- Direct Evaluation eventually computes correct average values, but is ineffcient and needs to be run individually for everys state\n- Use Policy Iteration instead of Direct Evaluation!!!\n$$V_{k+1}^{\\pi} = \\sum_{s'}T(s, \\pi(s), s')[R(s, \\pi(s), s') + V_k^{\\pi}(s')]$$\n$$V_{0}^{\\pi} = 0$$\n\n- But we dont know the transition model and rewards so we can take samples and average them.\n$$sample= R(s, a, s') + yV(s')$$\n$$V^{\\pi}(s) = (1-a)V^{\\pi}(s) + a*sample$$\n$$V^{\\pi}(s) = V^{\\pi}(s) + (sample - V^{\\pi}(s))$$\n\n- This form of update results in an exponential moving average:\n\n$$x_n^{mean} = (1-a)x_{n-1}^{mean} + ax_n$$\n$$x_n^{mean} = \\frac{x_n + (1-a)x_{n-1} + (1-a)^2x_{n-2} + ...}{1 + (1-a) + (1-a)^2 + ...}$$\n\n- decreasing leraning rate gives converging averages\n- This is great but we don't have the transition model (probability of ending up in s' by taking action a from state s). So we need another approach.\nSolution is to infer Q values instead of actual values (values of Q states ) to make things model free\n\n- How do we do Q learning. The equation mirrors the bellman update\n\n$$Q_{k+1}(s,a) = \\sum_{s'}T(s, a, s')[R(s, a, s') + max_a'Q_k(s', a')]$$\n\n- This can be learned by sampling \n- 1. Recieve a sample (s, a, s', r)\n- 2. Define the sample estimate to be $sample = R(s,a,s') + y * max_a(Q(s',a))$\n- 3. Update Q value: $Q_{i+1}(s,a) = (1-a)Q_i(s,a) + a * sample$\n\n- The optimal policy ends up being $\\pi*(s) = argmax_a Q(s,a)$\n\n- Q learning converges to optimal policy even if acting suboptimally (but you have to explore enough and make the learning rate a small enough)\n \n- In order to sample well so we must incorporate exploration. Therefore with some probability e choose a random action in a state\n- But this is not best because it might be better to explore areas who' badness is not established \n- Define $f(u,n) = u + \\frac{k}{n}$ where k is a constant, n is the nunber of times visited and u is the utility \n- Agument the q values by factor $Q(s,a)' = f(Q(s,a), n)$. This means that the modified Q update is \n\n$$Q_i(s,a) = R(s,a s')$$\n\n- Regret caputures the idea that we are \"optimally\" learning (ie. not wasting time making mistakes)\n- Regret can be defined as the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n- Random exploration has a higher regre than other exploration functions\n\n- Aproximate Q Learning: In a realistic environment we cannot know every single state (example driving a car)\n- So we want to generalize by learning about a small subset of states and applying to new situations\n- We can write a Q function to estimate the Q value based on some percepts from the environment\n\n$$Q(s,a) = w_1*f_1(s) + w_2*f_2(s) + ... + w_k*f_k(s)$$\n\n- Without applying any Neural Net to this, we can reformat Q Learning to be:\n- 1. transition = (s, a, s', r)\n- 2. difference $[r + max_{a'}Q(s',a')] - Q(s,a)$\n- 3. update: $Q(s,a) = Q(s,a) - a*difference$\n- 4. update: $w_i = w_i + a * difference * f_i(s,a)$\n\n- The intutiion is :  if something unexpectedly bad happens, blame the features that were on:\ndisprefer all states with that state’s features\n \n\n## Module 9 Definitions\n* **Reinforcement** - signal to tell agent how they are doing\n* **Passive learning** - agent’s policy is fixed and the task is to learn the utilities of states\n* **Active learning** - agent learns wht to do (some policy)\n* **Off policy learning** - can achieve optimal policy regardless of the agents actions\n* **Regret** - measure of the total mistake cost\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \n",
        "- no rational agent can have beliefs that violate the axioms of probability\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\" \n",
        " \"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        " \"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" \n",
        "- natural language models should be defined as a probability distribution over sentences\n",
        "- A model of the probability distribution of n-letter sequences is thus called an n-gram model\n",
        "- n gram models can also be distributions over words, syllabules etc.\n",
        "- n gram model is defined as a Markov Chain of order n-1 (ie. the next character depends on the n-1 characters preceeding it!!)\n",
        "- We can train n gram models on multiple languages. Then, when given an input sequence, we can estimate which languge it comes from by the following\n",
        "\n",
        "$$L = argmax_LP(L) * P(c_1:c_n|L)$$\n",
        "\n",
        "- Difficulty with n gram models is that they are only an estimate of the true probabililty distribtuion (ie. just because we dont see the word http in our sample does not mean\n",
        "we should estimate its probability to be 0)\n",
        "- Thus we adjust the probability of low frequency count instances through smoothing\n",
        "- Different ways of smoothing include:\n",
        "- 1. Adding $\\\\frac{1}{n + 2}$ to each probability (assume if we took two more samples we would see our instance)\n",
        "- 2. Laplace Smoothing\n",
        "- 3. Interpolation Smoothing: $P(c_i|c_{i-1}, c_{i-2}) = \\lambda_1 P(c_i|c_{i-1}, c_{i-2}) + \\lambda_2P(c_i|c_{i-1}) + \\lambda_3 * P(c_i|c_{i-1})$\n",
        "\n",
        "- To determine best ngram and smoothing use cross validation \n",
        "- perplexity = $P(c_i|c_1:c_n)^{-\\\\frac{1}{n}}$\n",
        "\n",
        "- We can apply n gram models to words but more difficult (new words could come up, number of possible words is far larger, etc.)\n",
        "- To handle unkown words we can just add a \"unkown\" placeholder \"UKN\" in our vocab\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "- To estimate the probability of a sequence of words $w_1, w_2, ..., w_n$ we can use chaining\n",
        "\n",
        "$$P(w_1,..,w_n) = P(w_n|w_{n-1}...w_1) * P(w_{n-1}|w_{n-2}...w_1) * ... * P(w_1))$$$\n",
        "\n",
        "- n grams allow us to limit scope to a few preceding words so that we can reasonable estimate the probabilities above\n",
        "- we evaluate the performance of NLP models by test set, performance is evaluated by whichever model assigns higher probability to the test set\n",
        "\n",
        "- perplexity is approximately the branching factor of the vocabulary\n",
        "- increasing the number of grams decreases perplexity \n",
        "- perplexity of two language models is comparable only if the use nearly identical vocabularies\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" \n",
        "- Laplace Smoothing (adds a value of one by each count and increases the total by V (the size of the vocabulary)):\n",
        "\n",
        "$$P(w_i) = \\\\frac{w_i + 1}{N + V}$$\n",
        "\n",
        "- To do discounting, consider an adjusted count $c*$\n",
        "$$c* = (c_i + 1)\\\\frac{N}{N + V}$$\n",
        "- No this means that the ratio of discounted counts to original counts is:\n",
        "\n",
        "$$d = \\\\frac{c*}{c}$$\n",
        "\n",
        "- With this we show that too much probability mass is moved to zero count instances\n",
        "\n",
        "- We can change by doing \"Add K smoothing\" (adding k instead of 1) but that also fails often (can optimize during training)\n",
        "- Backoff and Interpolation are two other techniques to shift probability mass to zero instances\n",
        "- For Backoff, if we have zero evidence of $P(w_n|w_{n-1}...w_1)$ we estimate its probability as $P(w_n|w_{n-2}...w_1)$ and keep decreasing grams until probability is non zero\n",
        "- For Backoff we need to discount the mass of higher order n grams to save mass for lower order n grams. Otherwise, too much mass is shifted to zero evidence instances and models fail\n",
        "- Backoff with discounting is also known as Katz backoff\n",
        "- For Iterpoloation we mix and match different n grams\n",
        "$$P(w_n|w_{n-1}, w_{n-2}) = \\lambda_0 * P(w_n) + \\lambda_1*P(w_n|w_{n-1}) + \\lambda_2 *P(w_n|w_{n-1}, w_{n-2})$$\n",
        "- One of the best n gram smoothing interpolations is Kneser-Ney Smoothing\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"language\" : \"a set of strings\",\n",
        "\"n gram\": \"a sequence of symbols of length n\",\n",
        "\"corpus\": \"a body of text\",\n",
        "\"perplexity\": \"way of caputring the probability of a sequence\",\n",
        "\"Probability\": \"provides a way of summarizing the uncertainty that comes from our laziness and ignorance\",\n",
        "\"sample space\": \"set of all possible worlds\",\n",
        "\"proposition\": \"event or outcome from a sample space\",\n",
        "\"evidence\": \"information to consider when gauging probability (essentially given that)\",\n",
        "\"language models\": \"models that assign probabilities to sequences of words\",\n",
        "\"n gram\": \"a sequence of n words\",\n",
        "\"discounting\": \"a way of smoothing by lowering non zero counts and increasing the prbability mass of zero counts\"\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "3edbde7a-0749-4f1d-c431-627af51206a8"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n- no rational agent can have beliefs that violate the axioms of probability\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n \n\n## AIMA Chapter 12.4 Independence\n \n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n \n- natural language models should be defined as a probability distribution over sentences\n- A model of the probability distribution of n-letter sequences is thus called an n-gram model\n- n gram models can also be distributions over words, syllabules etc.\n- n gram model is defined as a Markov Chain of order n-1 (ie. the next character depends on the n-1 characters preceeding it!!)\n- We can train n gram models on multiple languages. Then, when given an input sequence, we can estimate which languge it comes from by the following\n\n$$L = argmax_LP(L) * P(c_1:c_n|L)$$\n\n- Difficulty with n gram models is that they are only an estimate of the true probabililty distribtuion (ie. just because we dont see the word http in our sample does not mean\nwe should estimate its probability to be 0)\n- Thus we adjust the probability of low frequency count instances through smoothing\n- Different ways of smoothing include:\n- 1. Adding $\\frac{1}{n + 2}$ to each probability (assume if we took two more samples we would see our instance)\n- 2. Laplace Smoothing\n- 3. Interpolation Smoothing: $P(c_i|c_{i-1}, c_{i-2}) = \\lambda_1 P(c_i|c_{i-1}, c_{i-2}) + \\lambda_2P(c_i|c_{i-1}) + \\lambda_3 * P(c_i|c_{i-1})$\n\n- To determine best ngram and smoothing use cross validation \n- perplexity = $P(c_i|c_1:c_n)^{-\\frac{1}{n}}$\n\n- We can apply n gram models to words but more difficult (new words could come up, number of possible words is far larger, etc.)\n- To handle unkown words we can just add a \"unkown\" placeholder \"UKN\" in our vocab\n\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- To estimate the probability of a sequence of words $w_1, w_2, ..., w_n$ we can use chaining\n\n$$P(w_1,..,w_n) = P(w_n|w_{n-1}...w_1) * P(w_{n-1}|w_{n-2}...w_1) * ... * P(w_1))$$$\n\n- n grams allow us to limit scope to a few preceding words so that we can reasonable estimate the probabilities above\n- we evaluate the performance of NLP models by test set, performance is evaluated by whichever model assigns higher probability to the test set\n\n- perplexity is approximately the branching factor of the vocabulary\n- increasing the number of grams decreases perplexity \n- perplexity of two language models is comparable only if the use nearly identical vocabularies\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n \n- Laplace Smoothing (adds a value of one by each count and increases the total by V (the size of the vocabulary)):\n\n$$P(w_i) = \\frac{w_i + 1}{N + V}$$\n\n- To do discounting, consider an adjusted count $c*$\n$$c* = (c_i + 1)\\frac{N}{N + V}$$\n- No this means that the ratio of discounted counts to original counts is:\n\n$$d = \\frac{c*}{c}$$\n\n- With this we show that too much probability mass is moved to zero count instances\n\n- We can change by doing \"Add K smoothing\" (adding k instead of 1) but that also fails often (can optimize during training)\n- Backoff and Interpolation are two other techniques to shift probability mass to zero instances\n- For Backoff, if we have zero evidence of $P(w_n|w_{n-1}...w_1)$ we estimate its probability as $P(w_n|w_{n-2}...w_1)$ and keep decreasing grams until probability is non zero\n- For Backoff we need to discount the mass of higher order n grams to save mass for lower order n grams. Otherwise, too much mass is shifted to zero evidence instances and models fail\n- Backoff with discounting is also known as Katz backoff\n- For Iterpoloation we mix and match different n grams\n$$P(w_n|w_{n-1}, w_{n-2}) = \\lambda_0 * P(w_n) + \\lambda_1*P(w_n|w_{n-1}) + \\lambda_2 *P(w_n|w_{n-1}, w_{n-2})$$\n- One of the best n gram smoothing interpolations is Kneser-Ney Smoothing\n\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Language** - a set of strings\n* **N gram** - a sequence of n words\n* **Corpus** - a body of text\n* **Perplexity** - way of caputring the probability of a sequence\n* **Probability** - provides a way of summarizing the uncertainty that comes from our laziness and ignorance\n* **Sample space** - set of all possible worlds\n* **Proposition** - event or outcome from a sample space\n* **Evidence** - information to consider when gauging probability (essentially given that)\n* **Language models** - models that assign probabilities to sequences of words\n* **Discounting** - a way of smoothing by lowering non zero counts and increasing the prbability mass of zero counts\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "- Full specification of Bayesian network requires:\n",
        "- 1. Each node corresponds to a random variable, which may be discrete or continuous.\n",
        "- 2. If there is an edge from node X to node Y ,then X is a parent of Y. Graph is a DAG\n",
        "- 3. Each node Xi has a conditional probability distribution P(Xi | Parents(Xi)) that quantifies the effect of the parents on the node.\n",
        "\n",
        "- An edge from X to Y implies that X influences Y\n",
        "\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\" \n",
        "- Baysian network is a representation of a joint probability distribution\n",
        "- It assumes $P(X_i |X_{i-1}, ..., X_1)= P(X_i|Parents(X_i))$ (a big assumption, essentially we create the Bayes net how we want)\n",
        "\n",
        "- To form a Baysian Network do the following with states $X_1, ..., X_n$\n",
        "- Choose a state $X_n$ and determine a minimal set of paretns from $X_1,...X_{n-1}$\n",
        "- For each parent draw and edge from the parent to $X_n$\n",
        "- Write the conditional Probability $P(X_n|Parents(X_n))$\n",
        "\n",
        "- Each node is only connected to earlier nodes so cycles dont arise\n",
        "\n",
        "- Baysian netowrrk is a locally strucutred (sparse) system\n",
        "\n",
        "- Baysian networks are great at saving space\n",
        "- Suppose that in most domains each node is directly influenced by at most k others. If we assume n Boolean variables for simplicity, then the amount of information needed to specify each conditional\n",
        "probability table will be at most $2^k$ numbers, and the complete network can be specified by $n2^k$ numbers\n",
        "- The joint distribution contains $2^n$ numbers. (far larger) \n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "- All strucutres garantee x indpendent of z given y except (v structure aka common effect)!!!\n",
        "- Strucutre that garantee it are (chain, common cause, etc.)\n",
        "- D seperation algirithm tells us if two nodes in a Baysian Network are conditionally indpendent given some other varibale\n",
        "- X and Y and conditionally indpendent given z if there are no active paths between them. To check if path is active, break it down into triples along the path and see if the triple is active or inactive\n",
        "- If there is an active path between X and Y then not independent given Z\n",
        "- Paths are non directed\n",
        "- Also if we want to condition or multiple variables we just shade those variables in the network\n",
        "- a path is active if evry triple in it is active\n",
        "\n",
        "- To do inference we can simply do \n",
        "\n",
        "$$argmax_qP(Q=q|e_1, e_2, ..., e_n)$$\n",
        "- inference by enumeration is slow because you have to re create the entire distribution\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian network\": \"a directed graph in which each node is annotated with quantitative probability information\",\n",
        "\"inference\": \"calculate usefull quantity from joint probability distribution\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "07d90b4e-f522-40da-9148-70ca23628973"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n- Full specification of Bayesian network requires:\n- 1. Each node corresponds to a random variable, which may be discrete or continuous.\n- 2. If there is an edge from node X to node Y ,then X is a parent of Y. Graph is a DAG\n- 3. Each node Xi has a conditional probability distribution P(Xi | Parents(Xi)) that quantifies the effect of the parents on the node.\n\n- An edge from X to Y implies that X influences Y\n\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n- Baysian network is a representation of a joint probability distribution\n- It assumes $P(X_i |X_{i-1}, ..., X_1)= P(X_i|Parents(X_i))$ (a big assumption, essentially we create the Bayes net how we want)\n\n- To form a Baysian Network do the following with states $X_1, ..., X_n$\n- Choose a state $X_n$ and determine a minimal set of paretns from $X_1,...X_{n-1}$\n- For each parent draw and edge from the parent to $X_n$\n- Write the conditional Probability $P(X_n|Parents(X_n))$\n\n- Each node is only connected to earlier nodes so cycles dont arise\n\n- Baysian netowrrk is a locally strucutred (sparse) system\n\n- Baysian networks are great at saving space\n- Suppose that in most domains each node is directly influenced by at most k others. If we assume n Boolean variables for simplicity, then the amount of information needed to specify each conditional\nprobability table will be at most $2^k$ numbers, and the complete network can be specified by $n2^k$ numbers\n- The joint distribution contains $2^n$ numbers. (far larger) \n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\n- All strucutres garantee x indpendent of z given y except (v structure aka common effect)!!!\n- Strucutre that garantee it are (chain, common cause, etc.)\n- D seperation algirithm tells us if two nodes in a Baysian Network are conditionally indpendent given some other varibale\n- X and Y and conditionally indpendent given z if there are no active paths between them. To check if path is active, break it down into triples along the path and see if the triple is active or inactive\n- If there is an active path between X and Y then not independent given Z\n- Paths are non directed\n- Also if we want to condition or multiple variables we just shade those variables in the network\n- a path is active if evry triple in it is active\n\n- To do inference we can simply do \n\n$$argmax_qP(Q=q|e_1, e_2, ..., e_n)$$\n- inference by enumeration is slow because you have to re create the entire distribution\n\n\n\n## Module 11 Definitions\n* **Bayesian network** - a directed graph in which each node is annotated with quantitative probability information\n* **Inference** - calculate usefull quantity from joint probability distribution\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "- We want to estimate the probability of a class given parameters. First, create a Bayes Net with the class as perent all paraemters as indidivudal children\n",
        "$$P(Y_c| F_1, F_2, ...F_n) = P(Y=Y_c) * \\\\frac{P(F_1, F_2, ...F_n|Y_c)}{P(F_1, F_2, ...,F_n)}$$\n",
        "\n",
        "- But by bayes net assumption, we can run D sepration to show that $F_1, ..., F_n$ are conditionally independent given $Y$ and so:\n",
        "\n",
        "$$P(Y_c| F_1, F_2, ...F_n) = P(Y=Y_c) * \\\\frac{P(F_1|Y_c) *P(F_2|Y_c) * ...* P(F_n|Y_c)}{P(F_1, F_2, ...,F_n)}$$\n",
        "\n",
        "- So in order to estimate using Naive Baies we need the following\n",
        "- We can use training data to estimate probabilities above but this is prone to overfitting (for example suppose that P(F_1|Y_c) = 0) then $P(Y_c| F_1, F_2, ...F_n) =0$ always! this can't be true\n",
        "- To fix this we use smoothing and regularization\n",
        "\n",
        "- Estimate parameters through empirical estimates of the distrubtion. This should be a maximum liklhihood estimate:\n",
        "$$P_{ML} = \\\\frac{count(x)}{total}$$\n",
        "\n",
        "- This estimate maximizes the liklihood of the data\n",
        "$$L(x, \\\\theta) = \\prod_i^nP_{\\\\theta}(x_i)$$\n",
        "\n",
        "- training data = train\n",
        "- held out data = tune hyperparameters\n",
        "- test data = evaluation\n",
        "\n",
        "- confidence of a classifier given a prediction c and input x is\n",
        "\n",
        "$$confidence = max_cP(c|x)$$\n",
        "\n",
        "- any probabalistic model has confidences (but these may not be true)\n",
        "\n",
        "- Now lets look at perceptron. A perceptron is a single layer of a NN. It takes in an input x and applies\n",
        "\n",
        "$$activation_w(x) = \\sum_{i}w_i * f_i(x) = w * f$$\n",
        "\n",
        "- For multiclass setting. Create a weight vector $w_i$ for each class and do the following\n",
        "\n",
        "$$activation_i = w_i \\cdot f(x)$$\n",
        "$$argmax_i (w_i \\cdot f(x))$$\n",
        "\n",
        "- When doing any computation set weight of the bias equal to 1\n",
        "\n",
        "\n",
        "- Properties of perceptron:\n",
        "- 1. If data is perfectly linearly seprable then the perceptron weights are garanteed to converge (binary case)\n",
        "- 2. The maximum number of mistakes on the training data is related to the degree of seperability. Let k be the number of features and d is the margin (the distance betweeen the postive and negative classes - think SVM) then:\n",
        "$$mistakes < \\\\frac{k}{d^2}$$\n",
        "\n",
        "- Problems with perceptrons:\n",
        "- 1. If data is not linearly seprable then the weights learned might thrash (swing back and forth). To fix this we could consider averaging the weights over time (this is an averaged perceptron)\n",
        "- 2. Even if data is linearly sperable, not all separators are equally good (some better than others). Think minimizing the margin like SVMS\n",
        "- 3. Perceptron's are prone to overtraining (type of overfitting). We fix this by stopping training when there is a dropoff in performance\n",
        "\n",
        "- How to fix thrashing and best sperating hyperplane. Use the MIRA algorithm (margin infused relaxed algorithm) or SVMs\n",
        "\n",
        "- If data is not linearly seprable we can always make it linearly seperable by augmenting it to some higher dimensional space\n",
        "\n",
        "- Perceptrons cannot solve the XOR problem but can solve the XAND problem \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6b08baac-e861-48b3-d34f-fc5383a00a98"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n- We want to estimate the probability of a class given parameters. First, create a Bayes Net with the class as perent all paraemters as indidivudal children\n$$P(Y_c| F_1, F_2, ...F_n) = P(Y=Y_c) * \\frac{P(F_1, F_2, ...F_n|Y_c)}{P(F_1, F_2, ...,F_n)}$$\n\n- But by bayes net assumption, we can run D sepration to show that $F_1, ..., F_n$ are conditionally independent given $Y$ and so:\n\n$$P(Y_c| F_1, F_2, ...F_n) = P(Y=Y_c) * \\frac{P(F_1|Y_c) *P(F_2|Y_c) * ...* P(F_n|Y_c)}{P(F_1, F_2, ...,F_n)}$$\n\n- So in order to estimate using Naive Baies we need the following\n- We can use training data to estimate probabilities above but this is prone to overfitting (for example suppose that P(F_1|Y_c) = 0) then $P(Y_c| F_1, F_2, ...F_n) =0$ always! this can't be true\n- To fix this we use smoothing and regularization\n\n- Estimate parameters through empirical estimates of the distrubtion. This should be a maximum liklhihood estimate:\n$$P_{ML} = \\frac{count(x)}{total}$$\n\n- This estimate maximizes the liklihood of the data\n$$L(x, \\theta) = \\prod_i^nP_{\\theta}(x_i)$$\n\n- training data = train\n- held out data = tune hyperparameters\n- test data = evaluation\n\n- confidence of a classifier given a prediction c and input x is\n\n$$confidence = max_cP(c|x)$$\n\n- any probabalistic model has confidences (but these may not be true)\n\n- Now lets look at perceptron. A perceptron is a single layer of a NN. It takes in an input x and applies\n\n$$activation_w(x) = \\sum_{i}w_i * f_i(x) = w * f$$\n\n- For multiclass setting. Create a weight vector $w_i$ for each class and do the following\n\n$$activation_i = w_i \\cdot f(x)$$\n$$argmax_i (w_i \\cdot f(x))$$\n\n- When doing any computation set weight of the bias equal to 1\n\n\n- Properties of perceptron:\n- 1. If data is perfectly linearly seprable then the perceptron weights are garanteed to converge (binary case)\n- 2. The maximum number of mistakes on the training data is related to the degree of seperability. Let k be the number of features and d is the margin (the distance betweeen the postive and negative classes - think SVM) then:\n$$mistakes < \\frac{k}{d^2}$$\n\n- Problems with perceptrons:\n- 1. If data is not linearly seprable then the weights learned might thrash (swing back and forth). To fix this we could consider averaging the weights over time (this is an averaged perceptron)\n- 2. Even if data is linearly sperable, not all separators are equally good (some better than others). Think minimizing the margin like SVMS\n- 3. Perceptron's are prone to overtraining (type of overfitting). We fix this by stopping training when there is a dropoff in performance\n\n- How to fix thrashing and best sperating hyperplane. Use the MIRA algorithm (margin infused relaxed algorithm) or SVMs\n\n- If data is not linearly seprable we can always make it linearly seperable by augmenting it to some higher dimensional space\n\n- Perceptrons cannot solve the XOR problem but can solve the XAND problem \n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "- Machine learning classifiers require the following\n",
        "- 1. Training corpus of M observations input/output pairs $(x(i) ,y(i)$\n",
        "- 2. A feature representation of the input, $x(i)= [x_1,x_2,...,x_n]$\n",
        "2. A classification function that computes the estimated class $p(y|x)$\n",
        "3. An objective function for learning, involves minimizing\n",
        "error on training examples.\n",
        "4. An algorithm for optimizing the objective function\n",
        "\n",
        "\n",
        "- First lets consider a logistic regression classifier:\n",
        "\n",
        "$$P(y=1|x) = \\\\frac{1}{1+e^{-(w*x + b)}}$$\n",
        "\n",
        "where w is learned weights, x is the input and b is the bias term for each weight. To make a decision we classify a label as 1 if $P(y=1|x)>0.5$ and -1 otherwise\n",
        "\n",
        "- To learn the weights we need to define an objective function (usually Cross Entropy Loss) and an algorithm for optimizing the objective function (Gradient Descent)\n",
        "\n",
        "- We can use MSE loss:\n",
        "\n",
        "$$MSE = 0.5 \\cdot (y_{pred}-y_{true})$$\n",
        "\n",
        "- Cross entropy loss tries to maximize the predicted prbability is the lablel:\n",
        "\n",
        "$$Cross Entropy = y_{pred}^{y_{true}} * (1-y_{pred})^{1-y_{true}}$$\n",
        "$$ = y_{true}log(y_{pred}) + (1-y_{true})log(y_{pred})$$\n",
        "\n",
        "- We want to minimize the loss over all training samples with respect to the weights\n",
        "\n",
        "$$argmin_w -\\sum_i^n y_{true}log(y_{pred}) + (1-y_{true})log(y_{pred})$$\n",
        "\n",
        "- Important note:\n",
        "- For logistic regression, loss function is convex so there are no local minima. \n",
        "- Therefore Gradient descent starting from any point is guaranteed to find the global minimum\n",
        "\n",
        "- stochastistic gradient descemnt updates weights based on a single example. This can cause a lot of fluctuation\n",
        "- Batch training does gradient descent on entire data set (but in efficient)\n",
        "- Minibatch traning takes small batches\n",
        "- We also need to regularize a neural net (this is done through l1 and l2 regularization)\n",
        "\n",
        "- In multiclass logistic regression, use the sofmax classifier. It takes an array of numbers and normalizes so that all are porbabilities that add up to one\n",
        "\n",
        "$$sofmax(z_j) = \\\\frac{e^{z_j}}{\\sum_{i=1}^n e^{z_i}$$\n",
        "\n",
        "- Now look at Neural Networks\n",
        "- threshold activation functions dont work because you cannot find gradients!!\n",
        "- We use a sigmoid activation function (this is good because a small change in weights lead to a small change in the prediction -> function is smooth)\n",
        "- Most common used functions are tanh and relu\n",
        "- \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "459a166a-91ad-48dd-f751-99dc7524e757"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n- Machine learning classifiers require the following\n- 1. Training corpus of M observations input/output pairs $(x(i) ,y(i)$\n- 2. A feature representation of the input, $x(i)= [x_1,x_2,...,x_n]$\n2. A classification function that computes the estimated class $p(y|x)$\n3. An objective function for learning, involves minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function\n\n\n- First lets consider a logistic regression classifier:\n\n$$P(y=1|x) = \\frac{1}{1+e^{-(w*x + b)}}$$\n\nwhere w is learned weights, x is the input and b is the bias term for each weight. To make a decision we classify a label as 1 if $P(y=1|x)>0.5$ and -1 otherwise\n\n- To learn the weights we need to define an objective function (usually Cross Entropy Loss) and an algorithm for optimizing the objective function (Gradient Descent)\n\n- We can use MSE loss:\n\n$$MSE = 0.5 \\cdot (y_{pred}-y_{true})$$\n\n- Cross entropy loss tries to maximize the predicted prbability is the lablel:\n\n$$Cross Entropy = y_{pred}^{y_{true}} * (1-y_{pred})^{1-y_{true}}$$\n$$ = y_{true}log(y_{pred}) + (1-y_{true})log(y_{pred})$$\n\n- We want to minimize the loss over all training samples with respect to the weights\n\n$$argmin_w -\\sum_i^n y_{true}log(y_{pred}) + (1-y_{true})log(y_{pred})$$\n\n- Important note:\n- For logistic regression, loss function is convex so there are no local minima. \n- Therefore Gradient descent starting from any point is guaranteed to find the global minimum\n\n- stochastistic gradient descemnt updates weights based on a single example. This can cause a lot of fluctuation\n- Batch training does gradient descent on entire data set (but in efficient)\n- Minibatch traning takes small batches\n- We also need to regularize a neural net (this is done through l1 and l2 regularization)\n\n- In multiclass logistic regression, use the sofmax classifier. It takes an array of numbers and normalizes so that all are porbabilities that add up to one\n\n$$sofmax(z_j) = \\frac{e^{z_j}}{\\sum_{i=1}^n e^{z_i}$$\n\n- Now look at Neural Networks\n- threshold activation functions dont work because you cannot find gradients!!\n- We use a sigmoid activation function (this is good because a small change in weights lead to a small change in the prediction -> function is smooth)\n- Most common used functions are tanh and relu\n- \n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" \n",
        "- embedd words (ie. assign vector representation to a word)\n",
        "- learn word embeddings through NN\n",
        "- How do we obtain vectors like this\n",
        "- train a neural network to take in k-gram words and predict the next word (input vector is concatentation of word emeddings of k grams)\n",
        "\n",
        "- Neural Language models have several advantages over n-gram LMs:\n",
        "- 1. They don’t need smoothing\n",
        "- 2. They can handle much longer histories.\n",
        "- 3. They can generalize over contexts of similar words.\n",
        "- 4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
        "- 5. They produce word embeddings which is great\n",
        "\n",
        "- Skip Gram training data\n",
        "- We are interested in determining the liklihood that a word t appears next to a context word\n",
        "- To do this we can compute \n",
        "$$similarity = t \\cdot c$$\n",
        "$$P(+| t,c) = \\\\frac{1}{1+e^{-similarity}}$$\n",
        "\n",
        "- Now we can further assume that context words are independent and so:\n",
        "\n",
        "$$P(+|t, c_{1:k}) = \\prod_{i=1}^k\\\\frac{1}{1+e^{-t \\cdot c_i}}$$\n",
        "\n",
        "- Now how do we get the embeddings for c and t:\n",
        "- We can obtain those using the skip-gram algorithm \n",
        "\n",
        "- 1. Treat the target word and a neighboring context\n",
        "word as positive examples.\n",
        "- 2. Randomly sample other words in the lexicon to get\n",
        "negative samples\n",
        "- 3. Use logistic regression to train a classifier to\n",
        "distinguish those two cases\n",
        "- 4. Use the weights as the embeddings\n",
        "\n",
        "- First we consider a target word and the k context words around it\n",
        "- We will also sample some random not realted words which will be used as noise words\n",
        "- Sampling can be done uniformly but generally it is better to sample according to the following probability\n",
        "\n",
        "$$P_a(w) = \\\\frac{count(w)^a}{\\sum_wcount(w)^a}$$\n",
        "\n",
        "- Now during training we consider both noise words and context words. We look to minimize the following loss function\n",
        "\n",
        "$$L = \\sum_{c_i \\in C} log[P(+|t, c_i)] + \\sum_{n_i \\in N}log[P(-|t, n_i)]$$\n",
        "\n",
        "- Once we have the data, we can just run logistic regression to learn the weights\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "86030ce9-7d26-4419-fd02-56fa1a37b439"
      },
      "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\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \n- embedd words (ie. assign vector representation to a word)\n- learn word embeddings through NN\n- How do we obtain vectors like this\n- train a neural network to take in k-gram words and predict the next word (input vector is concatentation of word emeddings of k grams)\n\n- Neural Language models have several advantages over n-gram LMs:\n- 1. They don’t need smoothing\n- 2. They can handle much longer histories.\n- 3. They can generalize over contexts of similar words.\n- 4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n- 5. They produce word embeddings which is great\n\n- Skip Gram training data\n- We are interested in determining the liklihood that a word t appears next to a context word\n- To do this we can compute \n$$similarity = t \\cdot c$$\n$$P(+| t,c) = \\frac{1}{1+e^{-similarity}}$$\n\n- Now we can further assume that context words are independent and so:\n\n$$P(+|t, c_{1:k}) = \\prod_{i=1}^k\\frac{1}{1+e^{-t \\cdot c_i}}$$\n\n- Now how do we get the embeddings for c and t:\n- We can obtain those using the skip-gram algorithm \n\n- 1. Treat the target word and a neighboring context\nword as positive examples.\n- 2. Randomly sample other words in the lexicon to get\nnegative samples\n- 3. Use logistic regression to train a classifier to\ndistinguish those two cases\n- 4. Use the weights as the embeddings\n\n- First we consider a target word and the k context words around it\n- We will also sample some random not realted words which will be used as noise words\n- Sampling can be done uniformly but generally it is better to sample according to the following probability\n\n$$P_a(w) = \\frac{count(w)^a}{\\sum_wcount(w)^a}$$\n\n- Now during training we consider both noise words and context words. We look to minimize the following loss function\n\n$$L = \\sum_{c_i \\in C} log[P(+|t, c_i)] + \\sum_{n_i \\in N}log[P(-|t, n_i)]$$\n\n- Once we have the data, we can just run logistic regression to learn the weights\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "70db2069-b6eb-4b61-e138-07bdaf4308fd"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- environment assumed to be episodic in decision making theory\n- non deterministic, partially observable environments\n- Agent might not know current state so we let Result(a), be a random variable whos outcomes\nare all possible states\n- Probability of outcome s given action a and observation e is P(s | a, e)\n- Epected utility of an action is average utility over all outcomes weighted by thier probability\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- A lottery with outcomes $S_1, S_2, ..., S_n$ and probablities of ouctomes $p_1, p_2, ..., p_n$ can be written as $L = [S_1, p_1, S2_, p2, ..., S_n, p_n]$\n- An outcome $S_i$ can be an atomic state or another lottery\n- Reasonal preference should obey six axioms\n\n- Orderability: $A \\geq B$, $A \\leq B$ or $A = B$ must hold\n- Transitivity: If $A > B$ and $B>C$ then it must be $A > C$\n- Continuity: If some lottery B is between A and C in preference, then there is some\nprobability p for which the rational agent will be indifferent between getting B for sure\nand the lottery that yields A with probability p and C with probability 1 − p. In other words\n\n$$A \\geq B \\geq C \\implies [A, p, C, 1-p] = B$$\n\n- Substitutability: If an agent is indiferent between two lotteries A and B then the agent is indifferent,\n between two more complex lotteries that are the same except that B is substituted in one of them \n\n $$A = B \\implies [A, p, C, 1-p] = [B, p, C, 1-p]$$\n\n - Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B.\nIf an agent prefers A to B, then the agent must prefer the lottery that has a higher\nprobability for A (and vice versa)\n\n$$A > B \\implies [A, p, B, 1-p] > [A, q, B, 1-q], p \\geq q $$\n\n- Decomposability: Compounded loterries can be resolved into simpler ones using the law of probability \n\n- If these axioms are violated by an agent then it can be shown that this agent is not rational\n\n- If an agents preferences obey the axioms of utility then there exits a utility function the represent the preferences\nof that agent\n\n- Expected utility of lottery L is the sum of each outcomes utility weighted by the probability it occurs\n\n$$U(L) = \\sum_iU(S_i) *p_i$$\n\n- Expected utility of compounded lotteries can be copmuted through decomposability \n\n- Multiple utility functions exist that can capture there preferences of an agent\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- usually there is no scale for utility function but we can make one by fixing the values of the worst and best outcomes\n- Let $u_b$ be the expected utility in the best case, let $u_w$ be the expected utility of the worst possible outcome\n- A normalized utility scale has $u_b = 1$ and $u_w = 0$ \n- We can asses the utility of some other state $S$ by asking the agent to choose between S and $[u_b, p, u_w, 1-p]\n- If utilities are normalized, the utility of S is given by p\n- we are really working with estimates EU(a|e) of the true expected utility. We will assume, kindly perhaps, that the\nUNBIASED estimates are unbiased, that is, the expected value of the error, E(EU!(a|e) − EU (a|e))) =0\n- real outcome will usually be significantly worse than estimated even though estimator is unbiased \n- This is because we favor overestimates so this creates bias. As more utilities are considered bias grows\n- The phenomenon above is known as optimizers curse\n- framing effect, the wording of a decision probelm can have a great impact on agent preferences\n\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- we need to consider utility in sequential decision probelms\n- quality of a policy is measured by expected utility of the possible environment histories generated by that policy\n- optimal policy for a finite horizon is non stationary\n- With no fixed time limit no reason to behave differently in the same state at different times\n- Optimal action depends only on the current state, and the optimal policy is stationary\n- Assume agent's preferences between state sequences are stationary\n- ie. if there are two sequences $[s_1, s_2, ..., s_n]$ and $[s'_1, s'_2, ..., s'_n]$ and $s_1 = s'_1$, then the two sequences should be preference ordered\nthe same way as $[s_2, ..., s_n]$ and $[s'_2, ..., s'_n]$ \n- Stationarity leads to a few important conclusions\n- Additive rewards: utility of a state sequence $[s_1, s_2, ..., s_n]$ is $R(s_0) + R(s_1) + ... R(s_n)$\n- Discounted rewards: Utility of a state sequence $[s_1, s_2, ..., s_n]$ is $R(s_0) + yR(s_1) + ... y^{n-1}R(s_n)$. Where $y$ is a discount factor between 0 and 1. If $y$ is \nclose to zero then future rewards matter less and less to the current reward\n- This leads to to two further conclusions:\n- With discounted rewards, the utility of infinite sequence is finite and is further bounded by $R_{max}$\n$$U([s_1, s_2, ..., s_n]) = \\sum_{t=0}y^tR(s_t) \\leq \\sum_{t=0}y^t R_{max} = R_{max}/(1-y)$$\n- infinite series can be compared based on average reward per time step\n- Compare policies based on the expected utility from executing them\n- The optimal policy is therefore \n\n$$\\pi^* = argmax_{\\pi}U^{\\pi}(s)$$\n- This is the optimal policy starting at state $s$\n- Discounted utilities with infinite horizons means that the optimal policy is independnet of starting state\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- The Bellman Equation is Defined as \n$$U(s) = R(s) + max_{a \\in A}\\sum_{s'}P(s'; a, s) * U(s')$$\n\n- From this equation we can infer the value iteration algorithm \n- The iteration step, called the Bellman update, is as follows:\n\n$$U_{i+1} = R(s) + max_{a \\in A}\\sum_{s'}P(s'; a, s) * U_i(s')$$\n- The value iteration algorithm is shown in extra hand notes\n- If we apply the Bellman update infinitely, we are garanteed to reach equilibrium, the solutions are unique\n- This algorithm propagates information through stae space\n- Value iteration can be shown to converge through contraction - a function of one argument that, when applied to\ntwo different inputs in turn, produces two output values that are “closer together\" (example of this is division by 2)\n- A contraction has only one fixed point; if there were two fixed points they would not\nget closer together when the function was applied, so it would not be a contraction.\n- When the function is applied to any argument, the value must get closer to the fixed\npoint so repeated application of a contraction always reaches the fixed point in the limit.\n- Bellman update is a contraction by a factor of γ on the space of utility vectors. Therefore Bellman iteration always converges to a unique solution when y< 1\n- Value iteration also converges exponenentially in $y$\n\n\n## Module 8 Lecture Notes\n\nMDP needs:\n- A set of states $s \\in S$\n- A set of actions $a \\in A$\n- A transition function $T(s, a, s’)$\n- Probability that executing action a in s will lead to s’ $P(s’ | s, a)$\n- The probability is called the model\n- A reward function $R(s, a, s’)$\n- An initial state $s0$\n\n- Time complexity of each value iteration is O(S^2 * A)\n\n\n\n## Module 8 Definitions\n* **Decision theory** - choosing among actions based on the desirability of their immediate outcomes\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n* **Utility function** - maps lotteries to real numbers\n* **Principle of maximum expected utility meu** - rational agent should choose action that maximizes expected uitlity\n* **Lottery** - set of outcomes for each action\n* **Value function/ ordinal utilty** -  We care about the ordering of outcomes in terms of preference not the number\n* **Preference elicitation** - presenting choices to an agent to determine preferences\n* **Normalized utilities** - Use a scale from 0 to 1\n* **Normative theory** - describes how agent should act\n* **Descriptive theory** - describes how agents should act\n* **Certainty effect** - people are attracted to gains that are certain\n* **Markovian** - probability of reaching next state only depends on current state\n* **Environment history** - sequence of states the agent was in\n* **Markov decision process** - sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\n* **Policy** - a specification of what an agent should do at any state of an MDP\n* **Optimal policy** - policy that yeilds the highest expected utility\n* **Proper policy** - policy garanteed to reach a terminal state\n* **Value iteration** - algorithm for calculating optimal policy\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- Want to create policy iteration algorithm. Intuition is that if one action is better than all others, than the magnitute by which it differs need not precise\n- Policy iterationa algorithm works with two steps:\n1) Policy evaluation: given a policy $\\pi_i$, calculate $Ui = U^{\\pi_i}$ , the utility of each state if πi POLICY EVALUATION\nwere to be executed.\n2) Policy imporovement: Calculate a new MEU policy $\\pi_{i+1}$, using one-step look-ahead  based on $U_i$\n- Algorithm terminates when policy imporvement yeilds no changes in the utilities\n- This structure simplifies the Bellman equation to\n\n$$U_i(s) = R(s) + \\sum_{s'}P(s'; \\pi_i(s), s) * U(s')$$\n- Since max operator is removed, the equations are now linear and the Utility update can be solved in O(N^3) time where n is the number of states\n- Policy iteration algorithm is in the doc\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- A utility-based agent learns a utility function on states and uses it to select actions that\nmaximize the expected outcome utility.\n- A Q-learning agent learns an action-utility function, or Q-function, giving the exQ-FUNCTION pected utility of taking a given action in a given state.\n- A reflex agent learns a policy that maps directly from states to actions.\n- \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n- Direct Evaluation. Sample in the space by doing trial runs and calculate the utility of a state through discounting. In the end avaerage all samples to estimate \nutility for a particular state. With infinite samples this approaches the true value\n- Direct Evaluation converges very slowsly because it doesn't take advanatage of the relationship between state and actions\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n- Offline planning: determine all quantities through computation. Need to know the details of the MDP. Do not actually play the game!\n- Online learning: we don't plan the future\n- Reinforcement learning : Receive feedback in the form of rewards. Agent’s utility is defined by the reward function and act so as to maximize expected rewards\n- Context: Assume an MDP where we dont know T (the transition model) and R the rewards\n- So we first start exploring with a fixed policy $\\pi$ - this is online learning we are actually taking actions in the environment\n\n- Direct Evaluation: Act according to $\\pi$. Every time you visit a state, write down what the sum of discounted rewards turned out to be\nAverage those samples.\n- Direct Evaluation eventually computes correct average values, but is ineffcient and needs to be run individually for everys state\n- Use Policy Iteration instead of Direct Evaluation!!!\n$$V_{k+1}^{\\pi} = \\sum_{s'}T(s, \\pi(s), s')[R(s, \\pi(s), s') + V_k^{\\pi}(s')]$$\n$$V_{0}^{\\pi} = 0$$\n\n- But we dont know the transition model and rewards so we can take samples and average them.\n$$sample= R(s, a, s') + yV(s')$$\n$$V^{\\pi}(s) = (1-a)V^{\\pi}(s) + a*sample$$\n$$V^{\\pi}(s) = V^{\\pi}(s) + (sample - V^{\\pi}(s))$$\n\n- This form of update results in an exponential moving average:\n\n$$x_n^{mean} = (1-a)x_{n-1}^{mean} + ax_n$$\n$$x_n^{mean} = \\frac{x_n + (1-a)x_{n-1} + (1-a)^2x_{n-2} + ...}{1 + (1-a) + (1-a)^2 + ...}$$\n\n- decreasing leraning rate gives converging averages\n- This is great but we don't have the transition model (probability of ending up in s' by taking action a from state s). So we need another approach.\nSolution is to infer Q values instead of actual values (values of Q states ) to make things model free\n\n- How do we do Q learning. The equation mirrors the bellman update\n\n$$Q_{k+1}(s,a) = \\sum_{s'}T(s, a, s')[R(s, a, s') + max_a'Q_k(s', a')]$$\n\n- This can be learned by sampling \n- 1. Recieve a sample (s, a, s', r)\n- 2. Define the sample estimate to be $sample = R(s,a,s') + y * max_a(Q(s',a))$\n- 3. Update Q value: $Q_{i+1}(s,a) = (1-a)Q_i(s,a) + a * sample$\n\n- The optimal policy ends up being $\\pi*(s) = argmax_a Q(s,a)$\n\n- Q learning converges to optimal policy even if acting suboptimally (but you have to explore enough and make the learning rate a small enough)\n \n- In order to sample well so we must incorporate exploration. Therefore with some probability e choose a random action in a state\n- But this is not best because it might be better to explore areas who' badness is not established \n- Define $f(u,n) = u + \\frac{k}{n}$ where k is a constant, n is the nunber of times visited and u is the utility \n- Agument the q values by factor $Q(s,a)' = f(Q(s,a), n)$. This means that the modified Q update is \n\n$$Q_i(s,a) = R(s,a s')$$\n\n- Regret caputures the idea that we are \"optimally\" learning (ie. not wasting time making mistakes)\n- Regret can be defined as the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n- Random exploration has a higher regre than other exploration functions\n\n- Aproximate Q Learning: In a realistic environment we cannot know every single state (example driving a car)\n- So we want to generalize by learning about a small subset of states and applying to new situations\n- We can write a Q function to estimate the Q value based on some percepts from the environment\n\n$$Q(s,a) = w_1*f_1(s) + w_2*f_2(s) + ... + w_k*f_k(s)$$\n\n- Without applying any Neural Net to this, we can reformat Q Learning to be:\n- 1. transition = (s, a, s', r)\n- 2. difference $[r + max_{a'}Q(s',a')] - Q(s,a)$\n- 3. update: $Q(s,a) = Q(s,a) - a*difference$\n- 4. update: $w_i = w_i + a * difference * f_i(s,a)$\n\n- The intutiion is :  if something unexpectedly bad happens, blame the features that were on:\ndisprefer all states with that state’s features\n \n\n## Module 9 Definitions\n* **Reinforcement** - signal to tell agent how they are doing\n* **Passive learning** - agent’s policy is fixed and the task is to learn the utilities of states\n* **Active learning** - agent learns wht to do (some policy)\n* **Off policy learning** - can achieve optimal policy regardless of the agents actions\n* **Regret** - measure of the total mistake cost\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n- no rational agent can have beliefs that violate the axioms of probability\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n \n\n## AIMA Chapter 12.4 Independence\n \n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n \n- natural language models should be defined as a probability distribution over sentences\n- A model of the probability distribution of n-letter sequences is thus called an n-gram model\n- n gram models can also be distributions over words, syllabules etc.\n- n gram model is defined as a Markov Chain of order n-1 (ie. the next character depends on the n-1 characters preceeding it!!)\n- We can train n gram models on multiple languages. Then, when given an input sequence, we can estimate which languge it comes from by the following\n\n$$L = argmax_LP(L) * P(c_1:c_n|L)$$\n\n- Difficulty with n gram models is that they are only an estimate of the true probabililty distribtuion (ie. just because we dont see the word http in our sample does not mean\nwe should estimate its probability to be 0)\n- Thus we adjust the probability of low frequency count instances through smoothing\n- Different ways of smoothing include:\n- 1. Adding $\\frac{1}{n + 2}$ to each probability (assume if we took two more samples we would see our instance)\n- 2. Laplace Smoothing\n- 3. Interpolation Smoothing: $P(c_i|c_{i-1}, c_{i-2}) = \\lambda_1 P(c_i|c_{i-1}, c_{i-2}) + \\lambda_2P(c_i|c_{i-1}) + \\lambda_3 * P(c_i|c_{i-1})$\n\n- To determine best ngram and smoothing use cross validation \n- perplexity = $P(c_i|c_1:c_n)^{-\\frac{1}{n}}$\n\n- We can apply n gram models to words but more difficult (new words could come up, number of possible words is far larger, etc.)\n- To handle unkown words we can just add a \"unkown\" placeholder \"UKN\" in our vocab\n\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- To estimate the probability of a sequence of words $w_1, w_2, ..., w_n$ we can use chaining\n\n$$P(w_1,..,w_n) = P(w_n|w_{n-1}...w_1) * P(w_{n-1}|w_{n-2}...w_1) * ... * P(w_1))$$$\n\n- n grams allow us to limit scope to a few preceding words so that we can reasonable estimate the probabilities above\n- we evaluate the performance of NLP models by test set, performance is evaluated by whichever model assigns higher probability to the test set\n\n- perplexity is approximately the branching factor of the vocabulary\n- increasing the number of grams decreases perplexity \n- perplexity of two language models is comparable only if the use nearly identical vocabularies\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n \n- Laplace Smoothing (adds a value of one by each count and increases the total by V (the size of the vocabulary)):\n\n$$P(w_i) = \\frac{w_i + 1}{N + V}$$\n\n- To do discounting, consider an adjusted count $c*$\n$$c* = (c_i + 1)\\frac{N}{N + V}$$\n- No this means that the ratio of discounted counts to original counts is:\n\n$$d = \\frac{c*}{c}$$\n\n- With this we show that too much probability mass is moved to zero count instances\n\n- We can change by doing \"Add K smoothing\" (adding k instead of 1) but that also fails often (can optimize during training)\n- Backoff and Interpolation are two other techniques to shift probability mass to zero instances\n- For Backoff, if we have zero evidence of $P(w_n|w_{n-1}...w_1)$ we estimate its probability as $P(w_n|w_{n-2}...w_1)$ and keep decreasing grams until probability is non zero\n- For Backoff we need to discount the mass of higher order n grams to save mass for lower order n grams. Otherwise, too much mass is shifted to zero evidence instances and models fail\n- Backoff with discounting is also known as Katz backoff\n- For Iterpoloation we mix and match different n grams\n$$P(w_n|w_{n-1}, w_{n-2}) = \\lambda_0 * P(w_n) + \\lambda_1*P(w_n|w_{n-1}) + \\lambda_2 *P(w_n|w_{n-1}, w_{n-2})$$\n- One of the best n gram smoothing interpolations is Kneser-Ney Smoothing\n\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Language** - a set of strings\n* **N gram** - a sequence of n words\n* **Corpus** - a body of text\n* **Perplexity** - way of caputring the probability of a sequence\n* **Probability** - provides a way of summarizing the uncertainty that comes from our laziness and ignorance\n* **Sample space** - set of all possible worlds\n* **Proposition** - event or outcome from a sample space\n* **Evidence** - information to consider when gauging probability (essentially given that)\n* **Language models** - models that assign probabilities to sequences of words\n* **Discounting** - a way of smoothing by lowering non zero counts and increasing the prbability mass of zero counts\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n- Full specification of Bayesian network requires:\n- 1. Each node corresponds to a random variable, which may be discrete or continuous.\n- 2. If there is an edge from node X to node Y ,then X is a parent of Y. Graph is a DAG\n- 3. Each node Xi has a conditional probability distribution P(Xi | Parents(Xi)) that quantifies the effect of the parents on the node.\n\n- An edge from X to Y implies that X influences Y\n\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n- Baysian network is a representation of a joint probability distribution\n- It assumes $P(X_i |X_{i-1}, ..., X_1)= P(X_i|Parents(X_i))$ (a big assumption, essentially we create the Bayes net how we want)\n\n- To form a Baysian Network do the following with states $X_1, ..., X_n$\n- Choose a state $X_n$ and determine a minimal set of paretns from $X_1,...X_{n-1}$\n- For each parent draw and edge from the parent to $X_n$\n- Write the conditional Probability $P(X_n|Parents(X_n))$\n\n- Each node is only connected to earlier nodes so cycles dont arise\n\n- Baysian netowrrk is a locally strucutred (sparse) system\n\n- Baysian networks are great at saving space\n- Suppose that in most domains each node is directly influenced by at most k others. If we assume n Boolean variables for simplicity, then the amount of information needed to specify each conditional\nprobability table will be at most $2^k$ numbers, and the complete network can be specified by $n2^k$ numbers\n- The joint distribution contains $2^n$ numbers. (far larger) \n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\n- All strucutres garantee x indpendent of z given y except (v structure aka common effect)!!!\n- Strucutre that garantee it are (chain, common cause, etc.)\n- D seperation algirithm tells us if two nodes in a Baysian Network are conditionally indpendent given some other varibale\n- X and Y and conditionally indpendent given z if there are no active paths between them. To check if path is active, break it down into triples along the path and see if the triple is active or inactive\n- If there is an active path between X and Y then not independent given Z\n- Paths are non directed\n- Also if we want to condition or multiple variables we just shade those variables in the network\n- a path is active if evry triple in it is active\n\n- To do inference we can simply do \n\n$$argmax_qP(Q=q|e_1, e_2, ..., e_n)$$\n- inference by enumeration is slow because you have to re create the entire distribution\n\n\n\n## Module 11 Definitions\n* **Bayesian network** - a directed graph in which each node is annotated with quantitative probability information\n* **Inference** - calculate usefull quantity from joint probability distribution\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n- We want to estimate the probability of a class given parameters. First, create a Bayes Net with the class as perent all paraemters as indidivudal children\n$$P(Y_c| F_1, F_2, ...F_n) = P(Y=Y_c) * \\frac{P(F_1, F_2, ...F_n|Y_c)}{P(F_1, F_2, ...,F_n)}$$\n\n- But by bayes net assumption, we can run D sepration to show that $F_1, ..., F_n$ are conditionally independent given $Y$ and so:\n\n$$P(Y_c| F_1, F_2, ...F_n) = P(Y=Y_c) * \\frac{P(F_1|Y_c) *P(F_2|Y_c) * ...* P(F_n|Y_c)}{P(F_1, F_2, ...,F_n)}$$\n\n- So in order to estimate using Naive Baies we need the following\n- We can use training data to estimate probabilities above but this is prone to overfitting (for example suppose that P(F_1|Y_c) = 0) then $P(Y_c| F_1, F_2, ...F_n) =0$ always! this can't be true\n- To fix this we use smoothing and regularization\n\n- Estimate parameters through empirical estimates of the distrubtion. This should be a maximum liklhihood estimate:\n$$P_{ML} = \\frac{count(x)}{total}$$\n\n- This estimate maximizes the liklihood of the data\n$$L(x, \\theta) = \\prod_i^nP_{\\theta}(x_i)$$\n\n- training data = train\n- held out data = tune hyperparameters\n- test data = evaluation\n\n- confidence of a classifier given a prediction c and input x is\n\n$$confidence = max_cP(c|x)$$\n\n- any probabalistic model has confidences (but these may not be true)\n\n- Now lets look at perceptron. A perceptron is a single layer of a NN. It takes in an input x and applies\n\n$$activation_w(x) = \\sum_{i}w_i * f_i(x) = w * f$$\n\n- For multiclass setting. Create a weight vector $w_i$ for each class and do the following\n\n$$activation_i = w_i \\cdot f(x)$$\n$$argmax_i (w_i \\cdot f(x))$$\n\n- When doing any computation set weight of the bias equal to 1\n\n\n- Properties of perceptron:\n- 1. If data is perfectly linearly seprable then the perceptron weights are garanteed to converge (binary case)\n- 2. The maximum number of mistakes on the training data is related to the degree of seperability. Let k be the number of features and d is the margin (the distance betweeen the postive and negative classes - think SVM) then:\n$$mistakes < \\frac{k}{d^2}$$\n\n- Problems with perceptrons:\n- 1. If data is not linearly seprable then the weights learned might thrash (swing back and forth). To fix this we could consider averaging the weights over time (this is an averaged perceptron)\n- 2. Even if data is linearly sperable, not all separators are equally good (some better than others). Think minimizing the margin like SVMS\n- 3. Perceptron's are prone to overtraining (type of overfitting). We fix this by stopping training when there is a dropoff in performance\n\n- How to fix thrashing and best sperating hyperplane. Use the MIRA algorithm (margin infused relaxed algorithm) or SVMs\n\n- If data is not linearly seprable we can always make it linearly seperable by augmenting it to some higher dimensional space\n\n- Perceptrons cannot solve the XOR problem but can solve the XAND problem \n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n- Machine learning classifiers require the following\n- 1. Training corpus of M observations input/output pairs $(x(i) ,y(i)$\n- 2. A feature representation of the input, $x(i)= [x_1,x_2,...,x_n]$\n2. A classification function that computes the estimated class $p(y|x)$\n3. An objective function for learning, involves minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function\n\n\n- First lets consider a logistic regression classifier:\n\n$$P(y=1|x) = \\frac{1}{1+e^{-(w*x + b)}}$$\n\nwhere w is learned weights, x is the input and b is the bias term for each weight. To make a decision we classify a label as 1 if $P(y=1|x)>0.5$ and -1 otherwise\n\n- To learn the weights we need to define an objective function (usually Cross Entropy Loss) and an algorithm for optimizing the objective function (Gradient Descent)\n\n- We can use MSE loss:\n\n$$MSE = 0.5 \\cdot (y_{pred}-y_{true})$$\n\n- Cross entropy loss tries to maximize the predicted prbability is the lablel:\n\n$$Cross Entropy = y_{pred}^{y_{true}} * (1-y_{pred})^{1-y_{true}}$$\n$$ = y_{true}log(y_{pred}) + (1-y_{true})log(y_{pred})$$\n\n- We want to minimize the loss over all training samples with respect to the weights\n\n$$argmin_w -\\sum_i^n y_{true}log(y_{pred}) + (1-y_{true})log(y_{pred})$$\n\n- Important note:\n- For logistic regression, loss function is convex so there are no local minima. \n- Therefore Gradient descent starting from any point is guaranteed to find the global minimum\n\n- stochastistic gradient descemnt updates weights based on a single example. This can cause a lot of fluctuation\n- Batch training does gradient descent on entire data set (but in efficient)\n- Minibatch traning takes small batches\n- We also need to regularize a neural net (this is done through l1 and l2 regularization)\n\n- In multiclass logistic regression, use the sofmax classifier. It takes an array of numbers and normalizes so that all are porbabilities that add up to one\n\n$$sofmax(z_j) = \\frac{e^{z_j}}{\\sum_{i=1}^n e^{z_i}$$\n\n- Now look at Neural Networks\n- threshold activation functions dont work because you cannot find gradients!!\n- We use a sigmoid activation function (this is good because a small change in weights lead to a small change in the prediction -> function is smooth)\n- Most common used functions are tanh and relu\n- \n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \n- embedd words (ie. assign vector representation to a word)\n- learn word embeddings through NN\n- How do we obtain vectors like this\n- train a neural network to take in k-gram words and predict the next word (input vector is concatentation of word emeddings of k grams)\n\n- Neural Language models have several advantages over n-gram LMs:\n- 1. They don’t need smoothing\n- 2. They can handle much longer histories.\n- 3. They can generalize over contexts of similar words.\n- 4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n- 5. They produce word embeddings which is great\n\n- Skip Gram training data\n- We are interested in determining the liklihood that a word t appears next to a context word\n- To do this we can compute \n$$similarity = t \\cdot c$$\n$$P(+| t,c) = \\frac{1}{1+e^{-similarity}}$$\n\n- Now we can further assume that context words are independent and so:\n\n$$P(+|t, c_{1:k}) = \\prod_{i=1}^k\\frac{1}{1+e^{-t \\cdot c_i}}$$\n\n- Now how do we get the embeddings for c and t:\n- We can obtain those using the skip-gram algorithm \n\n- 1. Treat the target word and a neighboring context\nword as positive examples.\n- 2. Randomly sample other words in the lexicon to get\nnegative samples\n- 3. Use logistic regression to train a classifier to\ndistinguish those two cases\n- 4. Use the weights as the embeddings\n\n- First we consider a target word and the k context words around it\n- We will also sample some random not realted words which will be used as noise words\n- Sampling can be done uniformly but generally it is better to sample according to the following probability\n\n$$P_a(w) = \\frac{count(w)^a}{\\sum_wcount(w)^a}$$\n\n- Now during training we consider both noise words and context words. We look to minimize the following loss function\n\n$$L = \\sum_{c_i \\in C} log[P(+|t, c_i)] + \\sum_{n_i \\in N}log[P(-|t, n_i)]$$\n\n- Once we have the data, we can just run logistic regression to learn the weights\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}