{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Template_for CIS521_midterm_2_notes.ipynb adlı not defterinin kopyası",
      "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": "a156ff49-6618-4417-d7a7-fb77fc4309d7"
      },
      "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": 63,
      "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": "0551b48b-b323-4c0d-ff6d-70e427c9b223"
      },
      "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": 64,
      "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": 65,
      "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 = \"\"\" We begin with an agent that, like all agents, has to make a decision. It has available some\n",
        "actions $a$. There may be uncertainty about the current state, so we’ll assume that the agent\n",
        "assigns a probability $P(s)$ to each possible current state s. There may also be uncertainty\n",
        "about the action outcomes; the transition model is given by $P(s'|s,a)$, the probability that action a in state s reaches state s'. \n",
        "Because we’re primarily interested in the outcome s', we’ll also use the abbreviated notation $P(RESULT(a)=s')$, the probability of reaching s' by doing\n",
        "a in the current state, whatever that is. \\n \n",
        " The agent’s preferences are captured by a <b>utility function</b>, $U(s)$, which assigns a single number to express the \n",
        "desirability of a state. The <b>expected utility</b> of an action given the evidence, EU(a), is just the\n",
        "average utility value of the outcomes, weighted by the probability that the outcome occurs: \\n\n",
        "$EU(a) = \\sum_{s'}P(\\\\textnormal{RESULT}(a)=s')U(s')$ \\n\n",
        "The principle of <b>maximum expected utility</b> (MEU) says that a rational agent should choose\n",
        "the action that maximizes the agent’s expected utility.\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" \n",
        "<b>Orderability</b>: Given any two lotteries, a rational agent must either prefer one or else\n",
        "rate them as equally preferable. That is, the agent cannot avoid deciding. As noted on\n",
        "page 412, refusing to bet is like refusing to allow time to pass. \\n\n",
        "Exactly one of $(A \\succ B), (B \\succ A), or (A \\sim B)$ holds. \\n\n",
        "\n",
        "<b>Transitivity</b>: Given any three lotteries, if an agent prefers A to B and prefers B to C,\n",
        "then the agent must prefer A to C. \\n\n",
        "$(A \\succ B) \\wedge (B \\succ C) \\implies (A \\succ C)$. \\n\n",
        "\n",
        "<b>Continuity</b>: 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. \\n\n",
        "$A \\succ B \\succ C ⇒ \\exists p [p,A; 1− p,C] \\sim B$ \\n\n",
        "\n",
        "\n",
        "<b>Substitutability</b>: If an agent is indifferent between two lotteries A and B, then the\n",
        "agent is indifferent between two more complex lotteries that are the same except that\n",
        "B is substituted for A in one of them. This holds regardless of the probabilities and the\n",
        "other outcome(s) in the lotteries. \\n\n",
        "$A \\sim B ⇒ [p,A; 1− p,C] \\sim [p,B; 1− p,C]$ \\n\n",
        "\n",
        "<b>Monotonicity</b>: Suppose two lotteries have the same two possible outcomes, A and\n",
        "B. 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 \\sim B \\implies (p > q \\Leftrightarrow [p,A; 1− p,B] \\succ [q,A; 1−q,B])$ \\n\n",
        "\n",
        "<b>Decomposability</b>: Compound lotteries can be reduced to simpler ones using the laws \n",
        "of probability. \\n\n",
        "$[p,A; 1− p,[q,B; 1−q,C]] \\sim [p,A; (1− p)q,B; (1− p)(1−q),C]$ \\n\n",
        "\n",
        "<b>Existence of Utility Function</b>: If an agent’s preferences obey the axioms of utility, then\n",
        "there exists a function U such that $U(A) > U(B)$ if and only if A is preferred to B, and\n",
        "$U(A) = U(B)$ if and only if the agent is indifferent between A and B. \\n\n",
        "\n",
        "<b>Expected Utility of a Lottery</b>: The utility of a lottery is the sum of the probability of\n",
        "each outcome times the utility of that outcome: \\n\n",
        "$U([p_1,S_1;\\ldots; p_n,S_n]) = \\sum_i p_i U(S_i)$ \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"The transition model (or just “model,” when the meaning is clear) de\u0002scribes the outcome of each action in each state. Here, the outcome is stochastic, so we write\n",
        "$P(s'|s,a)$ for the probability of reaching state s' if action a is done in state s. (Some authors write $T(s,a,s')$ for the transition model.) \n",
        "We will assume that transitions are <b>Markovian</b>: the probability of reaching s' from s depends only on s and not on the history of earlier states. \\n\n",
        "Because the decision problem is sequential, the utility function will depend\n",
        "on a sequence of states and actions—an environment history—rather than on a single state.\n",
        "Later in this section, we investigate the nature of utility functions on histories; for now, we\n",
        "simply stipulate that for every transition from s to s' via action a, the agent receives a reward Reward $R(s,a,s')$. \\n\n",
        "To sum up: a sequential decision problem for a fully observable, stochastic environment\n",
        "with a Markovian transition model and additive rewards is called a <b>Markov decision process</b>,\n",
        "or MDP, and consists of a set of states (with an initial state $s_0$); a set ACTIONS(s) of actions\n",
        "in each state; a transition model $P(s'|s,a)$; and a reward function $R(s,a,s')$. \\n\n",
        "No fixed action sequence can solve the problem, because the agent might end up in a state other than the\n",
        "goal. Therefore, a solution must specify what the agent should do for any state that the agent\n",
        "might reach. A solution of this kind is called a <b>policy</b>. \\n\n",
        "Each time a given policy is executed starting from the initial state, the stochastic nature\n",
        "of the environment may lead to a different environment history. The quality of a policy is\n",
        "therefore measured by the expected utility of the possible environment histories generated\n",
        "by that policy. An <b>optimal policy</b> is a policy that yields the highest expected utility. \\n\n",
        "A <b>finite horizon</b> means that there is a fixed time N after which nothing Infinite horizon\n",
        "matters—the game is over, so to speak. \\n\n",
        "A policy that depends on the time is called <b>nonstationary</b>. \\n\n",
        "With no fixed time limit, on the other hand, there is no reason to behave differently in the\n",
        "same state at different times. Hence, an optimal action depends only on the current state, and\n",
        "the optimal policy is <b>stationary</b>. \\n\n",
        "Utility of history using additive discounted rewards: \\n\n",
        "$U_h([s_0,a_0,s_1,a_1,s_2,\\ldots]) = R(s_0,a_0,_1) + \\gamma R(s_1,a_1,s_2) + \\gamma^2 R(s_2,a_2,s_3) + \\ldots$\n",
        "where the discount factor $\\gamma$ is a number between 0 and 1. The discount factor describes the\n",
        "preference of an agent for current rewards over future rewards. When $\\gamma$ is close to 0, rewards\n",
        "in the distant future are viewed as insignificant. When $\\gamma$ is close to 1, an agent is more willing\n",
        "to wait for long-term rewards. \\n\n",
        "A policy that is guaranteed to reach a terminal state is called a $proper policy$. \\n\n",
        "The utility of a state is the expected reward for the\n",
        "next transition plus the discounted utility of the next state, assuming that the agent chooses\n",
        "the optimal action. That is, the utility of a state is given by (Bellman Equation): \\n\n",
        "$U(s) = max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma U(s')]$ \\n\n",
        "Another important quantity is the action-utility function, or <b>Q-function</b>: $Q(s,a)$ is the\n",
        "expected utility of taking a given action in a given state. The Q-function is related to utilities\n",
        "in the obvious way: \\n\n",
        "$U(s) = max_a Q(s,a)$ \\n\n",
        "$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma max_{a'} Q(s',a')$ \\n\n",
        "$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma U(s')$\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\" <b>Value Iteration</b>: Start from the bottom of the tree and work your way up. At each iteration, update the utility of each state: \n",
        "$U_{i+1}(s) ← max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s0) + \\gamma U_i(s')]$ \\n\n",
        "Value iteration converges due to <b>contraction</b>(a function with one argument that brings two different inputs closer when applied to both). \\n\n",
        "<b>Policy Iteration: </b> Start with some initial policy $\\pi_0$ and repeat policy evaluation and policy improvement until it converges to optimal policy. \\n\n",
        "<b>Policy evaluation</b>: Given a policy $\\pi_i$, calculate $U_i =U^{\\pi_i}$ the utility of each state if $\\pi_i$ \\n were to be executed. \\n\n",
        "$U_{i+1}(s) ← \\sum_{s'} P(s'|s, \\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$ \\n\n",
        "<b>Policy improvement</b>: Calculate a new MEU policy $\\pi_{i+1}$, using one-step look-ahead based on $U_i$. \\n\n",
        "$\\pi_{i+1}(s) ← argmax_{a} \\sum_{s'} P(s'|s, a)[R(s,a,s') + \\gamma U_i(s')]$ \\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 66,
      "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": "d7d4d166-fb88-4d6c-aef6-fa0ce8a68d81"
      },
      "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": 67,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 17.1 Sequential Decision Problems' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n We begin with an agent that, like all agents, has to make a decision. It has available some\nactions $a$. There may be uncertainty about the current state, so we’ll assume that the agent\nassigns a probability $P(s)$ to each possible current state s. There may also be uncertainty\nabout the action outcomes; the transition model is given by $P(s'|s,a)$, the probability that action a in state s reaches state s'. \nBecause we’re primarily interested in the outcome s', we’ll also use the abbreviated notation $P(RESULT(a)=s')$, the probability of reaching s' by doing\na in the current state, whatever that is. \n \n The agent’s preferences are captured by a <b>utility function</b>, $U(s)$, which assigns a single number to express the \ndesirability of a state. The <b>expected utility</b> of an action given the evidence, EU(a), is just the\naverage utility value of the outcomes, weighted by the probability that the outcome occurs: \n\n$EU(a) = \\sum_{s'}P(\\textnormal{RESULT}(a)=s')U(s')$ \n\nThe principle of <b>maximum expected utility</b> (MEU) says that a rational agent should choose\nthe action that maximizes the agent’s expected utility.\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n<b>Orderability</b>: Given any two lotteries, a rational agent must either prefer one or else\nrate them as equally preferable. That is, the agent cannot avoid deciding. As noted on\npage 412, refusing to bet is like refusing to allow time to pass. \n\nExactly one of $(A \\succ B), (B \\succ A), or (A \\sim B)$ holds. \n\n\n<b>Transitivity</b>: Given any three lotteries, if an agent prefers A to B and prefers B to C,\nthen the agent must prefer A to C. \n\n$(A \\succ B) \\wedge (B \\succ C) \\implies (A \\succ C)$. \n\n\n<b>Continuity</b>: 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. \n\n$A \\succ B \\succ C ⇒ \\exists p [p,A; 1− p,C] \\sim B$ \n\n\n\n<b>Substitutability</b>: If an agent is indifferent between two lotteries A and B, then the\nagent is indifferent between two more complex lotteries that are the same except that\nB is substituted for A in one of them. This holds regardless of the probabilities and the\nother outcome(s) in the lotteries. \n\n$A \\sim B ⇒ [p,A; 1− p,C] \\sim [p,B; 1− p,C]$ \n\n\n<b>Monotonicity</b>: Suppose two lotteries have the same two possible outcomes, A and\nB. If 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 \\sim B \\implies (p > q \\Leftrightarrow [p,A; 1− p,B] \\succ [q,A; 1−q,B])$ \n\n\n<b>Decomposability</b>: Compound lotteries can be reduced to simpler ones using the laws \nof probability. \n\n$[p,A; 1− p,[q,B; 1−q,C]] \\sim [p,A; (1− p)q,B; (1− p)(1−q),C]$ \n\n\n<b>Existence of Utility Function</b>: If an agent’s preferences obey the axioms of utility, then\nthere exists a function U such that $U(A) > U(B)$ if and only if A is preferred to B, and\n$U(A) = U(B)$ if and only if the agent is indifferent between A and B. \n\n\n<b>Expected Utility of a Lottery</b>: The utility of a lottery is the sum of the probability of\neach outcome times the utility of that outcome: \n\n$U([p_1,S_1;\\ldots; p_n,S_n]) = \\sum_i p_i U(S_i)$ \n\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\nThe transition model (or just “model,” when the meaning is clear) de\u0002scribes the outcome of each action in each state. Here, the outcome is stochastic, so we write\n$P(s'|s,a)$ for the probability of reaching state s' if action a is done in state s. (Some authors write $T(s,a,s')$ for the transition model.) \nWe will assume that transitions are <b>Markovian</b>: the probability of reaching s' from s depends only on s and not on the history of earlier states. \n\nBecause the decision problem is sequential, the utility function will depend\non a sequence of states and actions—an environment history—rather than on a single state.\nLater in this section, we investigate the nature of utility functions on histories; for now, we\nsimply stipulate that for every transition from s to s' via action a, the agent receives a reward Reward $R(s,a,s')$. \n\nTo sum up: a sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a <b>Markov decision process</b>,\nor MDP, and consists of a set of states (with an initial state $s_0$); a set ACTIONS(s) of actions\nin each state; a transition model $P(s'|s,a)$; and a reward function $R(s,a,s')$. \n\nNo fixed action sequence can solve the problem, because the agent might end up in a state other than the\ngoal. Therefore, a solution must specify what the agent should do for any state that the agent\nmight reach. A solution of this kind is called a <b>policy</b>. \n\nEach time a given policy is executed starting from the initial state, the stochastic nature\nof the environment may lead to a different environment history. The quality of a policy is\ntherefore measured by the expected utility of the possible environment histories generated\nby that policy. An <b>optimal policy</b> is a policy that yields the highest expected utility. \n\nA <b>finite horizon</b> means that there is a fixed time N after which nothing Infinite horizon\nmatters—the game is over, so to speak. \n\nA policy that depends on the time is called <b>nonstationary</b>. \n\nWith no fixed time limit, on the other hand, there is no reason to behave differently in the\nsame state at different times. Hence, an optimal action depends only on the current state, and\nthe optimal policy is <b>stationary</b>. \n\nUtility of history using additive discounted rewards: \n\n$U_h([s_0,a_0,s_1,a_1,s_2,\\ldots]) = R(s_0,a_0,_1) + \\gamma R(s_1,a_1,s_2) + \\gamma^2 R(s_2,a_2,s_3) + \\ldots$\nwhere the discount factor $\\gamma$ is a number between 0 and 1. The discount factor describes the\npreference of an agent for current rewards over future rewards. When $\\gamma$ is close to 0, rewards\nin the distant future are viewed as insignificant. When $\\gamma$ is close to 1, an agent is more willing\nto wait for long-term rewards. \n\nA policy that is guaranteed to reach a terminal state is called a $proper policy$. \n\nThe utility of a state is the expected reward for the\nnext transition plus the discounted utility of the next state, assuming that the agent chooses\nthe optimal action. That is, the utility of a state is given by (Bellman Equation): \n\n$U(s) = max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma U(s')]$ \n\nAnother important quantity is the action-utility function, or <b>Q-function</b>: $Q(s,a)$ is the\nexpected utility of taking a given action in a given state. The Q-function is related to utilities\nin the obvious way: \n\n$U(s) = max_a Q(s,a)$ \n\n$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma max_{a'} Q(s',a')$ \n\n$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma U(s')$\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n <b>Value Iteration</b>: Start from the bottom of the tree and work your way up. At each iteration, update the utility of each state: \n$U_{i+1}(s) ← max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s0) + \\gamma U_i(s')]$ \n\nValue iteration converges due to <b>contraction</b>(a function with one argument that brings two different inputs closer when applied to both). \n\n<b>Policy Iteration: </b> Start with some initial policy $\\pi_0$ and repeat policy evaluation and policy improvement until it converges to optimal policy. \n\n<b>Policy evaluation</b>: Given a policy $\\pi_i$, calculate $U_i =U^{\\pi_i}$ the utility of each state if $\\pi_i$ \n were to be executed. \n\n$U_{i+1}(s) ← \\sum_{s'} P(s'|s, \\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$ \n\n<b>Policy improvement</b>: Calculate a new MEU policy $\\pi_{i+1}$, using one-step look-ahead based on $U_i$. \n\n$\\pi_{i+1}(s) ← argmax_{a} \\sum_{s'} P(s'|s, a)[R(s,a,s') + \\gamma U_i(s')]$ \n\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" An n-armed bandit has n levers. Behind each\n",
        "lever is a fixed but unknown probability distribution of winnings; each pull samples from that\n",
        "unknown distribution. \\n\n",
        "This is an example of the ubiquitous\n",
        "tradeoff between exploitation of the current best action to obtain rewards and exploration\n",
        "of previously unknown states and actions to gain information, which can in some cases be\n",
        "converted into a better policy and better long-term rewards. \\n\n",
        "The key property is that the arms are independent, coupled only by the fact that the agent can work on only one arm at a time.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" An alternative is reinforcement learning (RL), in which an agent interacts with the world and periodically receives rewards (or, in the terminology of psychology, reinforcements)\n",
        "that reflect how well it is doing. \\n \n",
        "The goal is the same in as in MDP reinforcement learning: maximize the expected sum of rewards. Reinforcement learning differs from “just solving\n",
        "an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. It may not know the transition model or the reward function, and it has to act in order\n",
        "to learn more. \\n\n",
        "It turns out, however, that a little bit of expertise can go a long way in reinforcement learning. The two examples in the preceding paragraph—the win/loss rewards for chess and\n",
        "racing—are what we call <b>sparse</b> rewards, because in the vast majority of states the agent is given no informative reward signal at all. \\n\n",
        "<b>Model-based reinforcement learning</b>: In these approaches the agent uses a transition model of the environment to help interpret the reward signals and to make decisions\n",
        "about how to act. The model may be initially unknown, in which case the agent learns\n",
        "the model from observing the effects of its actions, or it may already be known—for\n",
        "example, a chess program may know the rules of chess even if it does not know how\n",
        "to choose good moves. In partially observable environments, the transition model is\n",
        "also useful for state estimation. Model-based reinforcement learning\n",
        "systems often learn a utility function $U(s)$, in terms of the sum of rewards from state s onward. \\n\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" We start with the simple case of a fully observable environment with a small number of\n",
        "actions and states, in which an agent already has a fixed policy $\\pi(s)$ that determines its actions.\n",
        "The agent is trying to learn the utility function $U^\\pi(s)$—the expected total discounted reward\n",
        "if policy $\\pi$ is executed beginning in state s. We call this a passive learning agent. \\n\n",
        "<b>Direct utility estimation</b>: The idea of direct utility estimation is that the utility of a state is defined as the expected\n",
        "total reward from that state onward (called the expected reward-to-go), and that each trial Reward-to-go\n",
        "provides a sample of this quantity for each state visited. By ignoring the connections between states, direct utility estimation misses opportunities for\n",
        "learning. \\n \n",
        "$U_{i}(s) ← \\sum_{s'} P(s'|s, \\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$ \\n\n",
        "<b> Temporal Difference Learning </b>: Update the utility of a state s when a transition occurs from state s to s': \\n\n",
        "$U^\\pi(s) ← U^\\pi(s) + \\\\alpha[R(s,\\pi(s),s') +γ\\gamma U^\\pi(s')− U^\\pi(s)]$ where $\\\\alpha$ is the learning rate. \\n\n",
        "Furthermore, if we turn the parameter $\\\\alpha$ into a function that decreases as the number\n",
        "of times a state has been visited increases, then $U^\\pi(s)$ itself will converge to the correct value.\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" The <b>Q-learning</b> method avoids the need for a model by learning an action-utility function\n",
        "$Q(s,a)$ instead of a utility function $U(s)$. $Q(s,a)$ denotes the expected total discounted reward\n",
        "if the agent takes action a in s and acts optimally thereafter. Knowing the Q-function enables\n",
        "the agent to act optimally simply by choosing $argmax_a Q(s,a)$, with no need for look-ahead\n",
        "based on a transition model: \\n\n",
        "$Q(s,a) = Q(s,a) + \\\\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)]$ \\n \n",
        "This update is calculated whenever action a is executed in state s leading to state s'. \\n\n",
        "The important part of this equation is what it does not contain: a TD Q-learning agent does not need a transition model either for learning or for action selection.\n",
        "As noted at the beginning of the chapter, model-free methods can be applied even in very complex domains because no model need be provided or learned. On the other hand, the Q-learning agent has no means of looking into the future, so it may have difficulty when rewards\n",
        "are sparse and long action sequences must be constructed to reach them. \\n\n",
        "Q-learning is an <b>off-policy</b> learning algorithm, because it learns Q-values that answer the \n",
        "question “What would this action be worth in this state, assuming that I stop using whatever\n",
        "policy I am using now, and start acting according to a policy that chooses the best action\n",
        "(according to my estimates)?” \n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" If there are too many states to hold in memory, we can use function approximation to approximate the utility function and Q-functions as weighted linear combination of features: \\n\n",
        "$Q(s,a) =  w_1 f_1(s,a) + w_2 f_2(s,a) + w_3 f_3(s,a) + \\ldots$ \\n\n",
        "Updating the Q-function after a transition: \\n\n",
        "$Q(s,a) = Q(s,a) + \\\\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)]$ \\n\n",
        "Updating weights: \\n\n",
        "$w_i = w_i + \\\\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)] f_i(s,a)$\n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "3ccfe6ff-1efe-4fcc-ab65-ecc3b6da8a9d"
      },
      "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": 69,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n An n-armed bandit has n levers. Behind each\nlever is a fixed but unknown probability distribution of winnings; each pull samples from that\nunknown distribution. \n\nThis is an example of the ubiquitous\ntradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information, which can in some cases be\nconverted into a better policy and better long-term rewards. \n\nThe key property is that the arms are independent, coupled only by the fact that the agent can work on only one arm at a time.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n An alternative is reinforcement learning (RL), in which an agent interacts with the world and periodically receives rewards (or, in the terminology of psychology, reinforcements)\nthat reflect how well it is doing. \n \nThe goal is the same in as in MDP reinforcement learning: maximize the expected sum of rewards. Reinforcement learning differs from “just solving\nan MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. It may not know the transition model or the reward function, and it has to act in order\nto learn more. \n\nIt turns out, however, that a little bit of expertise can go a long way in reinforcement learning. The two examples in the preceding paragraph—the win/loss rewards for chess and\nracing—are what we call <b>sparse</b> rewards, because in the vast majority of states the agent is given no informative reward signal at all. \n\n<b>Model-based reinforcement learning</b>: In these approaches the agent uses a transition model of the environment to help interpret the reward signals and to make decisions\nabout how to act. The model may be initially unknown, in which case the agent learns\nthe model from observing the effects of its actions, or it may already be known—for\nexample, a chess program may know the rules of chess even if it does not know how\nto choose good moves. In partially observable environments, the transition model is\nalso useful for state estimation. Model-based reinforcement learning\nsystems often learn a utility function $U(s)$, in terms of the sum of rewards from state s onward. \n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n We start with the simple case of a fully observable environment with a small number of\nactions and states, in which an agent already has a fixed policy $\\pi(s)$ that determines its actions.\nThe agent is trying to learn the utility function $U^\\pi(s)$—the expected total discounted reward\nif policy $\\pi$ is executed beginning in state s. We call this a passive learning agent. \n\n<b>Direct utility estimation</b>: The idea of direct utility estimation is that the utility of a state is defined as the expected\ntotal reward from that state onward (called the expected reward-to-go), and that each trial Reward-to-go\nprovides a sample of this quantity for each state visited. By ignoring the connections between states, direct utility estimation misses opportunities for\nlearning. \n \n$U_{i}(s) ← \\sum_{s'} P(s'|s, \\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$ \n\n<b> Temporal Difference Learning </b>: Update the utility of a state s when a transition occurs from state s to s': \n\n$U^\\pi(s) ← U^\\pi(s) + \\alpha[R(s,\\pi(s),s') +γ\\gamma U^\\pi(s')− U^\\pi(s)]$ where $\\alpha$ is the learning rate. \n\nFurthermore, if we turn the parameter $\\alpha$ into a function that decreases as the number\nof times a state has been visited increases, then $U^\\pi(s)$ itself will converge to the correct value.\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n The <b>Q-learning</b> method avoids the need for a model by learning an action-utility function\n$Q(s,a)$ instead of a utility function $U(s)$. $Q(s,a)$ denotes the expected total discounted reward\nif the agent takes action a in s and acts optimally thereafter. Knowing the Q-function enables\nthe agent to act optimally simply by choosing $argmax_a Q(s,a)$, with no need for look-ahead\nbased on a transition model: \n\n$Q(s,a) = Q(s,a) + \\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)]$ \n \nThis update is calculated whenever action a is executed in state s leading to state s'. \n\nThe important part of this equation is what it does not contain: a TD Q-learning agent does not need a transition model either for learning or for action selection.\nAs noted at the beginning of the chapter, model-free methods can be applied even in very complex domains because no model need be provided or learned. On the other hand, the Q-learning agent has no means of looking into the future, so it may have difficulty when rewards\nare sparse and long action sequences must be constructed to reach them. \n\nQ-learning is an <b>off-policy</b> learning algorithm, because it learns Q-values that answer the \nquestion “What would this action be worth in this state, assuming that I stop using whatever\npolicy I am using now, and start acting according to a policy that chooses the best action\n(according to my estimates)?” \n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n If there are too many states to hold in memory, we can use function approximation to approximate the utility function and Q-functions as weighted linear combination of features: \n\n$Q(s,a) =  w_1 f_1(s,a) + w_2 f_2(s,a) + w_3 f_3(s,a) + \\ldots$ \n\nUpdating the Q-function after a transition: \n\n$Q(s,a) = Q(s,a) + \\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)]$ \n\nUpdating weights: \n\n$w_i = w_i + \\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)] f_i(s,a)$\n\n\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" The fundamental idea of decision theory is that\n",
        "an agent is rational if and only if it chooses\n",
        "the action that yields the highest expected utility, averaged over all the possible outcomes\n",
        "of the action. This is called the principle of maximum expected utility (MEU). \"\"\"\n",
        "chapter12_2 = \"\"\" In probability theory, the set of all possible worlds is called the <b>sample space</b>. \\n\n",
        "Probabilistic assertions and queries are not usually about particular possible worlds, but\n",
        "about sets of them. For example, we might ask for the probability that the two dice add up\n",
        "to 11, the probability that doubles are rolled, and so on. In probability theory, these sets\n",
        "are called <b>events</b>. In logic, a set of worlds corresponds to a <b>proposition</b> in a formal language; specifically, for each\n",
        "proposition, the corresponding set contains just those possible worlds in which the proposition holds. (Hence, “event” and “proposition” mean roughly the same thing in this context,\n",
        "except that a proposition is expressed in a formal language.) \\n\n",
        "The definition of conditional probability, can be written in a different form called the product rule: \\n\n",
        "$P(a \\wedge b) = P(a|b) P(b)$ \\n\n",
        "Variables in probability theory are called random variables, and their names begin with\n",
        "an uppercase letter. Thus, in the dice example, Total and Die1 are random variables. Every random variable is a function that maps from the domain of possible worlds $\\omega$ to some \n",
        "range—the set of possible values it can take on. \\n\n",
        "We can also derive the well-known formula for the probability of a disjunction, sometimes\n",
        "called the inclusion–exclusion principle: \\n\n",
        "$P(a \\\\vee b) = P(a) +P(b)− P(a \\wedge b)$ \\n\n",
        "This process is called <b>marginalization</b>, or summing out—because we sum up the probabilities for each possible value of the other variables, thereby taking them out of the equation.\n",
        "We can write the following general marginalization rule for any sets of variables Y and Z: \\n\n",
        "$P(Y) = \\sum_z P(Y,Z=z)$ \\n\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" The property is called independence (also marginal independence and absolute independence). In particular, the weather is independent of one’s\n",
        "dental problems. Independence between propositions a and b can be written as: \\n\n",
        "$P(a|b)=P(a)$ or $P(b|a)=P(b)$ or $P(a∧b)=P(a)P(b)$  \"\"\"\n",
        "chapter12_5 = \"\"\" <b>Bayes’ rule</b>: \\n\n",
        "$P(a|b) = \\\\frac{P(b|a)P(a)}{P(b)}$ \\n\n",
        "The general definition of <b>conditional independence</b> of two variables X and Y, given a\n",
        "third variable Z, is : \\n\n",
        "$P(X,Y |Z) = P(X |Z)P(Y |Z)$\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\" The dentistry example illustrates a commonly occurring pattern in which a single cause directly influences a number of effects, all of which are conditionally independent, given the\n",
        "cause. The full joint distribution can be written as: \\n\n",
        "$P(Cause,Effect_1,\\ldots,Effect_n) = P(Cause) \\prod_i P(Effect_i|Cause)$ \\n\n",
        "Such a probability distribution is called a $naive Bayes$ model—“naive” because it is often\n",
        "used (as a simplifying assumption) in cases where the “effect” variables are not strictly independent given the cause variable. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" We’ll represent a sequence of N words either as\n",
        "$w_1 \\ldots w_n $ or $w_{1:n}$ (so the expression $w_{1:n -  1}$ means the string w_1 \\ldots w_{n - 1}). \\n\n",
        "Now how can we compute probabilities of entire sequences like $P(w_1,w_2,\\ldots,w_n)$?\n",
        "One thing we can do is decompose this probability using the chain rule of probability: \\n\n",
        "$P(X_1 \\ldots X_n) = P(X_1)P(X_2|X_1)P(X_3|X_{1:2}) \\ldots P(X_n|X_{1:n−1})$ \\n\n",
        "Equation suggests that we could estimate the joint probability of an entire sequence of\n",
        "words by multiplying together a number of conditional probabilities. But using the\n",
        "chain rule doesn’t really seem to help us! We don’t know any way to compute the\n",
        "exact probability of a word given a long sequence of preceding words. \\n\n",
        "As we said above, we can’t just estimate by counting the number of times every word\n",
        "occurs following every long string, because language is creative and any particular\n",
        "context might have never occurred before! \\n\n",
        "The intuition of the n-gram model is that instead of computing the probability of\n",
        "a word given its entire history, we can approximate the history by just the last few\n",
        "words. \\n\n",
        "The assumption that the probability of a word depends only on the previous word is\n",
        "called a Markov assumption. Markov models are the class of probabilistic models\n",
        "that assume we can predict the probability of some future unit without looking too\n",
        "far into the past. We can generalize the bigram (which looks one word into the past)\n",
        "to the trigram (which looks two words into the past) and thus to the n-gram (which\n",
        "looks n−1 words into the past). \\n\n",
        "For example, to compute a particular bigram probability of a word y given a\n",
        "previous word x, we’ll compute the count of the bigram C(xy) and normalize by the\n",
        "sum of all the bigrams that share the same first word x:\n",
        "$P(w_n|w_{n−1}) = \\\\frac{C(w_{n−1}w_n)}{C(w_{n-1})}$\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\" The best way to evaluate the performance of a language model is to embed it in\n",
        "an application and measure how much the application improves. Such end-to-end\n",
        "evaluation is called extrinsic evaluation. \\n\n",
        "An intrinsic evaluation metric is one that measures the quality of a model independent of any application. \\n\n",
        "In practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (sometimes called PP for short)\n",
        "of a language model on a test set is the inverse probability of the test set, normalized\n",
        "by the number of words. \\n\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Statistical models are likely to be pretty useless as predictors if the training sets and the test sets are as different as Shakespeare and WSJ.\n",
        "How should we deal with this problem when we build n-gram models? One step\n",
        "is to be sure to use a training corpus that has a similar genre to whatever task we are\n",
        "trying to accomplish. To build a language model for translating legal documents,\n",
        "we need a training corpus of legal documents. To build a language model for a\n",
        "question-answering system, we need a training corpus of questions. \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" What do we do with words that are in our vocabulary (they are not unknown words)\n",
        "but appear in a test set in an unseen context (for example they appear after a word\n",
        "they never appeared after in training)? To keep a language model from assigning\n",
        "zero probability to these unseen events, we’ll have to shave off a bit of probability\n",
        "mass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting. \\n\n",
        "<b>Laplace Smoothing</b>\n",
        "$P(w_n|w_{n−1}) = \\\\frac{C(w_{n−1}w_n) + 1}{C(w_{n-1}) + |V|}$\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",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 70,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "19459061-0ba0-4e0b-bd74-59b36bbf3c8a"
      },
      "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": 71,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n The fundamental idea of decision theory is that\nan agent is rational if and only if it chooses\nthe action that yields the highest expected utility, averaged over all the possible outcomes\nof the action. This is called the principle of maximum expected utility (MEU). \n\n## AIMA Chapter 12.2 Basic Probability Notation\n In probability theory, the set of all possible worlds is called the <b>sample space</b>. \n\nProbabilistic assertions and queries are not usually about particular possible worlds, but\nabout sets of them. For example, we might ask for the probability that the two dice add up\nto 11, the probability that doubles are rolled, and so on. In probability theory, these sets\nare called <b>events</b>. In logic, a set of worlds corresponds to a <b>proposition</b> in a formal language; specifically, for each\nproposition, the corresponding set contains just those possible worlds in which the proposition holds. (Hence, “event” and “proposition” mean roughly the same thing in this context,\nexcept that a proposition is expressed in a formal language.) \n\nThe definition of conditional probability, can be written in a different form called the product rule: \n\n$P(a \\wedge b) = P(a|b) P(b)$ \n\nVariables in probability theory are called random variables, and their names begin with\nan uppercase letter. Thus, in the dice example, Total and Die1 are random variables. Every random variable is a function that maps from the domain of possible worlds $\\omega$ to some \nrange—the set of possible values it can take on. \n\nWe can also derive the well-known formula for the probability of a disjunction, sometimes\ncalled the inclusion–exclusion principle: \n\n$P(a \\vee b) = P(a) +P(b)− P(a \\wedge b)$ \n\nThis process is called <b>marginalization</b>, or summing out—because we sum up the probabilities for each possible value of the other variables, thereby taking them out of the equation.\nWe can write the following general marginalization rule for any sets of variables Y and Z: \n\n$P(Y) = \\sum_z P(Y,Z=z)$ \n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n The property is called independence (also marginal independence and absolute independence). In particular, the weather is independent of one’s\ndental problems. Independence between propositions a and b can be written as: \n\n$P(a|b)=P(a)$ or $P(b|a)=P(b)$ or $P(a∧b)=P(a)P(b)$  \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n <b>Bayes’ rule</b>: \n\n$P(a|b) = \\frac{P(b|a)P(a)}{P(b)}$ \n\nThe general definition of <b>conditional independence</b> of two variables X and Y, given a\nthird variable Z, is : \n\n$P(X,Y |Z) = P(X |Z)P(Y |Z)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n The dentistry example illustrates a commonly occurring pattern in which a single cause directly influences a number of effects, all of which are conditionally independent, given the\ncause. The full joint distribution can be written as: \n\n$P(Cause,Effect_1,\\ldots,Effect_n) = P(Cause) \\prod_i P(Effect_i|Cause)$ \n\nSuch a probability distribution is called a $naive Bayes$ model—“naive” because it is often\nused (as a simplifying assumption) in cases where the “effect” variables are not strictly independent given the cause variable. \n\n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n We’ll represent a sequence of N words either as\n$w_1 \\ldots w_n $ or $w_{1:n}$ (so the expression $w_{1:n -  1}$ means the string w_1 \\ldots w_{n - 1}). \n\nNow how can we compute probabilities of entire sequences like $P(w_1,w_2,\\ldots,w_n)$?\nOne thing we can do is decompose this probability using the chain rule of probability: \n\n$P(X_1 \\ldots X_n) = P(X_1)P(X_2|X_1)P(X_3|X_{1:2}) \\ldots P(X_n|X_{1:n−1})$ \n\nEquation suggests that we could estimate the joint probability of an entire sequence of\nwords by multiplying together a number of conditional probabilities. But using the\nchain rule doesn’t really seem to help us! We don’t know any way to compute the\nexact probability of a word given a long sequence of preceding words. \n\nAs we said above, we can’t just estimate by counting the number of times every word\noccurs following every long string, because language is creative and any particular\ncontext might have never occurred before! \n\nThe intuition of the n-gram model is that instead of computing the probability of\na word given its entire history, we can approximate the history by just the last few\nwords. \n\nThe assumption that the probability of a word depends only on the previous word is\ncalled a Markov assumption. Markov models are the class of probabilistic models\nthat assume we can predict the probability of some future unit without looking too\nfar into the past. We can generalize the bigram (which looks one word into the past)\nto the trigram (which looks two words into the past) and thus to the n-gram (which\nlooks n−1 words into the past). \n\nFor example, to compute a particular bigram probability of a word y given a\nprevious word x, we’ll compute the count of the bigram C(xy) and normalize by the\nsum of all the bigrams that share the same first word x:\n$P(w_n|w_{n−1}) = \\frac{C(w_{n−1}w_n)}{C(w_{n-1})}$\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n The best way to evaluate the performance of a language model is to embed it in\nan application and measure how much the application improves. Such end-to-end\nevaluation is called extrinsic evaluation. \n\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application. \n\nIn practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (sometimes called PP for short)\nof a language model on a test set is the inverse probability of the test set, normalized\nby the number of words. \n\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 Statistical models are likely to be pretty useless as predictors if the training sets and the test sets are as different as Shakespeare and WSJ.\nHow should we deal with this problem when we build n-gram models? One step\nis to be sure to use a training corpus that has a similar genre to whatever task we are\ntrying to accomplish. To build a language model for translating legal documents,\nwe need a training corpus of legal documents. To build a language model for a\nquestion-answering system, we need a training corpus of questions. \n\n## SLP Chapter 3.5 Smoothing\n What do we do with words that are in our vocabulary (they are not unknown words)\nbut appear in a test set in an unseen context (for example they appear after a word\nthey never appeared after in training)? To keep a language model from assigning\nzero probability to these unseen events, we’ll have to shave off a bit of probability\nmass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting. \n\n<b>Laplace Smoothing</b>\n$P(w_n|w_{n−1}) = \\frac{C(w_{n−1}w_n) + 1}{C(w_{n-1}) + |V|}$\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* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" This section introduces a data structure called a Bayesian network to represent the dependencies among variables. Bayesian networks can represent\n",
        "essentially any full joint probability distribution and in many cases can do so very concisely.\n",
        "A Bayesian network is a directed graph in which each node is annotated with quantitative\n",
        "probability information. The full specification is as follows: \\n\n",
        "1. Each node corresponds to a random variable, which may be discrete or continuous. \\n\n",
        "2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to\n",
        "node Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a\n",
        "directed acyclic graph, or DAG. \\n\n",
        "3. Each node $X_i$ has associated probability information $\\theta(X_i|Parents(X_i))$ that quantifies the effect of the parents on the node using a finite number of parameters. \\n\n",
        "The intuitive meaning of an arrow is typically that X has a direct influence on Y, which suggests that causes should be parents of effects. \\n\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\" The syntax of a Bayes net consists of a directed acyclic graph with some local probability\n",
        "information attached to each node. The semantics defines how the syntax corresponds to a joint distribution over the variables of the network. \\n\n",
        "The semantics of Bayes nets defines each entry in the joint distribution as follows: \\n\n",
        "$P(x_1, \\ldots, x_n) = \\prod_{i = 1}^n \\\\theta(x_i|parents(X_i))$ \\n\n",
        "<b> Chain Rule </b>: \\n\n",
        "$P(x_1, \\ldots, x_n) = P(x_n | x_{n−1}, \\ldots, x_1) P(x_{n−1} | x_{n−2}, \\ldots, x_1) \\ldots P(x_2 | x_1)P(x_1)$ \\n\n",
        "As well as being a complete and nonredundant representation of the domain, a Bayes net\n",
        "can often be far more compact than the full joint distribution. This property is what makes\n",
        "it feasible to handle domains with many variables. The compactness of Bayesian networks\n",
        "is an example of a general property of locally structured (also called sparse) systems. In a\n",
        "locally structured system, each subcomponent interacts directly with only a bounded number\n",
        "of other components, regardless of the total number of components. Local structure is usually\n",
        "associated with linear rather than exponential growth in complexity. \\n\n",
        "Two variables $X$, $Y$ are conditionally independent given a third variable $Z$ if all undirected paths from $X$ to $Y$ are inactive. \\n\n",
        "A path is active if each triple is active: either a causal chain ($A \\\\rightarrow B \\\\rightarrow C$ and B is unobserved), common cause ($A \\\\leftarrow B \\\\rightarrow C$ and B is unobserved)\n",
        "or common effect ($A \\\\rightarrow B \\\\leftarrow C$ and B or one of its descendants is observed)\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 72,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 867
        },
        "cellView": "form",
        "outputId": "62dadba3-b601-4af8-f3f5-e50f65d644dc"
      },
      "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": 73,
      "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 This section introduces a data structure called a Bayesian network to represent the dependencies among variables. Bayesian networks can represent\nessentially any full joint probability distribution and in many cases can do so very concisely.\nA Bayesian network is a directed graph in which each node is annotated with quantitative\nprobability information. The full specification is as follows: \n\n1. Each node corresponds to a random variable, which may be discrete or continuous. \n\n2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to\nnode Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a\ndirected acyclic graph, or DAG. \n\n3. Each node $X_i$ has associated probability information $\theta(X_i|Parents(X_i))$ that quantifies the effect of the parents on the node using a finite number of parameters. \n\nThe intuitive meaning of an arrow is typically that X has a direct influence on Y, which suggests that causes should be parents of effects. \n\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The syntax of a Bayes net consists of a directed acyclic graph with some local probability\ninformation attached to each node. The semantics defines how the syntax corresponds to a joint distribution over the variables of the network. \n\nThe semantics of Bayes nets defines each entry in the joint distribution as follows: \n\n$P(x_1, \\ldots, x_n) = \\prod_{i = 1}^n \\theta(x_i|parents(X_i))$ \n\n<b> Chain Rule </b>: \n\n$P(x_1, \\ldots, x_n) = P(x_n | x_{n−1}, \\ldots, x_1) P(x_{n−1} | x_{n−2}, \\ldots, x_1) \\ldots P(x_2 | x_1)P(x_1)$ \n\nAs well as being a complete and nonredundant representation of the domain, a Bayes net\ncan often be far more compact than the full joint distribution. This property is what makes\nit feasible to handle domains with many variables. The compactness of Bayesian networks\nis an example of a general property of locally structured (also called sparse) systems. In a\nlocally structured system, each subcomponent interacts directly with only a bounded number\nof other components, regardless of the total number of components. Local structure is usually\nassociated with linear rather than exponential growth in complexity. \n\nTwo variables $X$, $Y$ are conditionally independent given a third variable $Z$ if all undirected paths from $X$ to $Y$ are inactive. \n\nA path is active if each triple is active: either a causal chain ($A \\rightarrow B \\rightarrow C$ and B is unobserved), common cause ($A \\leftarrow B \\rightarrow C$ and B is unobserved)\nor common effect ($A \\rightarrow B \\leftarrow C$ and B or one of its descendants is observed)\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" In supervised learning the agent observes input-output pairs and learns a function that\n",
        "maps from input to output. For example, the inputs could be camera images, each\n",
        "one accompanied by an output saying “bus” or “pedestrian,” etc. An output like this\n",
        "is called a label. The agent learns a function that, when given a new image, predicts\n",
        "the appropriate label. In the case of braking actions (component 1 above), an input is\n",
        "the current state (speed and direction of the car, road condition), and an output is the\n",
        "distance it took to stop. In this case a set of output values can be obtained by the agent\n",
        "from its own percepts (after the fact); the environment is the teacher, and the agent\n",
        "learns a function that maps states to stopping distance. \\n\n",
        "\n",
        "In unsupervised learning the agent learns patterns in the input without any explicit\n",
        "feedback. The most common unsupervised learning task is clustering: detecting potentially useful clusters of input examples. For example, when shown millions of images\n",
        "taken from the Internet, a computer vision system can identify a large cluster of similar\n",
        "images which an English speaker would call “cats.” \\n\n",
        "\n",
        "In reinforcement learning the agent learns from a series of reinforcements: rewards \n",
        "and punishments. For example, at the end of a chess game the agent is told that it has\n",
        "won (a reward) or lost (a punishment). It is up to the agent to decide which of the\n",
        "actions prior to the reinforcement were most responsible for it, and to alter its actions\n",
        "to aim towards more rewards in the future.\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\" We say that a hypothesis is underfitting when it fails to find a Underfitting\n",
        "pattern in the data. \\n\n",
        "By variance we mean the amount of change in the hypothesis due to fluctuation in the Variance\n",
        "training data. \\n\n",
        "We say a function is overfitting the data when it pays too much attention to the particular data set it is trained Overfitting\n",
        "on, causing it to perform poorly on unseen data. \\n\n",
        "Often there is a bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may gen\u0002eralize better.\n",
        "\"\"\"\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 = \"\"\" We represent a text document as if it were a bag-of-words, that is, an unordered set of words with their position\n",
        "ignored, keeping only their frequency in the document. \\n\n",
        "\n",
        "To return to classification: we compute the most probable class $\\hat{c}$ given some\n",
        "document d by choosing the class which has the highest product of two probabilities:\n",
        "the prior probability of the class $P(c)$ and the likelihood of the document $P(d|c)$ \\n\n",
        "\n",
        "The first is the bag of words assumption discussed intuitively above: we assume\n",
        "position doesn’t matter, and that the word “love” has the same effect on classification\n",
        "whether it occurs as the 1st, 20th, or last word in the document. Thus we assume\n",
        "that the features f1, f2,..., fn only encode word identity and not position.\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\" To learn the probability $P(f_i|c)$, we’ll assume a feature is just the existence of a word\n",
        "in the document’s bag of words, and so we’ll want $P(w_i|c)$, which we compute as\n",
        "the fraction of times the word $w_i$ appears among all words in all documents of topic\n",
        "c. \"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 74,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "30e9eec5-d373-44c9-b7a8-70036b9f0cae"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 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": 75,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Game Theory\n In supervised learning the agent observes input-output pairs and learns a function that\nmaps from input to output. For example, the inputs could be camera images, each\none accompanied by an output saying “bus” or “pedestrian,” etc. An output like this\nis called a label. The agent learns a function that, when given a new image, predicts\nthe appropriate label. In the case of braking actions (component 1 above), an input is\nthe current state (speed and direction of the car, road condition), and an output is the\ndistance it took to stop. In this case a set of output values can be obtained by the agent\nfrom its own percepts (after the fact); the environment is the teacher, and the agent\nlearns a function that maps states to stopping distance. \n\n\nIn unsupervised learning the agent learns patterns in the input without any explicit\nfeedback. The most common unsupervised learning task is clustering: detecting potentially useful clusters of input examples. For example, when shown millions of images\ntaken from the Internet, a computer vision system can identify a large cluster of similar\nimages which an English speaker would call “cats.” \n\n\nIn reinforcement learning the agent learns from a series of reinforcements: rewards \nand punishments. For example, at the end of a chess game the agent is told that it has\nwon (a reward) or lost (a punishment). It is up to the agent to decide which of the\nactions prior to the reinforcement were most responsible for it, and to alter its actions\nto aim towards more rewards in the future.\n\n\n## AIMA Chapter 19.2 Optimal Decisions in Games\n We say that a hypothesis is underfitting when it fails to find a Underfitting\npattern in the data. \n\nBy variance we mean the amount of change in the hypothesis due to fluctuation in the Variance\ntraining data. \n\nWe say a function is overfitting the data when it pays too much attention to the particular data set it is trained Overfitting\non, causing it to perform poorly on unseen data. \n\nOften there is a bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may gen\u0002eralize better.\n\n\n## AIMA Chapter 19.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 19.4 Stochastic Games\n Your summary here \n\n## AIMA Chapter 19.5 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 19.6 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n We represent a text document as if it were a bag-of-words, that is, an unordered set of words with their position\nignored, keeping only their frequency in the document. \n\n\nTo return to classification: we compute the most probable class $\\hat{c}$ given some\ndocument d by choosing the class which has the highest product of two probabilities:\nthe prior probability of the class $P(c)$ and the likelihood of the document $P(d|c)$ \n\n\nThe first is the bag of words assumption discussed intuitively above: we assume\nposition doesn’t matter, and that the word “love” has the same effect on classification\nwhether it occurs as the 1st, 20th, or last word in the document. Thus we assume\nthat the features f1, f2,..., fn only encode word identity and not position.\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n To learn the probability $P(f_i|c)$, we’ll assume a feature is just the existence of a word\nin the document’s bag of words, and so we’ll want $P(w_i|c)$, which we compute as\nthe fraction of times the word $w_i$ appears among all words in all documents of topic\nc. \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 Your summary here \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 = \"\"\" Logistic regression has two phases:\n",
        "training: we train the system (specifically the weights w and b) using stochastic\n",
        "gradient descent and the cross-entropy loss.\n",
        "test: Given a test example x we compute p(y|x) and return the higher probability\n",
        "label y = 1 or y = 0. \\n\n",
        "Logistic regression solves this task by learning, from a training set, a vector of\n",
        "weights and a bias term. Each weight $w_i$ is a real number, and is associated with one of the input features $x_i$. The weight wi represents how important that input feature\n",
        "is to the classification decision, and can be positive (providing evidence that the in\u0002stance being classified belongs in the positive class) or negative (providing evidence\n",
        "that the instance being classified belongs in the negative class). Thus we might\n",
        "expect in a sentiment task the word awesome to have a high positive weight, and\n",
        "abysmal to have a very negative weight. The bias term, also called the intercept, is\n",
        "another real number that’s added to the weighted inputs. \\n\n",
        "To create a probability, we’ll pass z through the sigmoid function, $\\\\sigma(z)$. The\n",
        "sigmoid function (named because it looks like an s) is also called the logistic function, and gives logistic regression its name. The sigmoid has the following equation:\n",
        "$\\\\sigma(z) = \\\\frac{1}{1 + e^{-z}} =  \\\\frac{1}{1 + e^{-(w x + b)}}$\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" We need a loss function that expresses, for an observation x, how close the classifier\n",
        "output ($\\hat{y} = \\\\sigma(w \\\\times x + b)$) is to the correct output (y, which is 0 or 1). We’ll call this:\n",
        "$L(\\hat{y}, y)$ = How much $\\hat{y}$ differs from the true y. \\n\n",
        "We do this via a loss function that prefers the correct class labels of the training examples to be more likely. This is called conditional maximum likelihood\n",
        "estimation: we choose the parameters w,b that maximize the log probability of\n",
        "the true y labels in the training data given the observations x. The resulting loss\n",
        "function is the negative log likelihood loss, generally called the cross-entropy loss: \n",
        "$LCE(\\hat{y}, y) = −[y \\\\log \\\\sigma (w x + b) + (1−y) \\\\log(1−\\\\sigma(w x+b))]$\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Gradient descent\n",
        "is a method that finds a minimum of a function by figuring out in which direction\n",
        "(in the space of the parameters $\\\\theta$) the function’s slope is rising the most steeply,\n",
        "and moving in the opposite direction. \\n\n",
        "For logistic regression, this loss function is conveniently convex. A convex function has just one minimum; there are no local minima to get stuck in, so gradient\n",
        "descent starting from any point is guaranteed to find the minimum. (By contrast,\n",
        "the loss for multi-layer neural networks is non-convex, and gradient descent may\n",
        "get stuck in local minima for neural network training and never find the global optimum.) \\n\n",
        "The magnitude of the amount to move in gradient descent is the value of the\n",
        "slope $\\\\frac{d}{dw}L(f(x;w), y$) weighted by a learning rate $\\\\eta$. A higher (faster) learning\n",
        "rate means that we should move w more on each step. The change we make in our\n",
        "parameter is the learning rate times the gradient: \\n\n",
        "$w_{t+1} = w_t −\\\\eta \\\\frac{d}{dw}L(f(x;w), y$) \\n\n",
        "The learning rate $\\\\eta$ is a hyperparameter that must be adjusted. If it’s too high,\n",
        "the learner will take steps that are too large, overshooting the minimum of the loss\n",
        "function. If it’s too low, the learner will take steps that are too small, and take too\n",
        "long to get to the minimum. It is common to start with a higher learning rate and then\n",
        "slowly decrease it, so that it is a function of the iteration k of training; the notation\n",
        "$\\\\eta_k$can be used to mean the value of the learning rate at iteration k.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter5_5 = \"\"\" There is a problem with learning weights that make the model perfectly match the\n",
        "training data. If a feature is perfectly predictive of the outcome because it happens\n",
        "to only occur in one class, it will be assigned a very high weight. The weights for\n",
        "features will attempt to perfectly fit details of the training set, in fact too perfectly,\n",
        "modeling noisy factors that just accidentally correlate with the class. This problem is called overfitting. A good model should be able to generalize well from the training\n",
        "data to the unseen test set, but a model that overfits will have poor generalization. \\n\n",
        "To avoid overfitting, a new regularization term $R(\\\\theta)$ is added to the objective\n",
        "function: \\n\n",
        "$\\hat{\\\\theta} = argmax_{\\\\theta} \\\\sum_{i=1}^m \\\\log P(y^{(i)}|x^{(i)}) − \\\\alpha R(\\\\theta)$ \\n\n",
        "The new regularization term $R(\\\\theta))$ is used to penalize large weights. Thus a setting\n",
        "of the weights that matches the training data perfectly— but uses many weights with\n",
        "high values to do so—will be penalized more than a setting that matches the data a\n",
        "little less well, but does so using smaller weights. There are two common ways to\n",
        "compute this regularization term $R(\\\\theta))$. L2 regularization is a quadratic function of\n",
        "the weight values, named because it uses the (square of the) L2 norm of the weight\n",
        "values. The L2 norm, is the same as the Euclidean distance of the vector θ\n",
        "from the origin. \\n\n",
        "\n",
        "L1 regularization is a linear function of the weight values, named after the L1 norm\n",
        "the sum of the absolute values of the weights, or Manhattan distance (the\n",
        "Manhattan distance is the distance you’d have to walk between two points in a city\n",
        "with a street grid like New York). \\n\n",
        "\n",
        "These kinds of regularization come from statistics, where L1 regularization is called\n",
        "lasso regression and L2 regularization is called ridge regression.\n",
        "\"\"\"\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 = \"\"\" The building block of a neural network is a single computational unit. A unit takes\n",
        "a set of real valued numbers as input, performs some computation on them, and\n",
        "produces an output. \\n\n",
        "Finally, instead of using z, a linear function of x, as the output, neural units\n",
        "apply a non-linear function f to z. We will refer to the output of this function as\n",
        "the activation value for the unit, a. \\n\n",
        "These activation functions have different properties that make them useful for\n",
        "different language applications or network architectures. For example, the tanh function has the nice properties of being smoothly differentiable and mapping outlier values toward the mean. \n",
        "The rectifier function, on the other hand has nice properties\n",
        "that result from it being very close to linear. In the sigmoid or tanh functions, very\n",
        "high values of z result in values of y that are saturated, i.e., extremely close to 1,\n",
        "and have derivatives very close to 0. Zero derivatives cause problems for learning,\n",
        "because as we’ll see in Section 7.6, we’ll train networks by propagating an error\n",
        "signal backwards, multiplying gradients (partial derivatives) from each layer of the\n",
        "network; gradients that are almost 0 cause the error signal to get smaller and smaller\n",
        "until it is too small to be used for training, a problem called the vanishing gradient \n",
        "problem. Rectifiers don’t have this problem, since the derivative of ReLU for high\n",
        "values of z is 1 rather than very close to 0.\"\"\"\n",
        "slp_chapter7_2 = \"\"\" It turns out, however, that it’s not possible to build a perceptron to compute\n",
        "logical XOR! (It’s worth spending a moment to give it a try!) \\n\n",
        "Notice that there is simply no way to draw a line that separates the positive cases of XOR (01 and 10)\n",
        "from the negative cases (00 and 11). We say that XOR is not a linearly separable function. \\n\n",
        "While the XOR function cannot be calculated by a single perceptron, it can be calculated by a layered network of units. \\n\n",
        "Note that the solution to the XOR problem requires a network of units with non-linear activation functions. A network made up of simple linear (perceptron) units\n",
        "cannot solve the XOR problem. This is because a network formed by many layers of\n",
        "purely linear units can always be reduced (i.e., shown to be computationally identical\n",
        "to) a single layer of linear units with appropriate weights\"\"\"\n",
        "slp_chapter7_3 = \"\"\" A feedforward network is a multilayer \n",
        "network in which the units are connected with no cycles; the outputs from units in\n",
        "each layer are passed to units in the next higher layer, and no outputs are passed\n",
        "back to lower layers. \\n\n",
        "The core of the neural network is the hidden layer h formed of hidden units $h_i$,\n",
        "each of which is a neural unit as described in Section 7.1, taking a weighted sum of\n",
        "its inputs and then applying a non-linearity. In the standard architecture, each layer\n",
        "is fully-connected, meaning that each unit in each layer takes as input the outputs\n",
        "from all the units in the previous layer, and there is a link between every pair of units\n",
        "from two adjacent layers. Thus each hidden unit sums over all the input units. \\n\n",
        "The advantage of using a single matrix W for the weights of the entire layer is\n",
        "that now the hidden layer computation for a feedforward network can be done very\n",
        "efficiently with simple matrix operations. In fact, the computation only has three\n",
        "steps: multiplying the weight matrix by the input vector x, adding the bias vector b,\n",
        "and applying the activation function g (such as the sigmoid, tanh, or ReLU activation\n",
        "function defined above).\n",
        "The output of the hidden layer, the vector h, is thus the following; (for this\n",
        "example we’ll use the sigmoid function $\\\\sigma$ as our activation function): \\n\n",
        "$h = \\\\sigma (Wx + b)$\n",
        "\n",
        "\"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 76,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7341f0a4-b4af-4179-abd3-52cf0906e427"
      },
      "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": 77,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Logistic regression has two phases:\ntraining: we train the system (specifically the weights w and b) using stochastic\ngradient descent and the cross-entropy loss.\ntest: Given a test example x we compute p(y|x) and return the higher probability\nlabel y = 1 or y = 0. \n\nLogistic regression solves this task by learning, from a training set, a vector of\nweights and a bias term. Each weight $w_i$ is a real number, and is associated with one of the input features $x_i$. The weight wi represents how important that input feature\nis to the classification decision, and can be positive (providing evidence that the in\u0002stance being classified belongs in the positive class) or negative (providing evidence\nthat the instance being classified belongs in the negative class). Thus we might\nexpect in a sentiment task the word awesome to have a high positive weight, and\nabysmal to have a very negative weight. The bias term, also called the intercept, is\nanother real number that’s added to the weighted inputs. \n\nTo create a probability, we’ll pass z through the sigmoid function, $\\sigma(z)$. The\nsigmoid function (named because it looks like an s) is also called the logistic function, and gives logistic regression its name. The sigmoid has the following equation:\n$\\sigma(z) = \\frac{1}{1 + e^{-z}} =  \\frac{1}{1 + e^{-(w x + b)}}$\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n We need a loss function that expresses, for an observation x, how close the classifier\noutput ($\\hat{y} = \\sigma(w \\times x + b)$) is to the correct output (y, which is 0 or 1). We’ll call this:\n$L(\\hat{y}, y)$ = How much $\\hat{y}$ differs from the true y. \n\nWe do this via a loss function that prefers the correct class labels of the training examples to be more likely. This is called conditional maximum likelihood\nestimation: we choose the parameters w,b that maximize the log probability of\nthe true y labels in the training data given the observations x. The resulting loss\nfunction is the negative log likelihood loss, generally called the cross-entropy loss: \n$LCE(\\hat{y}, y) = −[y \\log \\sigma (w x + b) + (1−y) \\log(1−\\sigma(w x+b))]$\n\n\n \n\n## SLP Chapter 5.4 Gradient Descent\n Gradient descent\nis a method that finds a minimum of a function by figuring out in which direction\n(in the space of the parameters $\\theta$) the function’s slope is rising the most steeply,\nand moving in the opposite direction. \n\nFor logistic regression, this loss function is conveniently convex. A convex function has just one minimum; there are no local minima to get stuck in, so gradient\ndescent starting from any point is guaranteed to find the minimum. (By contrast,\nthe loss for multi-layer neural networks is non-convex, and gradient descent may\nget stuck in local minima for neural network training and never find the global optimum.) \n\nThe magnitude of the amount to move in gradient descent is the value of the\nslope $\\frac{d}{dw}L(f(x;w), y$) weighted by a learning rate $\\eta$. A higher (faster) learning\nrate means that we should move w more on each step. The change we make in our\nparameter is the learning rate times the gradient: \n\n$w_{t+1} = w_t −\\eta \\frac{d}{dw}L(f(x;w), y$) \n\nThe learning rate $\\eta$ is a hyperparameter that must be adjusted. If it’s too high,\nthe learner will take steps that are too large, overshooting the minimum of the loss\nfunction. If it’s too low, the learner will take steps that are too small, and take too\nlong to get to the minimum. It is common to start with a higher learning rate and then\nslowly decrease it, so that it is a function of the iteration k of training; the notation\n$\\eta_k$can be used to mean the value of the learning rate at iteration k.\n\n\n\n## SLP Chapter 5.5 Regularization\n There is a problem with learning weights that make the model perfectly match the\ntraining data. If a feature is perfectly predictive of the outcome because it happens\nto only occur in one class, it will be assigned a very high weight. The weights for\nfeatures will attempt to perfectly fit details of the training set, in fact too perfectly,\nmodeling noisy factors that just accidentally correlate with the class. This problem is called overfitting. A good model should be able to generalize well from the training\ndata to the unseen test set, but a model that overfits will have poor generalization. \n\nTo avoid overfitting, a new regularization term $R(\\theta)$ is added to the objective\nfunction: \n\n$\\hat{\\theta} = argmax_{\\theta} \\sum_{i=1}^m \\log P(y^{(i)}|x^{(i)}) − \\alpha R(\\theta)$ \n\nThe new regularization term $R(\\theta))$ is used to penalize large weights. Thus a setting\nof the weights that matches the training data perfectly— but uses many weights with\nhigh values to do so—will be penalized more than a setting that matches the data a\nlittle less well, but does so using smaller weights. There are two common ways to\ncompute this regularization term $R(\\theta))$. L2 regularization is a quadratic function of\nthe weight values, named because it uses the (square of the) L2 norm of the weight\nvalues. The L2 norm, is the same as the Euclidean distance of the vector θ\nfrom the origin. \n\n\nL1 regularization is a linear function of the weight values, named after the L1 norm\nthe sum of the absolute values of the weights, or Manhattan distance (the\nManhattan distance is the distance you’d have to walk between two points in a city\nwith a street grid like New York). \n\n\nThese kinds of regularization come from statistics, where L1 regularization is called\nlasso regression and L2 regularization is called ridge regression.\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n The building block of a neural network is a single computational unit. A unit takes\na set of real valued numbers as input, performs some computation on them, and\nproduces an output. \n\nFinally, instead of using z, a linear function of x, as the output, neural units\napply a non-linear function f to z. We will refer to the output of this function as\nthe activation value for the unit, a. \n\nThese activation functions have different properties that make them useful for\ndifferent language applications or network architectures. For example, the tanh function has the nice properties of being smoothly differentiable and mapping outlier values toward the mean. \nThe rectifier function, on the other hand has nice properties\nthat result from it being very close to linear. In the sigmoid or tanh functions, very\nhigh values of z result in values of y that are saturated, i.e., extremely close to 1,\nand have derivatives very close to 0. Zero derivatives cause problems for learning,\nbecause as we’ll see in Section 7.6, we’ll train networks by propagating an error\nsignal backwards, multiplying gradients (partial derivatives) from each layer of the\nnetwork; gradients that are almost 0 cause the error signal to get smaller and smaller\nuntil it is too small to be used for training, a problem called the vanishing gradient \nproblem. Rectifiers don’t have this problem, since the derivative of ReLU for high\nvalues of z is 1 rather than very close to 0.\n\n## SLP Chapter 7.2 The XOR problem\n It turns out, however, that it’s not possible to build a perceptron to compute\nlogical XOR! (It’s worth spending a moment to give it a try!) \n\nNotice that there is simply no way to draw a line that separates the positive cases of XOR (01 and 10)\nfrom the negative cases (00 and 11). We say that XOR is not a linearly separable function. \n\nWhile the XOR function cannot be calculated by a single perceptron, it can be calculated by a layered network of units. \n\nNote that the solution to the XOR problem requires a network of units with non-linear activation functions. A network made up of simple linear (perceptron) units\ncannot solve the XOR problem. This is because a network formed by many layers of\npurely linear units can always be reduced (i.e., shown to be computationally identical\nto) a single layer of linear units with appropriate weights\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n A feedforward network is a multilayer \nnetwork in which the units are connected with no cycles; the outputs from units in\neach layer are passed to units in the next higher layer, and no outputs are passed\nback to lower layers. \n\nThe core of the neural network is the hidden layer h formed of hidden units $h_i$,\neach of which is a neural unit as described in Section 7.1, taking a weighted sum of\nits inputs and then applying a non-linearity. In the standard architecture, each layer\nis fully-connected, meaning that each unit in each layer takes as input the outputs\nfrom all the units in the previous layer, and there is a link between every pair of units\nfrom two adjacent layers. Thus each hidden unit sums over all the input units. \n\nThe advantage of using a single matrix W for the weights of the entire layer is\nthat now the hidden layer computation for a feedforward network can be done very\nefficiently with simple matrix operations. In fact, the computation only has three\nsteps: multiplying the weight matrix by the input vector x, adding the bias vector b,\nand applying the activation function g (such as the sigmoid, tanh, or ReLU activation\nfunction defined above).\nThe output of the hidden layer, the vector h, is thus the following; (for this\nexample we’ll use the sigmoid function $\\sigma$ as our activation function): \n\n$h = \\sigma (Wx + b)$\n\n\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 Your summary here \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 = \"\"\"A recurrent neural network (RNN) is any network that contains a cycle within its\n",
        "network connections, meaning that the value of some unit is directly, or indirectly,\n",
        "dependent on its own earlier outputs as an input. While powerful, such networks\n",
        "are difficult to reason about and to train. \"\"\"\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 = \"\"\" As the example above shows, each lemma can have multiple meanings; the\n",
        "lemma mouse can refer to the rodent or the cursor control device. We call each\n",
        "of these aspects of the meaning of mouse a word sense. The fact that lemmas can\n",
        "be polysemous (have multiple senses) can make interpretation difficult. \\n\n",
        "A more formal definition of synonymy (between words rather than senses) is that\n",
        "two words are synonymous if they are substitutable for one another in any sentence\n",
        "without changing the truth conditions of the sentence, the situations in which the\n",
        "sentence would be true. We often say in this case that the two words have the same\n",
        "propositional meaning. \\n\n",
        "One common kind of relatedness between words is if they belong to the same\n",
        "semantic field. A semantic field is a set of words which cover a particular semantic\n",
        "domain and bear structured relations with each other. For example, words might be\n",
        "related by being in the semantic field of hospitals (surgeon, scalpel, nurse, anesthetic, hospital), restaurants (waiter, menu, plate, food, chef), or houses (door, roof, kitchen, family, bed). \\n\n",
        "\n",
        "Closely related to semantic fields is the idea of a\n",
        "semantic frame semantic frame. A semantic frame is a set of words that denote perspectives or\n",
        "participants in a particular type of event. A commercial transaction, for example,\n",
        "is a kind of event in which one entity trades money to another entity in return for\n",
        "some good or service, after which the good changes hands or perhaps the service is\n",
        "performed. This event can be encoded lexically by using verbs like buy (the event\n",
        "from the perspective of the buyer), sell (from the perspective of the seller), pay\n",
        "(focusing on the monetary aspect), or nouns like buyer. Frames have semantic roles\n",
        "(like buyer, seller, goods, money), and words in a sentence can take on these roles. \\n\n",
        "\n",
        "Finally, words have affective meanings or connotations. The word\n",
        "connotation has different meanings in different fields, but here we use it to mean\n",
        "the aspects of a word’s meaning that are related to a writer or reader’s emotions,\n",
        "sentiment, opinions, or evaluations. For example some words have positive conno\u0002tations (happy) while others have negative connotations (sad).\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\"The idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived (in ways we’ll see) from the distributions of\n",
        "word neighbors. Vectors for representing words are called embeddings (although\n",
        "the term is sometimes more strictly applied only to dense vectors like word2vec. \"\"\"\n",
        "\n",
        "slp_chapter6_3 = \"\"\" In a term-document matrix, each row represents a word in the vocabulary and each\n",
        "column represents a document from some collection of documents. Fig. 6.2 shows a\n",
        "small selection from a term-document matrix showing the occurrence of four words\n",
        "in four plays by Shakespeare. Each cell in this matrix represents the number of times\n",
        "a particular word (defined by the row) occurs in a particular document (defined by\n",
        "the column). \\n\n",
        "\n",
        "An alternative to using the term-document matrix to represent words as vectors of\n",
        "document counts, is to use the term-term matrix, also called the word-word matrix or the term-context matrix, in which the columns are labeled by words rather\n",
        "than documents. This matrix is thus of dimensionality |V|×|V| and each cell records the number of times the row (target) word and the column (context) word co-occur\n",
        "in some context in some training corpus.\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_4 = \"\"\" To measure similarity between two target words v and w, we need a metric that\n",
        "takes two vectors (of the same dimensionality, either both with words as dimensions,\n",
        "hence of length |V|, or both with documents as dimensions as documents, of length\n",
        "|D|) and gives a measure of their similarity. By far the most common similarity\n",
        "metric is the cosine of the angle between the vectors. \\n\n",
        "\n",
        "As we will see, most metrics for similarity between vectors are based on the dot\n",
        "product. The dot product acts as a similarity metric because it will tend to be high\n",
        "just when the two vectors have large values in the same dimensions. Alternatively,\n",
        "vectors that have zeros in different dimensions—orthogonal vectors—will have a\n",
        "dot product of 0, representing their strong dissimilarity. \\n\n",
        "\n",
        "The dot product is higher if a vector is longer, with higher values in each dimension.\n",
        "More frequent words have longer vectors, since they tend to co-occur with more\n",
        "words and have higher co-occurrence values with each of them. The raw dot product\n",
        "thus will be higher for frequent words. But this is a problem; we’d like a similarity\n",
        "metric that tells us how similar two words are regardless of their frequency.\n",
        "We modify the dot product to normalize for the vector length by dividing the\n",
        "dot product by the lengths of each of the two vectors. This normalized dot product\n",
        "turns out to be the same as the cosine of the angle between the two vectors, following\n",
        "from the definition of the dot product between two vectors a and b: \\n\n",
        "\n",
        "$cosine(v,w) = \\\\frac{\\\\sum_{i = 1} v_i w_i}{\\\\sqrt{\\\\sum_{i = 1} w_i^2} \\\\sqrt{\\\\sum_{i = 1} v_i^2}}$\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8c689037-b285-4bdc-afaa-58086c88850e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 79,
      "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\nA recurrent neural network (RNN) is any network that contains a cycle within its\nnetwork connections, meaning that the value of some unit is directly, or indirectly,\ndependent on its own earlier outputs as an input. While powerful, such networks\nare difficult to reason about and to train. \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n As the example above shows, each lemma can have multiple meanings; the\nlemma mouse can refer to the rodent or the cursor control device. We call each\nof these aspects of the meaning of mouse a word sense. The fact that lemmas can\nbe polysemous (have multiple senses) can make interpretation difficult. \n\nA more formal definition of synonymy (between words rather than senses) is that\ntwo words are synonymous if they are substitutable for one another in any sentence\nwithout changing the truth conditions of the sentence, the situations in which the\nsentence would be true. We often say in this case that the two words have the same\npropositional meaning. \n\nOne common kind of relatedness between words is if they belong to the same\nsemantic field. A semantic field is a set of words which cover a particular semantic\ndomain and bear structured relations with each other. For example, words might be\nrelated by being in the semantic field of hospitals (surgeon, scalpel, nurse, anesthetic, hospital), restaurants (waiter, menu, plate, food, chef), or houses (door, roof, kitchen, family, bed). \n\n\nClosely related to semantic fields is the idea of a\nsemantic frame semantic frame. A semantic frame is a set of words that denote perspectives or\nparticipants in a particular type of event. A commercial transaction, for example,\nis a kind of event in which one entity trades money to another entity in return for\nsome good or service, after which the good changes hands or perhaps the service is\nperformed. This event can be encoded lexically by using verbs like buy (the event\nfrom the perspective of the buyer), sell (from the perspective of the seller), pay\n(focusing on the monetary aspect), or nouns like buyer. Frames have semantic roles\n(like buyer, seller, goods, money), and words in a sentence can take on these roles. \n\n\nFinally, words have affective meanings or connotations. The word\nconnotation has different meanings in different fields, but here we use it to mean\nthe aspects of a word’s meaning that are related to a writer or reader’s emotions,\nsentiment, opinions, or evaluations. For example some words have positive conno\u0002tations (happy) while others have negative connotations (sad).\n\n\n## SLP Chapter 6.2 Vector Semantics\nThe idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived (in ways we’ll see) from the distributions of\nword neighbors. Vectors for representing words are called embeddings (although\nthe term is sometimes more strictly applied only to dense vectors like word2vec. \n\n## SLP Chapter 6.3 Words and Vectors\n In a term-document matrix, each row represents a word in the vocabulary and each\ncolumn represents a document from some collection of documents. Fig. 6.2 shows a\nsmall selection from a term-document matrix showing the occurrence of four words\nin four plays by Shakespeare. Each cell in this matrix represents the number of times\na particular word (defined by the row) occurs in a particular document (defined by\nthe column). \n\n\nAn alternative to using the term-document matrix to represent words as vectors of\ndocument counts, is to use the term-term matrix, also called the word-word matrix or the term-context matrix, in which the columns are labeled by words rather\nthan documents. This matrix is thus of dimensionality |V|×|V| and each cell records the number of times the row (target) word and the column (context) word co-occur\nin some context in some training corpus.\n\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n To measure similarity between two target words v and w, we need a metric that\ntakes two vectors (of the same dimensionality, either both with words as dimensions,\nhence of length |V|, or both with documents as dimensions as documents, of length\n|D|) and gives a measure of their similarity. By far the most common similarity\nmetric is the cosine of the angle between the vectors. \n\n\nAs we will see, most metrics for similarity between vectors are based on the dot\nproduct. The dot product acts as a similarity metric because it will tend to be high\njust when the two vectors have large values in the same dimensions. Alternatively,\nvectors that have zeros in different dimensions—orthogonal vectors—will have a\ndot product of 0, representing their strong dissimilarity. \n\n\nThe dot product is higher if a vector is longer, with higher values in each dimension.\nMore frequent words have longer vectors, since they tend to co-occur with more\nwords and have higher co-occurrence values with each of them. The raw dot product\nthus will be higher for frequent words. But this is a problem; we’d like a similarity\nmetric that tells us how similar two words are regardless of their frequency.\nWe modify the dot product to normalize for the vector length by dividing the\ndot product by the lengths of each of the two vectors. This normalized dot product\nturns out to be the same as the cosine of the angle between the two vectors, following\nfrom the definition of the dot product between two vectors a and b: \n\n\n$cosine(v,w) = \\frac{\\sum_{i = 1} v_i w_i}{\\sqrt{\\sum_{i = 1} w_i^2} \\sqrt{\\sum_{i = 1} v_i^2}}$\n\n \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \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": "9c79437e-fc84-46a4-8833-d4b1ba0eb9b2"
      },
      "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": 80,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 17.1 Sequential Decision Problems' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n We begin with an agent that, like all agents, has to make a decision. It has available some\nactions $a$. There may be uncertainty about the current state, so we’ll assume that the agent\nassigns a probability $P(s)$ to each possible current state s. There may also be uncertainty\nabout the action outcomes; the transition model is given by $P(s'|s,a)$, the probability that action a in state s reaches state s'. \nBecause we’re primarily interested in the outcome s', we’ll also use the abbreviated notation $P(RESULT(a)=s')$, the probability of reaching s' by doing\na in the current state, whatever that is. \n \n The agent’s preferences are captured by a <b>utility function</b>, $U(s)$, which assigns a single number to express the \ndesirability of a state. The <b>expected utility</b> of an action given the evidence, EU(a), is just the\naverage utility value of the outcomes, weighted by the probability that the outcome occurs: \n\n$EU(a) = \\sum_{s'}P(\\textnormal{RESULT}(a)=s')U(s')$ \n\nThe principle of <b>maximum expected utility</b> (MEU) says that a rational agent should choose\nthe action that maximizes the agent’s expected utility.\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n<b>Orderability</b>: Given any two lotteries, a rational agent must either prefer one or else\nrate them as equally preferable. That is, the agent cannot avoid deciding. As noted on\npage 412, refusing to bet is like refusing to allow time to pass. \n\nExactly one of $(A \\succ B), (B \\succ A), or (A \\sim B)$ holds. \n\n\n<b>Transitivity</b>: Given any three lotteries, if an agent prefers A to B and prefers B to C,\nthen the agent must prefer A to C. \n\n$(A \\succ B) \\wedge (B \\succ C) \\implies (A \\succ C)$. \n\n\n<b>Continuity</b>: 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. \n\n$A \\succ B \\succ C ⇒ \\exists p [p,A; 1− p,C] \\sim B$ \n\n\n\n<b>Substitutability</b>: If an agent is indifferent between two lotteries A and B, then the\nagent is indifferent between two more complex lotteries that are the same except that\nB is substituted for A in one of them. This holds regardless of the probabilities and the\nother outcome(s) in the lotteries. \n\n$A \\sim B ⇒ [p,A; 1− p,C] \\sim [p,B; 1− p,C]$ \n\n\n<b>Monotonicity</b>: Suppose two lotteries have the same two possible outcomes, A and\nB. If 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 \\sim B \\implies (p > q \\Leftrightarrow [p,A; 1− p,B] \\succ [q,A; 1−q,B])$ \n\n\n<b>Decomposability</b>: Compound lotteries can be reduced to simpler ones using the laws \nof probability. \n\n$[p,A; 1− p,[q,B; 1−q,C]] \\sim [p,A; (1− p)q,B; (1− p)(1−q),C]$ \n\n\n<b>Existence of Utility Function</b>: If an agent’s preferences obey the axioms of utility, then\nthere exists a function U such that $U(A) > U(B)$ if and only if A is preferred to B, and\n$U(A) = U(B)$ if and only if the agent is indifferent between A and B. \n\n\n<b>Expected Utility of a Lottery</b>: The utility of a lottery is the sum of the probability of\neach outcome times the utility of that outcome: \n\n$U([p_1,S_1;\\ldots; p_n,S_n]) = \\sum_i p_i U(S_i)$ \n\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\nThe transition model (or just “model,” when the meaning is clear) de\u0002scribes the outcome of each action in each state. Here, the outcome is stochastic, so we write\n$P(s'|s,a)$ for the probability of reaching state s' if action a is done in state s. (Some authors write $T(s,a,s')$ for the transition model.) \nWe will assume that transitions are <b>Markovian</b>: the probability of reaching s' from s depends only on s and not on the history of earlier states. \n\nBecause the decision problem is sequential, the utility function will depend\non a sequence of states and actions—an environment history—rather than on a single state.\nLater in this section, we investigate the nature of utility functions on histories; for now, we\nsimply stipulate that for every transition from s to s' via action a, the agent receives a reward Reward $R(s,a,s')$. \n\nTo sum up: a sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a <b>Markov decision process</b>,\nor MDP, and consists of a set of states (with an initial state $s_0$); a set ACTIONS(s) of actions\nin each state; a transition model $P(s'|s,a)$; and a reward function $R(s,a,s')$. \n\nNo fixed action sequence can solve the problem, because the agent might end up in a state other than the\ngoal. Therefore, a solution must specify what the agent should do for any state that the agent\nmight reach. A solution of this kind is called a <b>policy</b>. \n\nEach time a given policy is executed starting from the initial state, the stochastic nature\nof the environment may lead to a different environment history. The quality of a policy is\ntherefore measured by the expected utility of the possible environment histories generated\nby that policy. An <b>optimal policy</b> is a policy that yields the highest expected utility. \n\nA <b>finite horizon</b> means that there is a fixed time N after which nothing Infinite horizon\nmatters—the game is over, so to speak. \n\nA policy that depends on the time is called <b>nonstationary</b>. \n\nWith no fixed time limit, on the other hand, there is no reason to behave differently in the\nsame state at different times. Hence, an optimal action depends only on the current state, and\nthe optimal policy is <b>stationary</b>. \n\nUtility of history using additive discounted rewards: \n\n$U_h([s_0,a_0,s_1,a_1,s_2,\\ldots]) = R(s_0,a_0,_1) + \\gamma R(s_1,a_1,s_2) + \\gamma^2 R(s_2,a_2,s_3) + \\ldots$\nwhere the discount factor $\\gamma$ is a number between 0 and 1. The discount factor describes the\npreference of an agent for current rewards over future rewards. When $\\gamma$ is close to 0, rewards\nin the distant future are viewed as insignificant. When $\\gamma$ is close to 1, an agent is more willing\nto wait for long-term rewards. \n\nA policy that is guaranteed to reach a terminal state is called a $proper policy$. \n\nThe utility of a state is the expected reward for the\nnext transition plus the discounted utility of the next state, assuming that the agent chooses\nthe optimal action. That is, the utility of a state is given by (Bellman Equation): \n\n$U(s) = max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma U(s')]$ \n\nAnother important quantity is the action-utility function, or <b>Q-function</b>: $Q(s,a)$ is the\nexpected utility of taking a given action in a given state. The Q-function is related to utilities\nin the obvious way: \n\n$U(s) = max_a Q(s,a)$ \n\n$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma max_{a'} Q(s',a')$ \n\n$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma U(s')$\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n <b>Value Iteration</b>: Start from the bottom of the tree and work your way up. At each iteration, update the utility of each state: \n$U_{i+1}(s) ← max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s0) + \\gamma U_i(s')]$ \n\nValue iteration converges due to <b>contraction</b>(a function with one argument that brings two different inputs closer when applied to both). \n\n<b>Policy Iteration: </b> Start with some initial policy $\\pi_0$ and repeat policy evaluation and policy improvement until it converges to optimal policy. \n\n<b>Policy evaluation</b>: Given a policy $\\pi_i$, calculate $U_i =U^{\\pi_i}$ the utility of each state if $\\pi_i$ \n were to be executed. \n\n$U_{i+1}(s) ← \\sum_{s'} P(s'|s, \\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$ \n\n<b>Policy improvement</b>: Calculate a new MEU policy $\\pi_{i+1}$, using one-step look-ahead based on $U_i$. \n\n$\\pi_{i+1}(s) ← argmax_{a} \\sum_{s'} P(s'|s, a)[R(s,a,s') + \\gamma U_i(s')]$ \n\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n An n-armed bandit has n levers. Behind each\nlever is a fixed but unknown probability distribution of winnings; each pull samples from that\nunknown distribution. \n\nThis is an example of the ubiquitous\ntradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information, which can in some cases be\nconverted into a better policy and better long-term rewards. \n\nThe key property is that the arms are independent, coupled only by the fact that the agent can work on only one arm at a time.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n An alternative is reinforcement learning (RL), in which an agent interacts with the world and periodically receives rewards (or, in the terminology of psychology, reinforcements)\nthat reflect how well it is doing. \n \nThe goal is the same in as in MDP reinforcement learning: maximize the expected sum of rewards. Reinforcement learning differs from “just solving\nan MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. It may not know the transition model or the reward function, and it has to act in order\nto learn more. \n\nIt turns out, however, that a little bit of expertise can go a long way in reinforcement learning. The two examples in the preceding paragraph—the win/loss rewards for chess and\nracing—are what we call <b>sparse</b> rewards, because in the vast majority of states the agent is given no informative reward signal at all. \n\n<b>Model-based reinforcement learning</b>: In these approaches the agent uses a transition model of the environment to help interpret the reward signals and to make decisions\nabout how to act. The model may be initially unknown, in which case the agent learns\nthe model from observing the effects of its actions, or it may already be known—for\nexample, a chess program may know the rules of chess even if it does not know how\nto choose good moves. In partially observable environments, the transition model is\nalso useful for state estimation. Model-based reinforcement learning\nsystems often learn a utility function $U(s)$, in terms of the sum of rewards from state s onward. \n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n We start with the simple case of a fully observable environment with a small number of\nactions and states, in which an agent already has a fixed policy $\\pi(s)$ that determines its actions.\nThe agent is trying to learn the utility function $U^\\pi(s)$—the expected total discounted reward\nif policy $\\pi$ is executed beginning in state s. We call this a passive learning agent. \n\n<b>Direct utility estimation</b>: The idea of direct utility estimation is that the utility of a state is defined as the expected\ntotal reward from that state onward (called the expected reward-to-go), and that each trial Reward-to-go\nprovides a sample of this quantity for each state visited. By ignoring the connections between states, direct utility estimation misses opportunities for\nlearning. \n \n$U_{i}(s) ← \\sum_{s'} P(s'|s, \\pi_i(s))[R(s,\\pi_i(s),s') + \\gamma U_i(s')]$ \n\n<b> Temporal Difference Learning </b>: Update the utility of a state s when a transition occurs from state s to s': \n\n$U^\\pi(s) ← U^\\pi(s) + \\alpha[R(s,\\pi(s),s') +γ\\gamma U^\\pi(s')− U^\\pi(s)]$ where $\\alpha$ is the learning rate. \n\nFurthermore, if we turn the parameter $\\alpha$ into a function that decreases as the number\nof times a state has been visited increases, then $U^\\pi(s)$ itself will converge to the correct value.\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n The <b>Q-learning</b> method avoids the need for a model by learning an action-utility function\n$Q(s,a)$ instead of a utility function $U(s)$. $Q(s,a)$ denotes the expected total discounted reward\nif the agent takes action a in s and acts optimally thereafter. Knowing the Q-function enables\nthe agent to act optimally simply by choosing $argmax_a Q(s,a)$, with no need for look-ahead\nbased on a transition model: \n\n$Q(s,a) = Q(s,a) + \\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)]$ \n \nThis update is calculated whenever action a is executed in state s leading to state s'. \n\nThe important part of this equation is what it does not contain: a TD Q-learning agent does not need a transition model either for learning or for action selection.\nAs noted at the beginning of the chapter, model-free methods can be applied even in very complex domains because no model need be provided or learned. On the other hand, the Q-learning agent has no means of looking into the future, so it may have difficulty when rewards\nare sparse and long action sequences must be constructed to reach them. \n\nQ-learning is an <b>off-policy</b> learning algorithm, because it learns Q-values that answer the \nquestion “What would this action be worth in this state, assuming that I stop using whatever\npolicy I am using now, and start acting according to a policy that chooses the best action\n(according to my estimates)?” \n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n If there are too many states to hold in memory, we can use function approximation to approximate the utility function and Q-functions as weighted linear combination of features: \n\n$Q(s,a) =  w_1 f_1(s,a) + w_2 f_2(s,a) + w_3 f_3(s,a) + \\ldots$ \n\nUpdating the Q-function after a transition: \n\n$Q(s,a) = Q(s,a) + \\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)]$ \n\nUpdating weights: \n\n$w_i = w_i + \\alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') − Q(s,a)] f_i(s,a)$\n\n\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n The fundamental idea of decision theory is that\nan agent is rational if and only if it chooses\nthe action that yields the highest expected utility, averaged over all the possible outcomes\nof the action. This is called the principle of maximum expected utility (MEU). \n\n## AIMA Chapter 12.2 Basic Probability Notation\n In probability theory, the set of all possible worlds is called the <b>sample space</b>. \n\nProbabilistic assertions and queries are not usually about particular possible worlds, but\nabout sets of them. For example, we might ask for the probability that the two dice add up\nto 11, the probability that doubles are rolled, and so on. In probability theory, these sets\nare called <b>events</b>. In logic, a set of worlds corresponds to a <b>proposition</b> in a formal language; specifically, for each\nproposition, the corresponding set contains just those possible worlds in which the proposition holds. (Hence, “event” and “proposition” mean roughly the same thing in this context,\nexcept that a proposition is expressed in a formal language.) \n\nThe definition of conditional probability, can be written in a different form called the product rule: \n\n$P(a \\wedge b) = P(a|b) P(b)$ \n\nVariables in probability theory are called random variables, and their names begin with\nan uppercase letter. Thus, in the dice example, Total and Die1 are random variables. Every random variable is a function that maps from the domain of possible worlds $\\omega$ to some \nrange—the set of possible values it can take on. \n\nWe can also derive the well-known formula for the probability of a disjunction, sometimes\ncalled the inclusion–exclusion principle: \n\n$P(a \\vee b) = P(a) +P(b)− P(a \\wedge b)$ \n\nThis process is called <b>marginalization</b>, or summing out—because we sum up the probabilities for each possible value of the other variables, thereby taking them out of the equation.\nWe can write the following general marginalization rule for any sets of variables Y and Z: \n\n$P(Y) = \\sum_z P(Y,Z=z)$ \n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n The property is called independence (also marginal independence and absolute independence). In particular, the weather is independent of one’s\ndental problems. Independence between propositions a and b can be written as: \n\n$P(a|b)=P(a)$ or $P(b|a)=P(b)$ or $P(a∧b)=P(a)P(b)$  \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n <b>Bayes’ rule</b>: \n\n$P(a|b) = \\frac{P(b|a)P(a)}{P(b)}$ \n\nThe general definition of <b>conditional independence</b> of two variables X and Y, given a\nthird variable Z, is : \n\n$P(X,Y |Z) = P(X |Z)P(Y |Z)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n The dentistry example illustrates a commonly occurring pattern in which a single cause directly influences a number of effects, all of which are conditionally independent, given the\ncause. The full joint distribution can be written as: \n\n$P(Cause,Effect_1,\\ldots,Effect_n) = P(Cause) \\prod_i P(Effect_i|Cause)$ \n\nSuch a probability distribution is called a $naive Bayes$ model—“naive” because it is often\nused (as a simplifying assumption) in cases where the “effect” variables are not strictly independent given the cause variable. \n\n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n We’ll represent a sequence of N words either as\n$w_1 \\ldots w_n $ or $w_{1:n}$ (so the expression $w_{1:n -  1}$ means the string w_1 \\ldots w_{n - 1}). \n\nNow how can we compute probabilities of entire sequences like $P(w_1,w_2,\\ldots,w_n)$?\nOne thing we can do is decompose this probability using the chain rule of probability: \n\n$P(X_1 \\ldots X_n) = P(X_1)P(X_2|X_1)P(X_3|X_{1:2}) \\ldots P(X_n|X_{1:n−1})$ \n\nEquation suggests that we could estimate the joint probability of an entire sequence of\nwords by multiplying together a number of conditional probabilities. But using the\nchain rule doesn’t really seem to help us! We don’t know any way to compute the\nexact probability of a word given a long sequence of preceding words. \n\nAs we said above, we can’t just estimate by counting the number of times every word\noccurs following every long string, because language is creative and any particular\ncontext might have never occurred before! \n\nThe intuition of the n-gram model is that instead of computing the probability of\na word given its entire history, we can approximate the history by just the last few\nwords. \n\nThe assumption that the probability of a word depends only on the previous word is\ncalled a Markov assumption. Markov models are the class of probabilistic models\nthat assume we can predict the probability of some future unit without looking too\nfar into the past. We can generalize the bigram (which looks one word into the past)\nto the trigram (which looks two words into the past) and thus to the n-gram (which\nlooks n−1 words into the past). \n\nFor example, to compute a particular bigram probability of a word y given a\nprevious word x, we’ll compute the count of the bigram C(xy) and normalize by the\nsum of all the bigrams that share the same first word x:\n$P(w_n|w_{n−1}) = \\frac{C(w_{n−1}w_n)}{C(w_{n-1})}$\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n The best way to evaluate the performance of a language model is to embed it in\nan application and measure how much the application improves. Such end-to-end\nevaluation is called extrinsic evaluation. \n\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application. \n\nIn practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (sometimes called PP for short)\nof a language model on a test set is the inverse probability of the test set, normalized\nby the number of words. \n\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 Statistical models are likely to be pretty useless as predictors if the training sets and the test sets are as different as Shakespeare and WSJ.\nHow should we deal with this problem when we build n-gram models? One step\nis to be sure to use a training corpus that has a similar genre to whatever task we are\ntrying to accomplish. To build a language model for translating legal documents,\nwe need a training corpus of legal documents. To build a language model for a\nquestion-answering system, we need a training corpus of questions. \n\n## SLP Chapter 3.5 Smoothing\n What do we do with words that are in our vocabulary (they are not unknown words)\nbut appear in a test set in an unseen context (for example they appear after a word\nthey never appeared after in training)? To keep a language model from assigning\nzero probability to these unseen events, we’ll have to shave off a bit of probability\nmass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting. \n\n<b>Laplace Smoothing</b>\n$P(w_n|w_{n−1}) = \\frac{C(w_{n−1}w_n) + 1}{C(w_{n-1}) + |V|}$\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* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n This section introduces a data structure called a Bayesian network to represent the dependencies among variables. Bayesian networks can represent\nessentially any full joint probability distribution and in many cases can do so very concisely.\nA Bayesian network is a directed graph in which each node is annotated with quantitative\nprobability information. The full specification is as follows: \n\n1. Each node corresponds to a random variable, which may be discrete or continuous. \n\n2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to\nnode Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a\ndirected acyclic graph, or DAG. \n\n3. Each node $X_i$ has associated probability information $\theta(X_i|Parents(X_i))$ that quantifies the effect of the parents on the node using a finite number of parameters. \n\nThe intuitive meaning of an arrow is typically that X has a direct influence on Y, which suggests that causes should be parents of effects. \n\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The syntax of a Bayes net consists of a directed acyclic graph with some local probability\ninformation attached to each node. The semantics defines how the syntax corresponds to a joint distribution over the variables of the network. \n\nThe semantics of Bayes nets defines each entry in the joint distribution as follows: \n\n$P(x_1, \\ldots, x_n) = \\prod_{i = 1}^n \\theta(x_i|parents(X_i))$ \n\n<b> Chain Rule </b>: \n\n$P(x_1, \\ldots, x_n) = P(x_n | x_{n−1}, \\ldots, x_1) P(x_{n−1} | x_{n−2}, \\ldots, x_1) \\ldots P(x_2 | x_1)P(x_1)$ \n\nAs well as being a complete and nonredundant representation of the domain, a Bayes net\ncan often be far more compact than the full joint distribution. This property is what makes\nit feasible to handle domains with many variables. The compactness of Bayesian networks\nis an example of a general property of locally structured (also called sparse) systems. In a\nlocally structured system, each subcomponent interacts directly with only a bounded number\nof other components, regardless of the total number of components. Local structure is usually\nassociated with linear rather than exponential growth in complexity. \n\nTwo variables $X$, $Y$ are conditionally independent given a third variable $Z$ if all undirected paths from $X$ to $Y$ are inactive. \n\nA path is active if each triple is active: either a causal chain ($A \\rightarrow B \\rightarrow C$ and B is unobserved), common cause ($A \\leftarrow B \\rightarrow C$ and B is unobserved)\nor common effect ($A \\rightarrow B \\leftarrow C$ and B or one of its descendants is observed)\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Game Theory\n In supervised learning the agent observes input-output pairs and learns a function that\nmaps from input to output. For example, the inputs could be camera images, each\none accompanied by an output saying “bus” or “pedestrian,” etc. An output like this\nis called a label. The agent learns a function that, when given a new image, predicts\nthe appropriate label. In the case of braking actions (component 1 above), an input is\nthe current state (speed and direction of the car, road condition), and an output is the\ndistance it took to stop. In this case a set of output values can be obtained by the agent\nfrom its own percepts (after the fact); the environment is the teacher, and the agent\nlearns a function that maps states to stopping distance. \n\n\nIn unsupervised learning the agent learns patterns in the input without any explicit\nfeedback. The most common unsupervised learning task is clustering: detecting potentially useful clusters of input examples. For example, when shown millions of images\ntaken from the Internet, a computer vision system can identify a large cluster of similar\nimages which an English speaker would call “cats.” \n\n\nIn reinforcement learning the agent learns from a series of reinforcements: rewards \nand punishments. For example, at the end of a chess game the agent is told that it has\nwon (a reward) or lost (a punishment). It is up to the agent to decide which of the\nactions prior to the reinforcement were most responsible for it, and to alter its actions\nto aim towards more rewards in the future.\n\n\n## AIMA Chapter 19.2 Optimal Decisions in Games\n We say that a hypothesis is underfitting when it fails to find a Underfitting\npattern in the data. \n\nBy variance we mean the amount of change in the hypothesis due to fluctuation in the Variance\ntraining data. \n\nWe say a function is overfitting the data when it pays too much attention to the particular data set it is trained Overfitting\non, causing it to perform poorly on unseen data. \n\nOften there is a bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may gen\u0002eralize better.\n\n\n## AIMA Chapter 19.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 19.4 Stochastic Games\n Your summary here \n\n## AIMA Chapter 19.5 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 19.6 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n We represent a text document as if it were a bag-of-words, that is, an unordered set of words with their position\nignored, keeping only their frequency in the document. \n\n\nTo return to classification: we compute the most probable class $\\hat{c}$ given some\ndocument d by choosing the class which has the highest product of two probabilities:\nthe prior probability of the class $P(c)$ and the likelihood of the document $P(d|c)$ \n\n\nThe first is the bag of words assumption discussed intuitively above: we assume\nposition doesn’t matter, and that the word “love” has the same effect on classification\nwhether it occurs as the 1st, 20th, or last word in the document. Thus we assume\nthat the features f1, f2,..., fn only encode word identity and not position.\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n To learn the probability $P(f_i|c)$, we’ll assume a feature is just the existence of a word\nin the document’s bag of words, and so we’ll want $P(w_i|c)$, which we compute as\nthe fraction of times the word $w_i$ appears among all words in all documents of topic\nc. \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 Your summary here \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Logistic regression has two phases:\ntraining: we train the system (specifically the weights w and b) using stochastic\ngradient descent and the cross-entropy loss.\ntest: Given a test example x we compute p(y|x) and return the higher probability\nlabel y = 1 or y = 0. \n\nLogistic regression solves this task by learning, from a training set, a vector of\nweights and a bias term. Each weight $w_i$ is a real number, and is associated with one of the input features $x_i$. The weight wi represents how important that input feature\nis to the classification decision, and can be positive (providing evidence that the in\u0002stance being classified belongs in the positive class) or negative (providing evidence\nthat the instance being classified belongs in the negative class). Thus we might\nexpect in a sentiment task the word awesome to have a high positive weight, and\nabysmal to have a very negative weight. The bias term, also called the intercept, is\nanother real number that’s added to the weighted inputs. \n\nTo create a probability, we’ll pass z through the sigmoid function, $\\sigma(z)$. The\nsigmoid function (named because it looks like an s) is also called the logistic function, and gives logistic regression its name. The sigmoid has the following equation:\n$\\sigma(z) = \\frac{1}{1 + e^{-z}} =  \\frac{1}{1 + e^{-(w x + b)}}$\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n We need a loss function that expresses, for an observation x, how close the classifier\noutput ($\\hat{y} = \\sigma(w \\times x + b)$) is to the correct output (y, which is 0 or 1). We’ll call this:\n$L(\\hat{y}, y)$ = How much $\\hat{y}$ differs from the true y. \n\nWe do this via a loss function that prefers the correct class labels of the training examples to be more likely. This is called conditional maximum likelihood\nestimation: we choose the parameters w,b that maximize the log probability of\nthe true y labels in the training data given the observations x. The resulting loss\nfunction is the negative log likelihood loss, generally called the cross-entropy loss: \n$LCE(\\hat{y}, y) = −[y \\log \\sigma (w x + b) + (1−y) \\log(1−\\sigma(w x+b))]$\n\n\n \n\n## SLP Chapter 5.4 Gradient Descent\n Gradient descent\nis a method that finds a minimum of a function by figuring out in which direction\n(in the space of the parameters $\\theta$) the function’s slope is rising the most steeply,\nand moving in the opposite direction. \n\nFor logistic regression, this loss function is conveniently convex. A convex function has just one minimum; there are no local minima to get stuck in, so gradient\ndescent starting from any point is guaranteed to find the minimum. (By contrast,\nthe loss for multi-layer neural networks is non-convex, and gradient descent may\nget stuck in local minima for neural network training and never find the global optimum.) \n\nThe magnitude of the amount to move in gradient descent is the value of the\nslope $\\frac{d}{dw}L(f(x;w), y$) weighted by a learning rate $\\eta$. A higher (faster) learning\nrate means that we should move w more on each step. The change we make in our\nparameter is the learning rate times the gradient: \n\n$w_{t+1} = w_t −\\eta \\frac{d}{dw}L(f(x;w), y$) \n\nThe learning rate $\\eta$ is a hyperparameter that must be adjusted. If it’s too high,\nthe learner will take steps that are too large, overshooting the minimum of the loss\nfunction. If it’s too low, the learner will take steps that are too small, and take too\nlong to get to the minimum. It is common to start with a higher learning rate and then\nslowly decrease it, so that it is a function of the iteration k of training; the notation\n$\\eta_k$can be used to mean the value of the learning rate at iteration k.\n\n\n\n## SLP Chapter 5.5 Regularization\n There is a problem with learning weights that make the model perfectly match the\ntraining data. If a feature is perfectly predictive of the outcome because it happens\nto only occur in one class, it will be assigned a very high weight. The weights for\nfeatures will attempt to perfectly fit details of the training set, in fact too perfectly,\nmodeling noisy factors that just accidentally correlate with the class. This problem is called overfitting. A good model should be able to generalize well from the training\ndata to the unseen test set, but a model that overfits will have poor generalization. \n\nTo avoid overfitting, a new regularization term $R(\\theta)$ is added to the objective\nfunction: \n\n$\\hat{\\theta} = argmax_{\\theta} \\sum_{i=1}^m \\log P(y^{(i)}|x^{(i)}) − \\alpha R(\\theta)$ \n\nThe new regularization term $R(\\theta))$ is used to penalize large weights. Thus a setting\nof the weights that matches the training data perfectly— but uses many weights with\nhigh values to do so—will be penalized more than a setting that matches the data a\nlittle less well, but does so using smaller weights. There are two common ways to\ncompute this regularization term $R(\\theta))$. L2 regularization is a quadratic function of\nthe weight values, named because it uses the (square of the) L2 norm of the weight\nvalues. The L2 norm, is the same as the Euclidean distance of the vector θ\nfrom the origin. \n\n\nL1 regularization is a linear function of the weight values, named after the L1 norm\nthe sum of the absolute values of the weights, or Manhattan distance (the\nManhattan distance is the distance you’d have to walk between two points in a city\nwith a street grid like New York). \n\n\nThese kinds of regularization come from statistics, where L1 regularization is called\nlasso regression and L2 regularization is called ridge regression.\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n The building block of a neural network is a single computational unit. A unit takes\na set of real valued numbers as input, performs some computation on them, and\nproduces an output. \n\nFinally, instead of using z, a linear function of x, as the output, neural units\napply a non-linear function f to z. We will refer to the output of this function as\nthe activation value for the unit, a. \n\nThese activation functions have different properties that make them useful for\ndifferent language applications or network architectures. For example, the tanh function has the nice properties of being smoothly differentiable and mapping outlier values toward the mean. \nThe rectifier function, on the other hand has nice properties\nthat result from it being very close to linear. In the sigmoid or tanh functions, very\nhigh values of z result in values of y that are saturated, i.e., extremely close to 1,\nand have derivatives very close to 0. Zero derivatives cause problems for learning,\nbecause as we’ll see in Section 7.6, we’ll train networks by propagating an error\nsignal backwards, multiplying gradients (partial derivatives) from each layer of the\nnetwork; gradients that are almost 0 cause the error signal to get smaller and smaller\nuntil it is too small to be used for training, a problem called the vanishing gradient \nproblem. Rectifiers don’t have this problem, since the derivative of ReLU for high\nvalues of z is 1 rather than very close to 0.\n\n## SLP Chapter 7.2 The XOR problem\n It turns out, however, that it’s not possible to build a perceptron to compute\nlogical XOR! (It’s worth spending a moment to give it a try!) \n\nNotice that there is simply no way to draw a line that separates the positive cases of XOR (01 and 10)\nfrom the negative cases (00 and 11). We say that XOR is not a linearly separable function. \n\nWhile the XOR function cannot be calculated by a single perceptron, it can be calculated by a layered network of units. \n\nNote that the solution to the XOR problem requires a network of units with non-linear activation functions. A network made up of simple linear (perceptron) units\ncannot solve the XOR problem. This is because a network formed by many layers of\npurely linear units can always be reduced (i.e., shown to be computationally identical\nto) a single layer of linear units with appropriate weights\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n A feedforward network is a multilayer \nnetwork in which the units are connected with no cycles; the outputs from units in\neach layer are passed to units in the next higher layer, and no outputs are passed\nback to lower layers. \n\nThe core of the neural network is the hidden layer h formed of hidden units $h_i$,\neach of which is a neural unit as described in Section 7.1, taking a weighted sum of\nits inputs and then applying a non-linearity. In the standard architecture, each layer\nis fully-connected, meaning that each unit in each layer takes as input the outputs\nfrom all the units in the previous layer, and there is a link between every pair of units\nfrom two adjacent layers. Thus each hidden unit sums over all the input units. \n\nThe advantage of using a single matrix W for the weights of the entire layer is\nthat now the hidden layer computation for a feedforward network can be done very\nefficiently with simple matrix operations. In fact, the computation only has three\nsteps: multiplying the weight matrix by the input vector x, adding the bias vector b,\nand applying the activation function g (such as the sigmoid, tanh, or ReLU activation\nfunction defined above).\nThe output of the hidden layer, the vector h, is thus the following; (for this\nexample we’ll use the sigmoid function $\\sigma$ as our activation function): \n\n$h = \\sigma (Wx + b)$\n\n\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 Your summary here \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\nA recurrent neural network (RNN) is any network that contains a cycle within its\nnetwork connections, meaning that the value of some unit is directly, or indirectly,\ndependent on its own earlier outputs as an input. While powerful, such networks\nare difficult to reason about and to train. \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n As the example above shows, each lemma can have multiple meanings; the\nlemma mouse can refer to the rodent or the cursor control device. We call each\nof these aspects of the meaning of mouse a word sense. The fact that lemmas can\nbe polysemous (have multiple senses) can make interpretation difficult. \n\nA more formal definition of synonymy (between words rather than senses) is that\ntwo words are synonymous if they are substitutable for one another in any sentence\nwithout changing the truth conditions of the sentence, the situations in which the\nsentence would be true. We often say in this case that the two words have the same\npropositional meaning. \n\nOne common kind of relatedness between words is if they belong to the same\nsemantic field. A semantic field is a set of words which cover a particular semantic\ndomain and bear structured relations with each other. For example, words might be\nrelated by being in the semantic field of hospitals (surgeon, scalpel, nurse, anesthetic, hospital), restaurants (waiter, menu, plate, food, chef), or houses (door, roof, kitchen, family, bed). \n\n\nClosely related to semantic fields is the idea of a\nsemantic frame semantic frame. A semantic frame is a set of words that denote perspectives or\nparticipants in a particular type of event. A commercial transaction, for example,\nis a kind of event in which one entity trades money to another entity in return for\nsome good or service, after which the good changes hands or perhaps the service is\nperformed. This event can be encoded lexically by using verbs like buy (the event\nfrom the perspective of the buyer), sell (from the perspective of the seller), pay\n(focusing on the monetary aspect), or nouns like buyer. Frames have semantic roles\n(like buyer, seller, goods, money), and words in a sentence can take on these roles. \n\n\nFinally, words have affective meanings or connotations. The word\nconnotation has different meanings in different fields, but here we use it to mean\nthe aspects of a word’s meaning that are related to a writer or reader’s emotions,\nsentiment, opinions, or evaluations. For example some words have positive conno\u0002tations (happy) while others have negative connotations (sad).\n\n\n## SLP Chapter 6.2 Vector Semantics\nThe idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived (in ways we’ll see) from the distributions of\nword neighbors. Vectors for representing words are called embeddings (although\nthe term is sometimes more strictly applied only to dense vectors like word2vec. \n\n## SLP Chapter 6.3 Words and Vectors\n In a term-document matrix, each row represents a word in the vocabulary and each\ncolumn represents a document from some collection of documents. Fig. 6.2 shows a\nsmall selection from a term-document matrix showing the occurrence of four words\nin four plays by Shakespeare. Each cell in this matrix represents the number of times\na particular word (defined by the row) occurs in a particular document (defined by\nthe column). \n\n\nAn alternative to using the term-document matrix to represent words as vectors of\ndocument counts, is to use the term-term matrix, also called the word-word matrix or the term-context matrix, in which the columns are labeled by words rather\nthan documents. This matrix is thus of dimensionality |V|×|V| and each cell records the number of times the row (target) word and the column (context) word co-occur\nin some context in some training corpus.\n\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n To measure similarity between two target words v and w, we need a metric that\ntakes two vectors (of the same dimensionality, either both with words as dimensions,\nhence of length |V|, or both with documents as dimensions as documents, of length\n|D|) and gives a measure of their similarity. By far the most common similarity\nmetric is the cosine of the angle between the vectors. \n\n\nAs we will see, most metrics for similarity between vectors are based on the dot\nproduct. The dot product acts as a similarity metric because it will tend to be high\njust when the two vectors have large values in the same dimensions. Alternatively,\nvectors that have zeros in different dimensions—orthogonal vectors—will have a\ndot product of 0, representing their strong dissimilarity. \n\n\nThe dot product is higher if a vector is longer, with higher values in each dimension.\nMore frequent words have longer vectors, since they tend to co-occur with more\nwords and have higher co-occurrence values with each of them. The raw dot product\nthus will be higher for frequent words. But this is a problem; we’d like a similarity\nmetric that tells us how similar two words are regardless of their frequency.\nWe modify the dot product to normalize for the vector length by dividing the\ndot product by the lengths of each of the two vectors. This normalized dot product\nturns out to be the same as the cosine of the angle between the two vectors, following\nfrom the definition of the dot product between two vectors a and b: \n\n\n$cosine(v,w) = \\frac{\\sum_{i = 1} v_i w_i}{\\sqrt{\\sum_{i = 1} w_i^2} \\sqrt{\\sum_{i = 1} v_i^2}}$\n\n \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}