{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Daniel_Schwartz_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/",
          "height": 0
        },
        "outputId": "1b93064a-896d-432e-f3eb-20f34349f5a5"
      },
      "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": 84,
      "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/",
          "height": 0
        },
        "outputId": "c06a2105-e9a8-49db-f13c-006775628f58"
      },
      "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": 85,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 86,
      "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",
        "prob_dist = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "expect_util = r\"\"\" $a^* = \\textnormal{argmax}_a EU(a)$ \"\"\"\n",
        "expect_policy = r\"\"\" $U^\\pi(s) = E(\\sum_{t=0}^{\\infty} \\gamma^t R(S_t, \\pi(S_t), S_{t+1}))$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"Given uncertainty, decision theory involves choose the best action based on the desirability of their\n",
        "possible outcomes.  The principle of MEU gives a way to design intelligent behaviour given uncertainty.  Simply maximize utility,\n",
        "over all possible actions.  Estimating the probability distribution requires perception, learning, knowledge, and inference and it may\n",
        "require more planning to find what states follow from a given state.  It is not a final solution to this AI problem, but it provides a good\n",
        "framework that is somewhat general.\"\"\"  + prob_dist\n",
        "chapter16_2 =  \"\"\"Given two outcomes A and B an agent may prefer one over the other or be indifferent.\n",
        "The outcomes of each action can be though of as a lottery and each action is like a ticket.  Each outcome may lead to another\n",
        "lottery or it can lead to some terminal or atomic state.  A reasonable preference must maintain: orderability, transitivity, continuability,\n",
        "subsitutability, monotonicity, and decomposability.  A utility funciton must exist if an agent has preferences that obey these laws.\n",
        "The utility of a lottery is exactly the expected utility where the utility of an outcome is weighted by its probability.  \n",
        "In a deterministic environment, preference need only be ranked on states which is called a valur or ordinal utility function.\n",
        "The existence of a utility function does not garuntee that an agent acts to maximize that function given its preferences.\"\"\"\n",
        "chapter16_3 =  \"\"\"The expected utility according to a probability model will reflect the expectation given that model, but this \n",
        "is often an oversimplification because the true expected utility requires more imformation or is computationally difficult.\"\"\" + expect_util\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"In a sequential environment, the utility function will depend on an environtment history or a sequence of states and actions.\n",
        "A sequential decision problem given a fully observable, stochastic environment is solvable by a Markov Decision Process.  Methods for\n",
        "solving MDPs typically employ dynamic programming strategies.  The solution for such a problem takes the form of a policy the determines what\n",
        "the agent should do given any state.  The goal in an MDP is to determine the optimal policy.  A technique often applied to rewards is a \n",
        "discount factor applied to future rewards.  This is so that the agent is inclined to prefer more immediate rewards, but as the discount\n",
        "factor approaches 1, the agent will wait for long term rewards.  Discounted rewards also avoid infinite rewards in a space with an \n",
        "infinite horizon.  The Bellman equation shows the utility of a state given the expected utility of the subsequent states.  Using the \n",
        "Bellman equation and the action-utility or Q-function, we can extract the optimal policy.  We can replace the utility function with the\n",
        "Q-function to extract the policy.  A simple way to represent the transition and reward functions is with 3 dimensional table of size $|S|^2|A|$.  \n",
        "This is fine for small problems but for large problems the tables quickly become too big.\"\"\" + expect_policy\n",
        "chapter17_2 =  \"\"\"Four possible algorithms for solving MDPs: value iteration, policy iteration, linear programming, and Monte Carlo planning. \n",
        "In value iteration, a bellman update is applied until they converge.  Value iteration will eventually converge to a unique solution.\n",
        "In policy iteration, we can simply evalute the policy and then update the policy if needed until the policy no longer changes.  This\n",
        "can be done by using a simplified Bellman equation eliminating the max.  By removing the max operation, these become a system of linear\n",
        "equations that are solvable in $O(n^3)$ time.  On larger state spaces, modified policy iteration can be performed.  Both value iteration and\n",
        "policy iteration are offline algorithms, the monte carlo approach is an example of an online solution.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"$U(s)$ a single value to used to express how desirable a state is\",\n",
        "\"expected utility\" : \"$EU(a)$ is sum of the utility of each possible outcome weighted by its probability (average utility value)\",\n",
        "\"maximum expected utility MEU\": \"a rational agent should always choose an action to maximize expected utility\",\n",
        "\"preference eliciation\" : \"A method of presenting choices to a human and building a utility function based on their observed preferences\",\n",
        "\"micromort\" : \"one in a million chance of death\",\n",
        "\"monotonic preference\" : \"a preference to more rather than less if all else is equal\",\n",
        "\"reward\" : \"reward function $R(s,a,s')$\",\n",
        "\"markov decision process\" : \"a set of states, actions, a transition model  $P(s'|s,a)$, and a reward function\",\n",
        "\"policy\" : \"$\\pi(s)$ returns a recommended action by the policy for some state $s$.\",\n",
        "\"optimal policy\" : \"$\\pi^*$ denotes the policy that yields the highest expected utility\",\n",
        "\"finite horizon\" : \"there is a fixed time/steps $N$ and after it has elapsed, the game is over\",\n",
        "\"infinite horizon\" : \"there is no deadline, but sequences can still end by entering a terminal state\",\n",
        "\"discount factor\" : \"$\\gamma$ value between 0-1 applied toward future rewards to prefer current rewards\",\n",
        "\"proper policy\" : \"a policy guaranteed to reach a terminal state\",\n",
        "\"Bellman equation\" : \"$U(s) = max_{a \\in A(s)} \\sum_{s'} P(s' | s, a)[R(s,a,s') + \\gamma U(s')]$\",\n",
        "\"Q-function\" : \"$U(s) = max_a Q(s,a)$\",\n",
        "\"value iteration\" : \"solve bellman equations by applying some arbitrary inital utility and iteratively update until equillibrium is reached\",\n",
        "\"policy iteration\" : \"find an optimal policy by alternating policy evaluation and policy improvement\",\n",
        "\"linear programming\" : \"General approach for solving constrained optimization problems\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 87,
      "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": 0
        },
        "outputId": "37ef8f6a-2683-48e9-9c33-693c47f9e0f8"
      },
      "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": 88,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nGiven uncertainty, decision theory involves choose the best action based on the desirability of their\npossible outcomes.  The principle of MEU gives a way to design intelligent behaviour given uncertainty.  Simply maximize utility,\nover all possible actions.  Estimating the probability distribution requires perception, learning, knowledge, and inference and it may\nrequire more planning to find what states follow from a given state.  It is not a final solution to this AI problem, but it provides a good\nframework that is somewhat general. $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nGiven two outcomes A and B an agent may prefer one over the other or be indifferent.\nThe outcomes of each action can be though of as a lottery and each action is like a ticket.  Each outcome may lead to another\nlottery or it can lead to some terminal or atomic state.  A reasonable preference must maintain: orderability, transitivity, continuability,\nsubsitutability, monotonicity, and decomposability.  A utility funciton must exist if an agent has preferences that obey these laws.\nThe utility of a lottery is exactly the expected utility where the utility of an outcome is weighted by its probability.  \nIn a deterministic environment, preference need only be ranked on states which is called a valur or ordinal utility function.\nThe existence of a utility function does not garuntee that an agent acts to maximize that function given its preferences.\n\n## AIMA Chapter 16.3 Utility Functions\nThe expected utility according to a probability model will reflect the expectation given that model, but this \nis often an oversimplification because the true expected utility requires more imformation or is computationally difficult. $a^* = \\textnormal{argmax}_a EU(a)$ \n\n## AIMA Chapter 17.1 Sequential Decision Problems\nIn a sequential environment, the utility function will depend on an environtment history or a sequence of states and actions.\nA sequential decision problem given a fully observable, stochastic environment is solvable by a Markov Decision Process.  Methods for\nsolving MDPs typically employ dynamic programming strategies.  The solution for such a problem takes the form of a policy the determines what\nthe agent should do given any state.  The goal in an MDP is to determine the optimal policy.  A technique often applied to rewards is a \ndiscount factor applied to future rewards.  This is so that the agent is inclined to prefer more immediate rewards, but as the discount\nfactor approaches 1, the agent will wait for long term rewards.  Discounted rewards also avoid infinite rewards in a space with an \ninfinite horizon.  The Bellman equation shows the utility of a state given the expected utility of the subsequent states.  Using the \nBellman equation and the action-utility or Q-function, we can extract the optimal policy.  We can replace the utility function with the\nQ-function to extract the policy.  A simple way to represent the transition and reward functions is with 3 dimensional table of size $|S|^2|A|$.  \nThis is fine for small problems but for large problems the tables quickly become too big. $U^\\pi(s) = E(\\sum_{t=0}^{\\infty} \\gamma^t R(S_t, \\pi(S_t), S_{t+1}))$ \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nFour possible algorithms for solving MDPs: value iteration, policy iteration, linear programming, and Monte Carlo planning. \nIn value iteration, a bellman update is applied until they converge.  Value iteration will eventually converge to a unique solution.\nIn policy iteration, we can simply evalute the policy and then update the policy if needed until the policy no longer changes.  This\ncan be done by using a simplified Bellman equation eliminating the max.  By removing the max operation, these become a system of linear\nequations that are solvable in $O(n^3)$ time.  On larger state spaces, modified policy iteration can be performed.  Both value iteration and\npolicy iteration are offline algorithms, the monte carlo approach is an example of an online solution.\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - $U(s)$ a single value to used to express how desirable a state is\n* **Expected utility** - $EU(a)$ is sum of the utility of each possible outcome weighted by its probability (average utility value)\n* **Maximum expected utility meu** - a rational agent should always choose an action to maximize expected utility\n* **Preference eliciation** - A method of presenting choices to a human and building a utility function based on their observed preferences\n* **Micromort** - one in a million chance of death\n* **Monotonic preference** - a preference to more rather than less if all else is equal\n* **Reward** - reward function $R(s,a,s')$\n* **Markov decision process** - a set of states, actions, a transition model  $P(s'|s,a)$, and a reward function\n* **Policy** - $\\pi(s)$ returns a recommended action by the policy for some state $s$.\n* **Optimal policy** - $\\pi^*$ denotes the policy that yields the highest expected utility\n* **Finite horizon** - there is a fixed time/steps $N$ and after it has elapsed, the game is over\n* **Infinite horizon** - there is no deadline, but sequences can still end by entering a terminal state\n* **Discount factor** - $\\gamma$ value between 0-1 applied toward future rewards to prefer current rewards\n* **Proper policy** - a policy guaranteed to reach a terminal state\n* **Bellman equation** - $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s' | s, a)[R(s,a,s') + \\gamma U(s')]$\n* **Q-function** - $U(s) = max_a Q(s,a)$\n* **Value iteration** - solve bellman equations by applying some arbitrary inital utility and iteratively update until equillibrium is reached\n* **Policy iteration** - find an optimal policy by alternating policy evaluation and policy improvement\n* **Linear programming** - General approach for solving constrained optimization problems\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": [
        "td_q_learn = r\"\"\"$Q(s, a) = Q(s, a) + \\alpha [R(s,a,s') + \\gamma max_a Q(s', a') - Q(s, a)  ]$\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"In the bandit problem we see the trade off between exploration and exploitation.  Explotiation will yield the best known \n",
        "result, but exploration could lead to better long-term rewards or loss.  A balance must be made between the two.  In a bandit problem,\n",
        "each arm can be modelled as an MDP with only one possible action (also known as a Markov reward process) and the overall problem as \n",
        "the cartesian product of the actions.  An important part of this formulation is that the arms are independent.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" In reinforcement learning, as with MDPs, the goal is to maximize the sum of expected rewards.  The difference being that the\n",
        "agent is interacting within the problem and cannot simply solve the MDP offline.  Rather than just applying rewards to a win/loss, it is often\n",
        "easier to apply intermediate rewards when an agent makes a decision that brings it closer to a win.  This approach works well in simulated environments.\n",
        "In model-based reinforcement learning, an agent will learn a transition model and may learn some utility function starting from its intial state.\n",
        "In contrast, model-free reinforcemenet learning does not learn any transition model, but rather the agent learns how to act directly.  This is done\n",
        "using action-utility learning like Q-learning where the agent learns a Q-function to determine its actions or through policy search as a reflex agent.\n",
        " \"\"\"\n",
        "chapter22_2 =  \"\"\" In passive reinforcement learning, we can start with a fixed policy to determine actions and we attempt to learn $U^{\\pi}(s)$ as the\n",
        "total discounted reward given policy $\\pi$ starting at some state $s$.  This is learned through a process similar to policy evaluation, but in this case\n",
        "we do not know the transition model. Then we can use the defined equation for $U^{\\pi}(s)$.  Direct utility estimation ignores the connections between states\n",
        "and thus it will take a long time to converge.  By taking an adaptive dynamic programmming approach, we can learn the transition model and observe the rewards.\n",
        "By applying modified policy iteration, we can use previous estimations and converge very quickly.  It is easy to learn the transition model in a fully \n",
        "observable environment, as you only need to record the state-action pairs and resulting states and maintain counts $N(s'|s,a)$.  Temporal difference learning \n",
        "updates utility estimates based on the learning rate $\\alpha$ and the difference in utility between sucessive states.  This method works by updating utility\n",
        "estimates until the ideal equillibrium is reached.\"\"\" \n",
        "chapter22_3 =  \"\"\" In contrast to passive reinforcement, an active learning agent will decide which actions to take instead of being given a fixed policy.\n",
        "To do this the agent will have to learn the transition model and outcome probabilities for each action as opposed to just the fixed policy.  Active agents\n",
        "require a balance between exploitation and exploration much like bandit problems.  An exploration function is employed to determine this trade off.\n",
        "Safe exploration should avoid entering absorbing states or states with large negative rewards.  In temporal difference q-learning we can use a transition-model\n",
        "free TD way to update Q-values.  Q-learning is off-policy learning as it can change policy if a better action is found given new estimates.\"\"\" + td_q_learn\n",
        "chapter22_4 =  \"\"\" We can generalize reinforcement learning to larger state spaces by taking a utility function as an approximatation using a weighted \n",
        "linear combination of features. \"\"\"\n",
        "chapter22_5 =  \"\"\" Policy search is another simple reinforcement learning technique wehre we keep tweaking the policy while its performance continues to \n",
        "improve and then stop. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "temp_diff = r\"\"\" $U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s, \\pi(s), s') + \\gamma U^{\\pi}(s') - U^{\\pi}(s')]$ \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"n-armed bandit\" : \"a slot machine with n-levers where each has a fixed unknown probability distribution of winning\",\n",
        "\"exploitiation\" : \"taking the current known best action to obtain a reward\",\n",
        "\"exploration\" : \"taking an action to explore an unknown state\",\n",
        "\"one-armed bandit\" : \"A general case that models one arm as a sequence of rewards with a sequence of costs for each pull T times\",\n",
        "\"Gittins index\" : \"A value that describes the maximum obtainable utility for a unit of discounted time, it is a simple optimal policy for a bandit problem\",\n",
        "\"Bernoulli bandit\" : \"each arm produces either a reward of 0 or 1 with some fixed unknown probability\", \n",
        "\"exploration bonus\" : \"a bonus given to try arms that have not be explored\",\n",
        "\"upper confidence bound\" : \"take samples and find an estimated range for the outcome with high confidence - regret $O(logN)$\",\n",
        "\"Thompson sampling\" : \"similar to upper confidence bound, but choose an arm randomly based on the prob that the arm is optimal so far\",\n",
        "\"Selection problem\" : \"the task of making the best decision given a selection, superficially similar to bandit problems\",\n",
        "\"bandit superprocess\" : \"each arm is a full MDP and not a MRP\",\n",
        "\"reinforcement learning\" : \"As an agent interacts with the world, it recieves rewards based on how well it is performing\",\n",
        "\"Q-learning\" : \"an agent learns a Q-function $Q(s,a)$ to find the sum of rewards if an action is taken, then choose action with highest Q-value.\",\n",
        "\"direct utility estimation\" : \"for a starting state, each visited state provides a sample toward the expected total reward from that state\",\n",
        "\"adaptive dynamic programming\" : \"An agent learns the transition model, solving the MDP using dynamic programming \",\n",
        "\"temporal difference\" : temp_diff,\n",
        "\"pseudoexperience\" : \"a simulation of the current transition model\",\n",
        "\"GLIE\" : \"greedy in the limit of infinite exploration\",\n",
        "\"exploration function\" : \"$f(u,n)$ determines trade off between utility $u$ and curiosity $n$.\",\n",
        "\"absorbing state\" : \"actions have no effect and no rewards are given\",\n",
        "\"Bayesian reinforcement learning\" : \"Makes assumption of prior probability of hypothesis of true model\"\n",
        "}"
      ],
      "execution_count": 89,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "1abb8098-34f2-43c8-9729-4d6ec8b4775a"
      },
      "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": 90,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nIn the bandit problem we see the trade off between exploration and exploitation.  Explotiation will yield the best known \nresult, but exploration could lead to better long-term rewards or loss.  A balance must be made between the two.  In a bandit problem,\neach arm can be modelled as an MDP with only one possible action (also known as a Markov reward process) and the overall problem as \nthe cartesian product of the actions.  An important part of this formulation is that the arms are independent.\n\n## AIMA Chapter 22.1 Learning from Rewards\n In reinforcement learning, as with MDPs, the goal is to maximize the sum of expected rewards.  The difference being that the\nagent is interacting within the problem and cannot simply solve the MDP offline.  Rather than just applying rewards to a win/loss, it is often\neasier to apply intermediate rewards when an agent makes a decision that brings it closer to a win.  This approach works well in simulated environments.\nIn model-based reinforcement learning, an agent will learn a transition model and may learn some utility function starting from its intial state.\nIn contrast, model-free reinforcemenet learning does not learn any transition model, but rather the agent learns how to act directly.  This is done\nusing action-utility learning like Q-learning where the agent learns a Q-function to determine its actions or through policy search as a reflex agent.\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n In passive reinforcement learning, we can start with a fixed policy to determine actions and we attempt to learn $U^{\\pi}(s)$ as the\ntotal discounted reward given policy $\\pi$ starting at some state $s$.  This is learned through a process similar to policy evaluation, but in this case\nwe do not know the transition model. Then we can use the defined equation for $U^{\\pi}(s)$.  Direct utility estimation ignores the connections between states\nand thus it will take a long time to converge.  By taking an adaptive dynamic programmming approach, we can learn the transition model and observe the rewards.\nBy applying modified policy iteration, we can use previous estimations and converge very quickly.  It is easy to learn the transition model in a fully \nobservable environment, as you only need to record the state-action pairs and resulting states and maintain counts $N(s'|s,a)$.  Temporal difference learning \nupdates utility estimates based on the learning rate $\u0007lpha$ and the difference in utility between sucessive states.  This method works by updating utility\nestimates until the ideal equillibrium is reached.\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n In contrast to passive reinforcement, an active learning agent will decide which actions to take instead of being given a fixed policy.\nTo do this the agent will have to learn the transition model and outcome probabilities for each action as opposed to just the fixed policy.  Active agents\nrequire a balance between exploitation and exploration much like bandit problems.  An exploration function is employed to determine this trade off.\nSafe exploration should avoid entering absorbing states or states with large negative rewards.  In temporal difference q-learning we can use a transition-model\nfree TD way to update Q-values.  Q-learning is off-policy learning as it can change policy if a better action is found given new estimates.$Q(s, a) = Q(s, a) + \\alpha [R(s,a,s') + \\gamma max_a Q(s', a') - Q(s, a)  ]$\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n We can generalize reinforcement learning to larger state spaces by taking a utility function as an approximatation using a weighted \nlinear combination of features. \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **N-armed bandit** - a slot machine with n-levers where each has a fixed unknown probability distribution of winning\n* **Exploitiation** - taking the current known best action to obtain a reward\n* **Exploration** - taking an action to explore an unknown state\n* **One-armed bandit** - A general case that models one arm as a sequence of rewards with a sequence of costs for each pull T times\n* **Gittins index** - A value that describes the maximum obtainable utility for a unit of discounted time, it is a simple optimal policy for a bandit problem\n* **Bernoulli bandit** - each arm produces either a reward of 0 or 1 with some fixed unknown probability\n* **Exploration bonus** - a bonus given to try arms that have not be explored\n* **Upper confidence bound** - take samples and find an estimated range for the outcome with high confidence - regret $O(logN)$\n* **Thompson sampling** - similar to upper confidence bound, but choose an arm randomly based on the prob that the arm is optimal so far\n* **Selection problem** - the task of making the best decision given a selection, superficially similar to bandit problems\n* **Bandit superprocess** - each arm is a full MDP and not a MRP\n* **Reinforcement learning** - As an agent interacts with the world, it recieves rewards based on how well it is performing\n* **Q-learning** - an agent learns a Q-function $Q(s,a)$ to find the sum of rewards if an action is taken, then choose action with highest Q-value.\n* **Direct utility estimation** - for a starting state, each visited state provides a sample toward the expected total reward from that state\n* **Adaptive dynamic programming** - An agent learns the transition model, solving the MDP using dynamic programming \n* **Temporal difference** -  $U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s, \\pi(s), s') + \\gamma U^{\\pi}(s') - U^{\\pi}(s')]$ \n* **Pseudoexperience** - a simulation of the current transition model\n* **Glie** - greedy in the limit of infinite exploration\n* **Exploration function** - $f(u,n)$ determines trade off between utility $u$ and curiosity $n$.\n* **Absorbing state** - actions have no effect and no rewards are given\n* **Bayesian reinforcement learning** - Makes assumption of prior probability of hypothesis of true model\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",
        "p1 = r\"\"\"$$P(a|b) = \\frac{P(a \\cap b)}{P(b)}$$ \"\"\"\n",
        "p2 = r\"\"\"$$ P(a \\cap b) = P(a|b)P(b)$$ \"\"\"\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\"\"\"\" + p1 + p2\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "mle = r\"\"\"$P(W_n|W_{n-1}) = \\frac{C(W_{n-1}W_n)}{C(W_{n-1})}$ \"\"\"\n",
        "perplex = r\"\"\"$PP(W) = \\sqrt[N]{ \\prod_{i=1}^N \\frac{1}{P(w_i|w_1...w_{i-1})} }$\"\"\"\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 = \"\"\" Maximum likelihood estimate: given count $C(xy)$, \"\"\" + mle + \"\"\" language models are computed\n",
        "using log probabilities to avoid working with really small numbers which would result in underflow.  Log probabilities\n",
        "transforms these to large values. \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Extrinstic evaluation measures the performance of a model as it performs in an application whereas\n",
        "intrinsitc evaluation measures the performance of the model independent of any application. An intrinstic evlaution\n",
        "requires a test set, a training set, and held out set for tuning hyper parameters.  These can be partitioned from\n",
        "one set of data.  Perplexity is defined as the inverse probability: \"\"\" + perplex + \"\"\" perplexitiy is closely \n",
        "related to the idea of entropy.\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Sparsity is a problem in language models.  Words that don't appear in the corpus will have a\n",
        "probability of zero which will cause problems. If the probability for any word in the test set is 0 then the entire \n",
        "test set will have a probability of 0 meaning we can't calculate the perplexity.\"\"\"\n",
        "SLP_chapter3_5 = \"\"\" To keep a model from having a probability of zero, we can apply smoothing which removes some\n",
        "probability mass from likely events to increase the probability of unlikely events. With interpolation techniques\n",
        "we mix probability estimates.  \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"chain rule\" : \"$P(X_1...X_n) = P(X_1)P(X_2|X_1)P(X_3|X_{1:2})...P(X_n|X_{1:n-1})$\",\n",
        "\"bigram\" : \"approximates the probability of a word given all previous words by only conditioning on the previous word\",\n",
        "\"markov assumption\" : \"probability only depends on the previous word (conditional)\",\n",
        "\"maximum likelihood estimate\" : \"MLE count occurences to determine probability and then normalize over distribution\",\n",
        "\"relative frequency\" : \"the observed frequency of a sequence over the frequency of a prefix\",\n",
        "\"perplexity\" : \"used to measure performance rather than raw probability\",\n",
        "\"sampling\" : \"choose random points given their likelihood\",\n",
        "\"Laplace smoothing\" : \"add one to each count before the probabilities are normalized to avoid zeros\",\n",
        "\"discounting\" : \"lower non-zero count to assign probability mass to zero counts\",\n",
        "\"add-k smoothing\" : \"add some fraction instead of adding 1 to counts which moves less probability mass\"\n",
        "}"
      ],
      "execution_count": 91,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "e80bf5cf-4e8e-4a51-d75e-0f84738729a9"
      },
      "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": 92,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# 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$$P(a|b) = \\frac{P(a \\cap b)}{P(b)}$$ $$ P(a \\cap b) = P(a|b)P(b)$$ \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 Maximum likelihood estimate: given count $C(xy)$, $P(W_n|W_{n-1}) = \\frac{C(W_{n-1}W_n)}{C(W_{n-1})}$  language models are computed\nusing log probabilities to avoid working with really small numbers which would result in underflow.  Log probabilities\ntransforms these to large values. \n\n## SLP Chapter 3.2 Evaluating Language Models\n Extrinstic evaluation measures the performance of a model as it performs in an application whereas\nintrinsitc evaluation measures the performance of the model independent of any application. An intrinstic evlaution\nrequires a test set, a training set, and held out set for tuning hyper parameters.  These can be partitioned from\none set of data.  Perplexity is defined as the inverse probability: $PP(W) = \\sqrt[N]{ \\prod_{i=1}^N \\frac{1}{P(w_i|w_1...w_{i-1})} }$ perplexitiy is closely \nrelated to the idea of entropy.\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 Sparsity is a problem in language models.  Words that don't appear in the corpus will have a\nprobability of zero which will cause problems. If the probability for any word in the test set is 0 then the entire \ntest set will have a probability of 0 meaning we can't calculate the perplexity.\n\n## SLP Chapter 3.5 Smoothing\n To keep a model from having a probability of zero, we can apply smoothing which removes some\nprobability mass from likely events to increase the probability of unlikely events. With interpolation techniques\nwe mix probability estimates.  \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Chain rule** - $P(X_1...X_n) = P(X_1)P(X_2|X_1)P(X_3|X_{1:2})...P(X_n|X_{1:n-1})$\n* **Bigram** - approximates the probability of a word given all previous words by only conditioning on the previous word\n* **Markov assumption** - probability only depends on the previous word (conditional)\n* **Maximum likelihood estimate** - MLE count occurences to determine probability and then normalize over distribution\n* **Relative frequency** - the observed frequency of a sequence over the frequency of a prefix\n* **Perplexity** - used to measure performance rather than raw probability\n* **Sampling** - choose random points given their likelihood\n* **Laplace smoothing** - add one to each count before the probabilities are normalized to avoid zeros\n* **Discounting** - lower non-zero count to assign probability mass to zero counts\n* **Add-k smoothing** - add some fraction instead of adding 1 to counts which moves less probability mass\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": [
        "bayes = r\"\"\" $$P(x_1,...,x_n) = \\prod_{i=1}^n \\theta(x_i|parents(X_i))$$ \"\"\"\n",
        "\n",
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" A bayesian network can be represented as a directed acyclic graph such that each node represents some\n",
        "random variable or quantatative probability.  The edges in the graph represent relationships between parent and a child X->Y\n",
        "means X is the parent of Y and X has direct influence on Y.  Each node will contain some probability informaiton given some \n",
        "number of parameters in the form of a conditional probability table. An entry can be defined as follows: \"\"\" + bayes + \"\"\"\n",
        "bayesian networks operate on implied conditional independence relationships.  Bayes networks provide a more compact solution\n",
        "than full joint probability tables. \"\"\" \n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" The goal of an inference in a Bayesian network is to find a probability distribution given some query\n",
        "variables, some observed event, and some set of evidence variables.  A query can be answered by enumeration computing sums\n",
        "of products of conditional probabilities in $O(2^n)$ time. Given some evidence variables, some query variable, and some hidden \n",
        "variables, we can sum out the hidden variables to get a joint probability for the query and evidence which can be normalized.  \n",
        "The enumeration algorithm can be improved by elminating repeated calculations via dynamic programming in a process called \n",
        "variable elimination. \"\"\"\n",
        "\n",
        "independent = r\"\"\" $$\\forall x,y ~ P(xy) = P(x)P(y) \\rightarrow X \\perp Y $$ \"\"\"\n",
        "cond_indep = r\"\"\" $$\\forall x,y,z ~ P(xy|z) = P(x|z)P(y|z) \\rightarrow X \\perp Y | Z ~~also~~ \\forall x,y,z ~ P(x|z,y) = P(x|z) $$\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Two random variables are independent if and only if: \"\"\" + independent + \"\"\" \n",
        "Then we can say that they are conditionally independent on some variable $Z$ if: \"\"\" + cond_indep + \"\"\"\n",
        "It is rare to find true independence, and this doesn't tell us anything meaningful.  Conditional independence\n",
        "is much more useful.  In a causal chain we have edges X, Y and Y, Z and the relationship\n",
        "$P(x,y,z) = P(x)P(y|x)P(z|y)$.  In a common cause we have edges Y, X and Y, Z and the relationship \n",
        "$P(x,y,z) = P(y)P(x|y)P(z|y)$.  In a common effect we have edges X, Z and Y, Z where X and Y are independent,\n",
        "but they are not independent given Z which means observing the effect Z activates X and Y. In the D-separation algorithm,\n",
        "we ask a query whether two variables $X_i \\perp X_j$ are indepdendent.  Then examine all undirected paths between the two variables.  \n",
        "If any path is active then they are not independent, but if all paths are inactive then independence is gaurenteed.  A path is\n",
        "active if each triple in the path is active, but if one triple is not, then the path is inactive.  Using this algorithm, we can build\n",
        "a complete list of conditional independences that are true given a Bayes net.  These will determine which probabilities can be shown.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian Network\" : \"a data structure that represents dependencies between random variables\", \n",
        "\"hidden variables\" : \"variables that are neither input nor output, but are necessary for structuring the network\",\n",
        "\"D-Separation\" : \"algo used for answering queries by conditional independence properties of triples\"\n",
        "}\n"
      ],
      "execution_count": 93,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "a0f0de3c-9999-452e-aed6-64cff8041c62"
      },
      "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": 94,
      "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 A bayesian network can be represented as a directed acyclic graph such that each node represents some\nrandom variable or quantatative probability.  The edges in the graph represent relationships between parent and a child X->Y\nmeans X is the parent of Y and X has direct influence on Y.  Each node will contain some probability informaiton given some \nnumber of parameters in the form of a conditional probability table. An entry can be defined as follows:  $$P(x_1,...,x_n) = \\prod_{i=1}^n \\theta(x_i|parents(X_i))$$ \nbayesian networks operate on implied conditional independence relationships.  Bayes networks provide a more compact solution\nthan full joint probability tables. \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 The goal of an inference in a Bayesian network is to find a probability distribution given some query\nvariables, some observed event, and some set of evidence variables.  A query can be answered by enumeration computing sums\nof products of conditional probabilities in $O(2^n)$ time. Given some evidence variables, some query variable, and some hidden \nvariables, we can sum out the hidden variables to get a joint probability for the query and evidence which can be normalized.  \nThe enumeration algorithm can be improved by elminating repeated calculations via dynamic programming in a process called \nvariable elimination. \n\n## Module 11 Lecture Notes\n Two random variables are independent if and only if:  $$\\forall x,y ~ P(xy) = P(x)P(y) \\rightarrow X \\perp Y $$  \nThen we can say that they are conditionally independent on some variable $Z$ if:  $$\\forall x,y,z ~ P(xy|z) = P(x|z)P(y|z) \\rightarrow X \\perp Y | Z ~~also~~ \\forall x,y,z ~ P(x|z,y) = P(x|z) $$\nIt is rare to find true independence, and this doesn't tell us anything meaningful.  Conditional independence\nis much more useful.  In a causal chain we have edges X, Y and Y, Z and the relationship\n$P(x,y,z) = P(x)P(y|x)P(z|y)$.  In a common cause we have edges Y, X and Y, Z and the relationship \n$P(x,y,z) = P(y)P(x|y)P(z|y)$.  In a common effect we have edges X, Z and Y, Z where X and Y are independent,\nbut they are not independent given Z which means observing the effect Z activates X and Y. In the D-separation algorithm,\nwe ask a query whether two variables $X_i \\perp X_j$ are indepdendent.  Then examine all undirected paths between the two variables.  \nIf any path is active then they are not independent, but if all paths are inactive then independence is gaurenteed.  A path is\nactive if each triple in the path is active, but if one triple is not, then the path is inactive.  Using this algorithm, we can build\na complete list of conditional independences that are true given a Bayes net.  These will determine which probabilities can be shown.\n\n## Module 11 Definitions\n* **Bayesian network** - a data structure that represents dependencies between random variables\n* **Hidden variables** - variables that are neither input nor output, but are necessary for structuring the network\n* **D-separation** - algo used for answering queries by conditional independence properties of triples\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": [
        "bayes_rule = r\"\"\" $$P(x|y) = \\frac{P(y|x)P(x)}{P(y)}$$ \"\"\"\n",
        "class_estimate = r\"\"\" $$\\hat{c} = argmax_{c \\in C} P(c|d) = argmax_{c \\in C} P(d|c)P(c) $$\"\"\"\n",
        "bayes_classifier = r\"\"\" $$ C_{NB} = argmax_{c \\in C} \\prod_{f \\in F} P(f|c) $$\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Bayes' rule provides a way to breakdown conditional probabilities for inference. Bayes' rule: \"\"\" + bayes_rule + \"\"\"\n",
        "Then by applying this we can define a classifier $\\hat{c}$ given a set of classes $C$ as:\"\"\" + class_estimate + \"\"\"\n",
        "Naive Bayes calculations are done in log space to avoid underflow.  Bayes classifiers are a type of linear classifier.  \n",
        "Given a set of features $F$ we have a classifier:\"\"\" + bayes_classifier\n",
        "slp_chapter4_2 = \"\"\" A naive Bayes' classifier can be trained using the maximum likelihood estimate to learn probabilities.  We can apply\n",
        "some kind of smoothing like laplace smoothing to avoid zero probabilities in the case that there is a word in the vocabulary for which we\n",
        "never saw some classification.  Then words that did not appear in the training set at all can be ignored at test time. \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"multinomial naive bayes classifier\" : \"makes simplifying assumptions about how various features interact\",   \n",
        "\"bag-of-words\" : \"unordered set of words that ignore position and only frequency matters\",\n",
        "\"naive Bayes assumption\" : \"conditional assumption that all features $f_i$ are independent given the classifier $c$\",\n",
        "\"stop words\" : \"words that appear very frequently like 'the' or 'a'\",\n",
        "\"binary NB\" : \"duplicate words are removed from each document\",\n",
        "\"gold label\" : \"human defined label for classification\",\n",
        "\"confusion matrix\" : \"2D table used to visualize how well a given algorithm performs against the human defined labels\",\n",
        "\"precision\" : \"measure of accurracy: true positives / (true positives + false positives)\",\n",
        "\"recall\" : \"true positives / (true positives + false negatives)\",\n",
        "\"F-Measure\" : \"combines precision and recall into one metric\",\n",
        "\"dev set\" : \"development set used to tune some parameters after training\",\n",
        "\"cross-validation\" : \"partition data into k folds, test using one fold and train on the remaining k-1, then repeat\",\n",
        "\"model card\" : \"used to document informaiton about a model, particularly shown biases and harms\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 95,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "df7b583a-1faf-411b-c538-58f47dd15b60"
      },
      "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": 96,
      "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 Bayes' rule provides a way to breakdown conditional probabilities for inference. Bayes' rule:  $$P(x|y) = \\frac{P(y|x)P(x)}{P(y)}$$ \nThen by applying this we can define a classifier $\\hat{c}$ given a set of classes $C$ as: $$\\hat{c} = argmax_{c \\in C} P(c|d) = argmax_{c \\in C} P(d|c)P(c) $$\nNaive Bayes calculations are done in log space to avoid underflow.  Bayes classifiers are a type of linear classifier.  \nGiven a set of features $F$ we have a classifier: $$ C_{NB} = argmax_{c \\in C} \\prod_{f \\in F} P(f|c) $$\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n A naive Bayes' classifier can be trained using the maximum likelihood estimate to learn probabilities.  We can apply\nsome kind of smoothing like laplace smoothing to avoid zero probabilities in the case that there is a word in the vocabulary for which we\nnever saw some classification.  Then words that did not appear in the training set at all can be ignored at test time. \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Multinomial naive bayes classifier** - makes simplifying assumptions about how various features interact\n* **Bag-of-words** - unordered set of words that ignore position and only frequency matters\n* **Naive bayes assumption** - conditional assumption that all features $f_i$ are independent given the classifier $c$\n* **Stop words** - words that appear very frequently like 'the' or 'a'\n* **Binary nb** - duplicate words are removed from each document\n* **Gold label** - human defined label for classification\n* **Confusion matrix** - 2D table used to visualize how well a given algorithm performs against the human defined labels\n* **Precision** - measure of accurracy: true positives / (true positives + false positives)\n* **Recall** - true positives / (true positives + false negatives)\n* **F-measure** - combines precision and recall into one metric\n* **Dev set** - development set used to tune some parameters after training\n* **Cross-validation** - partition data into k folds, test using one fold and train on the remaining k-1, then repeat\n* **Model card** - used to document informaiton about a model, particularly shown biases and harms\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",
        "sigmoid = r\"\"\"$$\\sigma (z) = \\frac{1}{1 + e^{-z}}$$\"\"\"\n",
        "lce = r\"\"\"$$ L_{CE}(\\hat{y}, y) = -[y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})] $$ \"\"\"\n",
        "gradient = r\"\"\"$$ \\theta_{t+1} = \\theta_t - \\eta \\Delta L(f(x;\\theta), y) $$\"\"\"\n",
        "l2_reg = r\"\"\" $$R_{L2}(\\theta) = \\sum_{j=1}^n \\theta_j^2$$\"\"\"\n",
        "l1_reg = r\"\"\" $$R_{L1}(\\theta) = \\sum_{j=1}^n \\theta_j$$\"\"\"\n",
        "softmax = r\"\"\" $$ softmax(z_i) = \\frac{e^{z_i}}{\\sum_{j=1}^k e^{z_j}} ~ 1 \\leq i \\leq k$$ \"\"\"\n",
        "\n",
        "slp_chapter5_1 = \"\"\" For a sigmoid classifier, we have an observation $x$ a set of features and an output $y$ that can be either 0 or 1.  Then \n",
        "we want to determine $P(y=1|x)$.  This is solved using logistic regression by learning a set of weights and a bais from some training set. \n",
        "Then we can take a weighted sum of evidence (dot product) $$z = (\\sum_{i=1}^n w_i x_i) + b = w \\cdot x + b$$ Then we can take the output $z$ and \n",
        "pass it through the sigmoid function to transform it into a probability. \"\"\" + sigmoid + \"\"\" In logistic regression, the decision boundary will be .5.\n",
        "In logistic regression or naive bayes classification, the feature set often must be designed by hand, but often a large abstract number of features\n",
        "will be required for a given task. \"\"\"\n",
        "slp_chapter5_2 = \"\"\" To learn weights and bias in a logistic regression model, we need to measure the distance between the current output label and \n",
        "the true gold label.  The distance, or 'how far off the model was' is often referred to as the loss function or the cost function. \"\"\"\n",
        "slp_chapter5_3 = \"\"\" A given loss function measures how far off the model's classification $\\hat{y}$ was from the true label $y$.  This loss function\n",
        "should prefer that the correct labels of training examples are more likely.  This means that we want to maximize the log probability of the actual label\n",
        "$y$ in the training set given an observation.  This is what is referred to as cross-entropy loss. \"\"\" + lce + \"\"\" We want to minimize this negative log \n",
        "probability which will have the effect of maximizing the probability of the correct answer.\"\"\"\n",
        "slp_chapter5_4 = \"\"\" In logistic regression, the loss function is convex meaning there is a single minimum and no local minima which makes it possible\n",
        "to apply gradient descent.  The gradient descent algorithm finds the slope of the loss function at the current point and moves the weight in the \n",
        "opposite directiion. This process will repeat until the weight settles into the minimum.  Gradient is a multi-variable variant of slope and hence it allows\n",
        "us to apply this strategy to a multi-variable vector of weights.  The amount to move the weight is determined by the slope and weighted by the learning rate.\n",
        "A higher/faster learning rate means that the weights are moved a further distance on each step.  In each dimension of the weight vector, the slop will be\n",
        "the partial derivative of the loss function.\"\"\" + gradient\n",
        "slp_chapter5_5 = \"\"\" A good model can generalize from a set of training data to new unseen data and overfitting will compromise a model's ability to generalize.\n",
        "To solve this, a regularization term is added to the mode which will penalize large weights.  A common method of regulariztion is L2 regularization which is \n",
        "essentially the euclidean distance of the vector from the origin. \"\"\" + l2_reg + \"\"\"\n",
        "Another method is L1 regularization which uses a linear function as essentially the manhattan distance. \"\"\" + l1_reg + \"\"\" \n",
        "This regularization term is subtracted from the objective function. \"\"\"\n",
        "slp_chapter5_6 = \"\"\" In the case of a multi-classification problem then we need to apply multinomial logistic regression which is often referred to as\n",
        "softmax regression. Instead of using a sigmoid function to transform probabilities, this method uses a softmax function on an output vector.\"\"\" + softmax + \"\"\" \n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" A single node in a neural network consists of a single computational unit.  This unit takes a set or real numbers, performs a calculation,\n",
        "and then produces an output.  In a neural network this unit consists of a logistic regression classifier given a set of inputs, weights, and a bias term we have \n",
        "the weighted sum: $z = w \\cdot x + b$ . Then we apply some non-linear activation function to this output.  Some common activation functions include sigmoid, tanh \n",
        "which will map from -1 to +1, and ReLU which is a rectified linear function.  Both the sigmoid and tanh functions have saturated (close to 1) result for large values\n",
        "and derivatives that are close to 0.  Zero derivatives can cause problems like the vanishing gradient problem.\"\"\"\n",
        "slp_chapter7_2 = \"\"\" Neural networks provide a solution to non-linearly separable functions (like XOR) which presents a problem in other methods like the \n",
        "perceptron. \"\"\"\n",
        "slp_chapter7_3 = \"\"\" In a feedfoward network, we have a multilayer acyclic network of units that are connected where the outputs from one layer are connected as\n",
        "the inputs to the next.  In this structure we have an input layer, some number of hidden layers, and then an output layer.  Each layer will be fully connected to the\n",
        "previous layer.  The output layer must pass through a normalization function to transform it into a probability distribution for classification.  To do this we can\n",
        "apply the softmax function to the output vector.\"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" To train a neural network, we need a loss function and a method of training that loss function.  Cross-entropy loss and gradient descent are\n",
        "commonly used for training.  However, to calculate the loss over intermediate layers, we need to use a strategy call error backpropagation.  This depends on the\n",
        "notion of computation graphs.  We perform a backward pass on the computation graph and make use of the chain rule to calculate the derivatives in this backward pass.\n",
        "By using this backpropagation strategy, we calculate the partial derivatives backthrough the network and hence we can apply gradient descent to calculate the error and \n",
        "update using the loss function. \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"bias term\" : \"also referred to as intercept, real number added to weighted input\", \n",
        "\"sigmoid\" : \"also call logistic function, maps some real number to the range [0,1]\",\n",
        "\"decision boundary\" : \"the point at which we switch from one classificaiton to another\",\n",
        "\"period disambiguation\" : \"determine if a period is at the end of a sent or part of word\",\n",
        "\"feature templates\" : \"a large, abstract specification of features\",   \n",
        "\"cross-entropy loss\" : \"negative log likelihood loss\",\n",
        "\"convex\" : \"only one minimum in function\",\n",
        "\"hyperparameter\" : \"parameters chosen by the algorithm designer\",\n",
        "\"batch training\" : \"compute using the entire dataset (can take a lot of time to process)\",\n",
        "\"mini-batch\" : \"train on a set less than the complete dataset\",\n",
        "\"overfitting\" : \"weights too closely fit the details of training set and learn noisy factors\",\n",
        "\"pretraining\" : \"another algorithm has already learned an embedded representation of the input\",\n",
        "\"embedings\" : \"a representation of words with prior context\",\n",
        "\"one-hot vector\" : \"a vector with a single element equal to 1\",\n",
        "\"dropout\" : \"some units and connections are randomly removed during training to avoid overfitting\"\n",
        "}\n"
      ],
      "execution_count": 97,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "6c175eaa-f9d8-48f9-c030-162f8c3eb9f9"
      },
      "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": 98,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n For a sigmoid classifier, we have an observation $x$ a set of features and an output $y$ that can be either 0 or 1.  Then \nwe want to determine $P(y=1|x)$.  This is solved using logistic regression by learning a set of weights and a bais from some training set. \nThen we can take a weighted sum of evidence (dot product) $$z = (\\sum_{i=1}^n w_i x_i) + b = w \\cdot x + b$$ Then we can take the output $z$ and \npass it through the sigmoid function to transform it into a probability. $$\\sigma (z) = \\frac{1}{1 + e^{-z}}$$ In logistic regression, the decision boundary will be .5.\nIn logistic regression or naive bayes classification, the feature set often must be designed by hand, but often a large abstract number of features\nwill be required for a given task. \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n To learn weights and bias in a logistic regression model, we need to measure the distance between the current output label and \nthe true gold label.  The distance, or 'how far off the model was' is often referred to as the loss function or the cost function. \n\n## SLP Chapter 5.3 The cross-entropy loss function\n A given loss function measures how far off the model's classification $\\hat{y}$ was from the true label $y$.  This loss function\nshould prefer that the correct labels of training examples are more likely.  This means that we want to maximize the log probability of the actual label\n$y$ in the training set given an observation.  This is what is referred to as cross-entropy loss. $$ L_{CE}(\\hat{y}, y) = -[y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})] $$  We want to minimize this negative log \nprobability which will have the effect of maximizing the probability of the correct answer.\n\n## SLP Chapter 5.4 Gradient Descent\n In logistic regression, the loss function is convex meaning there is a single minimum and no local minima which makes it possible\nto apply gradient descent.  The gradient descent algorithm finds the slope of the loss function at the current point and moves the weight in the \nopposite directiion. This process will repeat until the weight settles into the minimum.  Gradient is a multi-variable variant of slope and hence it allows\nus to apply this strategy to a multi-variable vector of weights.  The amount to move the weight is determined by the slope and weighted by the learning rate.\nA higher/faster learning rate means that the weights are moved a further distance on each step.  In each dimension of the weight vector, the slop will be\nthe partial derivative of the loss function.$$ \\theta_{t+1} = \\theta_t - \\eta \\Delta L(f(x;\\theta), y) $$\n\n## SLP Chapter 5.5 Regularization\n A good model can generalize from a set of training data to new unseen data and overfitting will compromise a model's ability to generalize.\nTo solve this, a regularization term is added to the mode which will penalize large weights.  A common method of regulariztion is L2 regularization which is \nessentially the euclidean distance of the vector from the origin.  $$R_{L2}(\\theta) = \\sum_{j=1}^n \\theta_j^2$$\nAnother method is L1 regularization which uses a linear function as essentially the manhattan distance.  $$R_{L1}(\\theta) = \\sum_{j=1}^n \\theta_j$$ \nThis regularization term is subtracted from the objective function. \n\n## SLP Chapter 5.6 Multinomial logistic regression\n In the case of a multi-classification problem then we need to apply multinomial logistic regression which is often referred to as\nsoftmax regression. Instead of using a sigmoid function to transform probabilities, this method uses a softmax function on an output vector. $$ softmax(z_i) = \\frac{e^{z_i}}{\\sum_{j=1}^k e^{z_j}} ~ 1 \\leq i \\leq k$$  \n\n\n## SLP Chapter 7.1 Units\n A single node in a neural network consists of a single computational unit.  This unit takes a set or real numbers, performs a calculation,\nand then produces an output.  In a neural network this unit consists of a logistic regression classifier given a set of inputs, weights, and a bias term we have \nthe weighted sum: $z = w \\cdot x + b$ . Then we apply some non-linear activation function to this output.  Some common activation functions include sigmoid, tanh \nwhich will map from -1 to +1, and ReLU which is a rectified linear function.  Both the sigmoid and tanh functions have saturated (close to 1) result for large values\nand derivatives that are close to 0.  Zero derivatives can cause problems like the vanishing gradient problem.\n\n## SLP Chapter 7.2 The XOR problem\n Neural networks provide a solution to non-linearly separable functions (like XOR) which presents a problem in other methods like the \nperceptron. \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n In a feedfoward network, we have a multilayer acyclic network of units that are connected where the outputs from one layer are connected as\nthe inputs to the next.  In this structure we have an input layer, some number of hidden layers, and then an output layer.  Each layer will be fully connected to the\nprevious layer.  The output layer must pass through a normalization function to transform it into a probability distribution for classification.  To do this we can\napply the softmax function to the output vector.\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 To train a neural network, we need a loss function and a method of training that loss function.  Cross-entropy loss and gradient descent are\ncommonly used for training.  However, to calculate the loss over intermediate layers, we need to use a strategy call error backpropagation.  This depends on the\nnotion of computation graphs.  We perform a backward pass on the computation graph and make use of the chain rule to calculate the derivatives in this backward pass.\nBy using this backpropagation strategy, we calculate the partial derivatives backthrough the network and hence we can apply gradient descent to calculate the error and \nupdate using the loss function. \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Bias term** - also referred to as intercept, real number added to weighted input\n* **Sigmoid** - also call logistic function, maps some real number to the range [0,1]\n* **Decision boundary** - the point at which we switch from one classificaiton to another\n* **Period disambiguation** - determine if a period is at the end of a sent or part of word\n* **Feature templates** - a large, abstract specification of features\n* **Cross-entropy loss** - negative log likelihood loss\n* **Convex** - only one minimum in function\n* **Hyperparameter** - parameters chosen by the algorithm designer\n* **Batch training** - compute using the entire dataset (can take a lot of time to process)\n* **Mini-batch** - train on a set less than the complete dataset\n* **Overfitting** - weights too closely fit the details of training set and learn noisy factors\n* **Pretraining** - another algorithm has already learned an embedded representation of the input\n* **Embedings** - a representation of words with prior context\n* **One-hot vector** - a vector with a single element equal to 1\n* **Dropout** - some units and connections are randomly removed during training to avoid overfitting\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",
        "vector_len = r\"\"\" $$|v| = \\sqrt{\\sum_{i=1}^N v_i^2}$$\"\"\"\n",
        "cosine_metric = r\"\"\" $$cosine(v, w) = \\frac{v \\cdot w}{|v||w|} $$\"\"\"\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" In a recurrent neural network, there is a cycle within the network connections, so the value of some unit is dependent on its own earlier output.\n",
        "In an Elman/simple RNN, the hidden layer contains a recurrent connection (feedback loop) such that its activation depends on its input and last output.  RNN's require no \n",
        "specialized approach to training. \"\"\"\n",
        "slp_chapter9_3 = \"\"\" RNNs can be used as language models.  Given some input sequence, the RNN takes one word at a time and attempts to predict the next word using the\n",
        "current word and the hidden previous state.  This avoids the limited context problems found in n-gram models.  The input sequence consists of word embeddings each as a \n",
        "one-hot vector and outputs a prediction as a probability distribution over the entire vocabulary.  A softmax layer is used to generate the distribution.  The model can\n",
        "be trained using a text corpus.  CE loss is used based on if the model predicted the next word correctly. \"\"\"\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 = \"\"\" The word2vec model is used to contruct short, dense vectors/embeddings that show useful semantic properties. \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" We can measure the similarity of two words by taking the cosine of the angle between the two vectors. The cosine can \n",
        "be based on the dot product of the vectors.  This has the problem of favoring long vectors, so to account for this we take the normalized dot product: \"\"\" + cosine_metric + \"\"\" \n",
        "given vector length:\"\"\" + vector_len\n",
        "slp_chapter6_8 = \"\"\" Embeddings are short dense vectors where the number of dimensions ranges from 50-1000 and the values are real-valued numbers that can be negative. \n",
        "Word2Vec is a software package for determining these embeddings.  They are static embeddings meaning one fixed embedding is learned for each word.\"\"\"\n",
        "slp_chapter6_10 = \"\"\" These embeddings can be used to determine similarity between words.  First-order co-occurence are near each other and second-order have similar neighbors.\n",
        " \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Embeddings have the potential to amplify bias. Debiasing can be employed to reduce bias, but it cannot eliminate it.\"\"\"\n",
        "slp_chapter6_12 = \"\"\" A common method for evaluating vector models is by similarity.  This computes the correlation between the algo's similarity scores and similarity ratings \n",
        "created by humans. \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"leixical semantics\" : \"The study of word meaning\", \n",
        "\"word sense\" : \"The aspects of the meaning of a word\",\n",
        "\"polysemous\" : \"words can have multiple senses\",\n",
        "\"word sense disambiguation\" : \"determine the sense of a word given some context\",\n",
        "\"sentiment\" : \"positive or negative connotation evalutaion\",\n",
        "\"vector semantics\" : \"a standard way or representing word meaning using a vector space\",\n",
        "\"embeddings\" : \"vectors for the representation of words\",\n",
        "\"term-document matrix\" : \"table where each row is a word and each column is document, cells count appears of word in doc\",\n",
        "\"information retrieval\" : \"find a document that best matches some query\",\n",
        "\"representational harm\" : \"a harm caused by demaning or ignoring some social group\",\n",
        "\"teacher forcing\" : \"the model is given the correct history sequence, rather than basing training on its own output\",\n",
        "\"weight tying\" : \"combines a single set of embeddings at input with softmax to avoid redundency\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 99,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "7048bcc4-14dd-4c57-d22a-fabad3d4c42f"
      },
      "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": 100,
      "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 In a recurrent neural network, there is a cycle within the network connections, so the value of some unit is dependent on its own earlier output.\nIn an Elman/simple RNN, the hidden layer contains a recurrent connection (feedback loop) such that its activation depends on its input and last output.  RNN's require no \nspecialized approach to training. \n\n## SLP Chapter 9.3 RNNs as Language Models\n RNNs can be used as language models.  Given some input sequence, the RNN takes one word at a time and attempts to predict the next word using the\ncurrent word and the hidden previous state.  This avoids the limited context problems found in n-gram models.  The input sequence consists of word embeddings each as a \none-hot vector and outputs a prediction as a probability distribution over the entire vocabulary.  A softmax layer is used to generate the distribution.  The model can\nbe trained using a text corpus.  CE loss is used based on if the model predicted the next word correctly. \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n The word2vec model is used to contruct short, dense vectors/embeddings that show useful semantic properties. \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n We can measure the similarity of two words by taking the cosine of the angle between the two vectors. The cosine can \nbe based on the dot product of the vectors.  This has the problem of favoring long vectors, so to account for this we take the normalized dot product:  $$cosine(v, w) = \\frac{v \\cdot w}{|v||w|} $$ \ngiven vector length: $$|v| = \\sqrt{\\sum_{i=1}^N v_i^2}$$\n\n## SLP Chapter 6.8 Word2vec\n Embeddings are short dense vectors where the number of dimensions ranges from 50-1000 and the values are real-valued numbers that can be negative. \nWord2Vec is a software package for determining these embeddings.  They are static embeddings meaning one fixed embedding is learned for each word.\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n These embeddings can be used to determine similarity between words.  First-order co-occurence are near each other and second-order have similar neighbors.\n \n\n## SLP Chapter 6.11 Bias and Embeddings\n Embeddings have the potential to amplify bias. Debiasing can be employed to reduce bias, but it cannot eliminate it.\n\n## SLP Chapter 6.12 Evaluating Vector Models\n A common method for evaluating vector models is by similarity.  This computes the correlation between the algo's similarity scores and similarity ratings \ncreated by humans. \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Leixical semantics** - The study of word meaning\n* **Word sense** - The aspects of the meaning of a word\n* **Polysemous** - words can have multiple senses\n* **Word sense disambiguation** - determine the sense of a word given some context\n* **Sentiment** - positive or negative connotation evalutaion\n* **Vector semantics** - a standard way or representing word meaning using a vector space\n* **Embeddings** - vectors for the representation of words\n* **Term-document matrix** - table where each row is a word and each column is document, cells count appears of word in doc\n* **Information retrieval** - find a document that best matches some query\n* **Representational harm** - a harm caused by demaning or ignoring some social group\n* **Teacher forcing** - the model is given the correct history sequence, rather than basing training on its own output\n* **Weight tying** - combines a single set of embeddings at input with softmax to avoid redundency\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": 0
        },
        "id": "T3cm1WV542_a",
        "outputId": "640fc1a4-3266-4742-bcfc-a5c8f969bee2"
      },
      "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": 101,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nGiven uncertainty, decision theory involves choose the best action based on the desirability of their\npossible outcomes.  The principle of MEU gives a way to design intelligent behaviour given uncertainty.  Simply maximize utility,\nover all possible actions.  Estimating the probability distribution requires perception, learning, knowledge, and inference and it may\nrequire more planning to find what states follow from a given state.  It is not a final solution to this AI problem, but it provides a good\nframework that is somewhat general. $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nGiven two outcomes A and B an agent may prefer one over the other or be indifferent.\nThe outcomes of each action can be though of as a lottery and each action is like a ticket.  Each outcome may lead to another\nlottery or it can lead to some terminal or atomic state.  A reasonable preference must maintain: orderability, transitivity, continuability,\nsubsitutability, monotonicity, and decomposability.  A utility funciton must exist if an agent has preferences that obey these laws.\nThe utility of a lottery is exactly the expected utility where the utility of an outcome is weighted by its probability.  \nIn a deterministic environment, preference need only be ranked on states which is called a valur or ordinal utility function.\nThe existence of a utility function does not garuntee that an agent acts to maximize that function given its preferences.\n\n## AIMA Chapter 16.3 Utility Functions\nThe expected utility according to a probability model will reflect the expectation given that model, but this \nis often an oversimplification because the true expected utility requires more imformation or is computationally difficult. $a^* = \\textnormal{argmax}_a EU(a)$ \n\n## AIMA Chapter 17.1 Sequential Decision Problems\nIn a sequential environment, the utility function will depend on an environtment history or a sequence of states and actions.\nA sequential decision problem given a fully observable, stochastic environment is solvable by a Markov Decision Process.  Methods for\nsolving MDPs typically employ dynamic programming strategies.  The solution for such a problem takes the form of a policy the determines what\nthe agent should do given any state.  The goal in an MDP is to determine the optimal policy.  A technique often applied to rewards is a \ndiscount factor applied to future rewards.  This is so that the agent is inclined to prefer more immediate rewards, but as the discount\nfactor approaches 1, the agent will wait for long term rewards.  Discounted rewards also avoid infinite rewards in a space with an \ninfinite horizon.  The Bellman equation shows the utility of a state given the expected utility of the subsequent states.  Using the \nBellman equation and the action-utility or Q-function, we can extract the optimal policy.  We can replace the utility function with the\nQ-function to extract the policy.  A simple way to represent the transition and reward functions is with 3 dimensional table of size $|S|^2|A|$.  \nThis is fine for small problems but for large problems the tables quickly become too big. $U^\\pi(s) = E(\\sum_{t=0}^{\\infty} \\gamma^t R(S_t, \\pi(S_t), S_{t+1}))$ \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nFour possible algorithms for solving MDPs: value iteration, policy iteration, linear programming, and Monte Carlo planning. \nIn value iteration, a bellman update is applied until they converge.  Value iteration will eventually converge to a unique solution.\nIn policy iteration, we can simply evalute the policy and then update the policy if needed until the policy no longer changes.  This\ncan be done by using a simplified Bellman equation eliminating the max.  By removing the max operation, these become a system of linear\nequations that are solvable in $O(n^3)$ time.  On larger state spaces, modified policy iteration can be performed.  Both value iteration and\npolicy iteration are offline algorithms, the monte carlo approach is an example of an online solution.\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - $U(s)$ a single value to used to express how desirable a state is\n* **Expected utility** - $EU(a)$ is sum of the utility of each possible outcome weighted by its probability (average utility value)\n* **Maximum expected utility meu** - a rational agent should always choose an action to maximize expected utility\n* **Preference eliciation** - A method of presenting choices to a human and building a utility function based on their observed preferences\n* **Micromort** - one in a million chance of death\n* **Monotonic preference** - a preference to more rather than less if all else is equal\n* **Reward** - reward function $R(s,a,s')$\n* **Markov decision process** - a set of states, actions, a transition model  $P(s'|s,a)$, and a reward function\n* **Policy** - $\\pi(s)$ returns a recommended action by the policy for some state $s$.\n* **Optimal policy** - $\\pi^*$ denotes the policy that yields the highest expected utility\n* **Finite horizon** - there is a fixed time/steps $N$ and after it has elapsed, the game is over\n* **Infinite horizon** - there is no deadline, but sequences can still end by entering a terminal state\n* **Discount factor** - $\\gamma$ value between 0-1 applied toward future rewards to prefer current rewards\n* **Proper policy** - a policy guaranteed to reach a terminal state\n* **Bellman equation** - $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s' | s, a)[R(s,a,s') + \\gamma U(s')]$\n* **Q-function** - $U(s) = max_a Q(s,a)$\n* **Value iteration** - solve bellman equations by applying some arbitrary inital utility and iteratively update until equillibrium is reached\n* **Policy iteration** - find an optimal policy by alternating policy evaluation and policy improvement\n* **Linear programming** - General approach for solving constrained optimization problems\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nIn the bandit problem we see the trade off between exploration and exploitation.  Explotiation will yield the best known \nresult, but exploration could lead to better long-term rewards or loss.  A balance must be made between the two.  In a bandit problem,\neach arm can be modelled as an MDP with only one possible action (also known as a Markov reward process) and the overall problem as \nthe cartesian product of the actions.  An important part of this formulation is that the arms are independent.\n\n## AIMA Chapter 22.1 Learning from Rewards\n In reinforcement learning, as with MDPs, the goal is to maximize the sum of expected rewards.  The difference being that the\nagent is interacting within the problem and cannot simply solve the MDP offline.  Rather than just applying rewards to a win/loss, it is often\neasier to apply intermediate rewards when an agent makes a decision that brings it closer to a win.  This approach works well in simulated environments.\nIn model-based reinforcement learning, an agent will learn a transition model and may learn some utility function starting from its intial state.\nIn contrast, model-free reinforcemenet learning does not learn any transition model, but rather the agent learns how to act directly.  This is done\nusing action-utility learning like Q-learning where the agent learns a Q-function to determine its actions or through policy search as a reflex agent.\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n In passive reinforcement learning, we can start with a fixed policy to determine actions and we attempt to learn $U^{\\pi}(s)$ as the\ntotal discounted reward given policy $\\pi$ starting at some state $s$.  This is learned through a process similar to policy evaluation, but in this case\nwe do not know the transition model. Then we can use the defined equation for $U^{\\pi}(s)$.  Direct utility estimation ignores the connections between states\nand thus it will take a long time to converge.  By taking an adaptive dynamic programmming approach, we can learn the transition model and observe the rewards.\nBy applying modified policy iteration, we can use previous estimations and converge very quickly.  It is easy to learn the transition model in a fully \nobservable environment, as you only need to record the state-action pairs and resulting states and maintain counts $N(s'|s,a)$.  Temporal difference learning \nupdates utility estimates based on the learning rate $\u0007lpha$ and the difference in utility between sucessive states.  This method works by updating utility\nestimates until the ideal equillibrium is reached.\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n In contrast to passive reinforcement, an active learning agent will decide which actions to take instead of being given a fixed policy.\nTo do this the agent will have to learn the transition model and outcome probabilities for each action as opposed to just the fixed policy.  Active agents\nrequire a balance between exploitation and exploration much like bandit problems.  An exploration function is employed to determine this trade off.\nSafe exploration should avoid entering absorbing states or states with large negative rewards.  In temporal difference q-learning we can use a transition-model\nfree TD way to update Q-values.  Q-learning is off-policy learning as it can change policy if a better action is found given new estimates.$Q(s, a) = Q(s, a) + \\alpha [R(s,a,s') + \\gamma max_a Q(s', a') - Q(s, a)  ]$\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n We can generalize reinforcement learning to larger state spaces by taking a utility function as an approximatation using a weighted \nlinear combination of features. \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **N-armed bandit** - a slot machine with n-levers where each has a fixed unknown probability distribution of winning\n* **Exploitiation** - taking the current known best action to obtain a reward\n* **Exploration** - taking an action to explore an unknown state\n* **One-armed bandit** - A general case that models one arm as a sequence of rewards with a sequence of costs for each pull T times\n* **Gittins index** - A value that describes the maximum obtainable utility for a unit of discounted time, it is a simple optimal policy for a bandit problem\n* **Bernoulli bandit** - each arm produces either a reward of 0 or 1 with some fixed unknown probability\n* **Exploration bonus** - a bonus given to try arms that have not be explored\n* **Upper confidence bound** - take samples and find an estimated range for the outcome with high confidence - regret $O(logN)$\n* **Thompson sampling** - similar to upper confidence bound, but choose an arm randomly based on the prob that the arm is optimal so far\n* **Selection problem** - the task of making the best decision given a selection, superficially similar to bandit problems\n* **Bandit superprocess** - each arm is a full MDP and not a MRP\n* **Reinforcement learning** - As an agent interacts with the world, it recieves rewards based on how well it is performing\n* **Q-learning** - an agent learns a Q-function $Q(s,a)$ to find the sum of rewards if an action is taken, then choose action with highest Q-value.\n* **Direct utility estimation** - for a starting state, each visited state provides a sample toward the expected total reward from that state\n* **Adaptive dynamic programming** - An agent learns the transition model, solving the MDP using dynamic programming \n* **Temporal difference** -  $U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha[R(s, \\pi(s), s') + \\gamma U^{\\pi}(s') - U^{\\pi}(s')]$ \n* **Pseudoexperience** - a simulation of the current transition model\n* **Glie** - greedy in the limit of infinite exploration\n* **Exploration function** - $f(u,n)$ determines trade off between utility $u$ and curiosity $n$.\n* **Absorbing state** - actions have no effect and no rewards are given\n* **Bayesian reinforcement learning** - Makes assumption of prior probability of hypothesis of true model\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$$P(a|b) = \\frac{P(a \\cap b)}{P(b)}$$ $$ P(a \\cap b) = P(a|b)P(b)$$ \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 Maximum likelihood estimate: given count $C(xy)$, $P(W_n|W_{n-1}) = \\frac{C(W_{n-1}W_n)}{C(W_{n-1})}$  language models are computed\nusing log probabilities to avoid working with really small numbers which would result in underflow.  Log probabilities\ntransforms these to large values. \n\n## SLP Chapter 3.2 Evaluating Language Models\n Extrinstic evaluation measures the performance of a model as it performs in an application whereas\nintrinsitc evaluation measures the performance of the model independent of any application. An intrinstic evlaution\nrequires a test set, a training set, and held out set for tuning hyper parameters.  These can be partitioned from\none set of data.  Perplexity is defined as the inverse probability: $PP(W) = \\sqrt[N]{ \\prod_{i=1}^N \\frac{1}{P(w_i|w_1...w_{i-1})} }$ perplexitiy is closely \nrelated to the idea of entropy.\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 Sparsity is a problem in language models.  Words that don't appear in the corpus will have a\nprobability of zero which will cause problems. If the probability for any word in the test set is 0 then the entire \ntest set will have a probability of 0 meaning we can't calculate the perplexity.\n\n## SLP Chapter 3.5 Smoothing\n To keep a model from having a probability of zero, we can apply smoothing which removes some\nprobability mass from likely events to increase the probability of unlikely events. With interpolation techniques\nwe mix probability estimates.  \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Chain rule** - $P(X_1...X_n) = P(X_1)P(X_2|X_1)P(X_3|X_{1:2})...P(X_n|X_{1:n-1})$\n* **Bigram** - approximates the probability of a word given all previous words by only conditioning on the previous word\n* **Markov assumption** - probability only depends on the previous word (conditional)\n* **Maximum likelihood estimate** - MLE count occurences to determine probability and then normalize over distribution\n* **Relative frequency** - the observed frequency of a sequence over the frequency of a prefix\n* **Perplexity** - used to measure performance rather than raw probability\n* **Sampling** - choose random points given their likelihood\n* **Laplace smoothing** - add one to each count before the probabilities are normalized to avoid zeros\n* **Discounting** - lower non-zero count to assign probability mass to zero counts\n* **Add-k smoothing** - add some fraction instead of adding 1 to counts which moves less probability mass\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n A bayesian network can be represented as a directed acyclic graph such that each node represents some\nrandom variable or quantatative probability.  The edges in the graph represent relationships between parent and a child X->Y\nmeans X is the parent of Y and X has direct influence on Y.  Each node will contain some probability informaiton given some \nnumber of parameters in the form of a conditional probability table. An entry can be defined as follows:  $$P(x_1,...,x_n) = \\prod_{i=1}^n \\theta(x_i|parents(X_i))$$ \nbayesian networks operate on implied conditional independence relationships.  Bayes networks provide a more compact solution\nthan full joint probability tables. \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 The goal of an inference in a Bayesian network is to find a probability distribution given some query\nvariables, some observed event, and some set of evidence variables.  A query can be answered by enumeration computing sums\nof products of conditional probabilities in $O(2^n)$ time. Given some evidence variables, some query variable, and some hidden \nvariables, we can sum out the hidden variables to get a joint probability for the query and evidence which can be normalized.  \nThe enumeration algorithm can be improved by elminating repeated calculations via dynamic programming in a process called \nvariable elimination. \n\n## Module 11 Lecture Notes\n Two random variables are independent if and only if:  $$\\forall x,y ~ P(xy) = P(x)P(y) \\rightarrow X \\perp Y $$  \nThen we can say that they are conditionally independent on some variable $Z$ if:  $$\\forall x,y,z ~ P(xy|z) = P(x|z)P(y|z) \\rightarrow X \\perp Y | Z ~~also~~ \\forall x,y,z ~ P(x|z,y) = P(x|z) $$\nIt is rare to find true independence, and this doesn't tell us anything meaningful.  Conditional independence\nis much more useful.  In a causal chain we have edges X, Y and Y, Z and the relationship\n$P(x,y,z) = P(x)P(y|x)P(z|y)$.  In a common cause we have edges Y, X and Y, Z and the relationship \n$P(x,y,z) = P(y)P(x|y)P(z|y)$.  In a common effect we have edges X, Z and Y, Z where X and Y are independent,\nbut they are not independent given Z which means observing the effect Z activates X and Y. In the D-separation algorithm,\nwe ask a query whether two variables $X_i \\perp X_j$ are indepdendent.  Then examine all undirected paths between the two variables.  \nIf any path is active then they are not independent, but if all paths are inactive then independence is gaurenteed.  A path is\nactive if each triple in the path is active, but if one triple is not, then the path is inactive.  Using this algorithm, we can build\na complete list of conditional independences that are true given a Bayes net.  These will determine which probabilities can be shown.\n\n## Module 11 Definitions\n* **Bayesian network** - a data structure that represents dependencies between random variables\n* **Hidden variables** - variables that are neither input nor output, but are necessary for structuring the network\n* **D-separation** - algo used for answering queries by conditional independence properties of triples\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 Bayes' rule provides a way to breakdown conditional probabilities for inference. Bayes' rule:  $$P(x|y) = \\frac{P(y|x)P(x)}{P(y)}$$ \nThen by applying this we can define a classifier $\\hat{c}$ given a set of classes $C$ as: $$\\hat{c} = argmax_{c \\in C} P(c|d) = argmax_{c \\in C} P(d|c)P(c) $$\nNaive Bayes calculations are done in log space to avoid underflow.  Bayes classifiers are a type of linear classifier.  \nGiven a set of features $F$ we have a classifier: $$ C_{NB} = argmax_{c \\in C} \\prod_{f \\in F} P(f|c) $$\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n A naive Bayes' classifier can be trained using the maximum likelihood estimate to learn probabilities.  We can apply\nsome kind of smoothing like laplace smoothing to avoid zero probabilities in the case that there is a word in the vocabulary for which we\nnever saw some classification.  Then words that did not appear in the training set at all can be ignored at test time. \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Multinomial naive bayes classifier** - makes simplifying assumptions about how various features interact\n* **Bag-of-words** - unordered set of words that ignore position and only frequency matters\n* **Naive bayes assumption** - conditional assumption that all features $f_i$ are independent given the classifier $c$\n* **Stop words** - words that appear very frequently like 'the' or 'a'\n* **Binary nb** - duplicate words are removed from each document\n* **Gold label** - human defined label for classification\n* **Confusion matrix** - 2D table used to visualize how well a given algorithm performs against the human defined labels\n* **Precision** - measure of accurracy: true positives / (true positives + false positives)\n* **Recall** - true positives / (true positives + false negatives)\n* **F-measure** - combines precision and recall into one metric\n* **Dev set** - development set used to tune some parameters after training\n* **Cross-validation** - partition data into k folds, test using one fold and train on the remaining k-1, then repeat\n* **Model card** - used to document informaiton about a model, particularly shown biases and harms\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n For a sigmoid classifier, we have an observation $x$ a set of features and an output $y$ that can be either 0 or 1.  Then \nwe want to determine $P(y=1|x)$.  This is solved using logistic regression by learning a set of weights and a bais from some training set. \nThen we can take a weighted sum of evidence (dot product) $$z = (\\sum_{i=1}^n w_i x_i) + b = w \\cdot x + b$$ Then we can take the output $z$ and \npass it through the sigmoid function to transform it into a probability. $$\\sigma (z) = \\frac{1}{1 + e^{-z}}$$ In logistic regression, the decision boundary will be .5.\nIn logistic regression or naive bayes classification, the feature set often must be designed by hand, but often a large abstract number of features\nwill be required for a given task. \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n To learn weights and bias in a logistic regression model, we need to measure the distance between the current output label and \nthe true gold label.  The distance, or 'how far off the model was' is often referred to as the loss function or the cost function. \n\n## SLP Chapter 5.3 The cross-entropy loss function\n A given loss function measures how far off the model's classification $\\hat{y}$ was from the true label $y$.  This loss function\nshould prefer that the correct labels of training examples are more likely.  This means that we want to maximize the log probability of the actual label\n$y$ in the training set given an observation.  This is what is referred to as cross-entropy loss. $$ L_{CE}(\\hat{y}, y) = -[y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})] $$  We want to minimize this negative log \nprobability which will have the effect of maximizing the probability of the correct answer.\n\n## SLP Chapter 5.4 Gradient Descent\n In logistic regression, the loss function is convex meaning there is a single minimum and no local minima which makes it possible\nto apply gradient descent.  The gradient descent algorithm finds the slope of the loss function at the current point and moves the weight in the \nopposite directiion. This process will repeat until the weight settles into the minimum.  Gradient is a multi-variable variant of slope and hence it allows\nus to apply this strategy to a multi-variable vector of weights.  The amount to move the weight is determined by the slope and weighted by the learning rate.\nA higher/faster learning rate means that the weights are moved a further distance on each step.  In each dimension of the weight vector, the slop will be\nthe partial derivative of the loss function.$$ \\theta_{t+1} = \\theta_t - \\eta \\Delta L(f(x;\\theta), y) $$\n\n## SLP Chapter 5.5 Regularization\n A good model can generalize from a set of training data to new unseen data and overfitting will compromise a model's ability to generalize.\nTo solve this, a regularization term is added to the mode which will penalize large weights.  A common method of regulariztion is L2 regularization which is \nessentially the euclidean distance of the vector from the origin.  $$R_{L2}(\\theta) = \\sum_{j=1}^n \\theta_j^2$$\nAnother method is L1 regularization which uses a linear function as essentially the manhattan distance.  $$R_{L1}(\\theta) = \\sum_{j=1}^n \\theta_j$$ \nThis regularization term is subtracted from the objective function. \n\n## SLP Chapter 5.6 Multinomial logistic regression\n In the case of a multi-classification problem then we need to apply multinomial logistic regression which is often referred to as\nsoftmax regression. Instead of using a sigmoid function to transform probabilities, this method uses a softmax function on an output vector. $$ softmax(z_i) = \\frac{e^{z_i}}{\\sum_{j=1}^k e^{z_j}} ~ 1 \\leq i \\leq k$$  \n\n\n## SLP Chapter 7.1 Units\n A single node in a neural network consists of a single computational unit.  This unit takes a set or real numbers, performs a calculation,\nand then produces an output.  In a neural network this unit consists of a logistic regression classifier given a set of inputs, weights, and a bias term we have \nthe weighted sum: $z = w \\cdot x + b$ . Then we apply some non-linear activation function to this output.  Some common activation functions include sigmoid, tanh \nwhich will map from -1 to +1, and ReLU which is a rectified linear function.  Both the sigmoid and tanh functions have saturated (close to 1) result for large values\nand derivatives that are close to 0.  Zero derivatives can cause problems like the vanishing gradient problem.\n\n## SLP Chapter 7.2 The XOR problem\n Neural networks provide a solution to non-linearly separable functions (like XOR) which presents a problem in other methods like the \nperceptron. \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n In a feedfoward network, we have a multilayer acyclic network of units that are connected where the outputs from one layer are connected as\nthe inputs to the next.  In this structure we have an input layer, some number of hidden layers, and then an output layer.  Each layer will be fully connected to the\nprevious layer.  The output layer must pass through a normalization function to transform it into a probability distribution for classification.  To do this we can\napply the softmax function to the output vector.\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 To train a neural network, we need a loss function and a method of training that loss function.  Cross-entropy loss and gradient descent are\ncommonly used for training.  However, to calculate the loss over intermediate layers, we need to use a strategy call error backpropagation.  This depends on the\nnotion of computation graphs.  We perform a backward pass on the computation graph and make use of the chain rule to calculate the derivatives in this backward pass.\nBy using this backpropagation strategy, we calculate the partial derivatives backthrough the network and hence we can apply gradient descent to calculate the error and \nupdate using the loss function. \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Bias term** - also referred to as intercept, real number added to weighted input\n* **Sigmoid** - also call logistic function, maps some real number to the range [0,1]\n* **Decision boundary** - the point at which we switch from one classificaiton to another\n* **Period disambiguation** - determine if a period is at the end of a sent or part of word\n* **Feature templates** - a large, abstract specification of features\n* **Cross-entropy loss** - negative log likelihood loss\n* **Convex** - only one minimum in function\n* **Hyperparameter** - parameters chosen by the algorithm designer\n* **Batch training** - compute using the entire dataset (can take a lot of time to process)\n* **Mini-batch** - train on a set less than the complete dataset\n* **Overfitting** - weights too closely fit the details of training set and learn noisy factors\n* **Pretraining** - another algorithm has already learned an embedded representation of the input\n* **Embedings** - a representation of words with prior context\n* **One-hot vector** - a vector with a single element equal to 1\n* **Dropout** - some units and connections are randomly removed during training to avoid overfitting\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 In a recurrent neural network, there is a cycle within the network connections, so the value of some unit is dependent on its own earlier output.\nIn an Elman/simple RNN, the hidden layer contains a recurrent connection (feedback loop) such that its activation depends on its input and last output.  RNN's require no \nspecialized approach to training. \n\n## SLP Chapter 9.3 RNNs as Language Models\n RNNs can be used as language models.  Given some input sequence, the RNN takes one word at a time and attempts to predict the next word using the\ncurrent word and the hidden previous state.  This avoids the limited context problems found in n-gram models.  The input sequence consists of word embeddings each as a \none-hot vector and outputs a prediction as a probability distribution over the entire vocabulary.  A softmax layer is used to generate the distribution.  The model can\nbe trained using a text corpus.  CE loss is used based on if the model predicted the next word correctly. \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n The word2vec model is used to contruct short, dense vectors/embeddings that show useful semantic properties. \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n We can measure the similarity of two words by taking the cosine of the angle between the two vectors. The cosine can \nbe based on the dot product of the vectors.  This has the problem of favoring long vectors, so to account for this we take the normalized dot product:  $$cosine(v, w) = \\frac{v \\cdot w}{|v||w|} $$ \ngiven vector length: $$|v| = \\sqrt{\\sum_{i=1}^N v_i^2}$$\n\n## SLP Chapter 6.8 Word2vec\n Embeddings are short dense vectors where the number of dimensions ranges from 50-1000 and the values are real-valued numbers that can be negative. \nWord2Vec is a software package for determining these embeddings.  They are static embeddings meaning one fixed embedding is learned for each word.\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n These embeddings can be used to determine similarity between words.  First-order co-occurence are near each other and second-order have similar neighbors.\n \n\n## SLP Chapter 6.11 Bias and Embeddings\n Embeddings have the potential to amplify bias. Debiasing can be employed to reduce bias, but it cannot eliminate it.\n\n## SLP Chapter 6.12 Evaluating Vector Models\n A common method for evaluating vector models is by similarity.  This computes the correlation between the algo's similarity scores and similarity ratings \ncreated by humans. \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Leixical semantics** - The study of word meaning\n* **Word sense** - The aspects of the meaning of a word\n* **Polysemous** - words can have multiple senses\n* **Word sense disambiguation** - determine the sense of a word given some context\n* **Sentiment** - positive or negative connotation evalutaion\n* **Vector semantics** - a standard way or representing word meaning using a vector space\n* **Embeddings** - vectors for the representation of words\n* **Term-document matrix** - table where each row is a word and each column is document, cells count appears of word in doc\n* **Information retrieval** - find a document that best matches some query\n* **Representational harm** - a harm caused by demaning or ignoring some social group\n* **Teacher forcing** - the model is given the correct history sequence, rather than basing training on its own output\n* **Weight tying** - combines a single set of embeddings at input with softmax to avoid redundency\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}