{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other 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": "9b91dae8-1c55-4f17-8694-91b71b3f6965"
      },
      "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": 1,
      "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": "684c97d3-dbfd-4d2d-a19a-aa2e6025fd2c"
      },
      "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": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "Introduces the basics of decision theory: maximization of expected (average) utility. Utiltiy\n",
        "is another form of performance measure. Utility function applies to the next step so it \n",
        "can guide actions.\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" \n",
        "Shows behavior of a rational agent can be modeled by maximizing a utility function. It also\n",
        "discusses what makes a rational preference: orderability, transitivity, continuity, substitutability\n",
        "monotonicity, decomposability -> axioms. Rational preferences will lead to a utility\n",
        "function. The number/values of the preference doesn't matter in a determiniistic environment.\n",
        "CAlled value function or Ordinal utility function.\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "Discusses utility functions in relationshp to numbers.\n",
        "Utility functions map from lotteries to real  numbers. Micromort -> value on life. usually, people are\n",
        "risk adverse, but in debt, people are risk seeking. Normative theories describs how a rational\n",
        "agent should act, but descriptive theories model how agents actually act.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "Explains how sequential decision problems are defined. Methods for solving MDPs involve\n",
        "dynamic programming. An optimal policy yields highest expected utility. Utilities over time\n",
        "requries knowledge of time-frame for decision making (infinite or finite). A policy that depends\n",
        "on time is Nonstationary. If no fixed time limit, then optimal policy is stationary. \n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "Describes methods to solve them to produce appropriate behaviors. There are 3 algos for solving MDPs: \n",
        "Offline: value iteration, policy iteration, linear programming. Online: Monte Carlo planning. \n",
        "\n",
        "Linear Programming\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "MDP is offline planning\n",
        "\n",
        "**MDPFormulation1**: MDP is decision process where ENVIRONMENT FULL VISIBLE, TRANSITION STOCHASTIC, \n",
        "with REWARD FUNCTION and DISCOUNT.\n",
        "\n",
        "Infinite Games vs. Finite Games: Choice of actions depends on how long left \n",
        "in the game. Infinite is hard.\n",
        "\n",
        "Sometimes expected utility is same, but when you receive it differs (ex. incremental\n",
        "diamonds vs diamonds at end)->Have reward function dictate this.\n",
        "\n",
        "**MDPFormulation2**: discount dictates other factors. Helps converge.\n",
        "\n",
        "If game is infinite, use to resolve non convergence.\n",
        "\n",
        "MDP search tree is expectimax\n",
        "\n",
        "**ValueIteration**: Given a vector of Vk(s), do expectimax on each state. Repeat \n",
        "until convergence. Each iter O(s^2A) time.\n",
        "\n",
        "Went over example of value iteration.\n",
        "\n",
        "Convergence: HOw to know if converges? \n",
        "\n",
        "Case1: If has max depth\n",
        "\n",
        "Case2: If discount<1; for any state, the difference beween its value Vk and Vk+1\n",
        "is a depth 1 expectimax. The last layer will bound maximum amount (with the biggest\n",
        "change. At best it's Rmax, at worst it's Rmin. Vk and Vk+1 are at most y^k|R| diff.)\n",
        "\n",
        "**PolicyIteration**: Directly estimate best policy by using argmax. Turn\n",
        "Bellman Equation into updates like value iteration. Each iter is O(S^2). \n",
        "\n",
        "1.Calculate utility for some fixed policy (not optimal utilities) until convergence.\n",
        "\n",
        "2.Improve policy using one-step lookahead using values from 1. Repeat until convergence.\n",
        "\n",
        "Get action from normalValues: policyExtraction->perform neighbor minimax. \n",
        "\n",
        "Get action from qValues: trivial bc qValue implies best action.\n",
        "\n",
        "**policyIterAlgorithm**: valueIteration is slow, max at each state doesn't change much\n",
        "even though value changes. Policy converges faster than values.\n",
        "\n",
        "**whichOneToUse**: \n",
        "\n",
        "compute optimal values: value iteration\n",
        "\n",
        "compute values for some policy: policy eval\n",
        "\n",
        "turn values into policy: policy extract\n",
        "\n",
        "**Maximum Expected Utility**: \n",
        "\n",
        "Gives more optimistic policy. Need to have utility function that is insensitive to monotonic transforms.\n",
        "\n",
        "For average case expectimax, need meaningful magnitudes. \n",
        "\n",
        "Rationality: \n",
        "What is continuity: There must exist some threshold p for which you're indifferent to B.\n",
        "\n",
        "Substitutability: If A~B, then for two lotteries where A and B are the same probability,\n",
        "with the opposite being C, then they're both the same lottery.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"stationary preferences\" : \"If I prefer some reward sequence over another, preference will not be changed by adding something\",\n",
        "\"Utility\":\"function of outcome to value that reflects an agent's preferences\",\n",
        "\"expected utility\" : \"sum of all outcome value * probability it will occur\",\n",
        "\"expectimax:\": \"expected utility under optimal action\",\n",
        "\"MEU Principle\": \"Rational agent will always make choices that give MEU\",\n",
        "\"shaping theorem\": \"Transformation leaves optimal policy unchanged relatively speaking\",\n",
        "\"dynamic decision networks\": \"more realistic\",\n",
        "\"contraction\": \"a function of one argument such that when applied to two different inputs in turn, produces output vals that are close together\",\n",
        "\"policy loss\": \"||U^pi_i - U|| most agent can lose by executing pi_i instead of optimal policy\",\n",
        "\"asychronous policy iteration\": \"guaranteed to converge to an optimal policy\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 134,
      "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": "fdee8190-b728-4e03-9102-96871645dee2"
      },
      "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": 135,
      "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 \nIntroduces the basics of decision theory: maximization of expected (average) utility. Utiltiy\nis another form of performance measure. Utility function applies to the next step so it \ncan guide actions.\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nShows behavior of a rational agent can be modeled by maximizing a utility function. It also\ndiscusses what makes a rational preference: orderability, transitivity, continuity, substitutability\nmonotonicity, decomposability -> axioms. Rational preferences will lead to a utility\nfunction. The number/values of the preference doesn't matter in a determiniistic environment.\nCAlled value function or Ordinal utility function.\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nDiscusses utility functions in relationshp to numbers.\nUtility functions map from lotteries to real  numbers. Micromort -> value on life. usually, people are\nrisk adverse, but in debt, people are risk seeking. Normative theories describs how a rational\nagent should act, but descriptive theories model how agents actually act.\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nExplains how sequential decision problems are defined. Methods for solving MDPs involve\ndynamic programming. An optimal policy yields highest expected utility. Utilities over time\nrequries knowledge of time-frame for decision making (infinite or finite). A policy that depends\non time is Nonstationary. If no fixed time limit, then optimal policy is stationary. \n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \nDescribes methods to solve them to produce appropriate behaviors. There are 3 algos for solving MDPs: \nOffline: value iteration, policy iteration, linear programming. Online: Monte Carlo planning. \n\nLinear Programming\n\n\n## Module 8 Lecture Notes\n \nMDP is offline planning\n\n**MDPFormulation1**: MDP is decision process where ENVIRONMENT FULL VISIBLE, TRANSITION STOCHASTIC, \nwith REWARD FUNCTION and DISCOUNT.\n\nInfinite Games vs. Finite Games: Choice of actions depends on how long left \nin the game. Infinite is hard.\n\nSometimes expected utility is same, but when you receive it differs (ex. incremental\ndiamonds vs diamonds at end)->Have reward function dictate this.\n\n**MDPFormulation2**: discount dictates other factors. Helps converge.\n\nIf game is infinite, use to resolve non convergence.\n\nMDP search tree is expectimax\n\n**ValueIteration**: Given a vector of Vk(s), do expectimax on each state. Repeat \nuntil convergence. Each iter O(s^2A) time.\n\nWent over example of value iteration.\n\nConvergence: HOw to know if converges? \n\nCase1: If has max depth\n\nCase2: If discount<1; for any state, the difference beween its value Vk and Vk+1\nis a depth 1 expectimax. The last layer will bound maximum amount (with the biggest\nchange. At best it's Rmax, at worst it's Rmin. Vk and Vk+1 are at most y^k|R| diff.)\n\n**PolicyIteration**: Directly estimate best policy by using argmax. Turn\nBellman Equation into updates like value iteration. Each iter is O(S^2). \n\n1.Calculate utility for some fixed policy (not optimal utilities) until convergence.\n\n2.Improve policy using one-step lookahead using values from 1. Repeat until convergence.\n\nGet action from normalValues: policyExtraction->perform neighbor minimax. \n\nGet action from qValues: trivial bc qValue implies best action.\n\n**policyIterAlgorithm**: valueIteration is slow, max at each state doesn't change much\neven though value changes. Policy converges faster than values.\n\n**whichOneToUse**: \n\ncompute optimal values: value iteration\n\ncompute values for some policy: policy eval\n\nturn values into policy: policy extract\n\n**Maximum Expected Utility**: \n\nGives more optimistic policy. Need to have utility function that is insensitive to monotonic transforms.\n\nFor average case expectimax, need meaningful magnitudes. \n\nRationality: \nWhat is continuity: There must exist some threshold p for which you're indifferent to B.\n\nSubstitutability: If A~B, then for two lotteries where A and B are the same probability,\nwith the opposite being C, then they're both the same lottery.\n\n \n\n## Module 8 Definitions\n* **Stationary preferences** - If I prefer some reward sequence over another, preference will not be changed by adding something\n* **Utility** - function of outcome to value that reflects an agent's preferences\n* **Expected utility** - sum of all outcome value * probability it will occur\n* **Expectimax:** - expected utility under optimal action\n* **Meu principle** - Rational agent will always make choices that give MEU\n* **Shaping theorem** - Transformation leaves optimal policy unchanged relatively speaking\n* **Dynamic decision networks** - more realistic\n* **Contraction** - a function of one argument such that when applied to two different inputs in turn, produces output vals that are close together\n* **Policy loss** - ||U^pi_i - U|| most agent can lose by executing pi_i instead of optimal policy\n* **Asychronous policy iteration** - guaranteed to converge to an optimal policy\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" \n",
        "Bandit Problems\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "\n",
        "Reinforcement Learning involves an agent that interacts w/ the world and receives rewards that reflect\n",
        "its performance. In games like Chess, we have sparse rewards where we can't tell how\n",
        "well we are doing, vs. tennis where we can get points. There is Model based reinforcement learning,\n",
        "model-free learning (action utility learning aka q learning and policy search)\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "Passive reinforcement learning: similar to the policy evaluation task. Start with fully observable\n",
        "environment with small number of actions and states with a fixed policy. Agent is trying to learn the\n",
        "Utility function. Difference from policy evaluation is that Passive learning doesn't know\n",
        "transition model and reward model.\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "active reinforcement learning: decides what actions to take. Agent must make tradeoff between\n",
        "exploitation and exploration. Absorbing state: agent takes irreversible action either bc model is unknown,\n",
        "or model is incorrect and we didn't know it could have really bad result.\n",
        "\n",
        "Bayesian RL: assumes prior probability P(h) over hypothesis H what the true model is.\n",
        "\n",
        "Q Learning avoids the need for model by learning action-utility function Q(s,a) instead. Converges much faster?\n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "Approximate direct utility estimation. Can apply this to temporal difference learners. Adjust\n",
        "params to reduce temporal difference between successive states.\n",
        "\n",
        " Problems like diverging to infinity\n",
        "or catastrophic forgetting: assign high negative reward for something bad, but learned right\n",
        "behavior so well that it forgot what bad behavior was.\n",
        "\n",
        "Experience replay: learning algo can retain trajectories from entire leraning process and replay those to ensure\n",
        "that the value function is still accurate.\n",
        "\n",
        "Deep reinforcement learning: non linear function approximation\n",
        "\n",
        "Reward shaping: supply agent with aditional rewards for making progress. \n",
        "\n",
        "Hierarchical reinforcement learning: break long action sequence into smaller pieces until they're short enough\n",
        "to make learning easy. Solves MDP with:\n",
        "- transition model: if c invokes action a, then t borrows from physical model. If c invokes\n",
        "computational transition like calling subroutine, then transition modifies computational state m??\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" \n",
        "Methods for policy search. Often uses stochastic policy representation (has probabilty)\n",
        "ex) softmax.\n",
        "\n",
        "Policy gradient\n",
        "\n",
        "Empircal gradient:\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "**Intro1**: Learn probability distribution instead of having it given.\n",
        "\n",
        "Online Planning: Do not have any probabilities, must learn through playing. \n",
        "\n",
        "**Intro2**: \n",
        "\n",
        "Reinforcement learning gives feedback in form of rewards. \n",
        "\n",
        "Agent's utility defined by reward function.\n",
        "\n",
        "Learn to maximize expected rewards\n",
        "\n",
        "Observe a sample to learn.\n",
        "\n",
        "-States\n",
        "\n",
        "-actions per state\n",
        "\n",
        "-Transition function (not given)\n",
        "\n",
        "-Reward function (not given)\n",
        "\n",
        "Objective: still looking for best policy\n",
        "\n",
        "**Passive Reinforcement**: \n",
        "\n",
        "Model-free-learning: when results deviate, adjust values up or down. Track only\n",
        "the value of each state and don't keep track of transition or reward function.\n",
        "\n",
        "Passive Reinforcement: someone else picks policy for us. We evalute policy and improve it\n",
        "without knowing T or R.\n",
        "\n",
        "Direct Evaluation: goal compute values for each state under policy. Average together observed\n",
        "sample values. sum discounted rewards of each state you visit then avg them.\n",
        "\n",
        "Problem: Wastes information about state connections; Each state learned separately; \n",
        "Long time to learn. \n",
        "\n",
        "PolicyIteration without T and R: Sample basd policy evaluation. Sample n times and take avg.\n",
        "\n",
        "**Temporal difference learning**: Update estimates of the value of state every single time\n",
        "we experience a transition into it. Any outocmes s' will contribute more often. \n",
        "\n",
        "1. Take sample of V(s) with alpha learn rate, then update V(s) based on sample. \n",
        "\n",
        "2. learn rate alpha interpolates between V^pi(s) and sample val. The more recent\n",
        "samples become more important over time. \n",
        "\n",
        "Problems: Cannot turn values into a new policy.\n",
        "\n",
        "Solution: learn Q-values instead\n",
        "\n",
        "**QLearning Active Reinforcement**: \n",
        "\n",
        "QValueIteration: Same as value iteration but with Q. Start Q(s,a)=0\n",
        "\n",
        "Q(s,a): get sample (s,a,s',r) (non deterministically end in s' and receive r for ending\n",
        "in s' having done (s,a)), will keep a moving average so that every sample we receive\n",
        "helps us update. \n",
        "\n",
        "Consider Q(s,a), evaluate good or bad\n",
        "\n",
        "Consider new sample estimate\n",
        "\n",
        "Incorporate new estimate into running average.\n",
        "\n",
        "QLearning converges ot optimal policy even if you're behaving suboptimally.\n",
        "\n",
        "Caveats: must expore enough, eventually make learning rate small enough but not too\n",
        "quickly. \n",
        "\n",
        "**Exploration vs Exploitation**: \n",
        "Exploration: To do this, can do random actions, can do random actions with small probability. \n",
        "Issue is that we may pick things repeatedly. \n",
        "\n",
        "Solution: lower epsilon over time or write exploration function\n",
        "\n",
        "Exploration Function: Takes value estimate u and visit count n, then returns optimistic\n",
        "utility (onSheet) + some exploration penalty bonus. \n",
        "\n",
        "Regret: MInimizing it = optimally learning to be optimal \n",
        "\n",
        "**Approximate QLearning**: Too many states to visit them all during training/hold table of qstate\n",
        "values in memory. \n",
        "\n",
        "Linear Value Functions: Use feature representation, can write a q function for any state using\n",
        "some weights.  Disadvantage: states may share features but actually be very different in value.\n",
        "\n",
        "UpdateQLearning(s,a): \n",
        "1. given transition(s,a,r,s')\n",
        "2. find the difference between expectation and actual result\n",
        "3. take difference, multiply by learn rate and fi(s,a) (whether feature was active), then add to each weight rather than entire Q state\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Exploration\" : \"try unknown actions to get information\",\n",
        "\"exploitation\": \"eventually you ahve to use what you know\",\n",
        "\"regret\": \"measure of total mistake cost rewards. Minimize regret = learn optimality quickly\",\n",
        "\"sampling\": \"because of chance, you gotta try things repeatedly\",\n",
        "\"difficulty\": \"learning is harder than solving MDP\",\n",
        "\"Model-based\":\"\",\n",
        "\"Model-free learning\": \"take action, compare results to expectation, when deviating, adjust values\",\n",
        "\"Passive Reinforcement\": \"someone else picks policy and not us\",\n",
        "\"value iteration\": \"find successive depth limited value of vk+1(s) given vk\",\n",
        "\"epsilon-greedy policy\": \"if rand num gen is < epsilon, act randomly\",\n",
        "\"direct utility estimation\": \"sum of rewards from then until termination\"\n",
        "}"
      ],
      "execution_count": 136,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a46902d3-cce1-4fad-a78c-413b2e560ce9"
      },
      "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": 137,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \nBandit Problems\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n\n\nReinforcement Learning involves an agent that interacts w/ the world and receives rewards that reflect\nits performance. In games like Chess, we have sparse rewards where we can't tell how\nwell we are doing, vs. tennis where we can get points. There is Model based reinforcement learning,\nmodel-free learning (action utility learning aka q learning and policy search)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nPassive reinforcement learning\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nactive reinforcement learning\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \nInductive learning to learn faster form experiences\n\n\n## Module 9 Lecture Notes\n \n**Intro1**: Learn probability distribution instead of having it given.\n\nOnline Planning: Do not have any probabilities, must learn through playing. \n\n**Intro2**: \n\nReinforcement learning gives feedback in form of rewards. \n\nAgent's utility defined by reward function.\n\nLearn to maximize expected rewards\n\nObserve a sample to learn.\n\n-States\n\n-actions per state\n\n-Transition function (not given)\n\n-Reward function (not given)\n\nObjective: still looking for best policy\n\n**Passive Reinforcement**: \n\nModel-free-learning: when results deviate, adjust values up or down. Track only\nthe value of each state and don't keep track of transition or reward function.\n\nPassive Reinforcement: someone else picks policy for us. We evalute policy and improve it\nwithout knowing T or R.\n\nDirect Evaluation: goal compute values for each state under policy. Average together observed\nsample values. sum discounted rewards of each state you visit then avg them.\n\nProblem: Wastes information about state connections; Each state learned separately; \nLong time to learn. \n\nPolicyIteration without T and R: Sample basd policy evaluation. Sample n times and take avg.\n\n**Temporal difference learning**: Update estimates of the value of state every single time\nwe experience a transition into it. Any outocmes s' will contribute more often. \n\n1. Take sample of V(s) with alpha learn rate, then update V(s) based on sample. \n\n2. learn rate alpha interpolates between V^pi(s) and sample val. The more recent\nsamples become more important over time. \n\nProblems: Cannot turn values into a new policy.\n\nSolution: learn Q-values instead\n\n**QLearning Active Reinforcement**: \n\nQValueIteration: Same as value iteration but with Q. Start Q(s,a)=0\n\nQ(s,a): get sample (s,a,s',r) (non deterministically end in s' and receive r for ending\nin s' having done (s,a)), will keep a moving average so that every sample we receive\nhelps us update. \n\nConsider Q(s,a), evaluate good or bad\n\nConsider new sample estimate\n\nIncorporate new estimate into running average.\n\nQLearning converges ot optimal policy even if you're behaving suboptimally.\n\nCaveats: must expore enough, eventually make learning rate small enough but not too\nquickly. \n\n**Exploration vs Exploitation**: \nExploration: To do this, can do random actions, can do random actions with small probability. \nIssue is that we may pick things repeatedly. \n\nSolution: lower epsilon over time or write exploration function\n\nExploration Function: Takes value estimate u and visit count n, then returns optimistic\nutility (onSheet) + some exploration penalty bonus. \n\nRegret: MInimizing it = optimally learning to be optimal \n\n**Approximate QLearning**: Too many states to visit them all during training/hold table of qstate\nvalues in memory. \n\nLinear Value Functions: Use feature representation, can write a q function for any state using\nsome weights.  Disadvantage: states may share features but actually be very different in value.\n\nUpdateQLearning(s,a): \n1. given transition(s,a,r,s')\n2. find the difference between expectation and actual result\n3. take difference, multiply by learn rate and fi(s,a) (whether feature was active), then add to each weight rather than entire Q state\n \n \n\n## Module 9 Definitions\n* **Exploration** - try unknown actions to get information\n* **Exploitation** - eventually you ahve to use what you know\n* **Regret** - measure of total mistake cost rewards. Minimize regret = learn optimality quickly\n* **Sampling** - because of chance, you gotta try things repeatedly\n* **Difficulty** - learning is harder than solving MDP\n* **Model-based** - \n* **Model-free learning** - take action, compare results to expectation, when deviating, adjust values\n* **Passive reinforcement** - someone else picks policy and not us\n* **Value iteration** - find successive depth limited value of vk+1(s) given vk\n* **Epsilon-greedy policy** - if rand num gen is < epsilon, act randomly\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",
        "Uncertainty due to partial observability, nondterminism, or adversaries. Agent must have\n",
        "preferences among different aoutcomes of the plans. First mentioned MEU. Expected = average.\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\" \n",
        "Set of all possible worlds is sample space.\n",
        "\n",
        "Probability model associates numerical probabilty with each probability world.\n",
        "\n",
        "proposition: set of worlds\n",
        "\n",
        "unconditional probability: P(x) degrees of belief in the absence of any other info.\n",
        "\n",
        "conditional/posterior pobability.\n",
        "\n",
        "Discussed product rule.\n",
        "\n",
        "Factored representation: possible world is represented by a set of varialbe/value pairs.\n",
        "\n",
        "principle of Inclusion exclusion: p(a) + p(b) - p(a ^ b)\n",
        " \"\"\"\n",
        "chapter12_3 = \"\"\" \n",
        "describe method for probabilistic inference (computation of conditional probabilities for query prospositions\n",
        "given some observed evidence.)\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        "Describes the notion of independence of variable, discusses idea of conditional independence.\n",
        "\"\"\"\n",
        "chapter12_5 = \"\"\" \n",
        "Product rule can be rewritten to gain P(y|x) from P(x|y)\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "A naive bayes model (bayesian classifier) where a single cause directly influences a number of effects all of which are \n",
        "conditionally independent given the cause.\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",
        "**Review of Probabilities:**\n",
        "In probability theory, probabilities (possible worlds) are sample space, and are\n",
        "mutually exclusive and exhaustive. \n",
        "\n",
        "A specified probability model associates a probability P(w) with each possible world w.\n",
        "\n",
        "Axioms of probability: \n",
        "1. Any P(w) between 0 and 1\n",
        "2. Sum of everything = 1\n",
        "\n",
        "**Distributions**\n",
        "\n",
        "Unobserved random vars have distributions->a able of probabilities of values. \n",
        "\n",
        "probability is a single number for a single variable. \n",
        "\n",
        "Joint Distribution: JD over a set of vars specifies a real number for each outcome. \n",
        "Say whether assingments (outcomes) are likely. \n",
        "\n",
        "Marginal Distribution: a subtable which eliminates vars.\n",
        "\n",
        "Conditional Probability: A simple relation between joint and conditional probabilities. \n",
        "\n",
        "Conditional Distribution: PD over some variables given fixed values of others. \n",
        " \n",
        " **Probabilistic inference&Rules**: \n",
        " compute a desired probability from other known probabilities: ex conditional from joint.\n",
        "\n",
        " Probabilities will change with new evidence. \n",
        "\n",
        " 1. Inference by Enumeration: split random vars into 3 sets: Evidence vars, Query vars (things we wnat to know),\n",
        " Hidden vars (vars that occur in joint probability distribution but we don't have info on it)\n",
        "\n",
        "Step 1-select entries consistent w/ evidence\n",
        "\n",
        "Step 2-Sum out H to get joint of query and evidence\n",
        "\n",
        "Step 3-Normalize multiply everything with 1/z \n",
        "\n",
        "**Bayes' Rule**: How to derive P(x|y) given P(y|x)\n",
        "\n",
        "**Probabilistic Language Models**: Most likely next word given what you've already typed.\n",
        "\n",
        "Goal: compute probability of a sentence/sequence of words\n",
        "\n",
        "used in texting, machine translation, spelling correction, speech recognition.\n",
        "\n",
        "Example: P(\"The underdog Philadelphia Eagles won\") = P(the) * P(underdog | the) * P(philadelphia | the, underdog) ...\n",
        " \n",
        "Want to ESTIMATE these probabilities using Markov Assumption: Only depends on previous k words, not the whole context.\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Observd variables (evidence)\" : \"agent knows this about world\",\n",
        "\"unobserved\": \"agent wants to reason about this\",\n",
        "\"model\":\"agent knows something about how the known variables relate to unknowns.\",\n",
        "\"random var\": \"some event that we are uncertain about\",\n",
        "\"probabilistic model\": \"JD over a set of random vars, ideally many vars are independent of each other\",\n",
        "\"event\": \"a set E of outcomes\",\n",
        "\"marginalization\": \"combine collapsed rows by adding\",\n",
        "\"unigram\": \"no history\",\n",
        "\"bigram\": \"one word history\",\n",
        "\"trigram\": \"two word history\",\n",
        "\"4-gram\": \"3 word history\",\n",
        "}"
      ],
      "execution_count": 139,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "43985cd3-a349-4970-ac76-56c8ccd4a3aa"
      },
      "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": 140,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \nUncertainty due to partial observability, nondterminism, or adversaries. Agent must have\npreferences among different aoutcomes of the plans. First mentioned MEU. Expected = average.\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \nSet of all possible worlds is sample space.\n\nProbability model associates numerical probabilty with each probability world.\n\nproposition: set of worlds\n\nunconditional probability: P(x) degrees of belief in the absence of any other info.\n\nconditional/posterior pobability.\n\nDiscussed product rule.\n\nFactored representation: possible world is represented by a set of varialbe/value pairs.\n\nprinciple of Inclusion exclusion: p(a) + p(b) - p(a ^ b)\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n 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**Review of Probabilities:**\nIn probability theory, probabilities (possible worlds) are sample space, and are\nmutually exclusive and exhaustive. \n\nA specified probability model associates a probability P(w) with each possible world w.\n\nAxioms of probability: \n1. Any P(w) between 0 and 1\n2. Sum of everything = 1\n\n**Distributions**\n\nUnobserved random vars have distributions->a able of probabilities of values. \n\nprobability is a single number for a single variable. \n\nJoint Distribution: JD over a set of vars specifies a real number for each outcome. \nSay whether assingments (outcomes) are likely. \n\nMarginal Distribution: a subtable which eliminates vars.\n\nConditional Probability: A simple relation between joint and conditional probabilities. \n\nConditional Distribution: PD over some variables given fixed values of others. \n \n **Probabilistic inference&Rules**: \n compute a desired probability from other known probabilities: ex conditional from joint.\n\n Probabilities will change with new evidence. \n\n 1. Inference by Enumeration: split random vars into 3 sets: Evidence vars, Query vars (things we wnat to know),\n Hidden vars (vars that occur in joint probability distribution but we don't have info on it)\n\nStep 1-select entries consistent w/ evidence\n\nStep 2-Sum out H to get joint of query and evidence\n\nStep 3-Normalize multiply everything with 1/z \n\n**Bayes' Rule**: How to derive P(x|y) given P(y|x)\n\n**Probabilistic Language Models**: Most likely next word given what you've already typed.\n\nGoal: compute probability of a sentence/sequence of words\n\nused in texting, machine translation, spelling correction, speech recognition.\n\nExample: P(\"The underdog Philadelphia Eagles won\") = P(the) * P(underdog | the) * P(philadelphia | the, underdog) ...\n \nWant to ESTIMATE these probabilities using Markov Assumption: Only depends on previous k words, not the whole context.\n \n \n\n## Module 10 Definitions\n* **Observd variables (evidence)** - agent knows this about world\n* **Unobserved** - agent wants to reason about this\n* **Model** - agent knows something about how the known variables relate to unknowns.\n* **Random var** - some event that we are uncertain about\n* **Probabilistic model** - JD over a set of random vars, ideally many vars are independent of each other\n* **Event** - a set E of outcomes\n* **Marginalization** - combine collapsed rows by adding\n* **Unigram** - no history\n* **Bigram** - one word history\n* **Trigram** - two word history\n* **4-gram** - 3 word history\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",
        "Chapter discusses how to represent conditional independence relationships from the Bayesian network\n",
        "data structure. A graph where each node is annotated with probability information: \n",
        "\n",
        "1. Each node is a random var which is discrete or continuous\n",
        "\n",
        "2. Directed edges X->Y means X is parent of Y. Graph has no directed cycle so is a DAG.\n",
        "\n",
        "3. Each node Xi has probabilty info that has effect of parents on node.\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "Semantics defines how sytnax corresponds to a joint distribution over the vars in network. Is\n",
        "a complete and non reundnant representaiton of the domain. Is Locally Structured (Sparse) system.\n",
        "\n",
        "Sparse: subcomponent interacts directly only with a bounded number of othe rcomponents. Results\n",
        "in linear growth in complexity.\n",
        "\n",
        "D-Separation: On cheat sheet; Goal: Is a set of nodes X conditionally independent of another set Y \n",
        "given a third set Z? \n",
        "\n",
        "Context-specific independence: CSI: conditional Distribution has this if a variable is conditionally\n",
        "independent of some of its parents given certain values of others. \n",
        "\n",
        "Noisy relationships: relationships that are uncertain. NoisyOR. \n",
        "\n",
        "Hybrid Bayesian network: contians both discrete and continuous variables: needs conditional distribution\n",
        "for a continous variable given continnuous parents. When discrete parents with continous\n",
        "children, network makes conditional Gaussian. \n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\" \n",
        "Goal of inference system: find conditional probability distribution for set of query varables. \n",
        "Mentions inference by enumeration.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "**Review of Independence**:\n",
        "Conditional independence is a porperty of a distribution\n",
        "\n",
        "Unconditional(aboslute) independence is rare and not helpful. Conditional independence is \n",
        "robust and informative.  \n",
        "\n",
        "**Bayes Nets Properties**: Bayes nets contians independence assumptions. We model what we think\n",
        "the relationships look like. \n",
        "\n",
        "Algorithm on how to find the additional conditional independence assumptions on the graph: \n",
        "D-Separation Algorithm. (D=descendants)\n",
        "\n",
        "[1.Causal Chains]: x->y->z x is not guaranteed to be indepent of Z, but we can show that x is \n",
        "indepdenent of Z given Y.   \n",
        "\n",
        "[2.Common Cause]: X is not guaranteed to be independent of Z!\n",
        "\n",
        "Ex) X:Piazza busy and Z:OH is full are both caused by Y:project being due, but\n",
        "X and Z are not independent of each other.\n",
        "\n",
        "But X is guaranteed to be conditionally independent of Z given Y. \n",
        "\n",
        "[3.Common Effect]: Two causes of one effect: X:Rain, Y:Ballgame, Z:Traffic. X and Y ARE INDEPENDENT.\n",
        "\n",
        "But X and Z are NOT independent given Y. Seeing traffic puts the rain and ballgame in competition as explanation.\n",
        "\n",
        "\n",
        "**Reachability and Path**: Given BN, are two variables independent given some evidence? \n",
        "\n",
        "-Yes if X and Y are \"d-separated\" by Z\n",
        "-Consider all undirected paths from X to Y\n",
        "-No active paths = independence\n",
        "A path is active if each triple is active, but active is not the same as observed. \n",
        "\n",
        "\n",
        "**D-Separation Algorithm**:\n",
        "\n",
        "Question: Is Xi and Xj conditionally independent given set of observed vars {xk1, ...xkn)?\n",
        "\n",
        "If all paths are inactive, then independence is guaranteed. \n",
        "\n",
        "If some path is active, then independence is NOT guaranteed. \n",
        "\n",
        "**Inference:** calculating some useful quantity from a joint probability distribution given that we saw something\n",
        "Inference using Bayes Nets:\n",
        "\n",
        "Inference by enumeration is super slow because you join up the whole distribution before you sum the\n",
        "hidden variables. \n",
        " \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayes' Net\" : \"Probabilistic model where nodes=variables in probability model, arcs represent how events are related to each other\",    \n",
        "\"Conditionally independent\": \"Given z happened, x and y are independent x\\perp y | z\",\n",
        "\"activePath\":\"Path where all triples are active\",\n",
        "}\n"
      ],
      "execution_count": 141,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8ecd2de7-76f7-4ed9-badc-fbb0a9b09626"
      },
      "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": 118,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \n**Review of Independence**:\nConditional independence is a porperty of a distribution\n\nUnconditional(aboslute) independence is rare and not helpful. Conditional independence is \nrobust and informative.  \n\n**Bayes Nets Properties**: Bayes nets contians independence assumptions. We model what we think\nthe relationships look like. \n\nAlgorithm on how to find the additional conditional independence assumptions on the graph: \nD-Separation Algorithm. (D=descendants)\n\n[1.Causal Chains]: x->y->z x is not guaranteed to be indepent of Z, but we can show that x is \nindepdenent of Z given Y.   \n\n[2.Common Cause]: X is not guaranteed to be independent of Z!\n\nEx) X:Piazza busy and Z:OH is full are both caused by Y:project being due, but\nX and Z are not independent of each other.\n\nBut X is guaranteed to be conditionally independent of Z given Y. \n\n[3.Common Effect]: Two causes of one effect: X:Rain, Y:Ballgame, Z:Traffic. X and Y ARE INDEPENDENT.\n\nBut X and Z are NOT independent given Y. Seeing traffic puts the rain and ballgame in competition as explanation.\n\n\n**Reachability and Path**: Given BN, are two variables independent given some evidence? \n\n-Yes if X and Y are \"d-separated\" by Z\n-Consider all undirected paths from X to Y\n-No active paths = independence\nA path is active if each triple is active, but active is not the same as observed. \n\n\n**D-Separation Algorithm**:\n\nQuestion: Is Xi and Xj conditionally independent given set of observed vars {xk1, ...xkn)?\n\nIf all paths are inactive, then independence is guaranteed. \n\nIf some path is active, then independence is NOT guaranteed. \n\n**Inference:** calculating some useful quantity from a joint probability distribution given that we saw something\nInference using Bayes Nets:\n\nInference by enumeration is super slow because you join up the whole distribution before you sum the\nhidden variables. \n \n \n\n## Module 11 Definitions\n* **Bayes' net** - Probabilistic model where nodes=variables in probability model, arcs represent how events are related to each other\n* **Conditionally independent** - Given z happened, x and y are independent x\\perp y | z\n* **Activepath** - Path where all triples are active\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 = \"\"\" \n",
        "\n",
        "Introduces supervised vs unsupervised learning: agent observes innput output pairs \n",
        "and learns a function that maps from input to output. in unsupervised, agent learns patterns\n",
        "in the input without explicit feedback or featuring. \n",
        "\n",
        "bias vs. variance: low bias hypothesis is more complex. low variance hypothesis generalizes better.\n",
        "\n",
        "\"\"\"\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",
        "MACHINE LEARNING: \n",
        "**ClassificationTasks**\n",
        "**Naive Bayes**: Assumes all featuers are independent of each other. Only dependent on label.\n",
        "\n",
        "-Each input maps to a feature vector with values to the feature.\n",
        "\n",
        "P(Y|feature vec) proportional to P(y)*Mult_i(Fi|Y)\n",
        "\n",
        "Total number of params linear in number of features.\n",
        "\n",
        "Goal: copute posterior (conditional) distribution over label variable Y\n",
        "\n",
        "-Step 1: get joint probability of label and evidence to each label\n",
        "\n",
        "-Step 2: sum each term to get probability of evidence\n",
        "\n",
        "-step3: normalize by dividing step1/step2\n",
        "\n",
        "Tools Needed:\n",
        "-Inference method\n",
        "\n",
        "-Estimates of local conditional probability tables. \n",
        "\n",
        "**Basic ML Concepts**\n",
        "\n",
        "Assigning certain parameters with a value of 0 (if unseen for instance) could lead to\n",
        "overfitting and inf for every feature.\n",
        "\n",
        "Parameter Estimation: Estimate the distribution of a random variable based on training data.\n",
        "Ex) Empiracle rate of seeing an output, Maximum likelihood of the data. \n",
        "\n",
        "Avoid Unseen Events: \n",
        "Laplace Smoothing: pretend you saw every outcome once more than you actually did\n",
        " \n",
        " **Perceptrons**:\n",
        " \n",
        " Properties: Separability, Convergence, Mistake bound; Weights will trash if data is not separable. You\n",
        " can average weights over time (averaged perceptron). Sometimes solutions is not the best separation. You\n",
        " may also overtrain your data. \n",
        "\n",
        " To Fix: adjust the weight update to mitigate effects. \n",
        "\n",
        "**Support Vector Machines:** maximizes margin from boundary to points. \n",
        "**Non Linear separators**: Add dimensionality to the data to bring it to a dimensison where it's\n",
        "linearly separable.\n",
        "\n",
        "Compare Classifiers:\n",
        "Naive bayes:\n",
        "\n",
        "- builds model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data\n",
        "\n",
        "Perceptrons/MIRA\n",
        "\n",
        "- makes less assumptions about data, mistake driven learning, multiple passes through data, often more accurate.\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "}\n",
        "\n"
      ],
      "execution_count": 124,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "3656552c-9064-4dc3-ca1f-5514874b66bb"
      },
      "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": 123,
      "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\nMACHINE LEARNING: \n**ClassificationTasks**\n**Naive Bayes**: Assumes all featuers are independent of each other. Only dependent on label.\n\n-Each input maps to a feature vector with values to the feature.\n\nP(Y|feature vec) proportional to P(y)*Mult_i(Fi|Y)\n\nTotal number of params linear in number of features.\n\nGoal: copute posterior (conditional) distribution over label variable Y\n\n-Step 1: get joint probability of label and evidence to each label\n\n-Step 2: sum each term to get probability of evidence\n\n-step3: normalize by dividing step1/step2\n\nTools Needed:\n-Inference method\n\n-Estimates of local conditional probability tables. \n\n**Basic ML Concepts**\n\nAssigning certain parameters with a value of 0 (if unseen for instance) could lead to\noverfitting and inf for every feature.\n\nParameter Estimation: Estimate the distribution of a random variable based on training data.\nEx) Empiracle rate of seeing an output, Maximum likelihood of the data. \n\nAvoid Unseen Events: \nLaplace Smoothing: pretend you saw every outcome once more than you actually did\n \n **Perceptrons**:\n \n Properties: Separability, Convergence, Mistake bound; Weights will trash if data is not separable. You\n can average weights over time (averaged perceptron). Sometimes solutions is not the best separation. You\n may also overtrain your data. \n\n To Fix: adjust the weight update to mitigate effects. \n\n**Support Vector Machines: ** maximizes margin from boundary to points. \n**Non Linear separators**: Add dimensionality to the data to bring it to a dimensison where it's\nlinearly separable.\n\nCompare Classifiers:\nNaive bayes:\n\n- builds model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data\n\nPerceptrons/MIRA\n\n- makes less assumptions about data, mistake driven learning, multiple passes through data, often more accurate.\n \n \n\n## Module 12 Definitions\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 = \"\"\" \n",
        "Monte Carlo Tree Search: modern programs abandoned alpha beta search for this. Value of a state\n",
        "is average utility over a number of simulations of complete games starting from this state. \n",
        "\n",
        " \"\"\"\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",
        "**Logistic Regression**\n",
        "\n",
        "Perceptron vs. Logistic regression: Perceptron is neural item that uses a step function \n",
        "as a transfer function, but logistic regression smooths it with a logistic function.\n",
        "\n",
        "Components of a classifier\n",
        "1. Feature representation vector\n",
        "\n",
        "2. classification function that outputs estimated class yhat via p(y|x)\n",
        "\n",
        "3. objective function (loss function) for leanring (involving minimizing error on training examples)\n",
        "\n",
        "4. algorithm for optimizing objective function (to update each parameter in a good way)\n",
        "\n",
        "Learning: 1) objecive/loss function that tells us how far off we are from desired output. Use\n",
        "cross-entropy loss. 2) algorithm for optimizing objective function. Use stochastic gradient descend.\n",
        "\n",
        "\n",
        "**Stochastic Gradient Descent**\n",
        "In logistic regression, loss function is convex so no matter where you start, you are guaranteed to\n",
        "find the minimum. \n",
        "\n",
        "Mini-batch Training: SGD chooses a random example at a time and upates its weights on the example. Batch\n",
        "training is an alternative that computes gradient over entire dataset. Takes a logn time to compute but is\n",
        "more accurate. Mini-batch is compromise. \n",
        "\n",
        "Regularization: Overfitting results in poor performance. If feature only occurrs in 1 class then it will get high\n",
        "weight, very accurate for that feature. Lasso Regression is L1 reg. Ridge is L2. Regularization penalizes large weights.\n",
        "\n",
        "**Neural Networks**\n",
        "Neural networks are made of individual perceptrons, construed into many layers. If weights are set correctly and non linear activation function\n",
        "is used, then we can estimate a wide range of functions. \n",
        "\n",
        "Begins with input->perceptron->activationFunction->output\n",
        "\n",
        "Activation Functions: \n",
        "\n",
        "sigmoid - squashes output to meaningful range\n",
        "\n",
        "tanh\n",
        "\n",
        "rectified linear unit ReLU\n",
        "\n",
        "Feed-Forward NN: all layers are completed connected to the layer above.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"deep learning\" : \"multi-neural net neural net\",    \n",
        "\"computation graph\": \"graph that reprsents the process of computing a mathematical expression\"\n",
        "}\n"
      ],
      "execution_count": 132,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "20734b3f-57b4-49b4-cf4b-e066bede4f78"
      },
      "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": 133,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n**Logistic Regression**\n\nPerceptron vs. Logistic regression: Perceptron is neural item that uses a step function \nas a transfer function, but logistic regression smooths it with a logistic function.\n\nComponents of a classifier\n1. Feature representation vector\n\n2. classification function that outputs estimated class yhat via p(y|x)\n\n3. objective function (loss function) for leanring (involving minimizing error on training examples)\n\n4. algorithm for optimizing objective function (to update each parameter in a good way)\n\nLearning: 1) objecive/loss function that tells us how far off we are from desired output. Use\ncross-entropy loss. 2) algorithm for optimizing objective function. Use stochastic gradient descend.\n\n\n**Stochastic Gradient Descent**\nIn logistic regression, loss function is convex so no matter where you start, you are guaranteed to\nfind the minimum. \n\nMini-batch Training: SGD chooses a random example at a time and upates its weights on the example. Batch\ntraining is an alternative that computes gradient over entire dataset. Takes a logn time to compute but is\nmore accurate. Mini-batch is compromise. \n\nRegularization: Overfitting results in poor performance. If feature only occurrs in 1 class then it will get high\nweight, very accurate for that feature. Lasso Regression is L1 reg. Ridge is L2. Regularization penalizes large weights.\n\n**Neural Networks**\nNeural networks are made of individual perceptrons, construed into many layers. If weights are set correctly and non linear activation function\nis used, then we can estimate a wide range of functions. \n\nBegins with input->perceptron->activationFunction->output\n\nActivation Functions: \n\nsigmoid - squashes output to meaningful range\n\ntanh\n\nrectified linear unit ReLU\n\nFeed-Forward NN: all layers are completed connected to the layer above.\n\n\n## Module 13 Definitions\n* **Deep learning** - multi-neural net neural net\n* **Computation graph** - graph that reprsents the process of computing a mathematical expression\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",
        "\n",
        "**Neural Language Models**\n",
        "\n",
        "Issue with original ngram model: Sparsity. If unobserved words found, then count would be 0 \n",
        "and the overall probability for the sentence will also be 0 since we multiply. We used Laplacian\n",
        "smoothing to fix this issue. \n",
        "\n",
        "Neural Language: several advantages over n-grams:\n",
        "\n",
        "1. Don't need smoothing\n",
        "\n",
        "2. Handle much longer histories\n",
        "\n",
        "3. Generate over context of similar words\n",
        "\n",
        "4. More accurate.\n",
        "\n",
        "5. Slower to train.\n",
        "\n",
        "Associate each word in vocabular with a vector representation (creating a notion of similarity\n",
        "between words). Express joint probability function of a word sequence in terms of the word vectors for the\n",
        "words in that sequence. \n",
        "\n",
        "Simulatneously learn the word vectors and the parameters of the function. \n",
        "\n",
        "Probability function is product of conditonal probabilities of the next word given the previous word \n",
        "(using a multi-layer feed forward neural network).\n",
        "\n",
        "Input: k-gram of words\n",
        "\n",
        "Output: probability distribution over the next word.\n",
        "\n",
        "input x is fed into a neural network with 1 or more hidden layers. \n",
        "\n",
        "**Lexical Semantic Models**\n",
        "\n",
        "How to represent the meaning of a word\n",
        "****\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 945
        },
        "outputId": "5d0fa56c-fef4-454e-c004-debdc9ef103e"
      },
      "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": 17,
      "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 Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "0c8a0971-e845-4be0-e097-3a736216806b"
      },
      "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": 131,
      "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 Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nMDP is offline process\n\n**MDPFormulation1**: MDP is decision process where ENVIRONMENT FULL VISIBLE, TRANSITION STOCHASTIC, \nwith REWARD FUNCTION and DISCOUNT.\n\nInfinite Games vs. Finite Games: Choice of actions depends on how long left \nin the game. Infinite is hard.\n\nSometimes expected utility is same, but when you receive it differs (ex. incremental\ndiamonds vs diamonds at end)->Have reward function dictate this.\n\n**MDPFormulation2**: discount dictates other factors. Helps converge.\n\nIf game is infinite, use to resolve non convergence.\n\nMDP search tree is expectimax\n\n**ValueIteration**: Given a vector of Vk(s), do expectimax on each state. Repeat \nuntil convergence. Each iter O(s^2A) time.\n\nWent over example of value iteration.\n\nConvergence: HOw to know if converges? \n\nCase1: If has max depth\n\nCase2: If discount<1; for any state, the difference beween its value Vk and Vk+1\nis a depth 1 expectimax. The last layer will bound maximum amount (with the biggest\nchange. At best it's Rmax, at worst it's Rmin. Vk and Vk+1 are at most y^k|R| diff.)\n\n**PolicyIteration**: Directly estimate best policy by using argmax. Turn\nBellman Equation into updates like value iteration. Each iter is O(S^2). \n\n1.Calculate utility for some fixed policy (not optimal utilities) until convergence.\n\n2.Improve policy using one-step lookahead using values from 1. Repeat until convergence.\n\nGet action from normalValues: policyExtraction->perform neighbor minimax. \n\nGet action from qValues: trivial bc qValue implies best action.\n\n**policyIterAlgorithm**: valueIteration is slow, max at each state doesn't change much\neven though value changes. Policy converges faster than values.\n\n**whichOneToUse**: \n\ncompute optimal values: value iteration\n\ncompute values for some policy: policy eval\n\nturn values into policy: policy extract\n\n**Maximum Expected Utility**: \n\nGives more optimistic policy. Need to have utility function that is insensitive to monotonic transforms.\n\nFor average case expectimax, need meaningful magnitudes. \n\nRationality: \nWhat is continuity: There must exist some threshold p for which you're indifferent to B.\n\nSubstitutability: If A~B, then for two lotteries where A and B are the same probability,\nwith the opposite being C, then they're both the same lottery.\n\n \n\n## Module 8 Definitions\n* **Stationary preferences** - If I prefer some reward sequence over another, preference will not be changed by adding something\n* **Utility** - function of outcome to value that reflects an agent's preferences\n* **Expected utility** - sum of all outcome value * probability it will occur\n* **Expectimax:** - expected utility under optimal action\n* **Meu principle** - Rational agent will always make choices that give MEU\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n \n**Intro1**: Learn probability distribution instead of having it given.\n\nOnline Planning: Do not have any probabilities, must learn through playing. \n\n**Intro2**: \n\nReinforcement learning gives feedback in form of rewards. \n\nAgent's utility defined by reward function.\n\nLearn to maximize expected rewards\n\nObserve a sample to learn.\n\n-States\n\n-actions per state\n\n-Transition function (not given)\n\n-Reward function (not given)\n\nObjective: still looking for best policy\n\n**Passive Reinforcement**: \n\nModel-free-learning: when results deviate, adjust values up or down. Track only\nthe value of each state and don't keep track of transition or reward function.\n\nPassive Reinforcement: someone else picks policy for us. We evalute policy and improve it\nwithout knowing T or R.\n\nDirect Evaluation: goal compute values for each state under policy. Average together observed\nsample values. sum discounted rewards of each state you visit then avg them.\n\nProblem: Wastes information about state connections; Each state learned separately; \nLong time to learn. \n\nPolicyIteration without T and R: Sample basd policy evaluation. Sample n times and take avg.\n\n**Temporal difference learning**: Update estimates of the value of state every single time\nwe experience a transition into it. Any outocmes s' will contribute more often. \n\n1. Take sample of V(s) with alpha learn rate, then update V(s) based on sample. \n\n2. learn rate alpha interpolates between V^pi(s) and sample val. The more recent\nsamples become more important over time. \n\nProblems: Cannot turn values into a new policy.\n\nSolution: learn Q-values instead\n\n**QLearning Active Reinforcement**: \n\nQValueIteration: Same as value iteration but with Q. Start Q(s,a)=0\n\nQ(s,a): get sample (s,a,s',r) (non deterministically end in s' and receive r for ending\nin s' having done (s,a)), will keep a moving average so that every sample we receive\nhelps us update. \n\nConsider Q(s,a), evaluate good or bad\n\nConsider new sample estimate\n\nIncorporate new estimate into running average.\n\nQLearning converges ot optimal policy even if you're behaving suboptimally.\n\nCaveats: must expore enough, eventually make learning rate small enough but not too\nquickly. \n\n**Exploration vs Exploitation**: \nExploration: To do this, can do random actions, can do random actions with small probability. \nIssue is that we may pick things repeatedly. \n\nSolution: lower epsilon over time or write exploration function\n\nExploration Function: Takes value estimate u and visit count n, then returns optimistic\nutility (onSheet) + some exploration penalty bonus. \n\nRegret: MInimizing it = optimally learning to be optimal \n\n**Approximate QLearning**: Too many states to visit them all during training/hold table of qstate\nvalues in memory. \n\nLinear Value Functions: Use feature representation, can write a q function for any state using\nsome weights.  Disadvantage: states may share features but actually be very different in value.\n\nUpdateQLearning(s,a): \n1. given transition(s,a,r,s')\n2. find the difference between expectation and actual result\n3. take difference, multiply by learn rate and fi(s,a) (whether feature was active), then add to each weight rather than entire Q state\n \n \n\n## Module 9 Definitions\n* **Exploration** - try unknown actions to get information\n* **Exploitation** - eventually you ahve to use what you know\n* **Regret** - measure of total mistake cost rewards. Minimize regret = learn optimality quickly\n* **Sampling** - because of chance, you gotta try things repeatedly\n* **Difficulty** - learning is harder than solving MDP\n* **Model-based** - \n* **Model-free learning** - take action, compare results to expectation, when deviating, adjust values\n* **Passive reinforcement** - someone else picks policy and not us\n* **Value iteration** - find successive depth limited value of vk+1(s) given vk\n* **Epsilon-greedy policy** - if rand num gen is < epsilon, act randomly\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n 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**Review of Probabilities:**\nIn probability theory, probabilities (possible worlds) are sample space, and are\nmutually exclusive and exhaustive. \n\nA specified probability model associates a probability P(w) with each possible world w.\n\nAxioms of probability: \n1. Any P(w) between 0 and 1\n2. Sum of everything = 1\n\n**Distributions**\n\nUnobserved random vars have distributions->a able of probabilities of values. \n\nprobability is a single number for a single variable. \n\nJoint Distribution: JD over a set of vars specifies a real number for each outcome. \nSay whether assingments (outcomes) are likely. \n\nMarginal Distribution: a subtable which eliminates vars.\n\nConditional Probability: A simple relation between joint and conditional probabilities. \n\nConditional Distribution: PD over some variables given fixed values of others. \n \n **Probabilistic inference&Rules**: \n compute a desired probability from other known probabilities: ex conditional from joint.\n\n Probabilities will change with new evidence. \n\n 1. Inference by Enumeration: split random vars into 3 sets: Evidence vars, Query vars (things we wnat to know),\n Hidden vars (vars that occur in joint probability distribution but we don't have info on it)\n\nStep 1-select entries consistent w/ evidence\n\nStep 2-Sum out H to get joint of query and evidence\n\nStep 3-Normalize multiply everything with 1/z \n\n**Bayes' Rule**: How to derive P(x|y) given P(y|x)\n\n**Probabilistic Language Models**: Most likely next word given what you've already typed.\n\nGoal: compute probability of a sentence/sequence of words\n\nused in texting, machine translation, spelling correction, speech recognition.\n\nExample: P(\"The underdog Philadelphia Eagles won\") = P(the) * P(underdog | the) * P(philadelphia | the, underdog) ...\n \nWant to ESTIMATE these probabilities using Markov Assumption: Only depends on previous k words, not the whole context.\n \n \n\n## Module 10 Definitions\n* **Observd variables (evidence)** - agent knows this about world\n* **Unobserved** - agent wants to reason about this\n* **Model** - agent knows something about how the known variables relate to unknowns.\n* **Random var** - some event that we are uncertain about\n* **Probabilistic model** - JD over a set of random vars, ideally many vars are independent of each other\n* **Event** - a set E of outcomes\n* **Marginalization** - combine collapsed rows by adding\n* **Unigram** - no history\n* **Bigram** - one word history\n* **Trigram** - two word history\n* **4-gram** - 3 word history\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \n**Review of Independence**:\nConditional independence is a porperty of a distribution\n\nUnconditional(aboslute) independence is rare and not helpful. Conditional independence is \nrobust and informative.  \n\n**Bayes Nets Properties**: Bayes nets contians independence assumptions. We model what we think\nthe relationships look like. \n\nAlgorithm on how to find the additional conditional independence assumptions on the graph: \nD-Separation Algorithm. (D=descendants)\n\n[1.Causal Chains]: x->y->z x is not guaranteed to be indepent of Z, but we can show that x is \nindepdenent of Z given Y.   \n\n[2.Common Cause]: X is not guaranteed to be independent of Z!\n\nEx) X:Piazza busy and Z:OH is full are both caused by Y:project being due, but\nX and Z are not independent of each other.\n\nBut X is guaranteed to be conditionally independent of Z given Y. \n\n[3.Common Effect]: Two causes of one effect: X:Rain, Y:Ballgame, Z:Traffic. X and Y ARE INDEPENDENT.\n\nBut X and Z are NOT independent given Y. Seeing traffic puts the rain and ballgame in competition as explanation.\n\n\n**Reachability and Path**: Given BN, are two variables independent given some evidence? \n\n-Yes if X and Y are \"d-separated\" by Z\n-Consider all undirected paths from X to Y\n-No active paths = independence\nA path is active if each triple is active, but active is not the same as observed. \n\n\n**D-Separation Algorithm**:\n\nQuestion: Is Xi and Xj conditionally independent given set of observed vars {xk1, ...xkn)?\n\nIf all paths are inactive, then independence is guaranteed. \n\nIf some path is active, then independence is NOT guaranteed. \n\n**Inference:** calculating some useful quantity from a joint probability distribution given that we saw something\nInference using Bayes Nets:\n\nInference by enumeration is super slow because you join up the whole distribution before you sum the\nhidden variables. \n \n \n\n## Module 11 Definitions\n* **Bayes' net** - Probabilistic model where nodes=variables in probability model, arcs represent how events are related to each other\n* **Conditionally independent** - Given z happened, x and y are independent x\\perp y | z\n* **Activepath** - Path where all triples are active\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\nMACHINE LEARNING: \n**ClassificationTasks**\n**Naive Bayes**: Assumes all featuers are independent of each other. Only dependent on label.\n\n-Each input maps to a feature vector with values to the feature.\n\nP(Y|feature vec) proportional to P(y)*Mult_i(Fi|Y)\n\nTotal number of params linear in number of features.\n\nGoal: copute posterior (conditional) distribution over label variable Y\n\n-Step 1: get joint probability of label and evidence to each label\n\n-Step 2: sum each term to get probability of evidence\n\n-step3: normalize by dividing step1/step2\n\nTools Needed:\n-Inference method\n\n-Estimates of local conditional probability tables. \n\n**Basic ML Concepts**\n\nAssigning certain parameters with a value of 0 (if unseen for instance) could lead to\noverfitting and inf for every feature.\n\nParameter Estimation: Estimate the distribution of a random variable based on training data.\nEx) Empiracle rate of seeing an output, Maximum likelihood of the data. \n\nAvoid Unseen Events: \nLaplace Smoothing: pretend you saw every outcome once more than you actually did\n \n **Perceptrons**:\n \n Properties: Separability, Convergence, Mistake bound; Weights will trash if data is not separable. You\n can average weights over time (averaged perceptron). Sometimes solutions is not the best separation. You\n may also overtrain your data. \n\n To Fix: adjust the weight update to mitigate effects. \n\n**Support Vector Machines: ** maximizes margin from boundary to points. \n**Non Linear separators**: Add dimensionality to the data to bring it to a dimensison where it's\nlinearly separable.\n\nCompare Classifiers:\nNaive bayes:\n\n- builds model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data\n\nPerceptrons/MIRA\n\n- makes less assumptions about data, mistake driven learning, multiple passes through data, often more accurate.\n \n \n\n## Module 12 Definitions\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n**Logistic Regression**\n\n**Stochastic Gradient Descend**\n\n**Neural Networks**\nNeural networks are made of individual perceptrons, construed into many layers. If weights are set correctly and non linear activation function\nis used, then we can estimate a wide range of functions. \n\nBegins with input->perceptron->activationFunction->output\n\nActivation Functions: \n\nsigmoid - squashes output to meaningful range\n\ntanh\n\nrectified linear unit ReLU\n\nForward Propagation: \n\n\n## Module 13 Definitions\n* **Deep learning** - multi-neural net neural net\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 Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}