{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c04f1b73-048c-4f99-efc3-9f8f1d544ad6"
      },
      "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": 30,
      "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": "cfc2609c-c095-4c85-f9ac-a3a5b71aa206"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "$P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\n",
        "utility function assigns number to desirability of state \n",
        "\n",
        "expected utility of an action is sum of probability of states times utility of state \n",
        "\n",
        "principle of maximum expected utility (MEU) says that a rational agent should choose\n",
        "the action that maximizes the agent’s expected utility \n",
        "\n",
        "meu formalizes notion of \"doing the right thing\" but does not operationalize\n",
        "\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\n",
        "the agent will achieve the highest possible performance score (averaged over all the possible\n",
        "environments)\n",
        "\n",
        "The utility function applies to the very next state, so it can\n",
        "be used to guide actions step by step.\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 =  \"\"\"\n",
        "orderability - must make a decision- one better, or equal\n",
        "\n",
        "transitivity a > b, b > c means a > c\n",
        "\n",
        "continuity if b is between a and c, then there is some probability for a and c where surefire b is equivalent\n",
        "\n",
        "SUBSTITUTABILITY - if indifferent between a and b, then comparisons for more complex lotteries should be the same if a is switched for b\n",
        "monotonicity - if a is better than b, then the agent prefers the lottery that has a higher probability for a and vice versa\n",
        "\n",
        "DECOMPOSABILITY - can be reduced to simpler ones with probability\n",
        "if preferences obery above, there is a utility function\n",
        "\n",
        "expected utility is sum of probability times utility\n",
        "\n",
        "only needs preference ranking, don't specifically need numbers - value function, ordinal utility function\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "preference elicitation - present choices and use observed preferences to pin down underlying utility function\n",
        "choose between s and standard lottery\n",
        "\n",
        "value of statistical life, ~$10 mil\n",
        "\n",
        "micromort, one in a million chance of death, actual behavior reflex lower monetary value for micromort\n",
        "\n",
        "qaly, quality adjusted life year, shorter life expectancy better than disability\n",
        "\n",
        "risk averse in gains, risk seeking in losses\n",
        "\n",
        "difference between emv of loterry and certainty equivalent is insurance premium\n",
        "\n",
        "small changes will be approx linear, linear curves are risk neutral\n",
        "\n",
        "optimizer's curse - estimated EU of best choice is too high\n",
        "\n",
        "decision theory is normative, describes should\n",
        "descriptive theory describes how it actually is\n",
        "\n",
        "framing effect\n",
        "anchoring effect\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "the transition model (or just “model,” when the meaning is clear)\n",
        "describes the outcome of each action in each state.\n",
        "\n",
        "We will assume that transitions are\n",
        "Markovian: the probability of reaching from depends only on and not on the history of\n",
        "earlier states. \n",
        "\n",
        "the utility function will depend on a\n",
        "sequence of states and actions—an environment history—rather than on a single state. \n",
        "\n",
        "agents will receive a reward from state s to s' on action a, bounded by +- r max\n",
        "\n",
        "a sequential decision problem for a fully observable, stochastic environment\n",
        "with a Markovian transition model and additive rewards is called a Markov decision\n",
        "process, or MDP, and consists of a set of states (with an initial state s0); a set ACTIONS(s) of\n",
        "actions in each state; a transition model P(s' | s, a); and a reward function R(s,a,s').\n",
        "\n",
        "usually solving mdps involve dp\n",
        "\n",
        "a policy specifies what an agent should do at any state (a solution to an mdp).\n",
        "optimal policy yields highest EU. pi* denotes optimal policy.\n",
        "\n",
        " A finite horizon means that there is a fixed time after which nothing\n",
        "matters\n",
        "\n",
        "A policy that\n",
        "depends on the time is called nonstationary, depends only on current state = stationary\n",
        "\n",
        "“infinite horizon” does not necessarily\n",
        "mean that all state sequences are infinite; it just means that there is no fixed deadline\n",
        "\n",
        "additive discounted rewards: the utility of a history is sum of rewards multiplied by a discount factor gamma between 0 and 1 at each step.\n",
        "gamma represents preference of agent for current over future rewards\n",
        "\n",
        "gamma = 1 = additive rewards, used implicitly in use of path cost functions in heuristic search\n",
        "\n",
        "reasons for discounted rewards\n",
        "(1) animals value near term\n",
        "(2) getting money now and investing is good\n",
        "(3) uncertainty of true rewards (may never arrive)\n",
        "(4) preferences over histories, preferences between state sequences are stationary\n",
        "\n",
        "expected utility of a policy is just expected value of executing it down with discount factor\n",
        "\n",
        "with infinite horizon, optimal strategy independent of starting state\n",
        "\n",
        "bellman equation: U(s) = max sum{ p(s'|s,a) * (R(s,a,s' + gamma * U(s')) } over actions a\n",
        "\n",
        "action utility function (q function) is expected utility of action + state instead  of just state, U = max action (q(s,a))\n",
        "\n",
        "pi * = argmax q\n",
        "\n",
        "shaping theorem:\n",
        "r(s,a,s' = r(s,a,s') + gamma f(s) - f(s)\n",
        "\n",
        "function phi (s) often called a :potential\", if higher in states with higher utility, you can lead the agent \"uphill\" in utility.\n",
        "phi acts as gradient\n",
        "\n",
        "simplest way to represent mdps is through 3d tables s^2a, or can be sparse so sa\n",
        "\n",
        "dynamic decision networks - decision, reward, utility nodes feed forward to utility function\n",
        "\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "\n",
        "value iteration \"bellman step\"\n",
        "\n",
        "set u_i+1(s) to max a of sum of p(s'|s,a) * r(s,a,s') + gamma u_i(s')\n",
        "\n",
        "applied simultaneously to all states at each iteration, eventually reach equilibrium, final must be solutions to bellman eq\n",
        "\n",
        "a contraction is a function of one argument that, when\n",
        "applied to two different inputs in turn, produces two output values that are “closer\n",
        "together,” by at least some constant factor, than the original inputs. For example, the\n",
        "function “divide by two” is a contraction, because, after we divide any two numbers by two,\n",
        "their difference is halved, eventually reaches \"fixed point\" where function doesn't change (0)\n",
        "\n",
        "contraction only has one fixed point\n",
        "\n",
        "value must get closer to fixed point with repeated application of contraction\n",
        "\n",
        "bellman update is a contraction by a factor of gamma on the space of utility vectors\n",
        "\n",
        "terminates after under certain error (can bound error in utility estimates if we stop after a finite nubmer of iterations)\n",
        "\n",
        "if ∥Ui − U ∥< ϵ then ∥ U πi − U ∥< 2ϵ.\n",
        "\n",
        "policy iteration alternates between policy evaluation and improvement, terminates when no change in utilities after improvement\n",
        "Ui(s) = ∑s′P(s′|s, πi(s))[R(s, πi(s), s′) + γ Ui(s′)].\n",
        "\n",
        "modified bellman update for modified policy iteration\n",
        "\n",
        "Ui+1(s) ← ∑s′P(s′|s, πi(s))[R(s, πi(s), s′) + γ Ui(s′)]\n",
        "\n",
        "can apply updating utility / states to subsets of states (asynchronous policy iteration)\n",
        "\n",
        "LP solution to a bellman\n",
        "\n",
        "minimize U(s) for all s constrained by \n",
        "U(s) ≥ ∑\n",
        "s\n",
        "′\n",
        "P(s\n",
        "′\n",
        "|s, a)[R(s, a, s\n",
        "′) + γ U(s\n",
        "′)]\n",
        "\n",
        "online algorithms for mdps: expectimax\n",
        "\n",
        "real time dynamic programming\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" not different from above \"\"\"\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": 33,
      "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": "727268f9-827e-4808-cabe-4b4a6150d720"
      },
      "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": 34,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n$P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\nutility function assigns number to desirability of state \n\nexpected utility of an action is sum of probability of states times utility of state \n\nprinciple of maximum expected utility (MEU) says that a rational agent should choose\nthe action that maximizes the agent’s expected utility \n\nmeu formalizes notion of \"doing the right thing\" but does not operationalize\n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible\nenvironments)\n\nThe utility function applies to the very next state, so it can\nbe used to guide actions step by step.\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\norderability - must make a decision- one better, or equal\n\ntransitivity a > b, b > c means a > c\n\ncontinuity if b is between a and c, then there is some probability for a and c where surefire b is equivalent\n\nSUBSTITUTABILITY - if indifferent between a and b, then comparisons for more complex lotteries should be the same if a is switched for b\nmonotonicity - if a is better than b, then the agent prefers the lottery that has a higher probability for a and vice versa\n\nDECOMPOSABILITY - can be reduced to simpler ones with probability\nif preferences obery above, there is a utility function\n\nexpected utility is sum of probability times utility\n\nonly needs preference ranking, don't specifically need numbers - value function, ordinal utility function\n\n\n## AIMA Chapter 16.3 Utility Functions\n\npreference elicitation - present choices and use observed preferences to pin down underlying utility function\nchoose between s and standard lottery\n\nvalue of statistical life, ~$10 mil\n\nmicromort, one in a million chance of death, actual behavior reflex lower monetary value for micromort\n\nqaly, quality adjusted life year, shorter life expectancy better than disability\n\nrisk averse in gains, risk seeking in losses\n\ndifference between emv of loterry and certainty equivalent is insurance premium\n\nsmall changes will be approx linear, linear curves are risk neutral\n\noptimizer's curse - estimated EU of best choice is too high\n\ndecision theory is normative, describes should\ndescriptive theory describes how it actually is\n\nframing effect\nanchoring effect\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nthe transition model (or just “model,” when the meaning is clear)\ndescribes the outcome of each action in each state.\n\nWe will assume that transitions are\nMarkovian: the probability of reaching from depends only on and not on the history of\nearlier states. \n\nthe utility function will depend on a\nsequence of states and actions—an environment history—rather than on a single state. \n\nagents will receive a reward from state s to s' on action a, bounded by +- r max\n\na sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a Markov decision\nprocess, or MDP, and consists of a set of states (with an initial state s0); a set ACTIONS(s) of\nactions in each state; a transition model P(s' | s, a); and a reward function R(s,a,s').\n\nusually solving mdps involve dp\n\na policy specifies what an agent should do at any state (a solution to an mdp).\noptimal policy yields highest EU. pi* denotes optimal policy.\n\n A finite horizon means that there is a fixed time after which nothing\nmatters\n\nA policy that\ndepends on the time is called nonstationary, depends only on current state = stationary\n\n“infinite horizon” does not necessarily\nmean that all state sequences are infinite; it just means that there is no fixed deadline\n\nadditive discounted rewards: the utility of a history is sum of rewards multiplied by a discount factor gamma between 0 and 1 at each step.\ngamma represents preference of agent for current over future rewards\n\ngamma = 1 = additive rewards, used implicitly in use of path cost functions in heuristic search\n\nreasons for discounted rewards\n(1) animals value near term\n(2) getting money now and investing is good\n(3) uncertainty of true rewards (may never arrive)\n(4) preferences over histories, preferences between state sequences are stationary\n\nexpected utility of a policy is just expected value of executing it down with discount factor\n\nwith infinite horizon, optimal strategy independent of starting state\n\nbellman equation: U(s) = max sum{ p(s'|s,a) * (R(s,a,s' + gamma * U(s')) } over actions a\n\naction utility function (q function) is expected utility of action + state instead  of just state, U = max action (q(s,a))\n\npi * = argmax q\n\nshaping theorem:\nr(s,a,s' = r(s,a,s') + gamma f(s) - f(s)\n\nfunction phi (s) often called a :potential\", if higher in states with higher utility, you can lead the agent \"uphill\" in utility.\nphi acts as gradient\n\nsimplest way to represent mdps is through 3d tables s^2a, or can be sparse so sa\n\ndynamic decision networks - decision, reward, utility nodes feed forward to utility function\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n\nvalue iteration \"bellman step\"\n\nset u_i+1(s) to max a of sum of p(s'|s,a) * r(s,a,s') + gamma u_i(s')\n\napplied simultaneously to all states at each iteration, eventually reach equilibrium, final must be solutions to bellman eq\n\na contraction is a function of one argument that, when\napplied to two different inputs in turn, produces two output values that are “closer\ntogether,” by at least some constant factor, than the original inputs. For example, the\nfunction “divide by two” is a contraction, because, after we divide any two numbers by two,\ntheir difference is halved, eventually reaches \"fixed point\" where function doesn't change (0)\n\ncontraction only has one fixed point\n\nvalue must get closer to fixed point with repeated application of contraction\n\nbellman update is a contraction by a factor of gamma on the space of utility vectors\n\nterminates after under certain error (can bound error in utility estimates if we stop after a finite nubmer of iterations)\n\nif ∥Ui − U ∥< ϵ then ∥ U πi − U ∥< 2ϵ.\n\npolicy iteration alternates between policy evaluation and improvement, terminates when no change in utilities after improvement\nUi(s) = ∑s′P(s′|s, πi(s))[R(s, πi(s), s′) + γ Ui(s′)].\n\nmodified bellman update for modified policy iteration\n\nUi+1(s) ← ∑s′P(s′|s, πi(s))[R(s, πi(s), s′) + γ Ui(s′)]\n\ncan apply updating utility / states to subsets of states (asynchronous policy iteration)\n\nLP solution to a bellman\n\nminimize U(s) for all s constrained by \nU(s) ≥ ∑\ns\n′\nP(s\n′\n|s, a)[R(s, a, s\n′) + γ U(s\n′)]\n\nonline algorithms for mdps: expectimax\n\nreal time dynamic programming\n\n\n\n\n\n## Module 8 Lecture Notes\n not different from above \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "In Las Vegas, a one-armed bandit is a slot machine. A gambler can insert a coin, pull the\n",
        "lever, and collect the winnings (if any). An n-armed bandit has levers. \n",
        "\n",
        "tradeoff between exploitation of the current best action to obtain rewards and exploration\n",
        "of previously unknown states and actions to gain information\n",
        "\n",
        "one definition of bandit problem:\n",
        "Each arm is a Markov reward process or MRP, that is, an MDP with only one\n",
        "possible action . It has states , transition model , and reward .\n",
        "The arm defines a distribution over sequences of rewards , where each \n",
        " is a random variable.\n",
        "The overall bandit problem is an MDP: the state space is given by the Cartesian product \n",
        "; the actions are ; the transition model updates the state of\n",
        "whichever arm is selected, according to its specific transition model, leaving the\n",
        "other arms unchanged; and the discount factor is gamma.\n",
        "\n",
        "If you pull the first T arm times we say that the stopping time is T.\n",
        "\n",
        "gittins index : sum of discounted rewards up to stopping time over just discount factor sum up to t\n",
        "\n",
        "\n",
        "pull the arm that has the highest gittins index, update the gittins indices\n",
        "the Bernoulli bandit,\n",
        "where each arm produces a reward of 0 or 1 with a fixed but unknown probability .\n",
        "The state of arm is defined by and , the counts of successes (1s) and failures (0s) so\n",
        "far for that arm; the transition probability predicts the next outcome to be 1 with probability\n",
        " and 0 with probability . The counts are initialized to 1 so that the initial probabilities are 1/2\n",
        "\n",
        "there is also an exploration bonus associated with arms that have only been\n",
        "tried a few times.\n",
        "\n",
        "Approximately optimal bandit policies (calculating gittins indices is hard)\n",
        "\n",
        "The first class of methods uses the upper confidence bound or UCB heuristic, previously\n",
        "introduced for Monte Carlo tree search\n",
        "\n",
        "Ni = number of times arm has been sampled\n",
        "\n",
        "UCB(Mi) = μˆi + g(N)/√Ni \n",
        "\n",
        "UCB policy picks arm with highest ucb\n",
        "\n",
        "The precise definition of g determines the regret relative to the clairvoyant policy, which\n",
        "simply picks the best arm and yields average reward .\n",
        "\n",
        "Regret lower bounded by log n\n",
        "\n",
        "Thompson sampling chooses chooses an arm\n",
        "randomly according to the probability that the arm is in fact optimal, given the samples so\n",
        "far\n",
        "\n",
        "bandit superprocess each arm is a full Markov decision process (multitasking\n",
        "\n",
        "opportunity cost: how\n",
        "much utility is given up per time step by not devoting that time step to another arm.\n",
        "\n",
        "when an optimal policy in a given arm is unaffected by the opportunity cost it's called a dominating policy. It turns out that by adding\n",
        "\n",
        "by adding actions to states, it is always possible to create a relaxed version of an MDP so it has a dominating policy, giving upper bound for value of acting on the arm, lower bound can be computed by solving each arm separately and computing gittins indices\n",
        "\n",
        "large bsps can be solved\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "An alternative is reinforcement learning (RL), in which an agent interacts with the world\n",
        "and periodically receives rewards (or, in the terminology of psychology, reinforcements)\n",
        "that reflect how well it is doing.\n",
        "\n",
        "sparse rewards, in the vast majority of states the agent is\n",
        "given no informative reward signal at all\n",
        "\n",
        "intermediate rewards are better\n",
        "\n",
        "MODEL-BASED REINFORCEMENT LEARNING: In these approaches the agent uses a\n",
        "transition model of the environment to help interpret the reward signals and to make\n",
        "decisions about how to act\n",
        "\n",
        "MODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither\n",
        "knows nor learns a transition model for the environment.\n",
        "ACTION-UTILITY LEARNING: The most common form of action-utility learning is Q-learning, where the\n",
        "agent learns a Q-function.\n",
        "POLICY SEARCH: The agent learns a policy that maps directly from states to\n",
        "actions.\n",
        "\n",
        "primary problem is exploration\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "passive learning agent: The agent is trying to learn the utility function —the expected total discounted\n",
        "reward if policy is executed beginning in state, similar to policy evaluation\n",
        "\n",
        "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\n",
        "provides a sample of this quantity for each state visited.\n",
        "\n",
        "The utility of a state is determined by the reward and the expected utility of\n",
        "the successor states. More specifically, the utility values obey the Bellman equations for a\n",
        "fixed policy\n",
        "\n",
        "(direct utility estimation is super slow)\n",
        "\n",
        "An adaptive dynamic programming (or ADP) agent takes advantage of the constraints\n",
        "among the utilities of states by learning the transition model that connects them and solving\n",
        "the corresponding Markov decision process using dynamic programming.\n",
        "\n",
        "modified policy iteration, using\n",
        "a simplified value iteration process to update the utility estimates after each change to the\n",
        "learned model. Because the model usually changes only slightly with each observation, the\n",
        "value iteration process can use the previous utility estimates as initial values and typically\n",
        "converge very quickly.\n",
        "\n",
        "For a passive\n",
        "learning agent, this means plugging in the learned transition model and the observed rewards\n",
        "\n",
        "Uπ(s) ← Uπ(s) + α[R(s,π(s),s′) + γUπ(s′) − Uπ(s)].\n",
        "\n",
        "a is the learning rate\n",
        "\n",
        "called temporal difference equation (temporal difference learning)\n",
        "\n",
        "All temporal-difference methods work by adjusting the utility estimates toward the ideal\n",
        "equilibrium that holds locally when the utility estimates are correct. I\n",
        "\n",
        "Each adjustment made by ADP could be seen, from the TD point of view, as a result of a\n",
        "pseudoexperience generated by simulating the current transition model.\n",
        "\n",
        "Bound the number of adjustmens made after each transition: The prioritized\n",
        "sweeping heuristic prefers to make adjustments to states whose likely successors have just\n",
        "undergone a large adjustment in their own utility estimates.\n",
        "\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "\n",
        "An active learning\n",
        "agent gets to decide what actions to take rather than fixed policy.\n",
        "\n",
        "should be “greedy in the limit of infinite exploration,” or GLIE\n",
        "\n",
        "one of simplest is to have the agent choose a random\n",
        "action at time step with probability and to follow the greedy policy otherwise. \n",
        "\n",
        "(better is give some weight to actions that the agent has not tried very often, while tending to avoid\n",
        "actions that are believed to be of low utility )\n",
        "\n",
        "let N(s,a) be the number of times action has been tried in state .\n",
        "\n",
        "U+(s) <- max action f(bellman, n)\n",
        "\n",
        "Here, f is the exploration function. The function determines how greed (preference\n",
        "for high values of the utility ) is traded off against curiosity (preference for actions that\n",
        "have not been tried often and have a low count ). \n",
        "\n",
        "Many actions are irreversible, may enter absorbing state where no actions have any effect and no rewards are received\n",
        "\n",
        "The second approach, derived from robust control theory, allows for a set of possible\n",
        "models without assigning probabilities to them, and defines an optimal robust policy as\n",
        "one that gives the best outcome in the worst case over :\n",
        "\n",
        "The robust control approach can be considered as a game between the agent and an\n",
        "adversary, where the adversary gets to pick the worst possible result for any action, and the\n",
        "policy we get is the minimax solution for the game. \n",
        "\n",
        "The Q-learning method avoids the need for a model by learning an action-utility function \n",
        " instead of a utility function. Enables the agent to act optimally simply by choosing , with no need for\n",
        "look-ahead based on a transition model.\n",
        "\n",
        "SARSA (for state, action, reward, state, action). The\n",
        "update rule for SARSA is very similar to the Q-learning update rule (Equation (22.7) ),\n",
        "except that SARSA updates with the Q-value of the action that is actually taken:\n",
        "\n",
        "Q(s,a) ← Q(s,a) + α[R(s,a,s\n",
        "′) + γ Q(s\n",
        "′\n",
        ",a\n",
        "′) − Q(s,a)],\n",
        "\n",
        "The rule is applied at the end of each quintuplet s, a, r, s', a\n",
        "\n",
        "q learning is off policy because because it assumes it switches policy\n",
        "\n",
        "sarsa is on policy it assumes you stick with current policy\n",
        "\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\n",
        "n evaluation function as a compact measure of\n",
        "desirability for potentially vast state spaces\n",
        "\n",
        "function\n",
        "approximation for the process of constructing a compact approximation of the true utility\n",
        "function or Q-function\n",
        "\n",
        "weighted linear combination of features instead of learning states\n",
        "\n",
        "supervised learning algorithm\n",
        "θi ← θi − α(derivative of half squared difference of predicted total and actual total)\n",
        "\n",
        "= θi + α[uj(s) − Uˆθ(s)] * derivative of half squared difference of predicted total and actual total .\n",
        "\n",
        "widrow-hoff rule / delta rule for online least squares\n",
        "\n",
        "features can be arbitrary nonlinear functions of state variables\n",
        "\n",
        "parameters can diverge to infinity\n",
        "\n",
        "catastrophic forgetting, learns something too well and forgets something very important\n",
        "\n",
        "expierence replay (ensures that car relives youthful crashing behavior at regular intervals)\n",
        "\n",
        "credit assignment - what among the many controls went wrong\n",
        "\n",
        "reward shaping: This\n",
        "involves supplying the agent with additional rewards, called pseudorewards, for “making\n",
        "progress.” For example, we might give pseudorewards to the robot for making contact with\n",
        "the ball or for advancing it toward the goal.\n",
        "\n",
        "Another way to cope with very long action sequences is to break them up into a few smaller\n",
        "pieces, and then break those into smaller pieces still, and so on until the action sequences\n",
        "are short enough to make learning easy. This approach is called hierarchical reinforcement\n",
        "learning (HRL),\n",
        "\n",
        "The hierarchical structure of behavior also provides a natural additive decomposition of the\n",
        "overall utility function.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" \n",
        "policy search - keep twiddling the policy as long as its performance improves, then stop.\n",
        "\n",
        "policy search\n",
        "methods often use a stochastic policy representation , which specifies the probability\n",
        "of selecting action in state . One popular representation is the softmax function:\n",
        "\n",
        "\n",
        "We can follow the policy gradient vector , provided is differentiable.\n",
        "\n",
        "Let be the policy value, that is,\n",
        "the expected reward-to-go when is executed.\n",
        "\n",
        "We can follow the empirical gradient by hill\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" not different from above \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 35,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "45828c61-bc5e-4b06-b664-7c32d431d762"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nIn Las Vegas, a one-armed bandit is a slot machine. A gambler can insert a coin, pull the\nlever, and collect the winnings (if any). An n-armed bandit has levers. \n\ntradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information\n\none definition of bandit problem:\nEach arm is a Markov reward process or MRP, that is, an MDP with only one\npossible action . It has states , transition model , and reward .\nThe arm defines a distribution over sequences of rewards , where each \n is a random variable.\nThe overall bandit problem is an MDP: the state space is given by the Cartesian product \n; the actions are ; the transition model updates the state of\nwhichever arm is selected, according to its specific transition model, leaving the\nother arms unchanged; and the discount factor is gamma.\n\nIf you pull the first T arm times we say that the stopping time is T.\n\ngittins index : sum of discounted rewards up to stopping time over just discount factor sum up to t\n\n\npull the arm that has the highest gittins index, update the gittins indices\nthe Bernoulli bandit,\nwhere each arm produces a reward of 0 or 1 with a fixed but unknown probability .\nThe state of arm is defined by and , the counts of successes (1s) and failures (0s) so\nfar for that arm; the transition probability predicts the next outcome to be 1 with probability\n and 0 with probability . The counts are initialized to 1 so that the initial probabilities are 1/2\n\nthere is also an exploration bonus associated with arms that have only been\ntried a few times.\n\nApproximately optimal bandit policies (calculating gittins indices is hard)\n\nThe first class of methods uses the upper confidence bound or UCB heuristic, previously\nintroduced for Monte Carlo tree search\n\nNi = number of times arm has been sampled\n\nUCB(Mi) = μˆi + g(N)/√Ni \n\nUCB policy picks arm with highest ucb\n\nThe precise definition of g determines the regret relative to the clairvoyant policy, which\nsimply picks the best arm and yields average reward .\n\nRegret lower bounded by log n\n\nThompson sampling chooses chooses an arm\nrandomly according to the probability that the arm is in fact optimal, given the samples so\nfar\n\nbandit superprocess each arm is a full Markov decision process (multitasking\n\nopportunity cost: how\nmuch utility is given up per time step by not devoting that time step to another arm.\n\nwhen an optimal policy in a given arm is unaffected by the opportunity cost it's called a dominating policy. It turns out that by adding\n\nby adding actions to states, it is always possible to create a relaxed version of an MDP so it has a dominating policy, giving upper bound for value of acting on the arm, lower bound can be computed by solving each arm separately and computing gittins indices\n\nlarge bsps can be solved\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nAn alternative is reinforcement learning (RL), in which an agent interacts with the world\nand periodically receives rewards (or, in the terminology of psychology, reinforcements)\nthat reflect how well it is doing.\n\nsparse rewards, in the vast majority of states the agent is\ngiven no informative reward signal at all\n\nintermediate rewards are better\n\nMODEL-BASED REINFORCEMENT LEARNING: In these approaches the agent uses a\ntransition model of the environment to help interpret the reward signals and to make\ndecisions about how to act\n\nMODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither\nknows nor learns a transition model for the environment.\nACTION-UTILITY LEARNING: The most common form of action-utility learning is Q-learning, where the\nagent learns a Q-function.\nPOLICY SEARCH: The agent learns a policy that maps directly from states to\nactions.\n\nprimary problem is exploration\n\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \npassive learning agent: The agent is trying to learn the utility function —the expected total discounted\nreward if policy is executed beginning in state, similar to policy evaluation\n\ndirect 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\nprovides a sample of this quantity for each state visited.\n\nThe utility of a state is determined by the reward and the expected utility of\nthe successor states. More specifically, the utility values obey the Bellman equations for a\nfixed policy\n\n(direct utility estimation is super slow)\n\nAn adaptive dynamic programming (or ADP) agent takes advantage of the constraints\namong the utilities of states by learning the transition model that connects them and solving\nthe corresponding Markov decision process using dynamic programming.\n\nmodified policy iteration, using\na simplified value iteration process to update the utility estimates after each change to the\nlearned model. Because the model usually changes only slightly with each observation, the\nvalue iteration process can use the previous utility estimates as initial values and typically\nconverge very quickly.\n\nFor a passive\nlearning agent, this means plugging in the learned transition model and the observed rewards\n\nUπ(s) ← Uπ(s) + α[R(s,π(s),s′) + γUπ(s′) − Uπ(s)].\n\na is the learning rate\n\ncalled temporal difference equation (temporal difference learning)\n\nAll temporal-difference methods work by adjusting the utility estimates toward the ideal\nequilibrium that holds locally when the utility estimates are correct. I\n\nEach adjustment made by ADP could be seen, from the TD point of view, as a result of a\npseudoexperience generated by simulating the current transition model.\n\nBound the number of adjustmens made after each transition: The prioritized\nsweeping heuristic prefers to make adjustments to states whose likely successors have just\nundergone a large adjustment in their own utility estimates.\n\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \n\nAn active learning\nagent gets to decide what actions to take rather than fixed policy.\n\nshould be “greedy in the limit of infinite exploration,” or GLIE\n\none of simplest is to have the agent choose a random\naction at time step with probability and to follow the greedy policy otherwise. \n\n(better is give some weight to actions that the agent has not tried very often, while tending to avoid\nactions that are believed to be of low utility )\n\nlet N(s,a) be the number of times action has been tried in state .\n\nU+(s) <- max action f(bellman, n)\n\nHere, f is the exploration function. The function determines how greed (preference\nfor high values of the utility ) is traded off against curiosity (preference for actions that\nhave not been tried often and have a low count ). \n\nMany actions are irreversible, may enter absorbing state where no actions have any effect and no rewards are received\n\nThe second approach, derived from robust control theory, allows for a set of possible\nmodels without assigning probabilities to them, and defines an optimal robust policy as\none that gives the best outcome in the worst case over :\n\nThe robust control approach can be considered as a game between the agent and an\nadversary, where the adversary gets to pick the worst possible result for any action, and the\npolicy we get is the minimax solution for the game. \n\nThe Q-learning method avoids the need for a model by learning an action-utility function \n instead of a utility function. Enables the agent to act optimally simply by choosing , with no need for\nlook-ahead based on a transition model.\n\nSARSA (for state, action, reward, state, action). The\nupdate rule for SARSA is very similar to the Q-learning update rule (Equation (22.7) ),\nexcept that SARSA updates with the Q-value of the action that is actually taken:\n\nQ(s,a) ← Q(s,a) + α[R(s,a,s\n′) + γ Q(s\n′\n,a\n′) − Q(s,a)],\n\nThe rule is applied at the end of each quintuplet s, a, r, s', a\n\nq learning is off policy because because it assumes it switches policy\n\nsarsa is on policy it assumes you stick with current policy\n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\nn evaluation function as a compact measure of\ndesirability for potentially vast state spaces\n\nfunction\napproximation for the process of constructing a compact approximation of the true utility\nfunction or Q-function\n\nweighted linear combination of features instead of learning states\n\nsupervised learning algorithm\nθi ← θi − α(derivative of half squared difference of predicted total and actual total)\n\n= θi + α[uj(s) − Uˆθ(s)] * derivative of half squared difference of predicted total and actual total .\n\nwidrow-hoff rule / delta rule for online least squares\n\nfeatures can be arbitrary nonlinear functions of state variables\n\nparameters can diverge to infinity\n\ncatastrophic forgetting, learns something too well and forgets something very important\n\nexpierence replay (ensures that car relives youthful crashing behavior at regular intervals)\n\ncredit assignment - what among the many controls went wrong\n\nreward shaping: This\ninvolves supplying the agent with additional rewards, called pseudorewards, for “making\nprogress.” For example, we might give pseudorewards to the robot for making contact with\nthe ball or for advancing it toward the goal.\n\nAnother way to cope with very long action sequences is to break them up into a few smaller\npieces, and then break those into smaller pieces still, and so on until the action sequences\nare short enough to make learning easy. This approach is called hierarchical reinforcement\nlearning (HRL),\n\nThe hierarchical structure of behavior also provides a natural additive decomposition of the\noverall utility function.\n\n\n\n\n\n## Module 9 Lecture Notes\n not different from above \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 = \"\"\"\n",
        "belief state —a representation of the set of all possible world states that it might be in\n",
        "\n",
        "None of these conditions\n",
        "can be deduced for sure, so we can’t infer that the plan succeeds. This is the logical\n",
        "qualification problem\n",
        "\n",
        "Trying to use logic to cope with a domain like\n",
        "medical diagnosis thus fails for three main reasons:\n",
        "\n",
        "LAZINESS: It is too much work to list the complete set of antecedents or consequents\n",
        "needed to ensure an exceptionless rule and too hard to use such rules.\n",
        "\n",
        "THEORETICAL IGNORANCE: Medical science has no complete theory for the domain.\n",
        "\n",
        "PRACTICAL IGNORANCE: Even if we know all the rules, we might be uncertain about\n",
        "a particular patient because not all the necessary tests have been or can be run.\n",
        "\n",
        "The agent’s\n",
        "knowledge can at best provide only a degree of belief in the relevant sentences. Our main\n",
        "tool for dealing with degrees of belief is probability theory\n",
        "\n",
        "To make such choices, an agent must first have preferences among the different possible\n",
        "outcomes of the various plans. An outcome is a completely specified state, including such\n",
        "factors as whether the agent arrives on time and the length of the wait at the airport. We use\n",
        "utility theory to represent preferences and reason quantitatively with them\n",
        "\n",
        "decision theory = probability theoyr + utility theory\n",
        "\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\" \n",
        "\n",
        "unconditional or prior\n",
        "probabilities\n",
        "\n",
        "evidence\n",
        "\n",
        "condition / posteireor probability\n",
        "\n",
        "update prior\n",
        "\n",
        "\n",
        "product rule\n",
        "\n",
        "P(a /\\ b) = P (a | b) P (b)\n",
        "\n",
        "if range between 0 and 1, variable has bernoulli distribution\n",
        "\n",
        "P(Weather) = ⟨0.6, 0.1, 0.29, 0.01⟩,\n",
        "\n",
        "We say that the \n",
        "statement defines a probability distribution for the random variable —that is, an\n",
        "assignment of a probability for each possible value of the random variable. (In this case,\n",
        "with a finite, discrete range, the distribution is called a categorical distribution.)\n",
        "\n",
        "probability density function describes continuous variable\n",
        "\n",
        "joint probability distribution\n",
        "\n",
        "P(a ∨ b) = P(a) + P(b) − P(a ∧ b).\n",
        " inclusion–exclusion principle:\n",
        "\n",
        "  Kolmogorov’s axioms\n",
        "\n",
        "P(A) >= 0\n",
        "P(Omega) = 1\n",
        "disjouint sets sum\n",
        "\n",
        " \"\"\"\n",
        "chapter12_3 = \"\"\" \n",
        "\n",
        "query propositions given observed evidence. We\n",
        "use the full joint distribution as the “knowledge base” from which answers to all questions\n",
        "may be derived\n",
        "\n",
        "For example, adding the entries in the first row gives the unconditional or\n",
        "marginal probability of :\n",
        "\n",
        "This process is called marginalization, or summing out\n",
        "\n",
        " conditioning\n",
        "\n",
        " \"\"\"\n",
        "chapter12_4 = \"\"\" independence good \"\"\"\n",
        "chapter12_5 = \"\"\" baye's rule\n",
        "p(b|a) = p (a|b) P(b) / p(a)\n",
        "\n",
        "effect give n cause is causal direction\n",
        "\n",
        "cause given effect is diagnostic direction\n",
        "\n",
        "conditional independence\n",
        "P(a /\\ b|c) = P(a|c) P(a|b)\n",
        "\n",
        "c separates a and b\n",
        "\n",
        " \"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "\n",
        "naive bayes model\n",
        "P(cause, e, e2, e3) = p(cause) * P (e | c ) * P (e2 | c )...\n",
        "\n",
        "(The naive Bayes model is sometimes called a\n",
        "Bayesian classifier, a somewhat careless usage that has prompted true Bayesians to call it\n",
        "the idiot Bayes model.)\n",
        "\n",
        "often works well, even when conditional indpenednece assumption not true\n",
        " \"\"\"\n",
        "chapter12_7 = \"\"\" wumpus \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "\n",
        "Out of vocabulary items (OOV)\n",
        "<unk> to deal with OOVs\n",
        "Fixed lexicon L of size V\n",
        "Normalize training data by replacing any word not in L with <unk>\n",
        "Avoid zeros with smoothin\n",
        "\n",
        "We do everything in log space\n",
        "• Avoid underflow\n",
        "• (also adding is faster than multiplying)\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a569f1b7-cfc7-4e1e-cc80-bd36c7093642"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\nbelief state —a representation of the set of all possible world states that it might be in\n\nNone of these conditions\ncan be deduced for sure, so we can’t infer that the plan succeeds. This is the logical\nqualification problem\n\nTrying to use logic to cope with a domain like\nmedical diagnosis thus fails for three main reasons:\n\nLAZINESS: It is too much work to list the complete set of antecedents or consequents\nneeded to ensure an exceptionless rule and too hard to use such rules.\n\nTHEORETICAL IGNORANCE: Medical science has no complete theory for the domain.\n\nPRACTICAL IGNORANCE: Even if we know all the rules, we might be uncertain about\na particular patient because not all the necessary tests have been or can be run.\n\nThe agent’s\nknowledge can at best provide only a degree of belief in the relevant sentences. Our main\ntool for dealing with degrees of belief is probability theory\n\nTo make such choices, an agent must first have preferences among the different possible\noutcomes of the various plans. An outcome is a completely specified state, including such\nfactors as whether the agent arrives on time and the length of the wait at the airport. We use\nutility theory to represent preferences and reason quantitatively with them\n\ndecision theory = probability theoyr + utility theory\n\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n\nunconditional or prior\nprobabilities\n\nevidence\n\ncondition / posteireor probability\n\nupdate prior\n\n\nproduct rule\n\nP(a /\\ b) = P (a | b) P (b)\n\nif range between 0 and 1, variable has bernoulli distribution\n\nP(Weather) = ⟨0.6, 0.1, 0.29, 0.01⟩,\n\nWe say that the \nstatement defines a probability distribution for the random variable —that is, an\nassignment of a probability for each possible value of the random variable. (In this case,\nwith a finite, discrete range, the distribution is called a categorical distribution.)\n\nprobability density function describes continuous variable\n\njoint probability distribution\n\nP(a ∨ b) = P(a) + P(b) − P(a ∧ b).\n inclusion–exclusion principle:\n\n  Kolmogorov’s axioms\n\nP(A) >= 0\nP(Omega) = 1\ndisjouint sets sum\n\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n\nquery propositions given observed evidence. We\nuse the full joint distribution as the “knowledge base” from which answers to all questions\nmay be derived\n\nFor example, adding the entries in the first row gives the unconditional or\nmarginal probability of :\n\nThis process is called marginalization, or summing out\n\n conditioning\n\n \n\n## AIMA Chapter 12.4 Independence\n independence good \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n baye's rule\np(b|a) = p (a|b) P(b) / p(a)\n\neffect give n cause is causal direction\n\ncause given effect is diagnostic direction\n\nconditional independence\nP(a /\\ b|c) = P(a|c) P(a|b)\n\nc separates a and b\n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n\nnaive bayes model\nP(cause, e, e2, e3) = p(cause) * P (e | c ) * P (e2 | c )...\n\n(The naive Bayes model is sometimes called a\nBayesian classifier, a somewhat careless usage that has prompted true Bayesians to call it\nthe idiot Bayes model.)\n\noften works well, even when conditional indpenednece assumption not true\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n wumpus \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \n\nOut of vocabulary items (OOV)\n<unk> to deal with OOVs\nFixed lexicon L of size V\nNormalize training data by replacing any word not in L with <unk>\nAvoid zeros with smoothin\n\nWe do everything in log space\n• Avoid underflow\n• (also adding is faster than multiplying)\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" \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 to\n",
        "node is said to be a parent of . The graph has no directed cycles and hence is\n",
        "a directed acyclic graph, or DAG.\n",
        "\n",
        "3. Each node has associated probability information that\n",
        "quantifies the effect of the parents on the node using a finite number of parameters.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Variable elimination works by evaluating expressions such as \n",
        "P(j|a)P(m|a) P(j|¬a)P(m|¬a)\n",
        "\n",
        "in right-to-left order (that is, bottom up in Figure 13.10 ). Intermediate results are stored,\n",
        "and summations over each variable are done only for those portions of the expression that\n",
        "depend on the variable.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "The conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of the parents\n",
        "\n",
        "x _||_ y \n",
        "indepdence\n",
        "\n",
        "Empirical joint distributions: at best “close” to independent\n",
        "\n",
        "Bayes’ nets: a technique for describing complex joint\n",
        "distributions (models) using simple, local\n",
        "distributions (conditional probabilities)\n",
        "\n",
        "More properly called graphical models\n",
        "§ We describe how variables locally interact\n",
        "§ Local interactions chain together to give global, indirect\n",
        "interactions\n",
        "\n",
        "A set of nodes, one per variable X\n",
        "\n",
        "A directed, acyclic graph\n",
        "\n",
        "A conditional distribution for each node\n",
        "\n",
        "Bayes’ nets implicitly encode joint distributions\n",
        "\n",
        "Why are we guarenteed in setting chaining parents results in a proper joint distribution\n",
        "\n",
        "Chain rule (valid for all distributions): \n",
        "\n",
        "Assume conditional independences:\n",
        "\n",
        "Not every BN can represent every joint distribution, topology enforces certain conditional independenceise\n",
        "\n",
        "joint distribution over n booleans is 2^n\n",
        "\n",
        "n-node net with k parents is O(N * 2^k+1)\n",
        "\n",
        "Both give power to calculate P(x1, x2, x)...\n",
        "\n",
        "BNs have huge space savings\n",
        "\n",
        "This configuration is a “causal chain”\n",
        "\n",
        "x - y - z\n",
        "\n",
        "common cause\n",
        "\n",
        "x - y\n",
        "\n",
        "|\n",
        "\n",
        "z\n",
        "\n",
        "guarenteed x independent of z\n",
        "\n",
        "\n",
        "two causes, one effect\n",
        "\n",
        "v-structures\n",
        "\n",
        "observing an effect activates influence between possible causes\n",
        "\n",
        "reachability\n",
        "\n",
        ": if two nodes are connected\n",
        "by an undirected path not blocked by\n",
        "a shaded node, they are conditionally\n",
        "independent, but : the v-structure at T doesn’t count\n",
        "as a link in a path unless “active”\n",
        "\n",
        "d-paration\n",
        "\n",
        "check all undirected paths between two variables\n",
        "\n",
        "if one or more active, independence not guarenteed\n",
        "\n",
        "otherwise, guarenteed\n",
        "\n",
        "inference, calculating some useful quantity from joint probability distribution\n",
        "\n",
        "inference by enumeration - slow\n",
        "\n",
        "variable elimination, usually much faster\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "65134896-327d-4d43-9fd9-ab1e75b850aa"
      },
      "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": 40,
      "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 \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 to\nnode is said to be a parent of . The graph has no directed cycles and hence is\na directed acyclic graph, or DAG.\n\n3. Each node has associated probability information that\nquantifies the effect of the parents on the node using a finite number of parameters.\n\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Variable elimination works by evaluating expressions such as \nP(j|a)P(m|a) P(j|¬a)P(m|¬a)\n\nin right-to-left order (that is, bottom up in Figure 13.10 ). Intermediate results are stored,\nand summations over each variable are done only for those portions of the expression that\ndepend on the variable.\n \n\n## Module 11 Lecture Notes\n \nThe conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of the parents\n\nx _||_ y \nindepdence\n\nEmpirical joint distributions: at best “close” to independent\n\nBayes’ nets: a technique for describing complex joint\ndistributions (models) using simple, local\ndistributions (conditional probabilities)\n\nMore properly called graphical models\n§ We describe how variables locally interact\n§ Local interactions chain together to give global, indirect\ninteractions\n\nA set of nodes, one per variable X\n\nA directed, acyclic graph\n\nA conditional distribution for each node\n\nBayes’ nets implicitly encode joint distributions\n\nWhy are we guarenteed in setting chaining parents results in a proper joint distribution\n\nChain rule (valid for all distributions): \n\nAssume conditional independences:\n\nNot every BN can represent every joint distribution, topology enforces certain conditional independenceise\n\njoint distribution over n booleans is 2^n\n\nn-node net with k parents is O(N * 2^k+1)\n\nBoth give power to calculate P(x1, x2, x)...\n\nBNs have huge space savings\n\nThis configuration is a “causal chain”\n\nx - y - z\n\ncommon cause\n\nx - y\n\n|\n\nz\n\nguarenteed x independent of z\n\n\ntwo causes, one effect\n\nv-structures\n\nobserving an effect activates influence between possible causes\n\nreachability\n\n: if two nodes are connected\nby an undirected path not blocked by\na shaded node, they are conditionally\nindependent, but : the v-structure at T doesn’t count\nas a link in a path unless “active”\n\nd-paration\n\ncheck all undirected paths between two variables\n\nif one or more active, independence not guarenteed\n\notherwise, guarenteed\n\ninference, calculating some useful quantity from joint probability distribution\n\ninference by enumeration - slow\n\nvariable elimination, usually much faster\n\n\n\n\n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "\n",
        "Laplace smoothing\n",
        "\n",
        "Pretend you saw every outcome k extra times\n",
        "\n",
        "k is the strength of the prior\n",
        "\n",
        "linear interpolation (learning rate)\n",
        "a p(x|y) + (1 - a)p(x)\n",
        "\n",
        "Learn parameters from training data\n",
        "\n",
        "tune hyperparameters on different data\n",
        "\n",
        "need more features - words aren't enough\n",
        "\n",
        "can add information sources as new variables\n",
        "\n",
        "Binary case: compare features to a weight vector\n",
        "Learning: figure out the weight vector from examples\n",
        "\n",
        "In the space of feature vectors\n",
        "• Examples are points\n",
        "• Any weight vector is a hyperplane\n",
        "• One side corresponds to Y=+1\n",
        "• Other corresponds to Y=-1\n",
        "\n",
        "binary perceptrons only output 1 and 0\n",
        "\n",
        "multiclass outputs highest\n",
        "\n",
        "problems\n",
        "\n",
        "Noise: if the data isn’t separable,\n",
        "weights might thrash\n",
        "• Averaging weight vectors over\n",
        "time can help (averaged\n",
        "perceptron)\n",
        "Mediocre generalization: finds a\n",
        "“barely” separating solution\n",
        "Overtraining: test / held-out\n",
        "accuracy usually rises, then falls\n",
        "• Overtraining is a kind of\n",
        "overfitting\n",
        "\n",
        "\n",
        "MIRA*: choose an update size that fixes the current\n",
        "mistake…\n",
        "… but, minimizes the change to w\n",
        "\n",
        "\n",
        "Minimum Correcting Update\n",
        "\n",
        "t = difference in weights dot f + 1 / (2 f dot f)\n",
        "\n",
        "\n",
        "wy = wy - tf(x)\n",
        "wy* = wy* + tf(x)\n",
        "\n",
        "\n",
        "maximum step size, cap with seom constant c\n",
        "\n",
        "maximize margin\n",
        "\n",
        "only support vectors matter\n",
        "\n",
        "Naïve Bayes\n",
        "• Builds a model training data\n",
        "• Gives prediction probabilities\n",
        "• Strong assumptions about feature independence\n",
        "• One pass through data (counting)\n",
        "\n",
        "Perceptrons / MIRA:\n",
        "• Makes less assumptions about data\n",
        "• Mistake-driven learning\n",
        "• Multiple passes through data (prediction)\n",
        "• Often more accurate\n",
        "\n",
        "perceptrons start with weight 0\n",
        "• If correct (i.e., y=y*), no change!\n",
        "• If wrong: adjust the weight vector\n",
        "\n",
        "A single neural unit cannot be used to compute the XOR function\n",
        "\n",
        "activation function\n",
        "\n",
        "ReLU - rectified linear unit\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 41,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d1cffe02-c038-495b-c091-3cbf99d2efd4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 42,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n\nLaplace smoothing\n\nPretend you saw every outcome k extra times\n\nk is the strength of the prior\n\nlinear interpolation (learning rate)\na p(x|y) + (1 - a)p(x)\n\nLearn parameters from training data\n\ntune hyperparameters on different data\n\nneed more features - words aren't enough\n\ncan add information sources as new variables\n\nBinary case: compare features to a weight vector\nLearning: figure out the weight vector from examples\n\nIn the space of feature vectors\n• Examples are points\n• Any weight vector is a hyperplane\n• One side corresponds to Y=+1\n• Other corresponds to Y=-1\n\nbinary perceptrons only output 1 and 0\n\nmulticlass outputs highest\n\nproblems\n\nNoise: if the data isn’t separable,\nweights might thrash\n• Averaging weight vectors over\ntime can help (averaged\nperceptron)\nMediocre generalization: finds a\n“barely” separating solution\nOvertraining: test / held-out\naccuracy usually rises, then falls\n• Overtraining is a kind of\noverfitting\n\n\nMIRA*: choose an update size that fixes the current\nmistake…\n… but, minimizes the change to w\n\n\nMinimum Correcting Update\n\nt = difference in weights dot f + 1 / (2 f dot f)\n\n\nwy = wy - tf(x)\nwy* = wy* + tf(x)\n\n\nmaximum step size, cap with seom constant c\n\nmaximize margin\n\nonly support vectors matter\n\nNaïve Bayes\n• Builds a model training data\n• Gives prediction probabilities\n• Strong assumptions about feature independence\n• One pass through data (counting)\n\nPerceptrons / MIRA:\n• Makes less assumptions about data\n• Mistake-driven learning\n• Multiple passes through data (prediction)\n• Often more accurate\n\nperceptrons start with weight 0\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector\n\nA single neural unit cannot be used to compute the XOR function\n\nactivation function\n\nReLU - rectified linear unit\n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "Classifier components\n",
        "Machine learning classifiers require a training corpus of M observations\n",
        "input/output pairs (x(i)\n",
        ",y(i)\n",
        ").\n",
        "1. A feature representation of the input. For each input observation\n",
        "x(i)\n",
        ", this will be a vector of features [x1,x2,...,xn].\n",
        "2. A classification function that computes the estimated class �! via\n",
        "p(y|x).\n",
        "3. An objective function for learning, usually involving minimizing\n",
        "error on training examples.\n",
        "4. An algorithm for optimizing the objective function.\n",
        "\n",
        "decision boundary, y > 0.5\n",
        "\n",
        "An objective function or loss function that tells us distance between\n",
        "the system output and the gold output. We will use cross-entropy\n",
        "loss.\n",
        "2. An algorithm for optimizing the objective function. We will use\n",
        "stochastic gradient descent to minimize the loss function. \n",
        "\n",
        "Conditional maximum likelihood estimation: Choose parameters w, b\n",
        "that maximize the (log) probabilities of the true labels in the training\n",
        "data.\n",
        "The resulting loss function is the negative log likelihood loss, more\n",
        "commonly called the cross entropy loss.\n",
        "\n",
        "The result is cross-entropy loss:\n",
        "Lce yhat, y = -log p( y|x) = - [y log yhat + (1-y) log (1- y hat)]\n",
        "\n",
        "gradient descent \n",
        "\n",
        "cost (w, b) = 1/m sum over m Lce ( yhat i, yi)\n",
        "\n",
        "stochastic gradient descent chooses single random example\n",
        "\n",
        "batch training computes gradient over entire dataset\n",
        "\n",
        "mini batch training, small batch, loss accumulated\n",
        "\n",
        "regularization penalizes large weights, regularization added to loss function\n",
        "\n",
        "To get a proper probability, we will use a generalization of the sigmoid function\n",
        "called the softmax function.\n",
        "\n",
        "smoothness is crucial, small change should produce small change in output\n",
        "\n",
        "The simplest kind of NN is the Feed-Forward Neural Network\n",
        "Multilayer network, all units are usually fully-connected, and no cycles.\n",
        "\n",
        "A loss function – cross-entropy loss\n",
        "An optimization algorithm – gradient descent\n",
        "A way of computing the gradient of the loss function – error propagation \n",
        "\n",
        "Like with logistic regression, we learn the best parameters for the neural net to make\n",
        "its predictions as close to possible as the gold standard labels in our training data y.\n",
        "We use:\n",
        "A cross entropy loss function\n",
        "Gradient descent to perform optimization\n",
        "Error back propagation to compute the gradient of the loss function\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f13c91a0-d9f2-480a-9b55-bca6aa50090b"
      },
      "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": 44,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i)\n,y(i)\n).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class �! via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.\n\ndecision boundary, y > 0.5\n\nAn objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nConditional maximum likelihood estimation: Choose parameters w, b\nthat maximize the (log) probabilities of the true labels in the training\ndata.\nThe resulting loss function is the negative log likelihood loss, more\ncommonly called the cross entropy loss.\n\nThe result is cross-entropy loss:\nLce yhat, y = -log p( y|x) = - [y log yhat + (1-y) log (1- y hat)]\n\ngradient descent \n\ncost (w, b) = 1/m sum over m Lce ( yhat i, yi)\n\nstochastic gradient descent chooses single random example\n\nbatch training computes gradient over entire dataset\n\nmini batch training, small batch, loss accumulated\n\nregularization penalizes large weights, regularization added to loss function\n\nTo get a proper probability, we will use a generalization of the sigmoid function\ncalled the softmax function.\n\nsmoothness is crucial, small change should produce small change in output\n\nThe simplest kind of NN is the Feed-Forward Neural Network\nMultilayer network, all units are usually fully-connected, and no cycles.\n\nA loss function – cross-entropy loss\nAn optimization algorithm – gradient descent\nA way of computing the gradient of the loss function – error propagation \n\nLike with logistic regression, we learn the best parameters for the neural net to make\nits predictions as close to possible as the gold standard labels in our training data y.\nWe use:\nA cross entropy loss function\nGradient descent to perform optimization\nError back propagation to compute the gradient of the loss function\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" \n",
        "Term-Document Matrix\n",
        "\n",
        "Each column vector\n",
        "represents a Document\n",
        "\n",
        "Each row vector\n",
        "represents a Term\n",
        "\n",
        "The value in a cell is\n",
        "based on how often that term\n",
        "occurred in that document\n",
        "\n",
        "The length of the\n",
        "document vectors\n",
        "is the size of the vocabulary \n",
        "\n",
        "Document vectors\n",
        "can be sparse\n",
        "(most values are 0)\n",
        "\n",
        "We can measure\n",
        "how similar two\n",
        "documents are\n",
        "by comparing their\n",
        "column vectors\n",
        "\n",
        "L2 normalization\n",
        "\n",
        "cosine distance\n",
        "\n",
        "\n",
        "Term-term / term-context matrix\n",
        "\n",
        "length of vector is now |V| instead of documents\n",
        "\n",
        "The value in a cell indicates how\n",
        "often abandon appears in a\n",
        "context window surrounding\n",
        "abdicate\n",
        "\n",
        "context window +- 2 words in the same sentence in the same document\n",
        "\n",
        "can use more complex contexts like dependeync patterns, subj of verb, adj mod, etc.\n",
        "\n",
        "tf idf - term frequency (how often a word occured in a document) * inverse document frequency (1 / number of docs it occured in)\n",
        "\n",
        "The training examples are simply word k-grams from the corpus\n",
        "The identities of the first k-1 words are used as features, and the last word is used as\n",
        "the target label for the classification.\n",
        "Conceptually, the model is trained using cross-entropy loss. \n",
        "\n",
        "better results, larger ns, generalize across contexts\n",
        "\n",
        "neural probabilisti lm\n",
        "\n",
        "vector space model -> joing probability function -> neural net learn both\n",
        "\n",
        "get dense vectors by training a classifier\n",
        "\n",
        "word embeddings - dense vectors that embed words\n",
        "\n",
        "Word2vec\n",
        "•Instead of counting how often each\n",
        "word w occurs near \"apricot\"\n",
        "•Train a classifier on a binary prediction task:\n",
        "• Is w likely to show up near \"apricot\"?\n",
        "\n",
        "\n",
        "Skip-Gram Goal\n",
        "Given a tuple (t,c) = target, context\n",
        "•(apricot, jam)\n",
        "•(apricot, aardvark)\n",
        "Return probability that c is a real context\n",
        "word:\n",
        "P(+|t,c)\n",
        "P(−|t,c) = 1−P(+|t,c)\n",
        "\n",
        "similarity = t dot c, turn to probability with sigmoid\n",
        "\n",
        "assume context words are independent\n",
        "\n",
        "starts with initial set of embedding vectors, iteratively shifts the embedding to be more like embeddings of words taht occur nearby in texts\n",
        "\n",
        "Similarity depends on window size\n",
        "\n",
        "vector arithmetic can solve analogies, capture relational meaning\n",
        "\n",
        "help study word history, reflect cultural bias\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 45,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "da00151c-c75a-42d9-830a-8d2724d91a21"
      },
      "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": 46,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i)\n,y(i)\n).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class �! via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.\n\ndecision boundary, y > 0.5\n\nAn objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nConditional maximum likelihood estimation: Choose parameters w, b\nthat maximize the (log) probabilities of the true labels in the training\ndata.\nThe resulting loss function is the negative log likelihood loss, more\ncommonly called the cross entropy loss.\n\nThe result is cross-entropy loss:\nLce yhat, y = -log p( y|x) = - [y log yhat + (1-y) log (1- y hat)]\n\ngradient descent \n\ncost (w, b) = 1/m sum over m Lce ( yhat i, yi)\n\nstochastic gradient descent chooses single random example\n\nbatch training computes gradient over entire dataset\n\nmini batch training, small batch, loss accumulated\n\nregularization penalizes large weights, regularization added to loss function\n\nTo get a proper probability, we will use a generalization of the sigmoid function\ncalled the softmax function.\n\nsmoothness is crucial, small change should produce small change in output\n\nThe simplest kind of NN is the Feed-Forward Neural Network\nMultilayer network, all units are usually fully-connected, and no cycles.\n\nA loss function – cross-entropy loss\nAn optimization algorithm – gradient descent\nA way of computing the gradient of the loss function – error propagation \n\nLike with logistic regression, we learn the best parameters for the neural net to make\nits predictions as close to possible as the gold standard labels in our training data y.\nWe use:\nA cross entropy loss function\nGradient descent to perform optimization\nError back propagation to compute the gradient of the loss function\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "0295e9b0-98e4-47de-a3fc-47228f5a2ed4"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n$P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\nutility function assigns number to desirability of state \n\nexpected utility of an action is sum of probability of states times utility of state \n\nprinciple of maximum expected utility (MEU) says that a rational agent should choose\nthe action that maximizes the agent’s expected utility \n\nmeu formalizes notion of \"doing the right thing\" but does not operationalize\n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible\nenvironments)\n\nThe utility function applies to the very next state, so it can\nbe used to guide actions step by step.\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\norderability - must make a decision- one better, or equal\n\ntransitivity a > b, b > c means a > c\n\ncontinuity if b is between a and c, then there is some probability for a and c where surefire b is equivalent\n\nSUBSTITUTABILITY - if indifferent between a and b, then comparisons for more complex lotteries should be the same if a is switched for b\nmonotonicity - if a is better than b, then the agent prefers the lottery that has a higher probability for a and vice versa\n\nDECOMPOSABILITY - can be reduced to simpler ones with probability\nif preferences obery above, there is a utility function\n\nexpected utility is sum of probability times utility\n\nonly needs preference ranking, don't specifically need numbers - value function, ordinal utility function\n\n\n## AIMA Chapter 16.3 Utility Functions\n\npreference elicitation - present choices and use observed preferences to pin down underlying utility function\nchoose between s and standard lottery\n\nvalue of statistical life, ~$10 mil\n\nmicromort, one in a million chance of death, actual behavior reflex lower monetary value for micromort\n\nqaly, quality adjusted life year, shorter life expectancy better than disability\n\nrisk averse in gains, risk seeking in losses\n\ndifference between emv of loterry and certainty equivalent is insurance premium\n\nsmall changes will be approx linear, linear curves are risk neutral\n\noptimizer's curse - estimated EU of best choice is too high\n\ndecision theory is normative, describes should\ndescriptive theory describes how it actually is\n\nframing effect\nanchoring effect\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nthe transition model (or just “model,” when the meaning is clear)\ndescribes the outcome of each action in each state.\n\nWe will assume that transitions are\nMarkovian: the probability of reaching from depends only on and not on the history of\nearlier states. \n\nthe utility function will depend on a\nsequence of states and actions—an environment history—rather than on a single state. \n\nagents will receive a reward from state s to s' on action a, bounded by +- r max\n\na sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a Markov decision\nprocess, or MDP, and consists of a set of states (with an initial state s0); a set ACTIONS(s) of\nactions in each state; a transition model P(s' | s, a); and a reward function R(s,a,s').\n\nusually solving mdps involve dp\n\na policy specifies what an agent should do at any state (a solution to an mdp).\noptimal policy yields highest EU. pi* denotes optimal policy.\n\n A finite horizon means that there is a fixed time after which nothing\nmatters\n\nA policy that\ndepends on the time is called nonstationary, depends only on current state = stationary\n\n“infinite horizon” does not necessarily\nmean that all state sequences are infinite; it just means that there is no fixed deadline\n\nadditive discounted rewards: the utility of a history is sum of rewards multiplied by a discount factor gamma between 0 and 1 at each step.\ngamma represents preference of agent for current over future rewards\n\ngamma = 1 = additive rewards, used implicitly in use of path cost functions in heuristic search\n\nreasons for discounted rewards\n(1) animals value near term\n(2) getting money now and investing is good\n(3) uncertainty of true rewards (may never arrive)\n(4) preferences over histories, preferences between state sequences are stationary\n\nexpected utility of a policy is just expected value of executing it down with discount factor\n\nwith infinite horizon, optimal strategy independent of starting state\n\nbellman equation: U(s) = max sum{ p(s'|s,a) * (R(s,a,s' + gamma * U(s')) } over actions a\n\naction utility function (q function) is expected utility of action + state instead  of just state, U = max action (q(s,a))\n\npi * = argmax q\n\nshaping theorem:\nr(s,a,s' = r(s,a,s') + gamma f(s) - f(s)\n\nfunction phi (s) often called a :potential\", if higher in states with higher utility, you can lead the agent \"uphill\" in utility.\nphi acts as gradient\n\nsimplest way to represent mdps is through 3d tables s^2a, or can be sparse so sa\n\ndynamic decision networks - decision, reward, utility nodes feed forward to utility function\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n\nvalue iteration \"bellman step\"\n\nset u_i+1(s) to max a of sum of p(s'|s,a) * r(s,a,s') + gamma u_i(s')\n\napplied simultaneously to all states at each iteration, eventually reach equilibrium, final must be solutions to bellman eq\n\na contraction is a function of one argument that, when\napplied to two different inputs in turn, produces two output values that are “closer\ntogether,” by at least some constant factor, than the original inputs. For example, the\nfunction “divide by two” is a contraction, because, after we divide any two numbers by two,\ntheir difference is halved, eventually reaches \"fixed point\" where function doesn't change (0)\n\ncontraction only has one fixed point\n\nvalue must get closer to fixed point with repeated application of contraction\n\nbellman update is a contraction by a factor of gamma on the space of utility vectors\n\nterminates after under certain error (can bound error in utility estimates if we stop after a finite nubmer of iterations)\n\nif ∥Ui − U ∥< ϵ then ∥ U πi − U ∥< 2ϵ.\n\npolicy iteration alternates between policy evaluation and improvement, terminates when no change in utilities after improvement\nUi(s) = ∑s′P(s′|s, πi(s))[R(s, πi(s), s′) + γ Ui(s′)].\n\nmodified bellman update for modified policy iteration\n\nUi+1(s) ← ∑s′P(s′|s, πi(s))[R(s, πi(s), s′) + γ Ui(s′)]\n\ncan apply updating utility / states to subsets of states (asynchronous policy iteration)\n\nLP solution to a bellman\n\nminimize U(s) for all s constrained by \nU(s) ≥ ∑\ns\n′\nP(s\n′\n|s, a)[R(s, a, s\n′) + γ U(s\n′)]\n\nonline algorithms for mdps: expectimax\n\nreal time dynamic programming\n\n\n\n\n\n## Module 8 Lecture Notes\n not different from above \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\nIn Las Vegas, a one-armed bandit is a slot machine. A gambler can insert a coin, pull the\nlever, and collect the winnings (if any). An n-armed bandit has levers. \n\ntradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information\n\none definition of bandit problem:\nEach arm is a Markov reward process or MRP, that is, an MDP with only one\npossible action . It has states , transition model , and reward .\nThe arm defines a distribution over sequences of rewards , where each \n is a random variable.\nThe overall bandit problem is an MDP: the state space is given by the Cartesian product \n; the actions are ; the transition model updates the state of\nwhichever arm is selected, according to its specific transition model, leaving the\nother arms unchanged; and the discount factor is gamma.\n\nIf you pull the first T arm times we say that the stopping time is T.\n\ngittins index : sum of discounted rewards up to stopping time over just discount factor sum up to t\n\n\npull the arm that has the highest gittins index, update the gittins indices\nthe Bernoulli bandit,\nwhere each arm produces a reward of 0 or 1 with a fixed but unknown probability .\nThe state of arm is defined by and , the counts of successes (1s) and failures (0s) so\nfar for that arm; the transition probability predicts the next outcome to be 1 with probability\n and 0 with probability . The counts are initialized to 1 so that the initial probabilities are 1/2\n\nthere is also an exploration bonus associated with arms that have only been\ntried a few times.\n\nApproximately optimal bandit policies (calculating gittins indices is hard)\n\nThe first class of methods uses the upper confidence bound or UCB heuristic, previously\nintroduced for Monte Carlo tree search\n\nNi = number of times arm has been sampled\n\nUCB(Mi) = μˆi + g(N)/√Ni \n\nUCB policy picks arm with highest ucb\n\nThe precise definition of g determines the regret relative to the clairvoyant policy, which\nsimply picks the best arm and yields average reward .\n\nRegret lower bounded by log n\n\nThompson sampling chooses chooses an arm\nrandomly according to the probability that the arm is in fact optimal, given the samples so\nfar\n\nbandit superprocess each arm is a full Markov decision process (multitasking\n\nopportunity cost: how\nmuch utility is given up per time step by not devoting that time step to another arm.\n\nwhen an optimal policy in a given arm is unaffected by the opportunity cost it's called a dominating policy. It turns out that by adding\n\nby adding actions to states, it is always possible to create a relaxed version of an MDP so it has a dominating policy, giving upper bound for value of acting on the arm, lower bound can be computed by solving each arm separately and computing gittins indices\n\nlarge bsps can be solved\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nAn alternative is reinforcement learning (RL), in which an agent interacts with the world\nand periodically receives rewards (or, in the terminology of psychology, reinforcements)\nthat reflect how well it is doing.\n\nsparse rewards, in the vast majority of states the agent is\ngiven no informative reward signal at all\n\nintermediate rewards are better\n\nMODEL-BASED REINFORCEMENT LEARNING: In these approaches the agent uses a\ntransition model of the environment to help interpret the reward signals and to make\ndecisions about how to act\n\nMODEL-FREE REINFORCEMENT LEARNING: In these approaches the agent neither\nknows nor learns a transition model for the environment.\nACTION-UTILITY LEARNING: The most common form of action-utility learning is Q-learning, where the\nagent learns a Q-function.\nPOLICY SEARCH: The agent learns a policy that maps directly from states to\nactions.\n\nprimary problem is exploration\n\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \npassive learning agent: The agent is trying to learn the utility function —the expected total discounted\nreward if policy is executed beginning in state, similar to policy evaluation\n\ndirect 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\nprovides a sample of this quantity for each state visited.\n\nThe utility of a state is determined by the reward and the expected utility of\nthe successor states. More specifically, the utility values obey the Bellman equations for a\nfixed policy\n\n(direct utility estimation is super slow)\n\nAn adaptive dynamic programming (or ADP) agent takes advantage of the constraints\namong the utilities of states by learning the transition model that connects them and solving\nthe corresponding Markov decision process using dynamic programming.\n\nmodified policy iteration, using\na simplified value iteration process to update the utility estimates after each change to the\nlearned model. Because the model usually changes only slightly with each observation, the\nvalue iteration process can use the previous utility estimates as initial values and typically\nconverge very quickly.\n\nFor a passive\nlearning agent, this means plugging in the learned transition model and the observed rewards\n\nUπ(s) ← Uπ(s) + α[R(s,π(s),s′) + γUπ(s′) − Uπ(s)].\n\na is the learning rate\n\ncalled temporal difference equation (temporal difference learning)\n\nAll temporal-difference methods work by adjusting the utility estimates toward the ideal\nequilibrium that holds locally when the utility estimates are correct. I\n\nEach adjustment made by ADP could be seen, from the TD point of view, as a result of a\npseudoexperience generated by simulating the current transition model.\n\nBound the number of adjustmens made after each transition: The prioritized\nsweeping heuristic prefers to make adjustments to states whose likely successors have just\nundergone a large adjustment in their own utility estimates.\n\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \n\nAn active learning\nagent gets to decide what actions to take rather than fixed policy.\n\nshould be “greedy in the limit of infinite exploration,” or GLIE\n\none of simplest is to have the agent choose a random\naction at time step with probability and to follow the greedy policy otherwise. \n\n(better is give some weight to actions that the agent has not tried very often, while tending to avoid\nactions that are believed to be of low utility )\n\nlet N(s,a) be the number of times action has been tried in state .\n\nU+(s) <- max action f(bellman, n)\n\nHere, f is the exploration function. The function determines how greed (preference\nfor high values of the utility ) is traded off against curiosity (preference for actions that\nhave not been tried often and have a low count ). \n\nMany actions are irreversible, may enter absorbing state where no actions have any effect and no rewards are received\n\nThe second approach, derived from robust control theory, allows for a set of possible\nmodels without assigning probabilities to them, and defines an optimal robust policy as\none that gives the best outcome in the worst case over :\n\nThe robust control approach can be considered as a game between the agent and an\nadversary, where the adversary gets to pick the worst possible result for any action, and the\npolicy we get is the minimax solution for the game. \n\nThe Q-learning method avoids the need for a model by learning an action-utility function \n instead of a utility function. Enables the agent to act optimally simply by choosing , with no need for\nlook-ahead based on a transition model.\n\nSARSA (for state, action, reward, state, action). The\nupdate rule for SARSA is very similar to the Q-learning update rule (Equation (22.7) ),\nexcept that SARSA updates with the Q-value of the action that is actually taken:\n\nQ(s,a) ← Q(s,a) + α[R(s,a,s\n′) + γ Q(s\n′\n,a\n′) − Q(s,a)],\n\nThe rule is applied at the end of each quintuplet s, a, r, s', a\n\nq learning is off policy because because it assumes it switches policy\n\nsarsa is on policy it assumes you stick with current policy\n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\nn evaluation function as a compact measure of\ndesirability for potentially vast state spaces\n\nfunction\napproximation for the process of constructing a compact approximation of the true utility\nfunction or Q-function\n\nweighted linear combination of features instead of learning states\n\nsupervised learning algorithm\nθi ← θi − α(derivative of half squared difference of predicted total and actual total)\n\n= θi + α[uj(s) − Uˆθ(s)] * derivative of half squared difference of predicted total and actual total .\n\nwidrow-hoff rule / delta rule for online least squares\n\nfeatures can be arbitrary nonlinear functions of state variables\n\nparameters can diverge to infinity\n\ncatastrophic forgetting, learns something too well and forgets something very important\n\nexpierence replay (ensures that car relives youthful crashing behavior at regular intervals)\n\ncredit assignment - what among the many controls went wrong\n\nreward shaping: This\ninvolves supplying the agent with additional rewards, called pseudorewards, for “making\nprogress.” For example, we might give pseudorewards to the robot for making contact with\nthe ball or for advancing it toward the goal.\n\nAnother way to cope with very long action sequences is to break them up into a few smaller\npieces, and then break those into smaller pieces still, and so on until the action sequences\nare short enough to make learning easy. This approach is called hierarchical reinforcement\nlearning (HRL),\n\nThe hierarchical structure of behavior also provides a natural additive decomposition of the\noverall utility function.\n\n\n\n\n\n## Module 9 Lecture Notes\n not different from above \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\nbelief state —a representation of the set of all possible world states that it might be in\n\nNone of these conditions\ncan be deduced for sure, so we can’t infer that the plan succeeds. This is the logical\nqualification problem\n\nTrying to use logic to cope with a domain like\nmedical diagnosis thus fails for three main reasons:\n\nLAZINESS: It is too much work to list the complete set of antecedents or consequents\nneeded to ensure an exceptionless rule and too hard to use such rules.\n\nTHEORETICAL IGNORANCE: Medical science has no complete theory for the domain.\n\nPRACTICAL IGNORANCE: Even if we know all the rules, we might be uncertain about\na particular patient because not all the necessary tests have been or can be run.\n\nThe agent’s\nknowledge can at best provide only a degree of belief in the relevant sentences. Our main\ntool for dealing with degrees of belief is probability theory\n\nTo make such choices, an agent must first have preferences among the different possible\noutcomes of the various plans. An outcome is a completely specified state, including such\nfactors as whether the agent arrives on time and the length of the wait at the airport. We use\nutility theory to represent preferences and reason quantitatively with them\n\ndecision theory = probability theoyr + utility theory\n\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n\nunconditional or prior\nprobabilities\n\nevidence\n\ncondition / posteireor probability\n\nupdate prior\n\n\nproduct rule\n\nP(a /\\ b) = P (a | b) P (b)\n\nif range between 0 and 1, variable has bernoulli distribution\n\nP(Weather) = ⟨0.6, 0.1, 0.29, 0.01⟩,\n\nWe say that the \nstatement defines a probability distribution for the random variable —that is, an\nassignment of a probability for each possible value of the random variable. (In this case,\nwith a finite, discrete range, the distribution is called a categorical distribution.)\n\nprobability density function describes continuous variable\n\njoint probability distribution\n\nP(a ∨ b) = P(a) + P(b) − P(a ∧ b).\n inclusion–exclusion principle:\n\n  Kolmogorov’s axioms\n\nP(A) >= 0\nP(Omega) = 1\ndisjouint sets sum\n\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n\nquery propositions given observed evidence. We\nuse the full joint distribution as the “knowledge base” from which answers to all questions\nmay be derived\n\nFor example, adding the entries in the first row gives the unconditional or\nmarginal probability of :\n\nThis process is called marginalization, or summing out\n\n conditioning\n\n \n\n## AIMA Chapter 12.4 Independence\n independence good \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n baye's rule\np(b|a) = p (a|b) P(b) / p(a)\n\neffect give n cause is causal direction\n\ncause given effect is diagnostic direction\n\nconditional independence\nP(a /\\ b|c) = P(a|c) P(a|b)\n\nc separates a and b\n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n\nnaive bayes model\nP(cause, e, e2, e3) = p(cause) * P (e | c ) * P (e2 | c )...\n\n(The naive Bayes model is sometimes called a\nBayesian classifier, a somewhat careless usage that has prompted true Bayesians to call it\nthe idiot Bayes model.)\n\noften works well, even when conditional indpenednece assumption not true\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n wumpus \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \n\nOut of vocabulary items (OOV)\n<unk> to deal with OOVs\nFixed lexicon L of size V\nNormalize training data by replacing any word not in L with <unk>\nAvoid zeros with smoothin\n\nWe do everything in log space\n• Avoid underflow\n• (also adding is faster than multiplying)\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \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 to\nnode is said to be a parent of . The graph has no directed cycles and hence is\na directed acyclic graph, or DAG.\n\n3. Each node has associated probability information that\nquantifies the effect of the parents on the node using a finite number of parameters.\n\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Variable elimination works by evaluating expressions such as \nP(j|a)P(m|a) P(j|¬a)P(m|¬a)\n\nin right-to-left order (that is, bottom up in Figure 13.10 ). Intermediate results are stored,\nand summations over each variable are done only for those portions of the expression that\ndepend on the variable.\n \n\n## Module 11 Lecture Notes\n \nThe conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of the parents\n\nx _||_ y \nindepdence\n\nEmpirical joint distributions: at best “close” to independent\n\nBayes’ nets: a technique for describing complex joint\ndistributions (models) using simple, local\ndistributions (conditional probabilities)\n\nMore properly called graphical models\n§ We describe how variables locally interact\n§ Local interactions chain together to give global, indirect\ninteractions\n\nA set of nodes, one per variable X\n\nA directed, acyclic graph\n\nA conditional distribution for each node\n\nBayes’ nets implicitly encode joint distributions\n\nWhy are we guarenteed in setting chaining parents results in a proper joint distribution\n\nChain rule (valid for all distributions): \n\nAssume conditional independences:\n\nNot every BN can represent every joint distribution, topology enforces certain conditional independenceise\n\njoint distribution over n booleans is 2^n\n\nn-node net with k parents is O(N * 2^k+1)\n\nBoth give power to calculate P(x1, x2, x)...\n\nBNs have huge space savings\n\nThis configuration is a “causal chain”\n\nx - y - z\n\ncommon cause\n\nx - y\n\n|\n\nz\n\nguarenteed x independent of z\n\n\ntwo causes, one effect\n\nv-structures\n\nobserving an effect activates influence between possible causes\n\nreachability\n\n: if two nodes are connected\nby an undirected path not blocked by\na shaded node, they are conditionally\nindependent, but : the v-structure at T doesn’t count\nas a link in a path unless “active”\n\nd-paration\n\ncheck all undirected paths between two variables\n\nif one or more active, independence not guarenteed\n\notherwise, guarenteed\n\ninference, calculating some useful quantity from joint probability distribution\n\ninference by enumeration - slow\n\nvariable elimination, usually much faster\n\n\n\n\n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n\nLaplace smoothing\n\nPretend you saw every outcome k extra times\n\nk is the strength of the prior\n\nlinear interpolation (learning rate)\na p(x|y) + (1 - a)p(x)\n\nLearn parameters from training data\n\ntune hyperparameters on different data\n\nneed more features - words aren't enough\n\ncan add information sources as new variables\n\nBinary case: compare features to a weight vector\nLearning: figure out the weight vector from examples\n\nIn the space of feature vectors\n• Examples are points\n• Any weight vector is a hyperplane\n• One side corresponds to Y=+1\n• Other corresponds to Y=-1\n\nbinary perceptrons only output 1 and 0\n\nmulticlass outputs highest\n\nproblems\n\nNoise: if the data isn’t separable,\nweights might thrash\n• Averaging weight vectors over\ntime can help (averaged\nperceptron)\nMediocre generalization: finds a\n“barely” separating solution\nOvertraining: test / held-out\naccuracy usually rises, then falls\n• Overtraining is a kind of\noverfitting\n\n\nMIRA*: choose an update size that fixes the current\nmistake…\n… but, minimizes the change to w\n\n\nMinimum Correcting Update\n\nt = difference in weights dot f + 1 / (2 f dot f)\n\n\nwy = wy - tf(x)\nwy* = wy* + tf(x)\n\n\nmaximum step size, cap with seom constant c\n\nmaximize margin\n\nonly support vectors matter\n\nNaïve Bayes\n• Builds a model training data\n• Gives prediction probabilities\n• Strong assumptions about feature independence\n• One pass through data (counting)\n\nPerceptrons / MIRA:\n• Makes less assumptions about data\n• Mistake-driven learning\n• Multiple passes through data (prediction)\n• Often more accurate\n\nperceptrons start with weight 0\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector\n\nA single neural unit cannot be used to compute the XOR function\n\nactivation function\n\nReLU - rectified linear unit\n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i)\n,y(i)\n).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class �! via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.\n\ndecision boundary, y > 0.5\n\nAn objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nConditional maximum likelihood estimation: Choose parameters w, b\nthat maximize the (log) probabilities of the true labels in the training\ndata.\nThe resulting loss function is the negative log likelihood loss, more\ncommonly called the cross entropy loss.\n\nThe result is cross-entropy loss:\nLce yhat, y = -log p( y|x) = - [y log yhat + (1-y) log (1- y hat)]\n\ngradient descent \n\ncost (w, b) = 1/m sum over m Lce ( yhat i, yi)\n\nstochastic gradient descent chooses single random example\n\nbatch training computes gradient over entire dataset\n\nmini batch training, small batch, loss accumulated\n\nregularization penalizes large weights, regularization added to loss function\n\nTo get a proper probability, we will use a generalization of the sigmoid function\ncalled the softmax function.\n\nsmoothness is crucial, small change should produce small change in output\n\nThe simplest kind of NN is the Feed-Forward Neural Network\nMultilayer network, all units are usually fully-connected, and no cycles.\n\nA loss function – cross-entropy loss\nAn optimization algorithm – gradient descent\nA way of computing the gradient of the loss function – error propagation \n\nLike with logistic regression, we learn the best parameters for the neural net to make\nits predictions as close to possible as the gold standard labels in our training data y.\nWe use:\nA cross entropy loss function\nGradient descent to perform optimization\nError back propagation to compute the gradient of the loss function\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i)\n,y(i)\n).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class �! via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.\n\ndecision boundary, y > 0.5\n\nAn objective function or loss function that tells us distance between\nthe system output and the gold output. We will use cross-entropy\nloss.\n2. An algorithm for optimizing the objective function. We will use\nstochastic gradient descent to minimize the loss function. \n\nConditional maximum likelihood estimation: Choose parameters w, b\nthat maximize the (log) probabilities of the true labels in the training\ndata.\nThe resulting loss function is the negative log likelihood loss, more\ncommonly called the cross entropy loss.\n\nThe result is cross-entropy loss:\nLce yhat, y = -log p( y|x) = - [y log yhat + (1-y) log (1- y hat)]\n\ngradient descent \n\ncost (w, b) = 1/m sum over m Lce ( yhat i, yi)\n\nstochastic gradient descent chooses single random example\n\nbatch training computes gradient over entire dataset\n\nmini batch training, small batch, loss accumulated\n\nregularization penalizes large weights, regularization added to loss function\n\nTo get a proper probability, we will use a generalization of the sigmoid function\ncalled the softmax function.\n\nsmoothness is crucial, small change should produce small change in output\n\nThe simplest kind of NN is the Feed-Forward Neural Network\nMultilayer network, all units are usually fully-connected, and no cycles.\n\nA loss function – cross-entropy loss\nAn optimization algorithm – gradient descent\nA way of computing the gradient of the loss function – error propagation \n\nLike with logistic regression, we learn the best parameters for the neural net to make\nits predictions as close to possible as the gold standard labels in our training data y.\nWe use:\nA cross entropy loss function\nGradient descent to perform optimization\nError back propagation to compute the gradient of the loss function\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}