{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Midterm2.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 = \\dfracc{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": "0fdf7c25-4da1-401c-f1ee-885f5be534af"
      },
      "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": 122,
      "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": "5d2a4959-cd64-4dd3-c613-d662862bff6f"
      },
      "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": 123,
      "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 = \"Paul Lin\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 124,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "-Project Formulation: agent with available actions $a$, at state $s$, going to state $s'$ with uncertain probability\n",
        "- $P(s'|s,a)$: probability that $s$ reaches $s'$ after taking $a$\n",
        "- $P(RESULT(a)=s') = \\sum_s (P(s) * P(s'|s, a))$, where $P(s'|s, a)$ is probability that $s$ reaches $s'$ after taking $a$\n",
        "- $EU(a) = \\sum_{s'} P(RESULT(a)=s') * U(s')$\\n\n",
        "-Maximum Expected Utility (MEU): agent choses action maximizing EU\n",
        "-Characteristic: formalizes what agent \"should do\", but not operalization\n",
        "\"\"\"\n",
        "\n",
        "chapter16_2 = \"\"\"\n",
        "-Lottery:\n",
        "- Function: $L = [p_1, S_1; p_2, S_2; ... p_n, S_n]$\n",
        "- Components: outcomes $S_1, ... S_n$ and probabilities $p_1, ..., p_n$\\n\n",
        "-Axioms of Utility Theory\n",
        "- Orderability: $A > B, B > A, or A ~ B$ must hold\n",
        "- Transitivity: $(A > B) ^ (B > C) => (A > C)$\n",
        "- Continuity: $A > B > C \\exists p ([p, A; 1 - p, C] ~ B)$\n",
        "- Substitutability: $A ~ B => [p, A; 1 - p, C] ~ [p, B; 1 - p, C]$\n",
        "- Monotonicity: $A > B => (p > q <-> [p, A; 1 - p, B] > [q, A; 1 - q, B])$\n",
        "- Decomposability:\\n\n",
        "-Existence of Utility Function: if agent obeys axioms, there exists a function U such that $U(A) > U(B)$ iff A > B and $U(A) = U(B)$ iff A=B\\n \n",
        "-Expected Utility of Lottery: utility of lottery is sum of probability * outcome such that $U(L) = \\sum_{i}p_i * U(S_i)$\\n\n",
        "-Utility Function: exists for all rational agent, not necessarily unique (e.g.: can transform with adding constant)\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "-Utility Scales: for each prize $S$, alter $p$ until agent indifferent between $U(S)$ and standard lottery\\n\n",
        "-Risk: risk-adverse (logartihmic), risk-neutral (linear), risk-seeking (S-Shape)\\n\n",
        "-Bias: selecting action with highest utility, estimates are overly optimistic\\n\n",
        "-Human Judgement: normative theory (how agent should act) vs descriptive theory (how humans actually act)\\n\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "-Utility Function: depends on environmental history since decision problem is sequential\\n\n",
        "-MDP\n",
        "- Characteristics: fully observable, stochastic environment, Markovian transtion, additive rewards, sequential decision problems\n",
        "- Consists: set of states, set of actions, transition model, reward function, initial state\\n\n",
        "-Horizons: \n",
        "- finite: fixed time N and game over afteward, optimal policy depend on time left, policy is nonstationary\n",
        "- infinite: policy is stationary\\n\n",
        "-Discount Factors: near term reward > long term reward, interest rate (better to get soon), uncertainty in true reward, infinity scenarios\\n\n",
        "-Policy & Time Scenarios: discount reward ($\\dfrac{R_{max}}{1 - Y}$), proper policy (compare), infinite (average reward / time step)\\n\n",
        "-Expected Utility: $U(S) = \\sum_ {t=0} ^\\infty Y^tR(S_t, \\pi(S_t), S_{t+1})$\\n\n",
        "-Infinite Horizons and Discount Utility: optimal policy independent of starting state\\n\n",
        "-Bellman Equation: utility of state = transition reward + discounted utility of next state, assuming agent picks optimal action\\n\n",
        "-Q Function: expected utiity of taking action at given state\\n\n",
        "-Equations\n",
        "- Bellman: $U(s) = argmax_{a} Q(s, a) = max_{a} \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU(s')]$\n",
        "- Q-Function / Action-Utility: $Q(s, a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU(s')]$\n",
        "- Shaping Theorem: $R'(s,a,s') = R(s,a,s') + Y\\phi(s') - \\phi(s)$\\n\n",
        "-Representations: dynamic decision networks (DDNS)\n",
        "\"\"\"\n",
        "chapter17_2 = \"\"\"\n",
        "-Bellman Equation: for $n$ states, there are $n$ bellman equation with $n$ unknowns\\n\n",
        "-Value Iteration: simultaneouly apply bellman update to all states at each , solved nonlinear (due to max)\n",
        "- Bellman Update: $U_{i+1}(s) = max_{a}  \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU_i(s')]$ \n",
        "- Policy Loss: $||U^{\\pi_i} - U||$, most agent can lose by executing $\\pi_i$ instead of $pi*$\\n\n",
        "-Policy Iteration: alternate between policy evaluation and policy improvement, not linear (due to no max)\n",
        "- Policy Evaluation: given policy $\\pi_i$, calculate $U_i = U^{\\pi_i}$ (each state's utility as if $\\pi_i$ is executed)\n",
        "- Policy Improvement: calculate new MEU $\\pi_{i+1}$\n",
        "- Update: $U_{i+1}(s) = \\sum_{s'} P(s'|s, \\pi_{i}(s))[R(s,\\pi_i(s),s') + YU_i(s')]$ \n",
        "- Runtime: $O(n^3)$ \\n\n",
        "-Linear Programming: variables as utilities of each state\n",
        "- Minimize all states $s$ where $U(s) >= \\sum_{s'} P(s'|s, a)[R(s,a,s') + YU_i(s')]$\\n\n",
        "-Offline Algorithms: agent compute at each point, not only precomputed information \\n\n",
        "-Real-Time Dynamic Programming (RDTP): for repeated states, re-use sub-MDP\\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "<h3>MDP Formulation</h3>\n",
        "-Quantities\n",
        "- Value (V): expected utility starting in $s$ and acting optimally\n",
        "- Q-State (Q): expected utility starting out from SsS and taking action SaS\n",
        "- Policy ($\\pi$): optimal action from state $s$\\n\n",
        "-Functions:\n",
        "- $Q^*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^*(s')]$\n",
        "- $V^*(s) = max_a Q*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^*(s')]$\\n\n",
        "<h3>Value Iteration</h3>\n",
        "-Idea: iteratively solve set of equations for utility of each state to neighbors\\n\n",
        "-Algorithm: start with all $V_0(s) = 0$, apply $V(s)$ update, repeat until convergence\\n\n",
        "-Complexity: $O(S^2A)$\\n\n",
        "-Convergence Property: converge to unique optimal values (approximations refined towards optimal value & policy converge before values)\n",
        "- Case 1: tree has max depth $M$, $V_m$ has untruncated values\n",
        "- Case 2: $Y < 1$, $V_k$ and $V_{k+1}$ at most $(Y^k)(max|R|)$ different\\n\n",
        "-Issues: $V_{k+1}$ repeats value iteration, value change  ... action's dont, policy converge before values\n",
        "<h3>Policy Iteration</h3>\n",
        "-Main Idea: select actions from q-values not values by alternating between calculating state utility under current policy and improving current policy with respect to current utilities\\n\n",
        "-Algorithm: \n",
        "- Policy evaluation: calculate utility for fixed policy until convergence\n",
        "- Policy improvement: update policy using one-step look ahead with converged utilities as future values\n",
        "- Repeat until convergence\\n\n",
        "-Functions: \n",
        "- $V^*(s) = \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s') + YV^*(s')]$\n",
        "- $\\pi^*(s) = argmax_{a}Q*(s,a) = argmax_{a} \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s') + YV^*(s')]$\n",
        "- Evaluation: $V_{k+1}(s) = \\sum_{s'} T(s,\\pi_i(s),s')[R(s,\\pi_i(s),s') + YV^{\\pi_i}(s')]$\n",
        "- Improvement: $\\pi_{i+1}(s) = argmax_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^{\\pi_i}(s')]$\\n\n",
        "-Complexity: $O(S^2)$ because only one action per state\\n\n",
        "-Comparisons\n",
        "- Value Iteration: every iteration updates values & policy, don't track policy\n",
        "- Policy Iteration: several passes with fixed policy, choose new policy\\n\n",
        "<h3>MEU</h3>\n",
        "-Utility Scales: normalized utility (0, 1), micromorts, QALYs\\n\n",
        "-Money: not behave as utility ... but having money is utility\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"$U(S)$, function giving state a desirability number\",\n",
        "\"expected utility\" : \"$EU(a)$, average utility of outcome\",\n",
        "\"value Function / Ordinal Utility Function\": \"prefernce on states where numbers are irrelevant\",\n",
        "\"orderability\": \"agent cannot avoide deciding preference, must either prefer one or rate as equal\",\n",
        "\"transitivity\": \"if agent prefers A > B and B > C, agent prefers A > C\",\n",
        "\"continuity\": \"if agent prefers A>B>C, exist probability where agent indifferent towards and A ($p$) or C ($1-p$)\",\n",
        "\"substitutability\": \"if agent indifferent/prefer towards A and B, agent indifferent towards more complex lotteries which are same except A & B\",\n",
        "\"monotonicity\": \"if two lotteries have same two possible outcomes A and B and agent prefers A, lottery with higher probability for A is preferred\",\n",
        "\"decomposability\": \"compounded lotteries can be reduced to simpler ones with probability laws\",\n",
        "\"prefernce elicitation\": \"presenting choices to humans and using preferneces to determine utility function\",\n",
        "\"micromort\": \"one in a million chance of death\",\n",
        "\"qaly\": \"quality-adjusted life years\",\n",
        "\"optimizer's curve\": \"choosing highest expected utility causes estiamtes to overestaimte\",\n",
        "\"certainity effect\": \"people attracted to certain gains\",\n",
        "\"markovian\": \"probability of moving from s to s' depends on s only, not history\",\n",
        "\"policy\": \"solution of what agent should do at any state\",\n",
        "\"nonstationary\": \"policy that is dependant on time\",\n",
        "\"stationary\": \"policy not dependant on time, only on current state\",\n",
        "\"proper policy\": \"policy that is guarenteed to reach terminal state\",\n",
        "\"contraction\": \"function that after applying, makes to output values closer to one another\",\n",
        "\"asynchronous policy iteration\": \"update subset of states, not all states\",\n",
        "\"markov decision process\": \"sequential decision problems within stochastic environments\",\n",
        "\"transition models\": \"model that specify probability of actions\",\n",
        "\"utility\": \"exepected sum of reward when optimal executed from that state\"\n",
        "}\n",
        "\n",
        "module8_definitions = {key: module8_definitions[key] for key in sorted(module8_definitions.keys())}\n"
      ],
      "execution_count": 125,
      "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": 2904
        },
        "outputId": "ac9b6d09-56b6-4e0c-d7f5-5f0339a214bd"
      },
      "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": 126,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n-Project Formulation: agent with available actions $a$, at state $s$, going to state $s'$ with uncertain probability\n- $P(s'|s,a)$: probability that $s$ reaches $s'$ after taking $a$\n- $P(RESULT(a)=s') = \\sum_s (P(s) * P(s'|s, a))$, where $P(s'|s, a)$ is probability that $s$ reaches $s'$ after taking $a$\n- $EU(a) = \\sum_{s'} P(RESULT(a)=s') * U(s')$\n\n-Maximum Expected Utility (MEU): agent choses action maximizing EU\n-Characteristic: formalizes what agent \"should do\", but not operalization\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n-Lottery:\n- Function: $L = [p_1, S_1; p_2, S_2; ... p_n, S_n]$\n- Components: outcomes $S_1, ... S_n$ and probabilities $p_1, ..., p_n$\n\n-Axioms of Utility Theory\n- Orderability: $A > B, B > A, or A ~ B$ must hold\n- Transitivity: $(A > B) ^ (B > C) => (A > C)$\n- Continuity: $A > B > C \\exists p ([p, A; 1 - p, C] ~ B)$\n- Substitutability: $A ~ B => [p, A; 1 - p, C] ~ [p, B; 1 - p, C]$\n- Monotonicity: $A > B => (p > q <-> [p, A; 1 - p, B] > [q, A; 1 - q, B])$\n- Decomposability:\n\n-Existence of Utility Function: if agent obeys axioms, there exists a function U such that $U(A) > U(B)$ iff A > B and $U(A) = U(B)$ iff A=B\n \n-Expected Utility of Lottery: utility of lottery is sum of probability * outcome such that $U(L) = \\sum_{i}p_i * U(S_i)$\n\n-Utility Function: exists for all rational agent, not necessarily unique (e.g.: can transform with adding constant)\n\n## AIMA Chapter 16.3 Utility Functions\n\n-Utility Scales: for each prize $S$, alter $p$ until agent indifferent between $U(S)$ and standard lottery\n\n-Risk: risk-adverse (logartihmic), risk-neutral (linear), risk-seeking (S-Shape)\n\n-Bias: selecting action with highest utility, estimates are overly optimistic\n\n-Human Judgement: normative theory (how agent should act) vs descriptive theory (how humans actually act)\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n-Utility Function: depends on environmental history since decision problem is sequential\n\n-MDP\n- Characteristics: fully observable, stochastic environment, Markovian transtion, additive rewards, sequential decision problems\n- Consists: set of states, set of actions, transition model, reward function, initial state\n\n-Horizons: \n- finite: fixed time N and game over afteward, optimal policy depend on time left, policy is nonstationary\n- infinite: policy is stationary\n\n-Discount Factors: near term reward > long term reward, interest rate (better to get soon), uncertainty in true reward, infinity scenarios\n\n-Policy & Time Scenarios: discount reward ($\\dfrac{R_{max}}{1 - Y}$), proper policy (compare), infinite (average reward / time step)\n\n-Expected Utility: $U(S) = \\sum_ {t=0} ^\\infty Y^tR(S_t, \\pi(S_t), S_{t+1})$\n\n-Infinite Horizons and Discount Utility: optimal policy independent of starting state\n\n-Bellman Equation: utility of state = transition reward + discounted utility of next state, assuming agent picks optimal action\n\n-Q Function: expected utiity of taking action at given state\n\n-Equations\n- Bellman: $U(s) = argmax_{a} Q(s, a) = max_{a} \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU(s')]$\n- Q-Function / Action-Utility: $Q(s, a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU(s')]$\n- Shaping Theorem: $R'(s,a,s') = R(s,a,s') + Y\\phi(s') - \\phi(s)$\n\n-Representations: dynamic decision networks (DDNS)\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n-Bellman Equation: for $n$ states, there are $n$ bellman equation with $n$ unknowns\n\n-Value Iteration: simultaneouly apply bellman update to all states at each , solved nonlinear (due to max)\n- Bellman Update: $U_{i+1}(s) = max_{a}  \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU_i(s')]$ \n- Policy Loss: $||U^{\\pi_i} - U||$, most agent can lose by executing $\\pi_i$ instead of $pi*$\n\n-Policy Iteration: alternate between policy evaluation and policy improvement, not linear (due to no max)\n- Policy Evaluation: given policy $\\pi_i$, calculate $U_i = U^{\\pi_i}$ (each state's utility as if $\\pi_i$ is executed)\n- Policy Improvement: calculate new MEU $\\pi_{i+1}$\n- Update: $U_{i+1}(s) = \\sum_{s'} P(s'|s, \\pi_{i}(s))[R(s,\\pi_i(s),s') + YU_i(s')]$ \n- Runtime: $O(n^3)$ \n\n-Linear Programming: variables as utilities of each state\n- Minimize all states $s$ where $U(s) >= \\sum_{s'} P(s'|s, a)[R(s,a,s') + YU_i(s')]$\n\n-Offline Algorithms: agent compute at each point, not only precomputed information \n\n-Real-Time Dynamic Programming (RDTP): for repeated states, re-use sub-MDP\n\n\n\n## Module 8 Lecture Notes\n\n<h3>MDP Formulation</h3>\n-Quantities\n- Value (V): expected utility starting in $s$ and acting optimally\n- Q-State (Q): expected utility starting out from SsS and taking action SaS\n- Policy ($\\pi$): optimal action from state $s$\n\n-Functions:\n- $Q^*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^*(s')]$\n- $V^*(s) = max_a Q*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^*(s')]$\n\n<h3>Value Iteration</h3>\n-Idea: iteratively solve set of equations for utility of each state to neighbors\n\n-Algorithm: start with all $V_0(s) = 0$, apply $V(s)$ update, repeat until convergence\n\n-Complexity: $O(S^2A)$\n\n-Convergence Property: converge to unique optimal values (approximations refined towards optimal value & policy converge before values)\n- Case 1: tree has max depth $M$, $V_m$ has untruncated values\n- Case 2: $Y < 1$, $V_k$ and $V_{k+1}$ at most $(Y^k)(max|R|)$ different\n\n-Issues: $V_{k+1}$ repeats value iteration, value change  ... action's dont, policy converge before values\n<h3>Policy Iteration</h3>\n-Main Idea: select actions from q-values not values by alternating between calculating state utility under current policy and improving current policy with respect to current utilities\n\n-Algorithm: \n- Policy evaluation: calculate utility for fixed policy until convergence\n- Policy improvement: update policy using one-step look ahead with converged utilities as future values\n- Repeat until convergence\n\n-Functions: \n- $V^*(s) = \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s') + YV^*(s')]$\n- $\\pi^*(s) = argmax_{a}Q*(s,a) = argmax_{a} \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s') + YV^*(s')]$\n- Evaluation: $V_{k+1}(s) = \\sum_{s'} T(s,\\pi_i(s),s')[R(s,\\pi_i(s),s') + YV^{\\pi_i}(s')]$\n- Improvement: $\\pi_{i+1}(s) = argmax_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^{\\pi_i}(s')]$\n\n-Complexity: $O(S^2)$ because only one action per state\n\n-Comparisons\n- Value Iteration: every iteration updates values & policy, don't track policy\n- Policy Iteration: several passes with fixed policy, choose new policy\n\n<h3>MEU</h3>\n-Utility Scales: normalized utility (0, 1), micromorts, QALYs\n\n-Money: not behave as utility ... but having money is utility\n \n\n## Module 8 Definitions\n* **Asynchronous policy iteration** - update subset of states, not all states\n* **Certainity effect** - people attracted to certain gains\n* **Continuity** - if agent prefers A>B>C, exist probability where agent indifferent towards and A ($p$) or C ($1-p$)\n* **Contraction** - function that after applying, makes to output values closer to one another\n* **Decomposability** - compounded lotteries can be reduced to simpler ones with probability laws\n* **Expected utility** - $EU(a)$, average utility of outcome\n* **Markov decision process** - sequential decision problems within stochastic environments\n* **Markovian** - probability of moving from s to s' depends on s only, not history\n* **Micromort** - one in a million chance of death\n* **Monotonicity** - if two lotteries have same two possible outcomes A and B and agent prefers A, lottery with higher probability for A is preferred\n* **Nonstationary** - policy that is dependant on time\n* **Optimizer's curve** - choosing highest expected utility causes estiamtes to overestaimte\n* **Orderability** - agent cannot avoide deciding preference, must either prefer one or rate as equal\n* **Policy** - solution of what agent should do at any state\n* **Prefernce elicitation** - presenting choices to humans and using preferneces to determine utility function\n* **Proper policy** - policy that is guarenteed to reach terminal state\n* **Qaly** - quality-adjusted life years\n* **Stationary** - policy not dependant on time, only on current state\n* **Substitutability** - if agent indifferent/prefer towards A and B, agent indifferent towards more complex lotteries which are same except A & B\n* **Transition models** - model that specify probability of actions\n* **Transitivity** - if agent prefers A > B and B > C, agent prefers A > C\n* **Utility** - exepected sum of reward when optimal executed from that state\n* **Utility function** - $U(S)$, function giving state a desirability number\n* **Value function / ordinal utility function** - prefernce on states where numbers are irrelevant\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "-Bandit Problem Formulation: given $n$-armed bandit, choose which lever to play on each succesive coin\\n\n",
        "-Bandit Problem Definition\n",
        "- Each arm $M_i$: Markov Reward Process (MDP with only one action $a_i$)\n",
        "- Overall Problem: MDP with state space ($S = S_1 ... S_n$), action ($a_i, ..., a_n$), $T$ updated when $M_i$ selected\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "-Model-Based RL: agent learns transition model of environment to interpret reward and learn utility function\\n\n",
        "-Model-Free RL: agent does not learn transition model\n",
        "- Action-Utility Learning (Q-Learning): agent learns Q-function and given Q-function, agent choses what to do at $s$\\n\n",
        "- Policy Search: agent learns policy that maps from states to action\n",
        "-Passive RL: agent's policy is fixed and task is to learn state utilities, $U^{\\pi}(s)$\\n\n",
        "-Active RL: agent must choose between exploration and exploitation\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "-Start: fully observable, small # of action/state, agent has fixed policy, agent trying to learn utility function\\n\n",
        "-Passive Learning vs Policy Evaluation: similar, but does not know $P(s'|s,a)$ or $R(s,a,s')$\\n\n",
        "- Perform multiple trials: in each trial, keep performing action until at terminal state\n",
        "- Calculate Utility: $U^{\\pi}(s)$ = E[$\\sum_{t=0} ^{\\infty} Y^t R(S_t, \\pi (S_t), S_{t+1})$] where $S_t$ is RV of state reached at time $t$ via policy $\\pi$ starting from $S_0 = s$\\n\n",
        "-Direct Evaluation: state utility is reward-to-go, with each trial providing sample for quantity of each state visited\n",
        "- Example: two samples of 0.80 and 0.88 for state (1,2) ... state utility = 0.84\n",
        "- Issue: ignores constraint that state utility determined by reward and expected utility of successor states ... learns nothing about state until end of trials ... slow convergence\\n\n",
        "-Adaptive Dynamic Programming: learns transition models to take advantage of constraints among state utilities\\n\n",
        "-Temporal Reinforcement Learning: adjust utility estimates towards ideal equilibrium\n",
        "- Transition Model: does not need, just uses environmental supplying connection between neighboring states\n",
        "- Updates: $U^{\\pi}(s) = U^{\\pi}(s) + α(s, \\pi (s), s') + Y*U^{\\pi}(s') - U^{\\pi}(s)] $\n",
        "- Approach: adjust state to agree with observed successor (i.e. if A is .80 and B is .96 and A -> B, then bump A value up)\\n\n",
        "-ADP vs TD\n",
        "- Approach: TD (state agree with observed successor), ADP (state agree with all successor)\n",
        "- Large Transitions: frequency of each successor proportional to probability, TD = ADP\n",
        "- Changes: TD (single adjustment / observed transition), ADP (multiple adjustment / transition)\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "-Active Learning Agent: needs to learn transition model for all actions\\n\n",
        "-GLIE: tries each action in each state for unbounded number of times, no optimal action missed\n",
        "- Method 1: agent choose random action at time step $t$ with probability $\\dfrac{1}{t}$\n",
        "- Method 2: weigh actions not tried often and avoid actions of low utility\\n\n",
        "-Exploration Function: $f(u,n)$ for utility ($u$) and count $n$\n",
        "- Equation: $f(u, n) = R^+$ (if $n < N_e$) and $u$ (otherwise)\n",
        "- Condition: increases with $u$ and decreases with $n$\n",
        "- $U^+$: optimistic estimate of utility, needed to ensure actions leading towards unexplored regions are weighted higher\\n\n",
        "-Safe Exploration: needed to ensure agent doesn't perform irreversible actions\n",
        "- States to avoid: large ngeative rewards, no escape, permanently limited future rewards\\n\n",
        "-Bayesian RL\n",
        "- Idea: assumes with probability $P(h)$ about what true model is\n",
        "- Updates: $\\pi* = argmax_{\\pi} \\sum_h P(h|e) U^{\\pi}_h$\\n\n",
        "-Robust Control Theory\n",
        "- Idea: allow for set of possible models $H$, optimal policy as one giving best outcome in worst case of $H$\n",
        "- Updates: $\\pi* = argmax_{\\pi} min_h U^{\\pi}_h$\\n\n",
        "-Q-Learning\n",
        "- Idea: learn $Q(s,a)$ instead of $U(s)$ where $Q(s,a)$ is expected total discount if agent takes action $a$ and $s$\n",
        "- Bellman Update: $Q(s,a) = Q(s,a) + α(R(s,a,s') + Y max_{a'} Q(s',a') - Q(s,a))$\n",
        "-Usage: flexible, learn to behave well in wide variety of exploration\\n\n",
        "-SARSA\n",
        "- Bellman Update: $Q(s,a) = Q(s,a) + α (R(s,a,s') + Y * Q(s',a') - Q(s,a))$\n",
        "- Q-Learning (off-policy) vs SARSA (on-policy): identifical if always exploitation, SARSA penalizes if exploration\n",
        "- Usage: overall policy is controlled by other agent/program, learn Q-function for what will actually happen ... not agent pick best estimates\n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\"\n",
        "-Approximating Direct Utility: $θ=θ_{i} + α[u_j(s) - U*^_{θ}(s)]$\\n\n",
        "-Approximating Temporal-Difference: converge only for linear features and passive learning, not active and neural nonlinear\\n\n",
        "-Experience Replay: replay trajectories to ensure value function accurate for non-visited parts\\n\n",
        "-Deep RL: RL system that uses deep network\n",
        "- Cons: difficult to get good performance, trained system behaves unpredictably if environment != training data\\n\n",
        "-Reward Shaping Example: reward for contacting ball or advancing goal ... rather than just goal\\n\n",
        "-Hierchial RL: break long action sequences into fewer, smaller pieces\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "-Policy Search Main Idea: twiddle policy as long as performance improves, otherwise, stop\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "<h3>Reinforcement Learning</h3>\n",
        "-Scenario: same as MDP ... except don't know T or R\\n\n",
        "-Model-Based Learning: learn approximate model based on experiences\n",
        "- Step 1: Learn Empircal MDP Model: count outcomes $s'$ for each $s, a$, normalize to get $T(s,a,s')$ estimate, discover $R(s,a,s')$ after experiencing $(s,a,s')$\n",
        "- Step 2: solve learned MDP (value iteration, policy iteration)\\n\n",
        "-Model-Free Learning: compare results of what happened to expected then update values\\n\n",
        "<h3>Passive RL</h3> \n",
        "-Passive RL (learns state values): input (fixed policy), goal (learn state values)\\n\n",
        "-Direct Evaluation\n",
        "- Idea: average observed sample values by acting according to $\\pi$, every visit ... add to sum of discoutned rewards, average samples\\n\n",
        "- Pros: easy to understand, doesn't require $R, T$, often computes correct average values\n",
        "- Cons: waste information about state connection, each stat elearned seperately, long time\\n\n",
        "-Sample-Based Evaluation\n",
        "- Idea: take sample of outcome $s'$ by doing action and average\n",
        "- $V^{\\pi}_{k+1} = \\dfrac{1}{n} \\sum_i sample_i$\n",
        "- $sample_i = R(s, \\pi(s), s'_i) + YV_k^{\\pi}(s'_i)$\\n\n",
        "<h3>Temporal Difference Learning</h3>\n",
        "-Idea (learns state values): learn from every experience, update as go ... not wait for $m$ \\n\n",
        "-Equations\n",
        "- Sample of $V(s)$: $sample = R(s, \\pi(s), s') + YV^{\\pi}(s')$\n",
        "- Update to $V(s)$: $V^{\\pi}(s) = (1 - α)V^\\{pi}(s) + (α)sample$\\n\n",
        "-Exponential Moving Average: $x_n = (1 - α) * x{n-1} + α * x_n$\\n\n",
        "<h3>Active Reinforcement Learning / Q-Learning</h3>\n",
        "-Full Reinforcement Learning (learn optimal oplicy): exploitation vs exploration\\n\n",
        "-Q-Value Iteration: $Q_{k+1}(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + Y*max_{a'} Q_k(s',a')$\\n\n",
        "-Q-Learning: sample-based Q-value iteration to learn $Q(s,a)$ as you go\n",
        "- Recieve sample (s, a, s', r)\n",
        "- New Sample Estimate: $sample = R(s,a,s') + Y * max_{a'}Q(s',a')$\n",
        "- Running Average: $Q(s,a) = (1-α)Q(s,a) + α*sample$\n",
        "-Issues: have to explore enough, eventually decrease learning rate\\n\n",
        "<h3>Exploration vs Exploitation</h3>\n",
        "-Random Action $\\epsilon-greedy$: flip coin, with small probably (act randomly), else (act on current policy)\\n\n",
        "-Exploration Function: explore areas whose badness is not yet etablished\n",
        "<h3>Approximate Q-Learning</h3>\n",
        "-Basic Q-Learning (keep table of all q-value) vs Approximate (only learn for small number of training state)\\n\n",
        "-Linear Value Functions\n",
        "- $V(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)$\n",
        "- $Q(s,a) = w_1f_1(s, a) + w_2f_2(s, a) + ... + w_nf_n(s, a)$\n",
        "- Pros (experienced summed up in few) and Cons (states share feature can have different values)\\n\n",
        "-Q-Learning\n",
        "- $difference = [r + Y*max_{a'}Q(s',a')] - Q(s,a)$\n",
        "- $Q(s,a) = Q(s,a) + α[difference]$\n",
        "- $w_i = w_i + α[difference]*f_i(s,a)$\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"off-Policy Learning\" : \"capable of converging to optimal policy, even when acting suboptimally\",\n",
        "\"regret\": \"measure of total mistake cost (expected rewards - optimal exected rewards)\",\n",
        "\"N-Armed Bandit\": \"slot machine with $n$ levers\",\n",
        "\"reward-to-go\": \"expected total reward from that state onward\",\n",
        "\"greedy agent\": \"agent that greedily takes action that currently believes is optimal\",\n",
        "\"glie\": \"greedy in limit of infinite exploration\",\n",
        "\"absorbing state\": \"state where no actions have affect and cannot recieve rewards\",\n",
        "\"catastrophic forgetting\": \"does so well that forget which areas do poorly\",\n",
        "\"experienec replay\": \"relive negative experiences at regular intervals\",\n",
        "\"credit assignment problem\": \"phenomenon when difficult to make judgements because rewards are sparse\",\n",
        "\"reward shaping\": \"giving agent additional rewards\"\n",
        "}\n",
        "module9_definitions = {key: module9_definitions[key] for key in sorted(module9_definitions.keys())}"
      ],
      "execution_count": 127,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3037
        },
        "outputId": "316a9960-b4f5-49cd-e747-9b9463176e3b"
      },
      "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": 128,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n-Bandit Problem Formulation: given $n$-armed bandit, choose which lever to play on each succesive coin\n\n-Bandit Problem Definition\n- Each arm $M_i$: Markov Reward Process (MDP with only one action $a_i$)\n- Overall Problem: MDP with state space ($S = S_1 ... S_n$), action ($a_i, ..., a_n$), $T$ updated when $M_i$ selected\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n-Model-Based RL: agent learns transition model of environment to interpret reward and learn utility function\n\n-Model-Free RL: agent does not learn transition model\n- Action-Utility Learning (Q-Learning): agent learns Q-function and given Q-function, agent choses what to do at $s$\n\n- Policy Search: agent learns policy that maps from states to action\n-Passive RL: agent's policy is fixed and task is to learn state utilities, $U^{\\pi}(s)$\n\n-Active RL: agent must choose between exploration and exploitation\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n-Start: fully observable, small # of action/state, agent has fixed policy, agent trying to learn utility function\n\n-Passive Learning vs Policy Evaluation: similar, but does not know $P(s'|s,a)$ or $R(s,a,s')$\n\n- Perform multiple trials: in each trial, keep performing action until at terminal state\n- Calculate Utility: $U^{\\pi}(s)$ = E[$\\sum_{t=0} ^{\\infty} Y^t R(S_t, \\pi (S_t), S_{t+1})$] where $S_t$ is RV of state reached at time $t$ via policy $\\pi$ starting from $S_0 = s$\n\n-Direct Evaluation: state utility is reward-to-go, with each trial providing sample for quantity of each state visited\n- Example: two samples of 0.80 and 0.88 for state (1,2) ... state utility = 0.84\n- Issue: ignores constraint that state utility determined by reward and expected utility of successor states ... learns nothing about state until end of trials ... slow convergence\n\n-Adaptive Dynamic Programming: learns transition models to take advantage of constraints among state utilities\n\n-Temporal Reinforcement Learning: adjust utility estimates towards ideal equilibrium\n- Transition Model: does not need, just uses environmental supplying connection between neighboring states\n- Updates: $U^{\\pi}(s) = U^{\\pi}(s) + α(s, \\pi (s), s') + Y*U^{\\pi}(s') - U^{\\pi}(s)] $\n- Approach: adjust state to agree with observed successor (i.e. if A is .80 and B is .96 and A -> B, then bump A value up)\n\n-ADP vs TD\n- Approach: TD (state agree with observed successor), ADP (state agree with all successor)\n- Large Transitions: frequency of each successor proportional to probability, TD = ADP\n- Changes: TD (single adjustment / observed transition), ADP (multiple adjustment / transition)\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n-Active Learning Agent: needs to learn transition model for all actions\n\n-GLIE: tries each action in each state for unbounded number of times, no optimal action missed\n- Method 1: agent choose random action at time step $t$ with probability $\\dfrac{1}{t}$\n- Method 2: weigh actions not tried often and avoid actions of low utility\n\n-Exploration Function: $f(u,n)$ for utility ($u$) and count $n$\n- Equation: $f(u, n) = R^+$ (if $n < N_e$) and $u$ (otherwise)\n- Condition: increases with $u$ and decreases with $n$\n- $U^+$: optimistic estimate of utility, needed to ensure actions leading towards unexplored regions are weighted higher\n\n-Safe Exploration: needed to ensure agent doesn't perform irreversible actions\n- States to avoid: large ngeative rewards, no escape, permanently limited future rewards\n\n-Bayesian RL\n- Idea: assumes with probability $P(h)$ about what true model is\n- Updates: $\\pi* = argmax_{\\pi} \\sum_h P(h|e) U^{\\pi}_h$\n\n-Robust Control Theory\n- Idea: allow for set of possible models $H$, optimal policy as one giving best outcome in worst case of $H$\n- Updates: $\\pi* = argmax_{\\pi} min_h U^{\\pi}_h$\n\n-Q-Learning\n- Idea: learn $Q(s,a)$ instead of $U(s)$ where $Q(s,a)$ is expected total discount if agent takes action $a$ and $s$\n- Bellman Update: $Q(s,a) = Q(s,a) + α(R(s,a,s') + Y max_{a'} Q(s',a') - Q(s,a))$\n-Usage: flexible, learn to behave well in wide variety of exploration\n\n-SARSA\n- Bellman Update: $Q(s,a) = Q(s,a) + α (R(s,a,s') + Y * Q(s',a') - Q(s,a))$\n- Q-Learning (off-policy) vs SARSA (on-policy): identifical if always exploitation, SARSA penalizes if exploration\n- Usage: overall policy is controlled by other agent/program, learn Q-function for what will actually happen ... not agent pick best estimates\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n-Approximating Direct Utility: $θ=θ_{i} + α[u_j(s) - U*^_{θ}(s)]$\n\n-Approximating Temporal-Difference: converge only for linear features and passive learning, not active and neural nonlinear\n\n-Experience Replay: replay trajectories to ensure value function accurate for non-visited parts\n\n-Deep RL: RL system that uses deep network\n- Cons: difficult to get good performance, trained system behaves unpredictably if environment != training data\n\n-Reward Shaping Example: reward for contacting ball or advancing goal ... rather than just goal\n\n-Hierchial RL: break long action sequences into fewer, smaller pieces\n\n\n## Module 9 Lecture Notes\n\n<h3>Reinforcement Learning</h3>\n-Scenario: same as MDP ... except don't know T or R\n\n-Model-Based Learning: learn approximate model based on experiences\n- Step 1: Learn Empircal MDP Model: count outcomes $s'$ for each $s, a$, normalize to get $T(s,a,s')$ estimate, discover $R(s,a,s')$ after experiencing $(s,a,s')$\n- Step 2: solve learned MDP (value iteration, policy iteration)\n\n-Model-Free Learning: compare results of what happened to expected then update values\n\n<h3>Passive RL</h3> \n-Passive RL (learns state values): input (fixed policy), goal (learn state values)\n\n-Direct Evaluation\n- Idea: average observed sample values by acting according to $\\pi$, every visit ... add to sum of discoutned rewards, average samples\n\n- Pros: easy to understand, doesn't require $R, T$, often computes correct average values\n- Cons: waste information about state connection, each stat elearned seperately, long time\n\n-Sample-Based Evaluation\n- Idea: take sample of outcome $s'$ by doing action and average\n- $V^{\\pi}_{k+1} = \\dfrac{1}{n} \\sum_i sample_i$\n- $sample_i = R(s, \\pi(s), s'_i) + YV_k^{\\pi}(s'_i)$\n\n<h3>Temporal Difference Learning</h3>\n-Idea (learns state values): learn from every experience, update as go ... not wait for $m$ \n\n-Equations\n- Sample of $V(s)$: $sample = R(s, \\pi(s), s') + YV^{\\pi}(s')$\n- Update to $V(s)$: $V^{\\pi}(s) = (1 - α)V^\\{pi}(s) + (α)sample$\n\n-Exponential Moving Average: $x_n = (1 - α) * x{n-1} + α * x_n$\n\n<h3>Active Reinforcement Learning / Q-Learning</h3>\n-Full Reinforcement Learning (learn optimal oplicy): exploitation vs exploration\n\n-Q-Value Iteration: $Q_{k+1}(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + Y*max_{a'} Q_k(s',a')$\n\n-Q-Learning: sample-based Q-value iteration to learn $Q(s,a)$ as you go\n- Recieve sample (s, a, s', r)\n- New Sample Estimate: $sample = R(s,a,s') + Y * max_{a'}Q(s',a')$\n- Running Average: $Q(s,a) = (1-α)Q(s,a) + α*sample$\n-Issues: have to explore enough, eventually decrease learning rate\n\n<h3>Exploration vs Exploitation</h3>\n-Random Action $\\epsilon-greedy$: flip coin, with small probably (act randomly), else (act on current policy)\n\n-Exploration Function: explore areas whose badness is not yet etablished\n<h3>Approximate Q-Learning</h3>\n-Basic Q-Learning (keep table of all q-value) vs Approximate (only learn for small number of training state)\n\n-Linear Value Functions\n- $V(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)$\n- $Q(s,a) = w_1f_1(s, a) + w_2f_2(s, a) + ... + w_nf_n(s, a)$\n- Pros (experienced summed up in few) and Cons (states share feature can have different values)\n\n-Q-Learning\n- $difference = [r + Y*max_{a'}Q(s',a')] - Q(s,a)$\n- $Q(s,a) = Q(s,a) + α[difference]$\n- $w_i = w_i + α[difference]*f_i(s,a)$\n\n## Module 9 Definitions\n* **N-armed bandit** - slot machine with $n$ levers\n* **Absorbing state** - state where no actions have affect and cannot recieve rewards\n* **Catastrophic forgetting** - does so well that forget which areas do poorly\n* **Credit assignment problem** - phenomenon when difficult to make judgements because rewards are sparse\n* **Experienec replay** - relive negative experiences at regular intervals\n* **Glie** - greedy in limit of infinite exploration\n* **Greedy agent** - agent that greedily takes action that currently believes is optimal\n* **Off-policy learning** - capable of converging to optimal policy, even when acting suboptimally\n* **Regret** - measure of total mistake cost (expected rewards - optimal exected rewards)\n* **Reward shaping** - giving agent additional rewards\n* **Reward-to-go** - expected total reward from that state onward\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "-Marginilization: $P(Y) = \\sum_z P(Y,z)$\\n\n",
        "-Conditioning: $P(Y) = \\sum_Z P(Y|Z)P(Z)$\"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "-Full Joint Distribution: $P(Cause, Effect_1, ..., Effect_n = P(Cause) \\pi_i P(Effect_i | Cause)$\\n\n",
        "-Inference from Joint: $P(Cause|e) = α P(Cause) \\pi_c P(e_j | Cause)$\n",
        "- Meaning: for each pausible cause, multiply prior probability of cause by product of conditional probabilities of observed effects given the clause\n",
        "- Runtime: linear (observed effects), does not depend on unobserved effects$\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\"\n",
        "-Maximum Likeliehood Estimation: $P(w_n | w_{n-N+1:n-1}) = \\dfrac{C(w_{n-N+1:n-1} w_n)}{C(w_{n-N+1:n-1})}$\\n\n",
        "-Relative Frequency: ratio of observed frequency of sequence / observed fequency of prefix\\n\n",
        "-Bigram for sentence: $P(<s> | I want english food) = P(i|<s>)P(want|i)P(english|want)P(food|english)$\n",
        " \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" \n",
        "-Perplxity: $(\\Pi_{i=1} ^ N \\dfrac{1}{P(w_i | w_{i-1})})^{1/N}$\n",
        "- Idea: weighted average branching factor\n",
        "- Trend: higher conditional probability, lower perplexity, higher accuracy\n",
        "- Example: 123456789 has higher perplexity than 00000000001\n",
        " \"\"\"\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "Unigram Sampling: assign each word some spac between 0 and 1 (i.e.: the is 0 - .06, of is 0.06 - 0.09)\n",
        "\"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "-Dialect and Genre: create specific models fore each\\n\n",
        "-Unknown words & zeros: replace with <UNK>\n",
        "- Method 1: turn to closed vocabary by treating <UNK> like any other word\n",
        "- Method 2: replace words in training data by <UNK> based on frequency (replace all words less than $n$ times)\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "-Laplace smoothing: add one to all n-gram counts before normalization, $P(w_n | w_{n-1}) | \\dfrac{C(w_{n-1}w)n) + 1}{C(w_{n-1}) + V}$\\n\n",
        "-Add-k smoothing: add fraction count $k$, $P(w_n | w_{n-1}) | \\dfrac{C(w_{n-1}w)n) + k}{C(w_{n-1}) + kV}$\\n\n",
        "-Backoff and Interpolation: use less context (change from trigram to bigram)\n",
        "- Backoff: use trigram if sufficient, otherwise bigram, otherwise unigram\n",
        "- Interpolation: mix probability estimates from all nn-ram estimator and weigh combinations\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "-Shrink large models: pruning by only storing n-gram with count greater than threshold\\n\n",
        "-Bloom Filters: sorted arrays with combine probabilities\\n\n",
        "-Stupid Backoff: doesn't do true probability distribution, backdown to lower order n-gram\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"<h3>Probability</h3>\n",
        "-General Situations: \\n\n",
        "- Observed Variables (evidence): agent knows certain things about state of world\n",
        "- Unobserved Variables (state): agent needs to reason for\n",
        "- Model: agent knows how known and unknown variables relate to another\\n\n",
        "-Random Variable Example: R (is it Raining), U (carrying umbrella?)\\n\n",
        "-Probability Rules\n",
        "- Probability of world between 0 and 1: $0 <= P(w) <=1$ for all $w$\n",
        "- Total probability of all worlds is 1: $\\sum_w P(w) = 1$\n",
        "- Conditional Probability: $P(a|b) = \\dfrac{P(a,b)}{P(b)}$\n",
        "- Product Rule: $P(y)P(x|y) = P(x,y)$\n",
        "- Chain Rule: $P(x_1,x_2,...x_n$ = \\Pi_i P(x_i|x_1 ... x_{i-1})$\n",
        "- Bayes Rue: $P(x|y) = \\dfrac{P(y|x)}{P(y)}P(x)$\\n\n",
        "<h3>Distributions</h3> \n",
        "-Joint Distributions\\n\n",
        "- for RV $X_1, X_2, ..., X_n$: $P(X_1 = x_1, X_2 = x_2, ..., X_n = x_n) = P(x_1, x_2, ... , x_n)$\n",
        "- Space Complexity: for $n$ variables and domain size $d$: $d^n$\\n\n",
        "-Probabilistic Model\n",
        "- Marginilization: combine collapsed row by adding (from probabilistic model to marginal distributions)\\n\n",
        "<h3>Probabilistic Inference and Rules</h3>\n",
        "-Goal: use known probabilities to compute desired probabilities, find $(Q|e_1, ..., e_k)$\n",
        "-General Case:\\n\n",
        "- Evidence (known) Variables: $E_1, ..., E_k = e_1, ..., e_k$\n",
        "- Query (want to reason about) Variables: $Q$\n",
        "- Hidden (not observed) Variables: $H_1, ..., H_r$\\n\n",
        "-Steps:\n",
        "- Step 1: select entries consistent with variables\n",
        "- Step 2: sum out $H$ to get join of query and evidence: $P(Q|e_1, ..., e_k) = \\sum_h P(Q, h_1 ... h_r, e_1 ... e_k)$\n",
        "- Step 3: normalize: $Z = \\sum_q P(Q, e_1 ... e_k)$, $P(Q|e_1, ..., e_k) = \\dfrac{1}{Z} P(Q, e_1 ... e_k)$\\n\n",
        "<h3>Probabilistic Language Models</h3>\n",
        "-Goal\\n\n",
        "- Idea: assign probability to sentence (e.g.: autocomplete, translation, spelling, speech)\n",
        "- Formula: $P(w_5|w_1,w_2,w_3,w_4)$\n",
        "-Estimating Probabilities\n",
        "- Count and Divide: does not work because specific configuration may never show up, would need large dataset\n",
        "- Markov Assumption: depend on current state by looking at previous $k$ word, not whole context (history)\\n\n",
        "-History\n",
        "- Unigram (no history): $P(w_1w_2...w_n) = \\pi_iP(w_i)$\n",
        "- Bigram (1-word history): $P(w_i | w_1w_2...w_{i-1}) = P(w_i | w_{i-1}) = \\dfrac{c(w_{i-1},w_i)}{c(w_{i-1 })}$\\n\n",
        "-MLE Issues and Solutions\n",
        "- Out of Vocabulary (OOV) items: replace with $<unk>$\n",
        "- Fixed lexicon $L$ of size $V$: normalize training data by replacing word not in $L$ with $<unk>$\n",
        "- Smalll space: convert to logspace\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"random variable\" : \"aspect of world with uncertainty\",\n",
        "\"distribution\": \"table of probability values\",\n",
        "\"probabilistic model\": \"join distribution over set of RV\",\n",
        "\"outcomes\": \"assignments to probabilistic models\",\n",
        "\"event\": \"set of outcomes\",\n",
        "\"marginal distributions\": \"sub-tables of probabilistic model that eliminate variables\",\n",
        "\"conditional distributions\": \"probability distributions for some variables where others are fixed\",\n",
        "\"language model\": \"model that computes probability of upcoming word or sequence of words\",\n",
        "\"belief state\": \"representation of set of all possible world states\",\n",
        "\"exttrinsic evaluation\": \"embedding into application and measure application improvement\",\n",
        "\"intrinsic evaluation\": \"measure model quality without application\",\n",
        "\"perplexity\": \"inverse probability of test set\",\n",
        "\"oon rate\": 'percent of OOV words appearing in test set',\n",
        "\"smoothing / discounting\": \"remove a bit from probability mass from frequent events to never seen events\"\n",
        "}\n",
        "\n",
        "module10_definitions = {key: module10_definitions[key] for key in sorted(module10_definitions.keys())}"
      ],
      "execution_count": 129,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2810
        },
        "cellView": "form",
        "outputId": "af3380f6-beef-4d2b-d4ad-e25f3eabfebb"
      },
      "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": 130,
      "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 Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n-Marginilization: $P(Y) = \\sum_z P(Y,z)$\n\n-Conditioning: $P(Y) = \\sum_Z P(Y|Z)P(Z)$\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\n-Full Joint Distribution: $P(Cause, Effect_1, ..., Effect_n = P(Cause) \\pi_i P(Effect_i | Cause)$\n\n-Inference from Joint: $P(Cause|e) = α P(Cause) \\pi_c P(e_j | Cause)$\n- Meaning: for each pausible cause, multiply prior probability of cause by product of conditional probabilities of observed effects given the clause\n- Runtime: linear (observed effects), does not depend on unobserved effects$\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n\n-Maximum Likeliehood Estimation: $P(w_n | w_{n-N+1:n-1}) = \\dfrac{C(w_{n-N+1:n-1} w_n)}{C(w_{n-N+1:n-1})}$\n\n-Relative Frequency: ratio of observed frequency of sequence / observed fequency of prefix\n\n-Bigram for sentence: $P(<s> | I want english food) = P(i|<s>)P(want|i)P(english|want)P(food|english)$\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n-Perplxity: $(\\Pi_{i=1} ^ N \\dfrac{1}{P(w_i | w_{i-1})})^{1/N}$\n- Idea: weighted average branching factor\n- Trend: higher conditional probability, lower perplexity, higher accuracy\n- Example: 123456789 has higher perplexity than 00000000001\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\nUnigram Sampling: assign each word some spac between 0 and 1 (i.e.: the is 0 - .06, of is 0.06 - 0.09)\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n-Dialect and Genre: create specific models fore each\n\n-Unknown words & zeros: replace with <UNK>\n- Method 1: turn to closed vocabary by treating <UNK> like any other word\n- Method 2: replace words in training data by <UNK> based on frequency (replace all words less than $n$ times)\n\n\n## SLP Chapter 3.5 Smoothing\n\n-Laplace smoothing: add one to all n-gram counts before normalization, $P(w_n | w_{n-1}) | \\dfrac{C(w_{n-1}w)n) + 1}{C(w_{n-1}) + V}$\n\n-Add-k smoothing: add fraction count $k$, $P(w_n | w_{n-1}) | \\dfrac{C(w_{n-1}w)n) + k}{C(w_{n-1}) + kV}$\n\n-Backoff and Interpolation: use less context (change from trigram to bigram)\n- Backoff: use trigram if sufficient, otherwise bigram, otherwise unigram\n- Interpolation: mix probability estimates from all nn-ram estimator and weigh combinations\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n-Shrink large models: pruning by only storing n-gram with count greater than threshold\n\n-Bloom Filters: sorted arrays with combine probabilities\n\n-Stupid Backoff: doesn't do true probability distribution, backdown to lower order n-gram\n \n\n## Module 10 Lecture Notes\n<h3>Probability</h3>\n-General Situations: \n\n- Observed Variables (evidence): agent knows certain things about state of world\n- Unobserved Variables (state): agent needs to reason for\n- Model: agent knows how known and unknown variables relate to another\n\n-Random Variable Example: R (is it Raining), U (carrying umbrella?)\n\n-Probability Rules\n- Probability of world between 0 and 1: $0 <= P(w) <=1$ for all $w$\n- Total probability of all worlds is 1: $\\sum_w P(w) = 1$\n- Conditional Probability: $P(a|b) = \\dfrac{P(a,b)}{P(b)}$\n- Product Rule: $P(y)P(x|y) = P(x,y)$\n- Chain Rule: $P(x_1,x_2,...x_n$ = \\Pi_i P(x_i|x_1 ... x_{i-1})$\n- Bayes Rue: $P(x|y) = \\dfrac{P(y|x)}{P(y)}P(x)$\n\n<h3>Distributions</h3> \n-Joint Distributions\n\n- for RV $X_1, X_2, ..., X_n$: $P(X_1 = x_1, X_2 = x_2, ..., X_n = x_n) = P(x_1, x_2, ... , x_n)$\n- Space Complexity: for $n$ variables and domain size $d$: $d^n$\n\n-Probabilistic Model\n- Marginilization: combine collapsed row by adding (from probabilistic model to marginal distributions)\n\n<h3>Probabilistic Inference and Rules</h3>\n-Goal: use known probabilities to compute desired probabilities, find $(Q|e_1, ..., e_k)$\n-General Case:\n\n- Evidence (known) Variables: $E_1, ..., E_k = e_1, ..., e_k$\n- Query (want to reason about) Variables: $Q$\n- Hidden (not observed) Variables: $H_1, ..., H_r$\n\n-Steps:\n- Step 1: select entries consistent with variables\n- Step 2: sum out $H$ to get join of query and evidence: $P(Q|e_1, ..., e_k) = \\sum_h P(Q, h_1 ... h_r, e_1 ... e_k)$\n- Step 3: normalize: $Z = \\sum_q P(Q, e_1 ... e_k)$, $P(Q|e_1, ..., e_k) = \\dfrac{1}{Z} P(Q, e_1 ... e_k)$\n\n<h3>Probabilistic Language Models</h3>\n-Goal\n\n- Idea: assign probability to sentence (e.g.: autocomplete, translation, spelling, speech)\n- Formula: $P(w_5|w_1,w_2,w_3,w_4)$\n-Estimating Probabilities\n- Count and Divide: does not work because specific configuration may never show up, would need large dataset\n- Markov Assumption: depend on current state by looking at previous $k$ word, not whole context (history)\n\n-History\n- Unigram (no history): $P(w_1w_2...w_n) = \\pi_iP(w_i)$\n- Bigram (1-word history): $P(w_i | w_1w_2...w_{i-1}) = P(w_i | w_{i-1}) = \\dfrac{c(w_{i-1},w_i)}{c(w_{i-1 })}$\n\n-MLE Issues and Solutions\n- Out of Vocabulary (OOV) items: replace with $<unk>$\n- Fixed lexicon $L$ of size $V$: normalize training data by replacing word not in $L$ with $<unk>$\n- Smalll space: convert to logspace\n\n\n## Module 10 Definitions\n* **Belief state** - representation of set of all possible world states\n* **Conditional distributions** - probability distributions for some variables where others are fixed\n* **Distribution** - table of probability values\n* **Event** - set of outcomes\n* **Exttrinsic evaluation** - embedding into application and measure application improvement\n* **Intrinsic evaluation** - measure model quality without application\n* **Language model** - model that computes probability of upcoming word or sequence of words\n* **Marginal distributions** - sub-tables of probabilistic model that eliminate variables\n* **Oon rate** - percent of OOV words appearing in test set\n* **Outcomes** - assignments to probabilistic models\n* **Perplexity** - inverse probability of test set\n* **Probabilistic model** - join distribution over set of RV\n* **Random variable** - aspect of world with uncertainty\n* **Smoothing / discounting** - remove a bit from probability mass from frequent events to never seen events\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "-Bayes Net Definition\n",
        "- Node: random variable (discrete or continuous)\n",
        "- Directed Link: connect pairs of node (X directly influence on Y)\n",
        "- Probability Information: each node $X_i$ has probability information $P(X_i|Parents(X_i))$\\n\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "-Syntax: $n$ variables ($X_1, ... X_n$) and predicting joint distribution $P(x_1, ..., x_n)$\\n\n",
        "- $P(x_1,...,x_n) = \\pi_{i=1} ^ n P(x_i | parents(X_i))$\n",
        "- Ex: $P(j,m,a, !=b, !=e) = P(j|a)P(m|a)P(a|!=b, != e)P(!=b)P(!=e)$\\n\n",
        "-Constructing Bayesian Networks\n",
        "- Step 1: use product rule to rewrite distribution in terms of joint probabilities via product rule\n",
        "- Step 2: use chain rule to reduce joint probability to conditional probability and joint probability on smaller set ot of variables\n",
        "- Step 3: for each parent, insert link from parent to $X_i$ then write conditional probality table of $P(X_i | Parents(X_i))$\\n\n",
        "-Compactness: leave out links with slight dependence (slight gain in accuracy not worth complexity)\\n\n",
        "-Node Ordering: affects Bayes Net structure\\n\n",
        "-Conditional Independence: conditionally independent with non-descendant, given parent\\n\n",
        "-Markov Blanket: node conditionally indepednent of all other nodes, given markov blanket\\n\n",
        "-Z D-Seperation Algorithm: set of nodes (X) is conditionally independent of another set (Y), given Z\n",
        "- Step 1: consider ancestral subgraph of X, Y, Z and ancestors\n",
        "- Step 2: add links between unlinked pair of nodes shairng common graph\n",
        "- Step 3: replace directed link with undirected links\n",
        "- Step 4: If Z blocks all paths between X and Y (d-seperate / not conditionally independent)\\n\n",
        "-Efficient Distribution\n",
        "- Deterministic Nodes: relationship of parents (Canada, US, Mexico) and child (NA)\n",
        "- CSI: P(Damage|Ruggedness,Accident) = if (accident=false) then $d_1$ else $d_2$(Ruggedness)\n",
        "- Noisy-OR: Fever true iff Cold, Flu, or Malaria\\n\n",
        "-Continuous Variables: discretization (divide values into intervals), probabilty density functions (Gaussian)\n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "-Formula: $P(X|e) = \\sum_{y} P(X,e,y)$ where $X$ (query), $e$ (evidence), $y$ (hidden)\\n\n",
        "-Example: $P(B|j,m) = \\sum_{e} \\sum_{a} P(B,j,m,e,a)$\\n\n",
        "-Runtime: naive ($n2^n$) and simplified ($2^n$)\\n\n",
        "-Enumeration-Ask Algrithm: DFS, left-to-right recursion\n",
        "- Complexity: space ($O(n)$) and time $O(2^n)$\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "<h3>Independence</h3>\n",
        "-Independence: $P(x,y) = P(x)P(y)$, $P(x|y)=P(x)$\\n\n",
        "-Conditional Independence: if X is conditionally independent of Y given Z\n",
        "- Not Independence Formula: $P(x|y,z) = \\dfrac{P(z)P(x,y|z)}{p(y,z)}$\n",
        "- Formulas: $P(x,y|z) = P(x|z)P(y|z)$ and $P(x|z,y)=P(x|z)$\n",
        "- Definition: after seeing Z, then know X and Y are independent of each other\\n\n",
        "- Example: P(Alarm, Fire | Smoke), normally Alarm and Fire not independent, but after knowing smoke, they are \\n\n",
        "-Decomposition for P(Traffic, Rain, Umbrella)\n",
        "- Trivial: =P(Rain)P(Traffic|Rain)P(Umbrella|Rain,Traffic)\n",
        "- With Conditional Independence: P(Rain)P(Traffic|Rain)P(Umbrella|Rain)\\n\n",
        "<h3>Bayes Net Properties</h3>\n",
        "-Problems with Full Joint Distribution Tables as Probabilistic Models\\n\n",
        "- Too big to represent\n",
        "- Hard to learn empirically about more than few variables at a time\\n\n",
        "-Bayes Net: uses simple, local distributions ... can also chain together to give global interactions\\n\n",
        "-Components (DAG)\n",
        "- Nodes (one for variables with domains): can be assigned (observed) or unassigned (unobserved)\n",
        "- Arcs (interactions): conditional independence / causation between variables\n",
        "- Collection of distribution over X, one for each combination of parents' value $P(X|a_1...a_n)$\\n\n",
        "-Probabilities in BNs: $P(x_1,x_2,...x_n) = \\pi_{i=1} ^ n P(x_i | parents(x_i))$\\n\n",
        "-Causality\n",
        "- Not necessary ... but when do: simpler, easier to think about, easier to elicit from experts\n",
        "- Correlation (not causation): root dripping and traffic (missing rain)\n",
        "- Arrows: topology encodes caonditional independence (not casual structure)\\n\n",
        "-Size: Joint Distribution ($2^N$) vs Bayes with $k$ parents ($N*2^{k+1}$) (for each variable, has T/F for self and all $k$ parents)\\n\n",
        "-Assumptions: conditional independence\\n\n",
        "<h3>Reachability and Paths</h3>\n",
        "-Cases\\n\n",
        "- Causal Chain: X -> Y -> Z (X not guarenteed to be independent of Z ... but X independent of Z given Y)\\n\n",
        "- Common Cause: Y -> X & Y -> Z (X not guarenteed to be independent of Z ... but X independent of Z given Y)\\n\n",
        "- Common Effect: X -> Z & Y -> Z (X and Y independent ... but X and Y not independent given Z)\\n\n",
        "-Failure of just trying to find path between two variables: doesn't handle \"V\" case from Common Effect\\n\n",
        "-Shaded vs Unshaded: observed / have evidence / on right side of | in probability (shaded) vs unobserved (unshaded)\\n\n",
        "-Active vs Inactive: there can still be influence (active) vs no influence (inactive)\\n\n",
        "<h3>D-Seperation Algorithm</h3>\n",
        "-Goal: are $X_i$ and $X_j$ conditionally independent given ${X_{k1}, ... X_{kn}}$\\n\n",
        "-Process: check all paths from $X_i$ to $X_j$\\n\n",
        "-Active\n",
        "- Independence (from path): >=1 path active (independent not guarenteed) vs 0 path active (independence is guarenteed)\\n\n",
        "- Path (from triples): active if each triple is active\\n\n",
        "<h3>Inference</h3>\n",
        "-Inference by Enumeration: see Probabilistic Inference and Rules\\n\n",
        "-Infernece by Enumeration in BN: $P(B |+j,+m) = \\sum_{e,a}P(B,e,a,+j,+m)$ ... but too many large variables\n",
        "\"\"\"\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"active Path\" : \"path where all triple is active\",\n",
        "\"inactive Path\": \"path where at least one triple is inactive\",\n",
        "\"infernece\": \"making useful quantity from partial observation\",\n",
        "\"conditional probability Table (CPT)\": \"local probability informatin attached to each node in BN\",\n",
        "\"conditioning case\": \"possible combination of values for parent node only\",\n",
        "\"locally structured\": \"network where each node only interacts with subset of nodes, not all\",\n",
        "\"markov blanket\": \"parent, children, and children's parent of a node\",\n",
        "\"deterministic nodes\": \"node with value specified exactly by parent value (no uncertainty)\",\n",
        "\"context specific independence\": \"conditional distributions where variable is conditionally independent of some parents given values of others\",\n",
        "\"hybrid Bayesian network\": \"network with both discrete and continuous variables\"  \n",
        "}\n",
        "\n",
        "module11_definitions = {key: module11_definitions[key] for key in sorted(module11_definitions.keys())}"
      ],
      "execution_count": 131,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2238
        },
        "cellView": "form",
        "outputId": "91cbf2db-de2f-4304-8d20-c7c1c4b33559"
      },
      "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": 132,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n-Bayes Net Definition\n- Node: random variable (discrete or continuous)\n- Directed Link: connect pairs of node (X directly influence on Y)\n- Probability Information: each node $X_i$ has probability information $P(X_i|Parents(X_i))$\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n-Syntax: $n$ variables ($X_1, ... X_n$) and predicting joint distribution $P(x_1, ..., x_n)$\n\n- $P(x_1,...,x_n) = \\pi_{i=1} ^ n P(x_i | parents(X_i))$\n- Ex: $P(j,m,a, !=b, !=e) = P(j|a)P(m|a)P(a|!=b, != e)P(!=b)P(!=e)$\n\n-Constructing Bayesian Networks\n- Step 1: use product rule to rewrite distribution in terms of joint probabilities via product rule\n- Step 2: use chain rule to reduce joint probability to conditional probability and joint probability on smaller set ot of variables\n- Step 3: for each parent, insert link from parent to $X_i$ then write conditional probality table of $P(X_i | Parents(X_i))$\n\n-Compactness: leave out links with slight dependence (slight gain in accuracy not worth complexity)\n\n-Node Ordering: affects Bayes Net structure\n\n-Conditional Independence: conditionally independent with non-descendant, given parent\n\n-Markov Blanket: node conditionally indepednent of all other nodes, given markov blanket\n\n-Z D-Seperation Algorithm: set of nodes (X) is conditionally independent of another set (Y), given Z\n- Step 1: consider ancestral subgraph of X, Y, Z and ancestors\n- Step 2: add links between unlinked pair of nodes shairng common graph\n- Step 3: replace directed link with undirected links\n- Step 4: If Z blocks all paths between X and Y (d-seperate / not conditionally independent)\n\n-Efficient Distribution\n- Deterministic Nodes: relationship of parents (Canada, US, Mexico) and child (NA)\n- CSI: P(Damage|Ruggedness,Accident) = if (accident=false) then $d_1$ else $d_2$(Ruggedness)\n- Noisy-OR: Fever true iff Cold, Flu, or Malaria\n\n-Continuous Variables: discretization (divide values into intervals), probabilty density functions (Gaussian)\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n-Formula: $P(X|e) = \\sum_{y} P(X,e,y)$ where $X$ (query), $e$ (evidence), $y$ (hidden)\n\n-Example: $P(B|j,m) = \\sum_{e} \\sum_{a} P(B,j,m,e,a)$\n\n-Runtime: naive ($n2^n$) and simplified ($2^n$)\n\n-Enumeration-Ask Algrithm: DFS, left-to-right recursion\n- Complexity: space ($O(n)$) and time $O(2^n)$\n \n\n## Module 11 Lecture Notes\n \n<h3>Independence</h3>\n-Independence: $P(x,y) = P(x)P(y)$, $P(x|y)=P(x)$\n\n-Conditional Independence: if X is conditionally independent of Y given Z\n- Not Independence Formula: $P(x|y,z) = \\dfrac{P(z)P(x,y|z)}{p(y,z)}$\n- Formulas: $P(x,y|z) = P(x|z)P(y|z)$ and $P(x|z,y)=P(x|z)$\n- Definition: after seeing Z, then know X and Y are independent of each other\n\n- Example: P(Alarm, Fire | Smoke), normally Alarm and Fire not independent, but after knowing smoke, they are \n\n-Decomposition for P(Traffic, Rain, Umbrella)\n- Trivial: =P(Rain)P(Traffic|Rain)P(Umbrella|Rain,Traffic)\n- With Conditional Independence: P(Rain)P(Traffic|Rain)P(Umbrella|Rain)\n\n<h3>Bayes Net Properties</h3>\n-Problems with Full Joint Distribution Tables as Probabilistic Models\n\n- Too big to represent\n- Hard to learn empirically about more than few variables at a time\n\n-Bayes Net: uses simple, local distributions ... can also chain together to give global interactions\n\n-Components (DAG)\n- Nodes (one for variables with domains): can be assigned (observed) or unassigned (unobserved)\n- Arcs (interactions): conditional independence / causation between variables\n- Collection of distribution over X, one for each combination of parents' value $P(X|a_1...a_n)$\n\n-Probabilities in BNs: $P(x_1,x_2,...x_n) = \\pi_{i=1} ^ n P(x_i | parents(x_i))$\n\n-Causality\n- Not necessary ... but when do: simpler, easier to think about, easier to elicit from experts\n- Correlation (not causation): root dripping and traffic (missing rain)\n- Arrows: topology encodes caonditional independence (not casual structure)\n\n-Size: Joint Distribution ($2^N$) vs Bayes with $k$ parents ($N*2^{k+1}$) (for each variable, has T/F for self and all $k$ parents)\n\n-Assumptions: conditional independence\n\n<h3>Reachability and Paths</h3>\n-Cases\n\n- Causal Chain: X -> Y -> Z (X not guarenteed to be independent of Z ... but X independent of Z given Y)\n\n- Common Cause: Y -> X & Y -> Z (X not guarenteed to be independent of Z ... but X independent of Z given Y)\n\n- Common Effect: X -> Z & Y -> Z (X and Y independent ... but X and Y not independent given Z)\n\n-Failure of just trying to find path between two variables: doesn't handle \"V\" case from Common Effect\n\n-Shaded vs Unshaded: observed / have evidence / on right side of | in probability (shaded) vs unobserved (unshaded)\n\n-Active vs Inactive: there can still be influence (active) vs no influence (inactive)\n\n<h3>D-Seperation Algorithm</h3>\n-Goal: are $X_i$ and $X_j$ conditionally independent given ${X_{k1}, ... X_{kn}}$\n\n-Process: check all paths from $X_i$ to $X_j$\n\n-Active\n- Independence (from path): >=1 path active (independent not guarenteed) vs 0 path active (independence is guarenteed)\n\n- Path (from triples): active if each triple is active\n\n<h3>Inference</h3>\n-Inference by Enumeration: see Probabilistic Inference and Rules\n\n-Infernece by Enumeration in BN: $P(B |+j,+m) = \\sum_{e,a}P(B,e,a,+j,+m)$ ... but too many large variables\n\n\n## Module 11 Definitions\n* **Active path** - path where all triple is active\n* **Conditional probability table (cpt)** - local probability informatin attached to each node in BN\n* **Conditioning case** - possible combination of values for parent node only\n* **Context specific independence** - conditional distributions where variable is conditionally independent of some parents given values of others\n* **Deterministic nodes** - node with value specified exactly by parent value (no uncertainty)\n* **Hybrid bayesian network** - network with both discrete and continuous variables\n* **Inactive path** - path where at least one triple is inactive\n* **Infernece** - making useful quantity from partial observation\n* **Locally structured** - network where each node only interacts with subset of nodes, not all\n* **Markov blanket** - parent, children, and children's parent of a node\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "-Bayseian Inference: $\\hat{c} = argmax_{c \\exists C}P(c|d) = argmax_{c \\exists C}P(d|c)P(c)$\\n\n",
        "-Components: likelihood $P(d|c)$ and prior $P(c)$\\n\n",
        "-Assumptions: position doesn't matter, naive Bayes assumption\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\"\n",
        "-Sentiment: $\\hat{P} = \\dfrac{N_c}{N_{doc}}$\\n\n",
        "-Word: $\\hat{P}(w_i|c) = \\dfrac{count(w_i,c)}{\\sum_{w \\exists V}count(w,c)}$\"\"\"\n",
        "slp_chapter4_3 = \"\"\"\n",
        "-For sentence \"predictable with no fun\"\n",
        "- Sentences: 5 total, 3 are negative and 2 are positive\n",
        "- Words: 34 total from 5 sentences\\n\n",
        "-Methods\n",
        "- Step 1: Calculate $\\dfrac{N_c}{N_{doc}}$: $P(-1) = 3/5, P(+) = 2/5$\n",
        "- Step 2: Calculate $P(word|-)$ and $P(word|+)$ for each word\n",
        "- Step 2 Example: $P(predictable|-) = \\dfrac{1 + 1}{14 + 20}$ (occurs once in negative, +1 for Laplace)\n",
        "- Step 3: combine words and calculate $P(-)P(S|-)$ and $P(+)P(S|+)$\n",
        " \"\"\"\n",
        "slp_chapter4_4 = \"\"\" \n",
        "-More important of word existance than frequency: use Binary NB, which remove all duplicate words before concateting into single document\\n\n",
        "-Negation: prepend 'NOT_' to logical negation (e.g.: 'NOT_like')\\n\n",
        "-Insufficient Training Data: derive sentiments from sentiment lexicons\n",
        " \"\"\"\n",
        "slp_chapter4_5 = \"\"\" \n",
        " \"\"\"\n",
        "slp_chapter4_6 = \"\"\"\n",
        "\"\"\"\n",
        "slp_chapter4_7 = \"\"\"\n",
        "-Metrics \n",
        "- Precision (TP / (TP + FP)): measure percent of classified positive that are actually positive\n",
        "- Recall (TP / (TP + FN)): measure percent actual positives that are classified as positive\n",
        "- F-Measure (2PR / (P + R)): if $B > 1$ (favor recall) and if $B < 1$ (favor precision)\\n\n",
        "-Multi-class Metrics\n",
        "- Macroaveraging: compute performance for each class, average over classes\n",
        "- Microwaveraging: collect decision for all class into 1 confusion matrix, compute precision and recall from table\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\"\n",
        "-Perform 10-fold in train set, error on test set\"\"\"\n",
        "slp_chapter4_9 = \"\"\"\n",
        "-Comparing performance of classifiers $A$ and $B$ on metric $M$\n",
        "- Performance Difference: $\\delta(x) = M(A,x) - M(B,x)$\n",
        "- Effect Size $\\delta(x)$: bigger (A way better than B), smaller (A only a bit better than B)\n",
        "- Hypothesis: null ($\\delta(x) <= 0$) and alternate ($\\delta(x) > 0$)\\n\n",
        "-Non-Parametric Test: approximate randomnization and bootstrap testing\n",
        " \"\"\"\n",
        "slp_chapter4_10 = \"\"\"\n",
        "-Model Card Component: training algorithm, training data / motivation, intended use/users, model performance across demographic groups\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "<h3>Classification Tasks</h3>\n",
        "-Examples: spam detection, medical diagonsis, essay grading, fraud detection\\n\n",
        "-Model Based Approach: build model, instantiate observed features, query for distributions of labels conditioned on features\\n\n",
        "<h3>Naive Bayes</h3>\n",
        "-Assumption: all features inpendent on each other, only affect level\\n\n",
        "-Learning: probability tables (prior probability and conditional probability)\\n\n",
        "-General Model: $P(Y, F_1...F)n = P(Y)\\pi_{i}P(F_i|Y)$\n",
        "- Number of Values: $|YF^n|$\n",
        "- Number of Parameters: $|nFY|$\\n\n",
        "-Goal: compute $P(Y|f_1...f_n)$\n",
        "- Step 1: compute joint probabiityof label and evidence for each label\n",
        "- Step 2: sum to get probability of evidence\n",
        "- Step 3: normalize by dividing step 1 by step 2\\n\n",
        "-Information (Parameters) needed\n",
        "- $P(Y)$: prior over labels\n",
        "- $P(F_i|Y)$: for each feature (evidence variables)\\n\n",
        "<h3>ML Concepts</h3>\n",
        "-Data: training set, held out set, test set\\n\n",
        "-Experimentation Cycle: learn parameters on training set, tune hyperparameters on held-out set, compute accuracy\\n\n",
        "-Parameter Estimation: distribution of random variables\n",
        "- Elicitation: ask expert / human\n",
        "- Empirically: use training data and calculate count / total sample\\n\n",
        "-Laplace Smoothing: pretend saw $k$ outcome $k$ extra times\n",
        "- Formula: $P = \\dfrac{c(x)+k}{N + k|X|}$, $P = \\dfrac{c(x, y)+k}{y + k|X|}$ (conditional)\n",
        "- Poor Performance: for $P(X|Y)$ when $|X|$ or $|Y|$ is very large\\n\n",
        "-Linear Interpolation: make sures $P(X|Y)$ isn't too diffent from empiral $P(X)$\n",
        "- Formula: $P(x|y) = α P(x|y) + (1-a)P(x)$ where $α$ is weight\n",
        "- $a$ values: $a=1$ weigh only prior probability, $a=1$ weigh only conditional probability\\n\n",
        "<h3>Perceptrons</h3>\n",
        "-Binary Preceptrons\\n\n",
        "- Start weight to 0\n",
        "- For each training instance, classify current weights via $w \\cdott f(x)$\n",
        "- If correct: no change\n",
        "- If incorrect: adjust weight in other direction $w = w - y* \\cdot f$\\n\n",
        "Multiclass Preceptrons\n",
        "- Start weight to 0\n",
        "- For each training instance, classify current weights via $y = argmax_y w_y \\cdot f(x)$\n",
        "- If correct: no change\n",
        "- If incorrect: lower score of wrong answer ($w_y = w_y - f(x)$), raise score of right answer ($w_{y*} = w_{y*} + f(x)$)\\n\n",
        "<h3>SVM</h3>\n",
        "-Preceptron Properties\\n\n",
        "- Linearly-Seperable: will converge (for binary)\n",
        "- Non-Linearly Seperable: mistake bound to margin of mistakes $< \\dfrac{k}{\\delta^2}$ where $\\delta$ is margin\\n\n",
        "-Preceptron Problems\n",
        "- Noise: data not seperable, weights don't converge and thrash (solved by averaging weight over times)\n",
        "- Mediocre generalization: hyperplane isn't the preferred hyperplane\n",
        "- Overtraiing: overfitting\\n\n",
        "-MIRA (Margin Infused Relaxed Algorithm): scale $w$ updates by $τ$\\n\n",
        "- $τ$ Value: $τ = min(\\dfrac{(w_y' - w_{y*}' f + 1)}{2f \\cdot f}, C)$\n",
        "- Update:$w_y = w_y - \tτ * f(x)$ (same for $y*$)\n",
        "- Effects: converge faster, works well for noisy data (reduce thrashing)\\n\n",
        "-Support Vector Machine: maximize marging for support vectors (ignore all other training examples)\\n\n",
        "-Non-Linear Seperator: transform feature space into higher dimensional feature space\\n\n",
        "-Naive Bayes vs Perceptrons / MIRA\n",
        "- Naive Bayes: builds model training data, gives prediction prpbabilities, strong feature independnce assumption, one pass throgh data (count)\n",
        "- Preceptrons: less data assumption, mistake-driven learning, multiple pass through data (prediction), more accurate\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"maximue likelihood estimates\" : \"relative frequencies\",\n",
        "\"generative classifiers\": \"build models of how class appears to most likely generate observations\",\n",
        "\"discriminative classifier\": \"model that learns most important feature to discriminate between different classes\",\n",
        "\"bag-of-words\": \"unordered set of words (ignoring position, focusing on frequency)\",\n",
        "\"naive Bayes Assumption\": \"conditional independence are given for class c\",\n",
        "\"binary Multinomial Naive Bayes\": \"Binary NB\",\n",
        "\"sentiment lexicon\": \"list of words pre-annotated with posiitive/negative sentiment\",\n",
        "\"gold labels\": \"human labels\",\n",
        "\"representational harms\": \"harms caused by system to negatively affect a group\",\n",
        "\"toxicity detection\": \"detecting hate speech and abuse\"\n",
        "}\n",
        "\n",
        "\n",
        "module12_definitions = {key: module12_definitions[key] for key in sorted(module12_definitions.keys())}"
      ],
      "execution_count": 133,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3326
        },
        "outputId": "a4c06545-a014-44e5-e995-dce6de68e16e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 Theory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter  19.6 Linear Regresion and Classification\", 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": 134,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n Your summary here \n\n## AIMA Chapter 19.2 Supervised Learning\n Your summary here \n\n## AIMA Chapter 19.3 Learning Decision Trees\n Your summary here \n\n## AIMA Chapter 19.4 Model Selection and Optimization\n Your summary here \n\n## AIMA Chapter 19.5 Theory of Learning\n Your summary here \n\n## AIMA Chapter  19.6 Linear Regresion and Classification\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n-Bayseian Inference: $\\hat{c} = argmax_{c \\exists C}P(c|d) = argmax_{c \\exists C}P(d|c)P(c)$\n\n-Components: likelihood $P(d|c)$ and prior $P(c)$\n\n-Assumptions: position doesn't matter, naive Bayes assumption\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n-Sentiment: $\\hat{P} = \\dfrac{N_c}{N_{doc}}$\n\n-Word: $\\hat{P}(w_i|c) = \\dfrac{count(w_i,c)}{\\sum_{w \\exists V}count(w,c)}$\n\n## SLP Chapter 4.3 Worked Example\n\n-For sentence \"predictable with no fun\"\n- Sentences: 5 total, 3 are negative and 2 are positive\n- Words: 34 total from 5 sentences\n\n-Methods\n- Step 1: Calculate $\\dfrac{N_c}{N_{doc}}$: $P(-1) = 3/5, P(+) = 2/5$\n- Step 2: Calculate $P(word|-)$ and $P(word|+)$ for each word\n- Step 2 Example: $P(predictable|-) = \\dfrac{1 + 1}{14 + 20}$ (occurs once in negative, +1 for Laplace)\n- Step 3: combine words and calculate $P(-)P(S|-)$ and $P(+)P(S|+)$\n \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \n-More important of word existance than frequency: use Binary NB, which remove all duplicate words before concateting into single document\n\n-Negation: prepend 'NOT_' to logical negation (e.g.: 'NOT_like')\n\n-Insufficient Training Data: derive sentiments from sentiment lexicons\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n \n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n-Metrics \n- Precision (TP / (TP + FP)): measure percent of classified positive that are actually positive\n- Recall (TP / (TP + FN)): measure percent actual positives that are classified as positive\n- F-Measure (2PR / (P + R)): if $B > 1$ (favor recall) and if $B < 1$ (favor precision)\n\n-Multi-class Metrics\n- Macroaveraging: compute performance for each class, average over classes\n- Microwaveraging: collect decision for all class into 1 confusion matrix, compute precision and recall from table\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n-Perform 10-fold in train set, error on test set\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n-Comparing performance of classifiers $A$ and $B$ on metric $M$\n- Performance Difference: $\\delta(x) = M(A,x) - M(B,x)$\n- Effect Size $\\delta(x)$: bigger (A way better than B), smaller (A only a bit better than B)\n- Hypothesis: null ($\\delta(x) <= 0$) and alternate ($\\delta(x) > 0$)\n\n-Non-Parametric Test: approximate randomnization and bootstrap testing\n \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n-Model Card Component: training algorithm, training data / motivation, intended use/users, model performance across demographic groups\n \n\n## Module 12 Lecture Notes\n\n<h3>Classification Tasks</h3>\n-Examples: spam detection, medical diagonsis, essay grading, fraud detection\n\n-Model Based Approach: build model, instantiate observed features, query for distributions of labels conditioned on features\n\n<h3>Naive Bayes</h3>\n-Assumption: all features inpendent on each other, only affect level\n\n-Learning: probability tables (prior probability and conditional probability)\n\n-General Model: $P(Y, F_1...F)n = P(Y)\\pi_{i}P(F_i|Y)$\n- Number of Values: $|YF^n|$\n- Number of Parameters: $|nFY|$\n\n-Goal: compute $P(Y|f_1...f_n)$\n- Step 1: compute joint probabiityof label and evidence for each label\n- Step 2: sum to get probability of evidence\n- Step 3: normalize by dividing step 1 by step 2\n\n-Information (Parameters) needed\n- $P(Y)$: prior over labels\n- $P(F_i|Y)$: for each feature (evidence variables)\n\n<h3>ML Concepts</h3>\n-Data: training set, held out set, test set\n\n-Experimentation Cycle: learn parameters on training set, tune hyperparameters on held-out set, compute accuracy\n\n-Parameter Estimation: distribution of random variables\n- Elicitation: ask expert / human\n- Empirically: use training data and calculate count / total sample\n\n-Laplace Smoothing: pretend saw $k$ outcome $k$ extra times\n- Formula: $P = \\dfrac{c(x)+k}{N + k|X|}$, $P = \\dfrac{c(x, y)+k}{y + k|X|}$ (conditional)\n- Poor Performance: for $P(X|Y)$ when $|X|$ or $|Y|$ is very large\n\n-Linear Interpolation: make sures $P(X|Y)$ isn't too diffent from empiral $P(X)$\n- Formula: $P(x|y) = α P(x|y) + (1-a)P(x)$ where $α$ is weight\n- $a$ values: $a=1$ weigh only prior probability, $a=1$ weigh only conditional probability\n\n<h3>Perceptrons</h3>\n-Binary Preceptrons\n\n- Start weight to 0\n- For each training instance, classify current weights via $w \\cdott f(x)$\n- If correct: no change\n- If incorrect: adjust weight in other direction $w = w - y* \\cdot f$\n\nMulticlass Preceptrons\n- Start weight to 0\n- For each training instance, classify current weights via $y = argmax_y w_y \\cdot f(x)$\n- If correct: no change\n- If incorrect: lower score of wrong answer ($w_y = w_y - f(x)$), raise score of right answer ($w_{y*} = w_{y*} + f(x)$)\n\n<h3>SVM</h3>\n-Preceptron Properties\n\n- Linearly-Seperable: will converge (for binary)\n- Non-Linearly Seperable: mistake bound to margin of mistakes $< \\dfrac{k}{\\delta^2}$ where $\\delta$ is margin\n\n-Preceptron Problems\n- Noise: data not seperable, weights don't converge and thrash (solved by averaging weight over times)\n- Mediocre generalization: hyperplane isn't the preferred hyperplane\n- Overtraiing: overfitting\n\n-MIRA (Margin Infused Relaxed Algorithm): scale $w$ updates by $τ$\n\n- $τ$ Value: $τ = min(\\dfrac{(w_y' - w_{y*}' f + 1)}{2f \\cdot f}, C)$\n- Update:$w_y = w_y - \tτ * f(x)$ (same for $y*$)\n- Effects: converge faster, works well for noisy data (reduce thrashing)\n\n-Support Vector Machine: maximize marging for support vectors (ignore all other training examples)\n\n-Non-Linear Seperator: transform feature space into higher dimensional feature space\n\n-Naive Bayes vs Perceptrons / MIRA\n- Naive Bayes: builds model training data, gives prediction prpbabilities, strong feature independnce assumption, one pass throgh data (count)\n- Preceptrons: less data assumption, mistake-driven learning, multiple pass through data (prediction), more accurate\n\n\n## Module 12 Definitions\n* **Bag-of-words** - unordered set of words (ignoring position, focusing on frequency)\n* **Binary multinomial naive bayes** - Binary NB\n* **Discriminative classifier** - model that learns most important feature to discriminate between different classes\n* **Generative classifiers** - build models of how class appears to most likely generate observations\n* **Gold labels** - human labels\n* **Maximue likelihood estimates** - relative frequencies\n* **Naive bayes assumption** - conditional independence are given for class c\n* **Representational harms** - harms caused by system to negatively affect a group\n* **Sentiment lexicon** - list of words pre-annotated with posiitive/negative sentiment\n* **Toxicity detection** - detecting hate speech and abuse\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"\n",
        "-Components of Probabilistic Machine Learning Classifier\n",
        "- Feature Representation of Input\n",
        "- Classification Function: computing $\\hat{y}$ via $p(x|y)$\n",
        "- Objective Function: cross-entropy loss functions\n",
        "- Algorithm for Optimizing Objective Function: stochastic gradient descent\\n\n",
        "-Functions\n",
        "- Value: $z = (\\sum_{i=1} ^ n w_ix_i) + b$\n",
        "- Sigmoid Function: $\\sigma(z) = \\dfrac{1}{1 + e^{-z}}$\n",
        "- Sigmoid Function Property: $1 - \\sigma(x) = \\sigma(-x)$\\n\n",
        "-Advantages of Logistic > Naive Bayes:\n",
        "- Conditional Independence: strong conditional independence assumed\n",
        "- Correlated Featurs: handled by logistic, multiplied twice by Naive Bayes\n",
        "- Naive Bayes Adv: works well on small datasets, easy to implement, fast to train\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" \n",
        " \"\"\"\n",
        "slp_chapter5_3 = \"\"\" \n",
        "-Loss Functions: $LC(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n",
        "- Conditional Max Likelihood: max log probabiity of true y labels\n",
        "- Cross Entropy Loss: function of negative log likelihood loss\n",
        "\"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "-Gradient Descent\n",
        "- Goal: find weight that minimize loss function, averaged across all samples\n",
        "- Function: $argmin_θ \\dfrac{1}{m} \\sum_{i=1} ^ m LC(f(x^i; θ), y^i)$\n",
        "- Method: find where slop is rising msot steeply, move in opposite direction\\n\n",
        "-Weight Updates\n",
        "- Single: $w^{t+1} = w^{t} - n\\dfrac{d}{dw}L(f(x;w),y)$\n",
        "- Logistic: $\\dfrac{\\delta L(\\hat{y},y)}{\\delta w_j} = [\\sigma (w \\cdot x + b) - y]x_j$\n",
        " \"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "-L2 / Ridge Regularization\n",
        "- Preference: vectors with many small weights\n",
        "- Norm : $R(θ) = ||θ||_2 ^ 2 = \\sum_{j=1} ^ n θ_j ^ 2$\n",
        "- Regularizer: $\\hat{θ} = argmax_{θ} [\\sum_{i=1} ^ m logP(y^i | x^i)] - α \\sum_{j=1} ^ n θ_j ^ 2$\\n\n",
        "-L1 / Lasso Regularization\n",
        "- Prefers: sparse, large weights with many zero vectors\n",
        "- Norm: $R(θ) = ||θ||_1 = \\sum_{j=1} ^ n θ_j$\\n\n",
        "- Regularizer: $\\hat{θ} = argmax_{θ} [\\sum_{i=1} ^ m logP(y^i | x^i)] - α \\sum_{j=1} ^ n |θ_j|$\n",
        "\"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "-Softmax Function: take vector $z$ of $k$ vlaues and map to probability distribution\n",
        "- Function: $softmax(z_i) = \\dfrac{exp(z_i)}{\\sum_{j=1} ^ k exp(z_j)}$\n",
        "- Probability: $p(y=c|x) = \\dfrac{exp(w_c \\cdot x + b_c)}{\\sum_{j=1} ^ K exp(w_j \\cdot x + b_j)}$\\n\n",
        "-Features: seperate weight vector and bias for each of the classes\\n\n",
        "-Learning\n",
        "- Loss: $LC = -logp(y=c|x) $ (see above)\n",
        "- Updates: $\\dfrac{\\delta LC}{\\delta w_{k,i}} = -(1(y-k)-p(y=k|x))x_i$\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" \n",
        "-Activation Functions:\n",
        "- Sigmoid: $y=\\sigma(z)=\\dfrac{1}{1+e^{-z}}$, ranges from 0 to 1\n",
        "- TanH: $y=\\dfrac{e^z - e^{-z}}{e^z + e{-z}}$, ranges from -1 to 1, smoothly differentiable, map outliers to mean\n",
        "- ReLu: $y=max(z,0)$, ranges from 0 to infinity, close to linear, no vanishing gradients\\n\n",
        "-Layer Usage: intermediate (ReLU, tanh) and output (softmax)\n",
        "\"\"\"\n",
        "slp_chapter7_2 = \"\"\"\n",
        "-XOR: not linearly seperable, can only be solved with 2 layer neural network\\n\n",
        "-Linear Layers: multiple layers can be reduced to single linear unit of weights\"\"\"\n",
        "slp_chapter7_3 = \"\"\"\n",
        "-Normalization: often normalize between layers\n",
        "-Replacing Bias Unit: add dummy node to each layer whose value will always be 1\"\"\"\n",
        "slp_chapter7_4 = \"\"\"\"\"\"\n",
        "slp_chapter7_5 = \"\"\"\n",
        "-Neural Language Models vs n-gram\n",
        "- Pros: longer histories, better generalize over context of similar words, more accurate at word-prediction\n",
        "- Cons: slower to train, more complex, less interpretable\\n\n",
        "-Forward Inference\n",
        "- Feature ($O(V)$): window that sees $N$ words in past, each as one-hot vectors\n",
        "- Embedding Matrix ($O(dV)$): column for each word, with each column having $d$ dimensions\n",
        "- Embedding Layer: output of multiplying feature one hot encode and embedding matrix\\n\n",
        "-Algorithm\n",
        "- Step 1: create one-hot vector for each word and multiply by $E$\n",
        "- Step 2: multiply by $W$ and add $b$, pass through ReLu to get hidden layer\n",
        "- Step 3: multiply h by $U$\n",
        "- Step 4: apply softmax so that each node in output layer is probability\n",
        "\"\"\"\n",
        "slp_chapter7_6 = \"\"\"\n",
        "-Activation Function Derivatives\n",
        "- Sigmoid: $\\sigma(z)(1-\\sigma(z))$\n",
        "- Tanh: $1-tanh^2(z)$\n",
        "- ReLu: 0 for z < 0, 1 for z >= 0\\n\n",
        "-Hyperparameters: leanring rate, minibatch size, model archiecture, number f hidden nodes, activation functions\"\"\"\n",
        "slp_chapter7_7 = \"\"\"\n",
        "-Method 1: freezing, hold $E$ constant while modifying $W, U, b$\\n\n",
        "-Method 2: gradient desent + back-propogation to create new $E$\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"<h3>Logistic Regression</h3>\n",
        "-Components of Classifier\\n\n",
        "- Feature Representation: [$x_1,x_2,...,x_n$]\n",
        "- Classification Function: computes $p(y|x)$\n",
        "- Objective Function: minimizing error on training examples\n",
        "- Algorithm for optimizing objective function\\n\n",
        "-Logistic Regression Functions\n",
        "- Z Function: $w \\cdot x + b$\n",
        "- Sigmoid Function: $y = \\dfrac{1}{1 + e ^{-z}}$\n",
        "- Probabilities: $P(y=1)= \\sigma(w \\cdot x + b) = \\dfrac{1}{1 + e ^{-w \\cdot x + b}}$\\n\n",
        "-Multiclass Logistic Regression\n",
        "- Function: $softmax(z_i) = \\dfrac{e^{z_j}}{\\sum_{j=1} ^ k e^{z_j}}$\n",
        "<h3>Loss Functions</h3>\n",
        "-Goal: determine how much $\\hat{Y}$ differes from $y$\n",
        "-Cross Entropy Loss: negative log likelihood loss\n",
        "- Binary: $LC(\\hat{y}, y) = -logp(y|x) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})] =  -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n",
        "- Multiclass: $LC(\\hat{y}, y) = \\sum_{i=1} ^ C y_ilog(\\hat{y})$\n",
        "- Values: correct prediction (lower) vs incorrect (higher)\n",
        "-Loss on All Training: $log\\pi_{i=1} ^ m p(y^i | x^i) = -\\sum_{i=1} ^m (\\hat{y}^i | y^i)$\n",
        "<h3>Stochastic Gradient Descent</h3>\n",
        "-Logistic Regression: convex, one minimum, starting point unimportant\\n\n",
        "-Gradient Types\n",
        "- Stochastic Gradient: choose single random example ... can fluctuate\n",
        "- Mini-batch: small batches ... loss is accumulated\n",
        "- Batch: choose entiredataset ... can take a while\\n\n",
        "-Regularization\n",
        "- Logistic Regression: feature only occurs in one class ... get high weight (but might be accidental)\n",
        "- Regularization: Lasso (L1) an Ridge (L2)\\n\n",
        "<h3>Neural Networks</h3>\n",
        "-Preceptrons: step function is _|-- so quick changes for weights\\n\n",
        "-Activation Functions: sigmoid, tanh, ReLU (close to linear)\\n\n",
        "-Feed-Forward NN: multilayer network, usually fully connected, no cycles, no backpropogation\\n\n",
        "- Multiply weight matrix by input vector $x$\n",
        "- add bias vector $b$\n",
        "- apply activation function to obtain output $h = \\sigma(Wx + b)$\\n\n",
        "-Training Neural Nets: loss function (cross-entropy loss), optimization algorithm (gradient descent), compute gradient of loss (error propogation)\n",
        "-Gradient Computations for one weight: $\\dfrac{\\delta LCE(w,b)}{\\delta wj} = (\\hat{y} - y)xj = (\\sigma(wx + b) - y)x_j$\\n\n",
        "-Chain Rule:\n",
        "- $f(x) = u(v(x))$: $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dx}$\n",
        "- $f(x) = u(v(w(x)))$:  $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dw} \\cdot \\dfrac{dw}{dx}$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Sentiment Classifier\": \"input of futures and use $P(y=1|x)$ to estimate 1 (positive) or 0 (negative)\",\n",
        "\"Gradient Descent\": \"method for minimizing functions\",\n",
        "\"Decision boundary\": \"threshold for cutting of logistic regression\",\n",
        "\"representation learning\": \"methods to learn features automatically (unsupervised) from input\",\n",
        "\"loss function\": \"function that details how much prediction differs from actual\",\n",
        "\"gradient\": \"vector that poitns in direction of greatest increase in function\",\n",
        "\"multi-layer preceptrons\": \"feed-forward networks\",\n",
        "\"forward inference\": \"task that runs a forward pass on network to product probability distribution of outputs\",\n",
        "\"freezing\": \"use word2vec / pretrained algorithm to calculate embedding matrix\"\n",
        "}\n",
        "\n",
        "module13_definitions = {key: module13_definitions[key] for key in sorted(module13_definitions.keys())}\n"
      ],
      "execution_count": 135,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3590
        },
        "outputId": "e827b579-2d68-436b-8a5d-ffc249447a17"
      },
      "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": 136,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n-Components of Probabilistic Machine Learning Classifier\n- Feature Representation of Input\n- Classification Function: computing $\\hat{y}$ via $p(x|y)$\n- Objective Function: cross-entropy loss functions\n- Algorithm for Optimizing Objective Function: stochastic gradient descent\n\n-Functions\n- Value: $z = (\\sum_{i=1} ^ n w_ix_i) + b$\n- Sigmoid Function: $\\sigma(z) = \\dfrac{1}{1 + e^{-z}}$\n- Sigmoid Function Property: $1 - \\sigma(x) = \\sigma(-x)$\n\n-Advantages of Logistic > Naive Bayes:\n- Conditional Independence: strong conditional independence assumed\n- Correlated Featurs: handled by logistic, multiplied twice by Naive Bayes\n- Naive Bayes Adv: works well on small datasets, easy to implement, fast to train\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \n-Loss Functions: $LC(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n- Conditional Max Likelihood: max log probabiity of true y labels\n- Cross Entropy Loss: function of negative log likelihood loss\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n-Gradient Descent\n- Goal: find weight that minimize loss function, averaged across all samples\n- Function: $argmin_θ \\dfrac{1}{m} \\sum_{i=1} ^ m LC(f(x^i; θ), y^i)$\n- Method: find where slop is rising msot steeply, move in opposite direction\n\n-Weight Updates\n- Single: $w^{t+1} = w^{t} - n\\dfrac{d}{dw}L(f(x;w),y)$\n- Logistic: $\\dfrac{\\delta L(\\hat{y},y)}{\\delta w_j} = [\\sigma (w \\cdot x + b) - y]x_j$\n \n\n## SLP Chapter 5.5 Regularization\n\n-L2 / Ridge Regularization\n- Preference: vectors with many small weights\n- Norm : $R(θ) = ||θ||_2 ^ 2 = \\sum_{j=1} ^ n θ_j ^ 2$\n- Regularizer: $\\hat{θ} = argmax_{θ} [\\sum_{i=1} ^ m logP(y^i | x^i)] - α \\sum_{j=1} ^ n θ_j ^ 2$\n\n-L1 / Lasso Regularization\n- Prefers: sparse, large weights with many zero vectors\n- Norm: $R(θ) = ||θ||_1 = \\sum_{j=1} ^ n θ_j$\n\n- Regularizer: $\\hat{θ} = argmax_{θ} [\\sum_{i=1} ^ m logP(y^i | x^i)] - α \\sum_{j=1} ^ n |θ_j|$\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n-Softmax Function: take vector $z$ of $k$ vlaues and map to probability distribution\n- Function: $softmax(z_i) = \\dfrac{exp(z_i)}{\\sum_{j=1} ^ k exp(z_j)}$\n- Probability: $p(y=c|x) = \\dfrac{exp(w_c \\cdot x + b_c)}{\\sum_{j=1} ^ K exp(w_j \\cdot x + b_j)}$\n\n-Features: seperate weight vector and bias for each of the classes\n\n-Learning\n- Loss: $LC = -logp(y=c|x) $ (see above)\n- Updates: $\\dfrac{\\delta LC}{\\delta w_{k,i}} = -(1(y-k)-p(y=k|x))x_i$\n\n\n## SLP Chapter 7.1 Units\n \n-Activation Functions:\n- Sigmoid: $y=\\sigma(z)=\\dfrac{1}{1+e^{-z}}$, ranges from 0 to 1\n- TanH: $y=\\dfrac{e^z - e^{-z}}{e^z + e{-z}}$, ranges from -1 to 1, smoothly differentiable, map outliers to mean\n- ReLu: $y=max(z,0)$, ranges from 0 to infinity, close to linear, no vanishing gradients\n\n-Layer Usage: intermediate (ReLU, tanh) and output (softmax)\n\n\n## SLP Chapter 7.2 The XOR problem\n\n-XOR: not linearly seperable, can only be solved with 2 layer neural network\n\n-Linear Layers: multiple layers can be reduced to single linear unit of weights\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n-Normalization: often normalize between layers\n-Replacing Bias Unit: add dummy node to each layer whose value will always be 1\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n-Neural Language Models vs n-gram\n- Pros: longer histories, better generalize over context of similar words, more accurate at word-prediction\n- Cons: slower to train, more complex, less interpretable\n\n-Forward Inference\n- Feature ($O(V)$): window that sees $N$ words in past, each as one-hot vectors\n- Embedding Matrix ($O(dV)$): column for each word, with each column having $d$ dimensions\n- Embedding Layer: output of multiplying feature one hot encode and embedding matrix\n\n-Algorithm\n- Step 1: create one-hot vector for each word and multiply by $E$\n- Step 2: multiply by $W$ and add $b$, pass through ReLu to get hidden layer\n- Step 3: multiply h by $U$\n- Step 4: apply softmax so that each node in output layer is probability\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n-Activation Function Derivatives\n- Sigmoid: $\\sigma(z)(1-\\sigma(z))$\n- Tanh: $1-tanh^2(z)$\n- ReLu: 0 for z < 0, 1 for z >= 0\n\n-Hyperparameters: leanring rate, minibatch size, model archiecture, number f hidden nodes, activation functions\n\n## SLP Chapter 7.7 Training the neural language model\n\n-Method 1: freezing, hold $E$ constant while modifying $W, U, b$\n\n-Method 2: gradient desent + back-propogation to create new $E$\n \n\n## Module 13 Lecture Notes\n<h3>Logistic Regression</h3>\n-Components of Classifier\n\n- Feature Representation: [$x_1,x_2,...,x_n$]\n- Classification Function: computes $p(y|x)$\n- Objective Function: minimizing error on training examples\n- Algorithm for optimizing objective function\n\n-Logistic Regression Functions\n- Z Function: $w \\cdot x + b$\n- Sigmoid Function: $y = \\dfrac{1}{1 + e ^{-z}}$\n- Probabilities: $P(y=1)= \\sigma(w \\cdot x + b) = \\dfrac{1}{1 + e ^{-w \\cdot x + b}}$\n\n-Multiclass Logistic Regression\n- Function: $softmax(z_i) = \\dfrac{e^{z_j}}{\\sum_{j=1} ^ k e^{z_j}}$\n<h3>Loss Functions</h3>\n-Goal: determine how much $\\hat{Y}$ differes from $y$\n-Cross Entropy Loss: negative log likelihood loss\n- Binary: $LC(\\hat{y}, y) = -logp(y|x) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})] =  -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n- Multiclass: $LC(\\hat{y}, y) = \\sum_{i=1} ^ C y_ilog(\\hat{y})$\n- Values: correct prediction (lower) vs incorrect (higher)\n-Loss on All Training: $log\\pi_{i=1} ^ m p(y^i | x^i) = -\\sum_{i=1} ^m (\\hat{y}^i | y^i)$\n<h3>Stochastic Gradient Descent</h3>\n-Logistic Regression: convex, one minimum, starting point unimportant\n\n-Gradient Types\n- Stochastic Gradient: choose single random example ... can fluctuate\n- Mini-batch: small batches ... loss is accumulated\n- Batch: choose entiredataset ... can take a while\n\n-Regularization\n- Logistic Regression: feature only occurs in one class ... get high weight (but might be accidental)\n- Regularization: Lasso (L1) an Ridge (L2)\n\n<h3>Neural Networks</h3>\n-Preceptrons: step function is _|-- so quick changes for weights\n\n-Activation Functions: sigmoid, tanh, ReLU (close to linear)\n\n-Feed-Forward NN: multilayer network, usually fully connected, no cycles, no backpropogation\n\n- Multiply weight matrix by input vector $x$\n- add bias vector $b$\n- apply activation function to obtain output $h = \\sigma(Wx + b)$\n\n-Training Neural Nets: loss function (cross-entropy loss), optimization algorithm (gradient descent), compute gradient of loss (error propogation)\n-Gradient Computations for one weight: $\\dfrac{\\delta LCE(w,b)}{\\delta wj} = (\\hat{y} - y)xj = (\\sigma(wx + b) - y)x_j$\n\n-Chain Rule:\n- $f(x) = u(v(x))$: $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dx}$\n- $f(x) = u(v(w(x)))$:  $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dw} \\cdot \\dfrac{dw}{dx}$\n\n\n## Module 13 Definitions\n* **Decision boundary** - threshold for cutting of logistic regression\n* **Gradient descent** - method for minimizing functions\n* **Sentiment classifier** - input of futures and use $P(y=1|x)$ to estimate 1 (positive) or 0 (negative)\n* **Forward inference** - task that runs a forward pass on network to product probability distribution of outputs\n* **Freezing** - use word2vec / pretrained algorithm to calculate embedding matrix\n* **Gradient** - vector that poitns in direction of greatest increase in function\n* **Loss function** - function that details how much prediction differs from actual\n* **Multi-layer preceptrons** - feed-forward networks\n* **Representation learning** - methods to learn features automatically (unsupervised) from input\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\"\n",
        "-Issues with Feedforward\n",
        "- Limited Context: words utisde context can't impact decision\n",
        "- Windows: difficult to learn systematic patterns\n",
        "\"\"\"\n",
        "slp_chapter9_2 = \"\"\"\n",
        "-RNN Differences\n",
        "- Sequences: processed one item at a time\n",
        "- Recurrent Link: link augment computation with value from a previous hidden layer form preceding time\\n\n",
        "-Components to Train\n",
        "- W: weights from input layer to hidden layer\n",
        "- U weights from previous hidden layer to current hidden layer\n",
        "- V: weights from hidden layer to output layer\\n\n",
        "-Inference: essentially identical, with addition of $h_{t-1}$\n",
        "- Formula: $h_t = g(Uh_{t-1} + Wx_t)$ where $x_t$ is input and $h_{t-1}$ is hidden layer of previous time step\n",
        "- Dimensions: $W: d_h, d_{in}; U: d_h, d_h; V: d_{out}, d_{in}$\\n\n",
        "-Training\n",
        "- Compute Loss Function at time $t$: need hidden layer from time $t-1$\n",
        "- Error: need to know influence of both current output and ones that follow\\n\n",
        "-Backpropogation Through Time: Two-Pass Training\n",
        "- First Pass: forward inference to compute $h_t, y_t$\n",
        "- Second Pass: process sequence in reverse, compute required gradients as go, save error term for each step\n",
        "\"\"\"\n",
        "slp_chapter9_3 = \"\"\"\n",
        "-Idea: process inpute sequence as one word / time to predict next word from current word & previous hidden state\\n\n",
        "-Property: $E=V$ \"\"\"\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 = \"\"\"\n",
        "-Lemma and Sense: mouse (lemma), sung/carpets (wordform), each meanining (word sense)\\n\n",
        "-Synonmy: principle of contrast, H20 and water\\n\n",
        "-Word Similarity: cat and dogs\\n\n",
        "-Word Relatedness: association (coffee, cup), semantic field (hospital: surgeon, nurse, scalpel)\\n\n",
        "-Semantic Frames and Roles: buy/sell/pay\\n\n",
        "-Connotation: valeance (pleasentness), arousal (intensity), dominance (degree of control) \"\"\"\n",
        "slp_chapter6_2 = \"\"\"\"\"\"\n",
        "slp_chapter6_3 = \"\"\"\n",
        "-Term-Document Matrix: row (word), column (documnet), cell (# of times word in document)\\n\n",
        "-Term-Term / Word-Word / Term-Context Matrix: row and columns (word), cell (#of times word appears in context) \"\"\"\n",
        "slp_chapter6_4 = \"\"\"\n",
        "-Vector Length: $|v| = \\sqrt{\\sum_{i=1} ^ N v_i ^ 2}$\\n\n",
        "-Cosine Similarity: $$cosine(v,w) = \\dfrac{v \\cdot w}{|v||w|}$\\n\n",
        "-Cosine Values: 1 (same), 0 (orthogonal), -1 (opposite, not possible since frequencies non-negative)\n",
        "\"\"\"\n",
        "slp_chapter6_8 = \"\"\"\n",
        "-Probabiltiies: $$P(+|w,c); P(-|w,c) = 1 - P(+|w,c)$\\n\n",
        "-Similarity: $c \\cdot w$, two words similar if embedding vectors are similar\\n\n",
        "-Chooinsg Noise Words: according to unigram frequency, to allow rare noise words higher probabilitiy\\n\n",
        "-Goal of Learning Algorithm: maximize similarity to $(w,c_{pos})$ and minimize to $(w,c_{neg})$\\n\n",
        "-Embeddings Learn: target embedding (W) and context embedding (C) \\n\n",
        "-Combination Method 1: add $w_i + c_i$\n",
        "-Combination Method 2: toss out $C$, only use $W$\\n\n",
        "-Fasttext: solves unknown words and sparsity bu using subword models (represent words as bag of constituent n-grams)\n",
        " \"\"\"\n",
        "slp_chapter6_10 = \"\"\"\n",
        "-Effect of Context widnow: shorter (syntactic), longer (topically related but not similar)\\n\n",
        "-Similariy and Association:\n",
        "- First-order co-occurence: nearby (wrote, book)\n",
        "- Secon-order co-occurence: similar neighbors (wrote, said)\\n\n",
        "-Analogy: foten return morphological variant (potato -> potatos)\\n\n",
        "-Historical Semantics\n",
        "\"\"\"\n",
        "slp_chapter6_11 = \"\"\"\n",
        "-Allocational Harm: system allocates resources differently to differnt groups\\n\n",
        "-Amplify Bias and implicit association\\n\n",
        "-Debiasing: embedding space without stereotype\n",
        "\"\"\"\n",
        "slp_chapter6_12 = \"\"\"\n",
        "-Similarity: correlation between algorithm similarity score and assigned by humans\\n\n",
        "-Analogy Tasks\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "<h3>Neural Language Models</h3>\n",
        "-Neural LM Ideas (Bengio)\n",
        "- Associate each word with vector representation: allows similarity to be established between words\n",
        "- Express joint probability function of word sequence in terms of word vectors for words in sequence\\n\n",
        "- Simultaneously learn word vectors and function parameters\n",
        "-Neural LM Component\n",
        "- Input: k-gram of words $w_{1:k}$, $x=[v(w_1);v(w_2);...;v(w_k)]$ (where each v is vector representation)\n",
        "- Output: probability distribution over next word\n",
        "- $k$ context words: word window with embedded vectors\n",
        "- Learning: $f(w_1...w_t)=P(w_t|w_1...w_{t=1}$\\n\n",
        "-Training: use k-gram words; first $k-1$ words as features and last as target label\\n\n",
        "-Advantages of Neural Language Models\n",
        "- No need for smoothing (use similar words)\n",
        "- Handle longer histories\n",
        "- Generalize contexts of similar words\n",
        "- Higher predictive accuracy\\n\n",
        "-Disadvantage of Neural Language Models: slower train than n-grams\\n\n",
        "-Current State of Art: ELMo, GPT, BERT, GPT-2\n",
        "<h3>Lexical Semantic Models</h3>\n",
        "-Goal Encoding: synonym, antonym, connotations, semantic roles (buy/sell/pay), support for entailment\\n\n",
        "-Entailment: mathematically well-understood, supports logical operations, knowledge comes from external sources\\n\n",
        "<h3>Vector Semantic Models</h3>\n",
        "-Distributional Hypiothesis: two words are similiar if they have similar contexts\\n\n",
        "-Vector Space Model History\n",
        "- Developed in SMART information retrieval system\n",
        "- Document in collection represented as point in space (vector in vector space)\n",
        "- User query as psuedo document to representpoint in same space\n",
        "- Perform IR by retrieving document whose vector are close in space to query vector\\n\n",
        "-Term-Document Matrix Components: size of $|D| \\cdot ||V||$\n",
        "- Column: vector representation fo document\n",
        "- Row: one term (vocabulary)\n",
        "- Cell: based on how often term occurs in document\n",
        "-Term Document Matrix Usage: compare 2 rows (synonyms), compare 2 columns (plaigarism)\\n\n",
        "-Distances\n",
        "- Euclidian: \"$\\sqrt{\\sum_{i=1} ^ N ||u_i - v_i|| ^ 2}$\", affected by frequency\n",
        "- Normalization by Length (L2): $\\sqrt{\\sum_{i=1} ^ N (u_i - v_i)^ 2}$\" (divide each vector by length)\n",
        "- Cosine Distance: $ 1 - \\dfrac{\\sum_{i=1} ^ n u_i \\cdot v_i}{L_2(u_i) \\cdot L_1(v_i)}$, smaller angle are closer\\n\n",
        "-Term-Term Matrix\n",
        "- Row / Column: one term (vocabulary)\n",
        "- Cell: how often term occurs in context to one another\n",
        "- Context Windows: +/- words, complex context / dependence (subj-verb)\\n\n",
        "-TF-IDF: term frequency * inverse document frequency, usage to weigh word frequency skewing\n",
        "- Term frequency: how often a word documents in document\n",
        "- Inverse document Frequency: 1 / number of document that occurs in\\n\n",
        "<h3>Word Embedding</h3>\n",
        "-Sparse/Dense: co-occurence (long and sparse), Word2Vec (short and dense)\\n\n",
        "- Less features: fewer weights to tune in learning\n",
        "- Better generalization\n",
        "- Better capture similaritiy: fewer features, less distinct in dimensions\\n\n",
        "-Word2Vec: train classifier\n",
        "- Process: learn word representation by training classifier to predict neighboring words\n",
        "- Idea: predict (will w show up near apricot)? rather than count (how many times does w show up near apricot)\n",
        "- Advantages: fast, easy to train, online packages\n",
        "- Use Cases: relational meaning / analogy\\n\n",
        "-Skip-Gram Algorithm: calculates $P(+|t,c)$ (probability hat $c$ is real context word for $t$)\n",
        "- Treat target word and neighboring word as positive samples\n",
        "- Randomly sample other words in lexicon as negative samples\n",
        "- Use logistic regression to classifiy between positive / negative\n",
        "- Use weights as embedding\\n\n",
        "-Noise Words: to oversample less common words, $P_α(w) = \\dfrac{count(w)^α}{\\sum_w count(w)^α}\\n\n",
        "-Learning Classifier: start with 0/random weights, iteratively adjust weights to have positive pairs more likely, negative pair less likely\\n\n",
        "-Usage of Embedding: studying language changes, understanding cultural bias\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"entailment\" : \"definition\",\n",
        "\"euclidian distance\": \"$\\sqrt{\\sum_{i=1} ^ N ||u_i - v_i|| ^ 2}$\",\n",
        "\"distributional hypothesis\": \"waords in similar contexts have similar meanings\",\n",
        "\"Principle of constrast\": \"changes in linguistic form associated with changes in meaning\",\n",
        "\"information retrieval\": \"task of finding documents matching a query\",\n",
        "\"embeddings\": \"vectors that are short and dense\",\n",
        "\"self-supervision\": \"supervision without hand label\",\n",
        "\"RNN\": \"network containing cycle with network connection (unit value dependant on earlier output)\"    \n",
        "}\n",
        "\n",
        "module14_definitions = {key: module14_definitions[key] for key in sorted(module14_definitions.keys())}"
      ],
      "execution_count": 137,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "outputId": "731dfa47-b4c6-4fb1-81f9-de9916670e2d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3016
        }
      },
      "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": 138,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n-Issues with Feedforward\n- Limited Context: words utisde context can't impact decision\n- Windows: difficult to learn systematic patterns\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n-RNN Differences\n- Sequences: processed one item at a time\n- Recurrent Link: link augment computation with value from a previous hidden layer form preceding time\n\n-Components to Train\n- W: weights from input layer to hidden layer\n- U weights from previous hidden layer to current hidden layer\n- V: weights from hidden layer to output layer\n\n-Inference: essentially identical, with addition of $h_{t-1}$\n- Formula: $h_t = g(Uh_{t-1} + Wx_t)$ where $x_t$ is input and $h_{t-1}$ is hidden layer of previous time step\n- Dimensions: $W: d_h, d_{in}; U: d_h, d_h; V: d_{out}, d_{in}$\n\n-Training\n- Compute Loss Function at time $t$: need hidden layer from time $t-1$\n- Error: need to know influence of both current output and ones that follow\n\n-Backpropogation Through Time: Two-Pass Training\n- First Pass: forward inference to compute $h_t, y_t$\n- Second Pass: process sequence in reverse, compute required gradients as go, save error term for each step\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n-Idea: process inpute sequence as one word / time to predict next word from current word & previous hidden state\n\n-Property: $E=V$ \n\n## SLP Chapter 6.1 Lexical Semantics\n\n-Lemma and Sense: mouse (lemma), sung/carpets (wordform), each meanining (word sense)\n\n-Synonmy: principle of contrast, H20 and water\n\n-Word Similarity: cat and dogs\n\n-Word Relatedness: association (coffee, cup), semantic field (hospital: surgeon, nurse, scalpel)\n\n-Semantic Frames and Roles: buy/sell/pay\n\n-Connotation: valeance (pleasentness), arousal (intensity), dominance (degree of control) \n\n## SLP Chapter 6.2 Vector Semantics\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n-Term-Document Matrix: row (word), column (documnet), cell (# of times word in document)\n\n-Term-Term / Word-Word / Term-Context Matrix: row and columns (word), cell (#of times word appears in context) \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n-Vector Length: $|v| = \\sqrt{\\sum_{i=1} ^ N v_i ^ 2}$\n\n-Cosine Similarity: $$cosine(v,w) = \\dfrac{v \\cdot w}{|v||w|}$\n\n-Cosine Values: 1 (same), 0 (orthogonal), -1 (opposite, not possible since frequencies non-negative)\n\n\n## SLP Chapter 6.8 Word2vec\n\n-Probabiltiies: $$P(+|w,c); P(-|w,c) = 1 - P(+|w,c)$\n\n-Similarity: $c \\cdot w$, two words similar if embedding vectors are similar\n\n-Chooinsg Noise Words: according to unigram frequency, to allow rare noise words higher probabilitiy\n\n-Goal of Learning Algorithm: maximize similarity to $(w,c_{pos})$ and minimize to $(w,c_{neg})$\n\n-Embeddings Learn: target embedding (W) and context embedding (C) \n\n-Combination Method 1: add $w_i + c_i$\n-Combination Method 2: toss out $C$, only use $W$\n\n-Fasttext: solves unknown words and sparsity bu using subword models (represent words as bag of constituent n-grams)\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n-Effect of Context widnow: shorter (syntactic), longer (topically related but not similar)\n\n-Similariy and Association:\n- First-order co-occurence: nearby (wrote, book)\n- Secon-order co-occurence: similar neighbors (wrote, said)\n\n-Analogy: foten return morphological variant (potato -> potatos)\n\n-Historical Semantics\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\n-Allocational Harm: system allocates resources differently to differnt groups\n\n-Amplify Bias and implicit association\n\n-Debiasing: embedding space without stereotype\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n-Similarity: correlation between algorithm similarity score and assigned by humans\n\n-Analogy Tasks\n\n\n## Module 13 Lecture Notes\n<h3>Logistic Regression</h3>\n-Components of Classifier\n\n- Feature Representation: [$x_1,x_2,...,x_n$]\n- Classification Function: computes $p(y|x)$\n- Objective Function: minimizing error on training examples\n- Algorithm for optimizing objective function\n\n-Logistic Regression Functions\n- Z Function: $w \\cdot x + b$\n- Sigmoid Function: $y = \\dfrac{1}{1 + e ^{-z}}$\n- Probabilities: $P(y=1)= \\sigma(w \\cdot x + b) = \\dfrac{1}{1 + e ^{-w \\cdot x + b}}$\n\n-Multiclass Logistic Regression\n- Function: $softmax(z_i) = \\dfrac{e^{z_j}}{\\sum_{j=1} ^ k e^{z_j}}$\n<h3>Loss Functions</h3>\n-Goal: determine how much $\\hat{Y}$ differes from $y$\n-Cross Entropy Loss: negative log likelihood loss\n- Binary: $LC(\\hat{y}, y) = -logp(y|x) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})] =  -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n- Multiclass: $LC(\\hat{y}, y) = \\sum_{i=1} ^ C y_ilog(\\hat{y})$\n- Values: correct prediction (lower) vs incorrect (higher)\n-Loss on All Training: $log\\pi_{i=1} ^ m p(y^i | x^i) = -\\sum_{i=1} ^m (\\hat{y}^i | y^i)$\n<h3>Stochastic Gradient Descent</h3>\n-Logistic Regression: convex, one minimum, starting point unimportant\n\n-Gradient Types\n- Stochastic Gradient: choose single random example ... can fluctuate\n- Mini-batch: small batches ... loss is accumulated\n- Batch: choose entiredataset ... can take a while\n\n-Regularization\n- Logistic Regression: feature only occurs in one class ... get high weight (but might be accidental)\n- Regularization: Lasso (L1) an Ridge (L2)\n\n<h3>Neural Networks</h3>\n-Preceptrons: step function is _|-- so quick changes for weights\n\n-Activation Functions: sigmoid, tanh, ReLU (close to linear)\n\n-Feed-Forward NN: multilayer network, usually fully connected, no cycles, no backpropogation\n\n- Multiply weight matrix by input vector $x$\n- add bias vector $b$\n- apply activation function to obtain output $h = \\sigma(Wx + b)$\n\n-Training Neural Nets: loss function (cross-entropy loss), optimization algorithm (gradient descent), compute gradient of loss (error propogation)\n-Gradient Computations for one weight: $\\dfrac{\\delta LCE(w,b)}{\\delta wj} = (\\hat{y} - y)xj = (\\sigma(wx + b) - y)x_j$\n\n-Chain Rule:\n- $f(x) = u(v(x))$: $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dx}$\n- $f(x) = u(v(w(x)))$:  $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dw} \\cdot \\dfrac{dw}{dx}$\n\n\n## Module 14 Definitions\n* **Principle of constrast** - changes in linguistic form associated with changes in meaning\n* **Rnn** - network containing cycle with network connection (unit value dependant on earlier output)\n* **Distributional hypothesis** - waords in similar contexts have similar meanings\n* **Embeddings** - vectors that are short and dense\n* **Entailment** - definition\n* **Euclidian distance** - $\\sqrt{\\sum_{i=1} ^ N ||u_i - v_i|| ^ 2}$\n* **Information retrieval** - task of finding documents matching a query\n* **Self-supervision** - supervision without hand label\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": {
        "id": "T3cm1WV542_a",
        "outputId": "b9ddfd3d-33e8-4f93-b71d-001eb835dfe7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 20788
        }
      },
      "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": 140,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n-Project Formulation: agent with available actions $a$, at state $s$, going to state $s'$ with uncertain probability\n- $P(s'|s,a)$: probability that $s$ reaches $s'$ after taking $a$\n- $P(RESULT(a)=s') = \\sum_s (P(s) * P(s'|s, a))$, where $P(s'|s, a)$ is probability that $s$ reaches $s'$ after taking $a$\n- $EU(a) = \\sum_{s'} P(RESULT(a)=s') * U(s')$\n\n-Maximum Expected Utility (MEU): agent choses action maximizing EU\n-Characteristic: formalizes what agent \"should do\", but not operalization\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n-Lottery:\n- Function: $L = [p_1, S_1; p_2, S_2; ... p_n, S_n]$\n- Components: outcomes $S_1, ... S_n$ and probabilities $p_1, ..., p_n$\n\n-Axioms of Utility Theory\n- Orderability: $A > B, B > A, or A ~ B$ must hold\n- Transitivity: $(A > B) ^ (B > C) => (A > C)$\n- Continuity: $A > B > C \\exists p ([p, A; 1 - p, C] ~ B)$\n- Substitutability: $A ~ B => [p, A; 1 - p, C] ~ [p, B; 1 - p, C]$\n- Monotonicity: $A > B => (p > q <-> [p, A; 1 - p, B] > [q, A; 1 - q, B])$\n- Decomposability:\n\n-Existence of Utility Function: if agent obeys axioms, there exists a function U such that $U(A) > U(B)$ iff A > B and $U(A) = U(B)$ iff A=B\n \n-Expected Utility of Lottery: utility of lottery is sum of probability * outcome such that $U(L) = \\sum_{i}p_i * U(S_i)$\n\n-Utility Function: exists for all rational agent, not necessarily unique (e.g.: can transform with adding constant)\n\n## AIMA Chapter 16.3 Utility Functions\n\n-Utility Scales: for each prize $S$, alter $p$ until agent indifferent between $U(S)$ and standard lottery\n\n-Risk: risk-adverse (logartihmic), risk-neutral (linear), risk-seeking (S-Shape)\n\n-Bias: selecting action with highest utility, estimates are overly optimistic\n\n-Human Judgement: normative theory (how agent should act) vs descriptive theory (how humans actually act)\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n-Utility Function: depends on environmental history since decision problem is sequential\n\n-MDP\n- Characteristics: fully observable, stochastic environment, Markovian transtion, additive rewards, sequential decision problems\n- Consists: set of states, set of actions, transition model, reward function, initial state\n\n-Horizons: \n- finite: fixed time N and game over afteward, optimal policy depend on time left, policy is nonstationary\n- infinite: policy is stationary\n\n-Discount Factors: near term reward > long term reward, interest rate (better to get soon), uncertainty in true reward, infinity scenarios\n\n-Policy & Time Scenarios: discount reward ($\\dfrac{R_{max}}{1 - Y}$), proper policy (compare), infinite (average reward / time step)\n\n-Expected Utility: $U(S) = \\sum_ {t=0} ^\\infty Y^tR(S_t, \\pi(S_t), S_{t+1})$\n\n-Infinite Horizons and Discount Utility: optimal policy independent of starting state\n\n-Bellman Equation: utility of state = transition reward + discounted utility of next state, assuming agent picks optimal action\n\n-Q Function: expected utiity of taking action at given state\n\n-Equations\n- Bellman: $U(s) = argmax_{a} Q(s, a) = max_{a} \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU(s')]$\n- Q-Function / Action-Utility: $Q(s, a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU(s')]$\n- Shaping Theorem: $R'(s,a,s') = R(s,a,s') + Y\\phi(s') - \\phi(s)$\n\n-Representations: dynamic decision networks (DDNS)\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n-Bellman Equation: for $n$ states, there are $n$ bellman equation with $n$ unknowns\n\n-Value Iteration: simultaneouly apply bellman update to all states at each , solved nonlinear (due to max)\n- Bellman Update: $U_{i+1}(s) = max_{a}  \\sum_{s'} P(s'|s,a)[R(s,a,s') + YU_i(s')]$ \n- Policy Loss: $||U^{\\pi_i} - U||$, most agent can lose by executing $\\pi_i$ instead of $pi*$\n\n-Policy Iteration: alternate between policy evaluation and policy improvement, not linear (due to no max)\n- Policy Evaluation: given policy $\\pi_i$, calculate $U_i = U^{\\pi_i}$ (each state's utility as if $\\pi_i$ is executed)\n- Policy Improvement: calculate new MEU $\\pi_{i+1}$\n- Update: $U_{i+1}(s) = \\sum_{s'} P(s'|s, \\pi_{i}(s))[R(s,\\pi_i(s),s') + YU_i(s')]$ \n- Runtime: $O(n^3)$ \n\n-Linear Programming: variables as utilities of each state\n- Minimize all states $s$ where $U(s) >= \\sum_{s'} P(s'|s, a)[R(s,a,s') + YU_i(s')]$\n\n-Offline Algorithms: agent compute at each point, not only precomputed information \n\n-Real-Time Dynamic Programming (RDTP): for repeated states, re-use sub-MDP\n\n\n\n## Module 8 Lecture Notes\n\n<h3>MDP Formulation</h3>\n-Quantities\n- Value (V): expected utility starting in $s$ and acting optimally\n- Q-State (Q): expected utility starting out from SsS and taking action SaS\n- Policy ($\\pi$): optimal action from state $s$\n\n-Functions:\n- $Q^*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^*(s')]$\n- $V^*(s) = max_a Q*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^*(s')]$\n\n<h3>Value Iteration</h3>\n-Idea: iteratively solve set of equations for utility of each state to neighbors\n\n-Algorithm: start with all $V_0(s) = 0$, apply $V(s)$ update, repeat until convergence\n\n-Complexity: $O(S^2A)$\n\n-Convergence Property: converge to unique optimal values (approximations refined towards optimal value & policy converge before values)\n- Case 1: tree has max depth $M$, $V_m$ has untruncated values\n- Case 2: $Y < 1$, $V_k$ and $V_{k+1}$ at most $(Y^k)(max|R|)$ different\n\n-Issues: $V_{k+1}$ repeats value iteration, value change  ... action's dont, policy converge before values\n<h3>Policy Iteration</h3>\n-Main Idea: select actions from q-values not values by alternating between calculating state utility under current policy and improving current policy with respect to current utilities\n\n-Algorithm: \n- Policy evaluation: calculate utility for fixed policy until convergence\n- Policy improvement: update policy using one-step look ahead with converged utilities as future values\n- Repeat until convergence\n\n-Functions: \n- $V^*(s) = \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s') + YV^*(s')]$\n- $\\pi^*(s) = argmax_{a}Q*(s,a) = argmax_{a} \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s') + YV^*(s')]$\n- Evaluation: $V_{k+1}(s) = \\sum_{s'} T(s,\\pi_i(s),s')[R(s,\\pi_i(s),s') + YV^{\\pi_i}(s')]$\n- Improvement: $\\pi_{i+1}(s) = argmax_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + YV^{\\pi_i}(s')]$\n\n-Complexity: $O(S^2)$ because only one action per state\n\n-Comparisons\n- Value Iteration: every iteration updates values & policy, don't track policy\n- Policy Iteration: several passes with fixed policy, choose new policy\n\n<h3>MEU</h3>\n-Utility Scales: normalized utility (0, 1), micromorts, QALYs\n\n-Money: not behave as utility ... but having money is utility\n \n\n## Module 8 Definitions\n* **Asynchronous policy iteration** - update subset of states, not all states\n* **Certainity effect** - people attracted to certain gains\n* **Continuity** - if agent prefers A>B>C, exist probability where agent indifferent towards and A ($p$) or C ($1-p$)\n* **Contraction** - function that after applying, makes to output values closer to one another\n* **Decomposability** - compounded lotteries can be reduced to simpler ones with probability laws\n* **Expected utility** - $EU(a)$, average utility of outcome\n* **Markov decision process** - sequential decision problems within stochastic environments\n* **Markovian** - probability of moving from s to s' depends on s only, not history\n* **Micromort** - one in a million chance of death\n* **Monotonicity** - if two lotteries have same two possible outcomes A and B and agent prefers A, lottery with higher probability for A is preferred\n* **Nonstationary** - policy that is dependant on time\n* **Optimizer's curve** - choosing highest expected utility causes estiamtes to overestaimte\n* **Orderability** - agent cannot avoide deciding preference, must either prefer one or rate as equal\n* **Policy** - solution of what agent should do at any state\n* **Prefernce elicitation** - presenting choices to humans and using preferneces to determine utility function\n* **Proper policy** - policy that is guarenteed to reach terminal state\n* **Qaly** - quality-adjusted life years\n* **Stationary** - policy not dependant on time, only on current state\n* **Substitutability** - if agent indifferent/prefer towards A and B, agent indifferent towards more complex lotteries which are same except A & B\n* **Transition models** - model that specify probability of actions\n* **Transitivity** - if agent prefers A > B and B > C, agent prefers A > C\n* **Utility** - exepected sum of reward when optimal executed from that state\n* **Utility function** - $U(S)$, function giving state a desirability number\n* **Value function / ordinal utility function** - prefernce on states where numbers are irrelevant\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n-Bandit Problem Formulation: given $n$-armed bandit, choose which lever to play on each succesive coin\n\n-Bandit Problem Definition\n- Each arm $M_i$: Markov Reward Process (MDP with only one action $a_i$)\n- Overall Problem: MDP with state space ($S = S_1 ... S_n$), action ($a_i, ..., a_n$), $T$ updated when $M_i$ selected\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n-Model-Based RL: agent learns transition model of environment to interpret reward and learn utility function\n\n-Model-Free RL: agent does not learn transition model\n- Action-Utility Learning (Q-Learning): agent learns Q-function and given Q-function, agent choses what to do at $s$\n\n- Policy Search: agent learns policy that maps from states to action\n-Passive RL: agent's policy is fixed and task is to learn state utilities, $U^{\\pi}(s)$\n\n-Active RL: agent must choose between exploration and exploitation\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n-Start: fully observable, small # of action/state, agent has fixed policy, agent trying to learn utility function\n\n-Passive Learning vs Policy Evaluation: similar, but does not know $P(s'|s,a)$ or $R(s,a,s')$\n\n- Perform multiple trials: in each trial, keep performing action until at terminal state\n- Calculate Utility: $U^{\\pi}(s)$ = E[$\\sum_{t=0} ^{\\infty} Y^t R(S_t, \\pi (S_t), S_{t+1})$] where $S_t$ is RV of state reached at time $t$ via policy $\\pi$ starting from $S_0 = s$\n\n-Direct Evaluation: state utility is reward-to-go, with each trial providing sample for quantity of each state visited\n- Example: two samples of 0.80 and 0.88 for state (1,2) ... state utility = 0.84\n- Issue: ignores constraint that state utility determined by reward and expected utility of successor states ... learns nothing about state until end of trials ... slow convergence\n\n-Adaptive Dynamic Programming: learns transition models to take advantage of constraints among state utilities\n\n-Temporal Reinforcement Learning: adjust utility estimates towards ideal equilibrium\n- Transition Model: does not need, just uses environmental supplying connection between neighboring states\n- Updates: $U^{\\pi}(s) = U^{\\pi}(s) + α(s, \\pi (s), s') + Y*U^{\\pi}(s') - U^{\\pi}(s)] $\n- Approach: adjust state to agree with observed successor (i.e. if A is .80 and B is .96 and A -> B, then bump A value up)\n\n-ADP vs TD\n- Approach: TD (state agree with observed successor), ADP (state agree with all successor)\n- Large Transitions: frequency of each successor proportional to probability, TD = ADP\n- Changes: TD (single adjustment / observed transition), ADP (multiple adjustment / transition)\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n-Active Learning Agent: needs to learn transition model for all actions\n\n-GLIE: tries each action in each state for unbounded number of times, no optimal action missed\n- Method 1: agent choose random action at time step $t$ with probability $\\dfrac{1}{t}$\n- Method 2: weigh actions not tried often and avoid actions of low utility\n\n-Exploration Function: $f(u,n)$ for utility ($u$) and count $n$\n- Equation: $f(u, n) = R^+$ (if $n < N_e$) and $u$ (otherwise)\n- Condition: increases with $u$ and decreases with $n$\n- $U^+$: optimistic estimate of utility, needed to ensure actions leading towards unexplored regions are weighted higher\n\n-Safe Exploration: needed to ensure agent doesn't perform irreversible actions\n- States to avoid: large ngeative rewards, no escape, permanently limited future rewards\n\n-Bayesian RL\n- Idea: assumes with probability $P(h)$ about what true model is\n- Updates: $\\pi* = argmax_{\\pi} \\sum_h P(h|e) U^{\\pi}_h$\n\n-Robust Control Theory\n- Idea: allow for set of possible models $H$, optimal policy as one giving best outcome in worst case of $H$\n- Updates: $\\pi* = argmax_{\\pi} min_h U^{\\pi}_h$\n\n-Q-Learning\n- Idea: learn $Q(s,a)$ instead of $U(s)$ where $Q(s,a)$ is expected total discount if agent takes action $a$ and $s$\n- Bellman Update: $Q(s,a) = Q(s,a) + α(R(s,a,s') + Y max_{a'} Q(s',a') - Q(s,a))$\n-Usage: flexible, learn to behave well in wide variety of exploration\n\n-SARSA\n- Bellman Update: $Q(s,a) = Q(s,a) + α (R(s,a,s') + Y * Q(s',a') - Q(s,a))$\n- Q-Learning (off-policy) vs SARSA (on-policy): identifical if always exploitation, SARSA penalizes if exploration\n- Usage: overall policy is controlled by other agent/program, learn Q-function for what will actually happen ... not agent pick best estimates\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n-Approximating Direct Utility: $θ=θ_{i} + α[u_j(s) - U*^_{θ}(s)]$\n\n-Approximating Temporal-Difference: converge only for linear features and passive learning, not active and neural nonlinear\n\n-Experience Replay: replay trajectories to ensure value function accurate for non-visited parts\n\n-Deep RL: RL system that uses deep network\n- Cons: difficult to get good performance, trained system behaves unpredictably if environment != training data\n\n-Reward Shaping Example: reward for contacting ball or advancing goal ... rather than just goal\n\n-Hierchial RL: break long action sequences into fewer, smaller pieces\n\n\n## Module 9 Lecture Notes\n\n<h3>Reinforcement Learning</h3>\n-Scenario: same as MDP ... except don't know T or R\n\n-Model-Based Learning: learn approximate model based on experiences\n- Step 1: Learn Empircal MDP Model: count outcomes $s'$ for each $s, a$, normalize to get $T(s,a,s')$ estimate, discover $R(s,a,s')$ after experiencing $(s,a,s')$\n- Step 2: solve learned MDP (value iteration, policy iteration)\n\n-Model-Free Learning: compare results of what happened to expected then update values\n\n<h3>Passive RL</h3> \n-Passive RL (learns state values): input (fixed policy), goal (learn state values)\n\n-Direct Evaluation\n- Idea: average observed sample values by acting according to $\\pi$, every visit ... add to sum of discoutned rewards, average samples\n\n- Pros: easy to understand, doesn't require $R, T$, often computes correct average values\n- Cons: waste information about state connection, each stat elearned seperately, long time\n\n-Sample-Based Evaluation\n- Idea: take sample of outcome $s'$ by doing action and average\n- $V^{\\pi}_{k+1} = \\dfrac{1}{n} \\sum_i sample_i$\n- $sample_i = R(s, \\pi(s), s'_i) + YV_k^{\\pi}(s'_i)$\n\n<h3>Temporal Difference Learning</h3>\n-Idea (learns state values): learn from every experience, update as go ... not wait for $m$ \n\n-Equations\n- Sample of $V(s)$: $sample = R(s, \\pi(s), s') + YV^{\\pi}(s')$\n- Update to $V(s)$: $V^{\\pi}(s) = (1 - α)V^\\{pi}(s) + (α)sample$\n\n-Exponential Moving Average: $x_n = (1 - α) * x{n-1} + α * x_n$\n\n<h3>Active Reinforcement Learning / Q-Learning</h3>\n-Full Reinforcement Learning (learn optimal oplicy): exploitation vs exploration\n\n-Q-Value Iteration: $Q_{k+1}(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + Y*max_{a'} Q_k(s',a')$\n\n-Q-Learning: sample-based Q-value iteration to learn $Q(s,a)$ as you go\n- Recieve sample (s, a, s', r)\n- New Sample Estimate: $sample = R(s,a,s') + Y * max_{a'}Q(s',a')$\n- Running Average: $Q(s,a) = (1-α)Q(s,a) + α*sample$\n-Issues: have to explore enough, eventually decrease learning rate\n\n<h3>Exploration vs Exploitation</h3>\n-Random Action $\\epsilon-greedy$: flip coin, with small probably (act randomly), else (act on current policy)\n\n-Exploration Function: explore areas whose badness is not yet etablished\n<h3>Approximate Q-Learning</h3>\n-Basic Q-Learning (keep table of all q-value) vs Approximate (only learn for small number of training state)\n\n-Linear Value Functions\n- $V(s) = w_1f_1(s) + w_2f_2(s) + ... + w_nf_n(s)$\n- $Q(s,a) = w_1f_1(s, a) + w_2f_2(s, a) + ... + w_nf_n(s, a)$\n- Pros (experienced summed up in few) and Cons (states share feature can have different values)\n\n-Q-Learning\n- $difference = [r + Y*max_{a'}Q(s',a')] - Q(s,a)$\n- $Q(s,a) = Q(s,a) + α[difference]$\n- $w_i = w_i + α[difference]*f_i(s,a)$\n\n## Module 9 Definitions\n* **N-armed bandit** - slot machine with $n$ levers\n* **Absorbing state** - state where no actions have affect and cannot recieve rewards\n* **Catastrophic forgetting** - does so well that forget which areas do poorly\n* **Credit assignment problem** - phenomenon when difficult to make judgements because rewards are sparse\n* **Experienec replay** - relive negative experiences at regular intervals\n* **Glie** - greedy in limit of infinite exploration\n* **Greedy agent** - agent that greedily takes action that currently believes is optimal\n* **Off-policy learning** - capable of converging to optimal policy, even when acting suboptimally\n* **Regret** - measure of total mistake cost (expected rewards - optimal exected rewards)\n* **Reward shaping** - giving agent additional rewards\n* **Reward-to-go** - expected total reward from that state onward\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n-Marginilization: $P(Y) = \\sum_z P(Y,z)$\n\n-Conditioning: $P(Y) = \\sum_Z P(Y|Z)P(Z)$\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\n-Full Joint Distribution: $P(Cause, Effect_1, ..., Effect_n = P(Cause) \\pi_i P(Effect_i | Cause)$\n\n-Inference from Joint: $P(Cause|e) = α P(Cause) \\pi_c P(e_j | Cause)$\n- Meaning: for each pausible cause, multiply prior probability of cause by product of conditional probabilities of observed effects given the clause\n- Runtime: linear (observed effects), does not depend on unobserved effects$\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n\n-Maximum Likeliehood Estimation: $P(w_n | w_{n-N+1:n-1}) = \\dfrac{C(w_{n-N+1:n-1} w_n)}{C(w_{n-N+1:n-1})}$\n\n-Relative Frequency: ratio of observed frequency of sequence / observed fequency of prefix\n\n-Bigram for sentence: $P(<s> | I want english food) = P(i|<s>)P(want|i)P(english|want)P(food|english)$\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n-Perplxity: $(\\Pi_{i=1} ^ N \\dfrac{1}{P(w_i | w_{i-1})})^{1/N}$\n- Idea: weighted average branching factor\n- Trend: higher conditional probability, lower perplexity, higher accuracy\n- Example: 123456789 has higher perplexity than 00000000001\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\nUnigram Sampling: assign each word some spac between 0 and 1 (i.e.: the is 0 - .06, of is 0.06 - 0.09)\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n-Dialect and Genre: create specific models fore each\n\n-Unknown words & zeros: replace with <UNK>\n- Method 1: turn to closed vocabary by treating <UNK> like any other word\n- Method 2: replace words in training data by <UNK> based on frequency (replace all words less than $n$ times)\n\n\n## SLP Chapter 3.5 Smoothing\n\n-Laplace smoothing: add one to all n-gram counts before normalization, $P(w_n | w_{n-1}) | \\dfrac{C(w_{n-1}w)n) + 1}{C(w_{n-1}) + V}$\n\n-Add-k smoothing: add fraction count $k$, $P(w_n | w_{n-1}) | \\dfrac{C(w_{n-1}w)n) + k}{C(w_{n-1}) + kV}$\n\n-Backoff and Interpolation: use less context (change from trigram to bigram)\n- Backoff: use trigram if sufficient, otherwise bigram, otherwise unigram\n- Interpolation: mix probability estimates from all nn-ram estimator and weigh combinations\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n-Shrink large models: pruning by only storing n-gram with count greater than threshold\n\n-Bloom Filters: sorted arrays with combine probabilities\n\n-Stupid Backoff: doesn't do true probability distribution, backdown to lower order n-gram\n \n\n## Module 10 Lecture Notes\n<h3>Probability</h3>\n-General Situations: \n\n- Observed Variables (evidence): agent knows certain things about state of world\n- Unobserved Variables (state): agent needs to reason for\n- Model: agent knows how known and unknown variables relate to another\n\n-Random Variable Example: R (is it Raining), U (carrying umbrella?)\n\n-Probability Rules\n- Probability of world between 0 and 1: $0 <= P(w) <=1$ for all $w$\n- Total probability of all worlds is 1: $\\sum_w P(w) = 1$\n- Conditional Probability: $P(a|b) = \\dfrac{P(a,b)}{P(b)}$\n- Product Rule: $P(y)P(x|y) = P(x,y)$\n- Chain Rule: $P(x_1,x_2,...x_n$ = \\Pi_i P(x_i|x_1 ... x_{i-1})$\n- Bayes Rue: $P(x|y) = \\dfrac{P(y|x)}{P(y)}P(x)$\n\n<h3>Distributions</h3> \n-Joint Distributions\n\n- for RV $X_1, X_2, ..., X_n$: $P(X_1 = x_1, X_2 = x_2, ..., X_n = x_n) = P(x_1, x_2, ... , x_n)$\n- Space Complexity: for $n$ variables and domain size $d$: $d^n$\n\n-Probabilistic Model\n- Marginilization: combine collapsed row by adding (from probabilistic model to marginal distributions)\n\n<h3>Probabilistic Inference and Rules</h3>\n-Goal: use known probabilities to compute desired probabilities, find $(Q|e_1, ..., e_k)$\n-General Case:\n\n- Evidence (known) Variables: $E_1, ..., E_k = e_1, ..., e_k$\n- Query (want to reason about) Variables: $Q$\n- Hidden (not observed) Variables: $H_1, ..., H_r$\n\n-Steps:\n- Step 1: select entries consistent with variables\n- Step 2: sum out $H$ to get join of query and evidence: $P(Q|e_1, ..., e_k) = \\sum_h P(Q, h_1 ... h_r, e_1 ... e_k)$\n- Step 3: normalize: $Z = \\sum_q P(Q, e_1 ... e_k)$, $P(Q|e_1, ..., e_k) = \\dfrac{1}{Z} P(Q, e_1 ... e_k)$\n\n<h3>Probabilistic Language Models</h3>\n-Goal\n\n- Idea: assign probability to sentence (e.g.: autocomplete, translation, spelling, speech)\n- Formula: $P(w_5|w_1,w_2,w_3,w_4)$\n-Estimating Probabilities\n- Count and Divide: does not work because specific configuration may never show up, would need large dataset\n- Markov Assumption: depend on current state by looking at previous $k$ word, not whole context (history)\n\n-History\n- Unigram (no history): $P(w_1w_2...w_n) = \\pi_iP(w_i)$\n- Bigram (1-word history): $P(w_i | w_1w_2...w_{i-1}) = P(w_i | w_{i-1}) = \\dfrac{c(w_{i-1},w_i)}{c(w_{i-1 })}$\n\n-MLE Issues and Solutions\n- Out of Vocabulary (OOV) items: replace with $<unk>$\n- Fixed lexicon $L$ of size $V$: normalize training data by replacing word not in $L$ with $<unk>$\n- Smalll space: convert to logspace\n\n\n## Module 10 Definitions\n* **Belief state** - representation of set of all possible world states\n* **Conditional distributions** - probability distributions for some variables where others are fixed\n* **Distribution** - table of probability values\n* **Event** - set of outcomes\n* **Exttrinsic evaluation** - embedding into application and measure application improvement\n* **Intrinsic evaluation** - measure model quality without application\n* **Language model** - model that computes probability of upcoming word or sequence of words\n* **Marginal distributions** - sub-tables of probabilistic model that eliminate variables\n* **Oon rate** - percent of OOV words appearing in test set\n* **Outcomes** - assignments to probabilistic models\n* **Perplexity** - inverse probability of test set\n* **Probabilistic model** - join distribution over set of RV\n* **Random variable** - aspect of world with uncertainty\n* **Smoothing / discounting** - remove a bit from probability mass from frequent events to never seen events\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n-Bayes Net Definition\n- Node: random variable (discrete or continuous)\n- Directed Link: connect pairs of node (X directly influence on Y)\n- Probability Information: each node $X_i$ has probability information $P(X_i|Parents(X_i))$\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n-Syntax: $n$ variables ($X_1, ... X_n$) and predicting joint distribution $P(x_1, ..., x_n)$\n\n- $P(x_1,...,x_n) = \\pi_{i=1} ^ n P(x_i | parents(X_i))$\n- Ex: $P(j,m,a, !=b, !=e) = P(j|a)P(m|a)P(a|!=b, != e)P(!=b)P(!=e)$\n\n-Constructing Bayesian Networks\n- Step 1: use product rule to rewrite distribution in terms of joint probabilities via product rule\n- Step 2: use chain rule to reduce joint probability to conditional probability and joint probability on smaller set ot of variables\n- Step 3: for each parent, insert link from parent to $X_i$ then write conditional probality table of $P(X_i | Parents(X_i))$\n\n-Compactness: leave out links with slight dependence (slight gain in accuracy not worth complexity)\n\n-Node Ordering: affects Bayes Net structure\n\n-Conditional Independence: conditionally independent with non-descendant, given parent\n\n-Markov Blanket: node conditionally indepednent of all other nodes, given markov blanket\n\n-Z D-Seperation Algorithm: set of nodes (X) is conditionally independent of another set (Y), given Z\n- Step 1: consider ancestral subgraph of X, Y, Z and ancestors\n- Step 2: add links between unlinked pair of nodes shairng common graph\n- Step 3: replace directed link with undirected links\n- Step 4: If Z blocks all paths between X and Y (d-seperate / not conditionally independent)\n\n-Efficient Distribution\n- Deterministic Nodes: relationship of parents (Canada, US, Mexico) and child (NA)\n- CSI: P(Damage|Ruggedness,Accident) = if (accident=false) then $d_1$ else $d_2$(Ruggedness)\n- Noisy-OR: Fever true iff Cold, Flu, or Malaria\n\n-Continuous Variables: discretization (divide values into intervals), probabilty density functions (Gaussian)\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n-Formula: $P(X|e) = \\sum_{y} P(X,e,y)$ where $X$ (query), $e$ (evidence), $y$ (hidden)\n\n-Example: $P(B|j,m) = \\sum_{e} \\sum_{a} P(B,j,m,e,a)$\n\n-Runtime: naive ($n2^n$) and simplified ($2^n$)\n\n-Enumeration-Ask Algrithm: DFS, left-to-right recursion\n- Complexity: space ($O(n)$) and time $O(2^n)$\n \n\n## Module 11 Lecture Notes\n \n<h3>Independence</h3>\n-Independence: $P(x,y) = P(x)P(y)$, $P(x|y)=P(x)$\n\n-Conditional Independence: if X is conditionally independent of Y given Z\n- Not Independence Formula: $P(x|y,z) = \\dfrac{P(z)P(x,y|z)}{p(y,z)}$\n- Formulas: $P(x,y|z) = P(x|z)P(y|z)$ and $P(x|z,y)=P(x|z)$\n- Definition: after seeing Z, then know X and Y are independent of each other\n\n- Example: P(Alarm, Fire | Smoke), normally Alarm and Fire not independent, but after knowing smoke, they are \n\n-Decomposition for P(Traffic, Rain, Umbrella)\n- Trivial: =P(Rain)P(Traffic|Rain)P(Umbrella|Rain,Traffic)\n- With Conditional Independence: P(Rain)P(Traffic|Rain)P(Umbrella|Rain)\n\n<h3>Bayes Net Properties</h3>\n-Problems with Full Joint Distribution Tables as Probabilistic Models\n\n- Too big to represent\n- Hard to learn empirically about more than few variables at a time\n\n-Bayes Net: uses simple, local distributions ... can also chain together to give global interactions\n\n-Components (DAG)\n- Nodes (one for variables with domains): can be assigned (observed) or unassigned (unobserved)\n- Arcs (interactions): conditional independence / causation between variables\n- Collection of distribution over X, one for each combination of parents' value $P(X|a_1...a_n)$\n\n-Probabilities in BNs: $P(x_1,x_2,...x_n) = \\pi_{i=1} ^ n P(x_i | parents(x_i))$\n\n-Causality\n- Not necessary ... but when do: simpler, easier to think about, easier to elicit from experts\n- Correlation (not causation): root dripping and traffic (missing rain)\n- Arrows: topology encodes caonditional independence (not casual structure)\n\n-Size: Joint Distribution ($2^N$) vs Bayes with $k$ parents ($N*2^{k+1}$) (for each variable, has T/F for self and all $k$ parents)\n\n-Assumptions: conditional independence\n\n<h3>Reachability and Paths</h3>\n-Cases\n\n- Causal Chain: X -> Y -> Z (X not guarenteed to be independent of Z ... but X independent of Z given Y)\n\n- Common Cause: Y -> X & Y -> Z (X not guarenteed to be independent of Z ... but X independent of Z given Y)\n\n- Common Effect: X -> Z & Y -> Z (X and Y independent ... but X and Y not independent given Z)\n\n-Failure of just trying to find path between two variables: doesn't handle \"V\" case from Common Effect\n\n-Shaded vs Unshaded: observed / have evidence / on right side of | in probability (shaded) vs unobserved (unshaded)\n\n-Active vs Inactive: there can still be influence (active) vs no influence (inactive)\n\n<h3>D-Seperation Algorithm</h3>\n-Goal: are $X_i$ and $X_j$ conditionally independent given ${X_{k1}, ... X_{kn}}$\n\n-Process: check all paths from $X_i$ to $X_j$\n\n-Active\n- Independence (from path): >=1 path active (independent not guarenteed) vs 0 path active (independence is guarenteed)\n\n- Path (from triples): active if each triple is active\n\n<h3>Inference</h3>\n-Inference by Enumeration: see Probabilistic Inference and Rules\n\n-Infernece by Enumeration in BN: $P(B |+j,+m) = \\sum_{e,a}P(B,e,a,+j,+m)$ ... but too many large variables\n\n\n## Module 11 Definitions\n* **Active path** - path where all triple is active\n* **Conditional probability table (cpt)** - local probability informatin attached to each node in BN\n* **Conditioning case** - possible combination of values for parent node only\n* **Context specific independence** - conditional distributions where variable is conditionally independent of some parents given values of others\n* **Deterministic nodes** - node with value specified exactly by parent value (no uncertainty)\n* **Hybrid bayesian network** - network with both discrete and continuous variables\n* **Inactive path** - path where at least one triple is inactive\n* **Infernece** - making useful quantity from partial observation\n* **Locally structured** - network where each node only interacts with subset of nodes, not all\n* **Markov blanket** - parent, children, and children's parent of a node\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n Your summary here \n\n## AIMA Chapter 19.2 Supervised Learning\n Your summary here \n\n## AIMA Chapter 19.3 Learning Decision Trees\n Your summary here \n\n## AIMA Chapter 19.4 Model Selection and Optimization\n Your summary here \n\n## AIMA Chapter 19.5 Theory of Learning\n Your summary here \n\n## AIMA Chapter  19.6 Linear Regresion and Classification\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n-Bayseian Inference: $\\hat{c} = argmax_{c \\exists C}P(c|d) = argmax_{c \\exists C}P(d|c)P(c)$\n\n-Components: likelihood $P(d|c)$ and prior $P(c)$\n\n-Assumptions: position doesn't matter, naive Bayes assumption\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n-Sentiment: $\\hat{P} = \\dfrac{N_c}{N_{doc}}$\n\n-Word: $\\hat{P}(w_i|c) = \\dfrac{count(w_i,c)}{\\sum_{w \\exists V}count(w,c)}$\n\n## SLP Chapter 4.3 Worked Example\n\n-For sentence \"predictable with no fun\"\n- Sentences: 5 total, 3 are negative and 2 are positive\n- Words: 34 total from 5 sentences\n\n-Methods\n- Step 1: Calculate $\\dfrac{N_c}{N_{doc}}$: $P(-1) = 3/5, P(+) = 2/5$\n- Step 2: Calculate $P(word|-)$ and $P(word|+)$ for each word\n- Step 2 Example: $P(predictable|-) = \\dfrac{1 + 1}{14 + 20}$ (occurs once in negative, +1 for Laplace)\n- Step 3: combine words and calculate $P(-)P(S|-)$ and $P(+)P(S|+)$\n \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \n-More important of word existance than frequency: use Binary NB, which remove all duplicate words before concateting into single document\n\n-Negation: prepend 'NOT_' to logical negation (e.g.: 'NOT_like')\n\n-Insufficient Training Data: derive sentiments from sentiment lexicons\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n \n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n-Metrics \n- Precision (TP / (TP + FP)): measure percent of classified positive that are actually positive\n- Recall (TP / (TP + FN)): measure percent actual positives that are classified as positive\n- F-Measure (2PR / (P + R)): if $B > 1$ (favor recall) and if $B < 1$ (favor precision)\n\n-Multi-class Metrics\n- Macroaveraging: compute performance for each class, average over classes\n- Microwaveraging: collect decision for all class into 1 confusion matrix, compute precision and recall from table\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n-Perform 10-fold in train set, error on test set\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n-Comparing performance of classifiers $A$ and $B$ on metric $M$\n- Performance Difference: $\\delta(x) = M(A,x) - M(B,x)$\n- Effect Size $\\delta(x)$: bigger (A way better than B), smaller (A only a bit better than B)\n- Hypothesis: null ($\\delta(x) <= 0$) and alternate ($\\delta(x) > 0$)\n\n-Non-Parametric Test: approximate randomnization and bootstrap testing\n \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n-Model Card Component: training algorithm, training data / motivation, intended use/users, model performance across demographic groups\n \n\n## Module 12 Lecture Notes\n\n<h3>Classification Tasks</h3>\n-Examples: spam detection, medical diagonsis, essay grading, fraud detection\n\n-Model Based Approach: build model, instantiate observed features, query for distributions of labels conditioned on features\n\n<h3>Naive Bayes</h3>\n-Assumption: all features inpendent on each other, only affect level\n\n-Learning: probability tables (prior probability and conditional probability)\n\n-General Model: $P(Y, F_1...F)n = P(Y)\\pi_{i}P(F_i|Y)$\n- Number of Values: $|YF^n|$\n- Number of Parameters: $|nFY|$\n\n-Goal: compute $P(Y|f_1...f_n)$\n- Step 1: compute joint probabiityof label and evidence for each label\n- Step 2: sum to get probability of evidence\n- Step 3: normalize by dividing step 1 by step 2\n\n-Information (Parameters) needed\n- $P(Y)$: prior over labels\n- $P(F_i|Y)$: for each feature (evidence variables)\n\n<h3>ML Concepts</h3>\n-Data: training set, held out set, test set\n\n-Experimentation Cycle: learn parameters on training set, tune hyperparameters on held-out set, compute accuracy\n\n-Parameter Estimation: distribution of random variables\n- Elicitation: ask expert / human\n- Empirically: use training data and calculate count / total sample\n\n-Laplace Smoothing: pretend saw $k$ outcome $k$ extra times\n- Formula: $P = \\dfrac{c(x)+k}{N + k|X|}$, $P = \\dfrac{c(x, y)+k}{y + k|X|}$ (conditional)\n- Poor Performance: for $P(X|Y)$ when $|X|$ or $|Y|$ is very large\n\n-Linear Interpolation: make sures $P(X|Y)$ isn't too diffent from empiral $P(X)$\n- Formula: $P(x|y) = α P(x|y) + (1-a)P(x)$ where $α$ is weight\n- $a$ values: $a=1$ weigh only prior probability, $a=1$ weigh only conditional probability\n\n<h3>Perceptrons</h3>\n-Binary Preceptrons\n\n- Start weight to 0\n- For each training instance, classify current weights via $w \\cdott f(x)$\n- If correct: no change\n- If incorrect: adjust weight in other direction $w = w - y* \\cdot f$\n\nMulticlass Preceptrons\n- Start weight to 0\n- For each training instance, classify current weights via $y = argmax_y w_y \\cdot f(x)$\n- If correct: no change\n- If incorrect: lower score of wrong answer ($w_y = w_y - f(x)$), raise score of right answer ($w_{y*} = w_{y*} + f(x)$)\n\n<h3>SVM</h3>\n-Preceptron Properties\n\n- Linearly-Seperable: will converge (for binary)\n- Non-Linearly Seperable: mistake bound to margin of mistakes $< \\dfrac{k}{\\delta^2}$ where $\\delta$ is margin\n\n-Preceptron Problems\n- Noise: data not seperable, weights don't converge and thrash (solved by averaging weight over times)\n- Mediocre generalization: hyperplane isn't the preferred hyperplane\n- Overtraiing: overfitting\n\n-MIRA (Margin Infused Relaxed Algorithm): scale $w$ updates by $τ$\n\n- $τ$ Value: $τ = min(\\dfrac{(w_y' - w_{y*}' f + 1)}{2f \\cdot f}, C)$\n- Update:$w_y = w_y - \tτ * f(x)$ (same for $y*$)\n- Effects: converge faster, works well for noisy data (reduce thrashing)\n\n-Support Vector Machine: maximize marging for support vectors (ignore all other training examples)\n\n-Non-Linear Seperator: transform feature space into higher dimensional feature space\n\n-Naive Bayes vs Perceptrons / MIRA\n- Naive Bayes: builds model training data, gives prediction prpbabilities, strong feature independnce assumption, one pass throgh data (count)\n- Preceptrons: less data assumption, mistake-driven learning, multiple pass through data (prediction), more accurate\n\n\n## Module 12 Definitions\n* **Bag-of-words** - unordered set of words (ignoring position, focusing on frequency)\n* **Binary multinomial naive bayes** - Binary NB\n* **Discriminative classifier** - model that learns most important feature to discriminate between different classes\n* **Generative classifiers** - build models of how class appears to most likely generate observations\n* **Gold labels** - human labels\n* **Maximue likelihood estimates** - relative frequencies\n* **Naive bayes assumption** - conditional independence are given for class c\n* **Representational harms** - harms caused by system to negatively affect a group\n* **Sentiment lexicon** - list of words pre-annotated with posiitive/negative sentiment\n* **Toxicity detection** - detecting hate speech and abuse\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n-Components of Probabilistic Machine Learning Classifier\n- Feature Representation of Input\n- Classification Function: computing $\\hat{y}$ via $p(x|y)$\n- Objective Function: cross-entropy loss functions\n- Algorithm for Optimizing Objective Function: stochastic gradient descent\n\n-Functions\n- Value: $z = (\\sum_{i=1} ^ n w_ix_i) + b$\n- Sigmoid Function: $\\sigma(z) = \\dfrac{1}{1 + e^{-z}}$\n- Sigmoid Function Property: $1 - \\sigma(x) = \\sigma(-x)$\n\n-Advantages of Logistic > Naive Bayes:\n- Conditional Independence: strong conditional independence assumed\n- Correlated Featurs: handled by logistic, multiplied twice by Naive Bayes\n- Naive Bayes Adv: works well on small datasets, easy to implement, fast to train\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \n-Loss Functions: $LC(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n- Conditional Max Likelihood: max log probabiity of true y labels\n- Cross Entropy Loss: function of negative log likelihood loss\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n-Gradient Descent\n- Goal: find weight that minimize loss function, averaged across all samples\n- Function: $argmin_θ \\dfrac{1}{m} \\sum_{i=1} ^ m LC(f(x^i; θ), y^i)$\n- Method: find where slop is rising msot steeply, move in opposite direction\n\n-Weight Updates\n- Single: $w^{t+1} = w^{t} - n\\dfrac{d}{dw}L(f(x;w),y)$\n- Logistic: $\\dfrac{\\delta L(\\hat{y},y)}{\\delta w_j} = [\\sigma (w \\cdot x + b) - y]x_j$\n \n\n## SLP Chapter 5.5 Regularization\n\n-L2 / Ridge Regularization\n- Preference: vectors with many small weights\n- Norm : $R(θ) = ||θ||_2 ^ 2 = \\sum_{j=1} ^ n θ_j ^ 2$\n- Regularizer: $\\hat{θ} = argmax_{θ} [\\sum_{i=1} ^ m logP(y^i | x^i)] - α \\sum_{j=1} ^ n θ_j ^ 2$\n\n-L1 / Lasso Regularization\n- Prefers: sparse, large weights with many zero vectors\n- Norm: $R(θ) = ||θ||_1 = \\sum_{j=1} ^ n θ_j$\n\n- Regularizer: $\\hat{θ} = argmax_{θ} [\\sum_{i=1} ^ m logP(y^i | x^i)] - α \\sum_{j=1} ^ n |θ_j|$\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n-Softmax Function: take vector $z$ of $k$ vlaues and map to probability distribution\n- Function: $softmax(z_i) = \\dfrac{exp(z_i)}{\\sum_{j=1} ^ k exp(z_j)}$\n- Probability: $p(y=c|x) = \\dfrac{exp(w_c \\cdot x + b_c)}{\\sum_{j=1} ^ K exp(w_j \\cdot x + b_j)}$\n\n-Features: seperate weight vector and bias for each of the classes\n\n-Learning\n- Loss: $LC = -logp(y=c|x) $ (see above)\n- Updates: $\\dfrac{\\delta LC}{\\delta w_{k,i}} = -(1(y-k)-p(y=k|x))x_i$\n\n\n## SLP Chapter 7.1 Units\n \n-Activation Functions:\n- Sigmoid: $y=\\sigma(z)=\\dfrac{1}{1+e^{-z}}$, ranges from 0 to 1\n- TanH: $y=\\dfrac{e^z - e^{-z}}{e^z + e{-z}}$, ranges from -1 to 1, smoothly differentiable, map outliers to mean\n- ReLu: $y=max(z,0)$, ranges from 0 to infinity, close to linear, no vanishing gradients\n\n-Layer Usage: intermediate (ReLU, tanh) and output (softmax)\n\n\n## SLP Chapter 7.2 The XOR problem\n\n-XOR: not linearly seperable, can only be solved with 2 layer neural network\n\n-Linear Layers: multiple layers can be reduced to single linear unit of weights\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n-Normalization: often normalize between layers\n-Replacing Bias Unit: add dummy node to each layer whose value will always be 1\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n-Neural Language Models vs n-gram\n- Pros: longer histories, better generalize over context of similar words, more accurate at word-prediction\n- Cons: slower to train, more complex, less interpretable\n\n-Forward Inference\n- Feature ($O(V)$): window that sees $N$ words in past, each as one-hot vectors\n- Embedding Matrix ($O(dV)$): column for each word, with each column having $d$ dimensions\n- Embedding Layer: output of multiplying feature one hot encode and embedding matrix\n\n-Algorithm\n- Step 1: create one-hot vector for each word and multiply by $E$\n- Step 2: multiply by $W$ and add $b$, pass through ReLu to get hidden layer\n- Step 3: multiply h by $U$\n- Step 4: apply softmax so that each node in output layer is probability\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n-Activation Function Derivatives\n- Sigmoid: $\\sigma(z)(1-\\sigma(z))$\n- Tanh: $1-tanh^2(z)$\n- ReLu: 0 for z < 0, 1 for z >= 0\n\n-Hyperparameters: leanring rate, minibatch size, model archiecture, number f hidden nodes, activation functions\n\n## SLP Chapter 7.7 Training the neural language model\n\n-Method 1: freezing, hold $E$ constant while modifying $W, U, b$\n\n-Method 2: gradient desent + back-propogation to create new $E$\n \n\n## Module 13 Lecture Notes\n<h3>Logistic Regression</h3>\n-Components of Classifier\n\n- Feature Representation: [$x_1,x_2,...,x_n$]\n- Classification Function: computes $p(y|x)$\n- Objective Function: minimizing error on training examples\n- Algorithm for optimizing objective function\n\n-Logistic Regression Functions\n- Z Function: $w \\cdot x + b$\n- Sigmoid Function: $y = \\dfrac{1}{1 + e ^{-z}}$\n- Probabilities: $P(y=1)= \\sigma(w \\cdot x + b) = \\dfrac{1}{1 + e ^{-w \\cdot x + b}}$\n\n-Multiclass Logistic Regression\n- Function: $softmax(z_i) = \\dfrac{e^{z_j}}{\\sum_{j=1} ^ k e^{z_j}}$\n<h3>Loss Functions</h3>\n-Goal: determine how much $\\hat{Y}$ differes from $y$\n-Cross Entropy Loss: negative log likelihood loss\n- Binary: $LC(\\hat{y}, y) = -logp(y|x) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})] =  -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n- Multiclass: $LC(\\hat{y}, y) = \\sum_{i=1} ^ C y_ilog(\\hat{y})$\n- Values: correct prediction (lower) vs incorrect (higher)\n-Loss on All Training: $log\\pi_{i=1} ^ m p(y^i | x^i) = -\\sum_{i=1} ^m (\\hat{y}^i | y^i)$\n<h3>Stochastic Gradient Descent</h3>\n-Logistic Regression: convex, one minimum, starting point unimportant\n\n-Gradient Types\n- Stochastic Gradient: choose single random example ... can fluctuate\n- Mini-batch: small batches ... loss is accumulated\n- Batch: choose entiredataset ... can take a while\n\n-Regularization\n- Logistic Regression: feature only occurs in one class ... get high weight (but might be accidental)\n- Regularization: Lasso (L1) an Ridge (L2)\n\n<h3>Neural Networks</h3>\n-Preceptrons: step function is _|-- so quick changes for weights\n\n-Activation Functions: sigmoid, tanh, ReLU (close to linear)\n\n-Feed-Forward NN: multilayer network, usually fully connected, no cycles, no backpropogation\n\n- Multiply weight matrix by input vector $x$\n- add bias vector $b$\n- apply activation function to obtain output $h = \\sigma(Wx + b)$\n\n-Training Neural Nets: loss function (cross-entropy loss), optimization algorithm (gradient descent), compute gradient of loss (error propogation)\n-Gradient Computations for one weight: $\\dfrac{\\delta LCE(w,b)}{\\delta wj} = (\\hat{y} - y)xj = (\\sigma(wx + b) - y)x_j$\n\n-Chain Rule:\n- $f(x) = u(v(x))$: $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dx}$\n- $f(x) = u(v(w(x)))$:  $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dw} \\cdot \\dfrac{dw}{dx}$\n\n\n## Module 13 Definitions\n* **Decision boundary** - threshold for cutting of logistic regression\n* **Gradient descent** - method for minimizing functions\n* **Sentiment classifier** - input of futures and use $P(y=1|x)$ to estimate 1 (positive) or 0 (negative)\n* **Forward inference** - task that runs a forward pass on network to product probability distribution of outputs\n* **Freezing** - use word2vec / pretrained algorithm to calculate embedding matrix\n* **Gradient** - vector that poitns in direction of greatest increase in function\n* **Loss function** - function that details how much prediction differs from actual\n* **Multi-layer preceptrons** - feed-forward networks\n* **Representation learning** - methods to learn features automatically (unsupervised) from input\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n-Issues with Feedforward\n- Limited Context: words utisde context can't impact decision\n- Windows: difficult to learn systematic patterns\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n-RNN Differences\n- Sequences: processed one item at a time\n- Recurrent Link: link augment computation with value from a previous hidden layer form preceding time\n\n-Components to Train\n- W: weights from input layer to hidden layer\n- U weights from previous hidden layer to current hidden layer\n- V: weights from hidden layer to output layer\n\n-Inference: essentially identical, with addition of $h_{t-1}$\n- Formula: $h_t = g(Uh_{t-1} + Wx_t)$ where $x_t$ is input and $h_{t-1}$ is hidden layer of previous time step\n- Dimensions: $W: d_h, d_{in}; U: d_h, d_h; V: d_{out}, d_{in}$\n\n-Training\n- Compute Loss Function at time $t$: need hidden layer from time $t-1$\n- Error: need to know influence of both current output and ones that follow\n\n-Backpropogation Through Time: Two-Pass Training\n- First Pass: forward inference to compute $h_t, y_t$\n- Second Pass: process sequence in reverse, compute required gradients as go, save error term for each step\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n-Idea: process inpute sequence as one word / time to predict next word from current word & previous hidden state\n\n-Property: $E=V$ \n\n## SLP Chapter 6.1 Lexical Semantics\n\n-Lemma and Sense: mouse (lemma), sung/carpets (wordform), each meanining (word sense)\n\n-Synonmy: principle of contrast, H20 and water\n\n-Word Similarity: cat and dogs\n\n-Word Relatedness: association (coffee, cup), semantic field (hospital: surgeon, nurse, scalpel)\n\n-Semantic Frames and Roles: buy/sell/pay\n\n-Connotation: valeance (pleasentness), arousal (intensity), dominance (degree of control) \n\n## SLP Chapter 6.2 Vector Semantics\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n-Term-Document Matrix: row (word), column (documnet), cell (# of times word in document)\n\n-Term-Term / Word-Word / Term-Context Matrix: row and columns (word), cell (#of times word appears in context) \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n-Vector Length: $|v| = \\sqrt{\\sum_{i=1} ^ N v_i ^ 2}$\n\n-Cosine Similarity: $$cosine(v,w) = \\dfrac{v \\cdot w}{|v||w|}$\n\n-Cosine Values: 1 (same), 0 (orthogonal), -1 (opposite, not possible since frequencies non-negative)\n\n\n## SLP Chapter 6.8 Word2vec\n\n-Probabiltiies: $$P(+|w,c); P(-|w,c) = 1 - P(+|w,c)$\n\n-Similarity: $c \\cdot w$, two words similar if embedding vectors are similar\n\n-Chooinsg Noise Words: according to unigram frequency, to allow rare noise words higher probabilitiy\n\n-Goal of Learning Algorithm: maximize similarity to $(w,c_{pos})$ and minimize to $(w,c_{neg})$\n\n-Embeddings Learn: target embedding (W) and context embedding (C) \n\n-Combination Method 1: add $w_i + c_i$\n-Combination Method 2: toss out $C$, only use $W$\n\n-Fasttext: solves unknown words and sparsity bu using subword models (represent words as bag of constituent n-grams)\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n-Effect of Context widnow: shorter (syntactic), longer (topically related but not similar)\n\n-Similariy and Association:\n- First-order co-occurence: nearby (wrote, book)\n- Secon-order co-occurence: similar neighbors (wrote, said)\n\n-Analogy: foten return morphological variant (potato -> potatos)\n\n-Historical Semantics\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\n-Allocational Harm: system allocates resources differently to differnt groups\n\n-Amplify Bias and implicit association\n\n-Debiasing: embedding space without stereotype\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n-Similarity: correlation between algorithm similarity score and assigned by humans\n\n-Analogy Tasks\n\n\n## Module 13 Lecture Notes\n<h3>Logistic Regression</h3>\n-Components of Classifier\n\n- Feature Representation: [$x_1,x_2,...,x_n$]\n- Classification Function: computes $p(y|x)$\n- Objective Function: minimizing error on training examples\n- Algorithm for optimizing objective function\n\n-Logistic Regression Functions\n- Z Function: $w \\cdot x + b$\n- Sigmoid Function: $y = \\dfrac{1}{1 + e ^{-z}}$\n- Probabilities: $P(y=1)= \\sigma(w \\cdot x + b) = \\dfrac{1}{1 + e ^{-w \\cdot x + b}}$\n\n-Multiclass Logistic Regression\n- Function: $softmax(z_i) = \\dfrac{e^{z_j}}{\\sum_{j=1} ^ k e^{z_j}}$\n<h3>Loss Functions</h3>\n-Goal: determine how much $\\hat{Y}$ differes from $y$\n-Cross Entropy Loss: negative log likelihood loss\n- Binary: $LC(\\hat{y}, y) = -logp(y|x) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})] =  -[ylog\\sigma(w \\cdot x + b) + (1-y)log(1-\\sigma(w \\cdot x + b))]$\n- Multiclass: $LC(\\hat{y}, y) = \\sum_{i=1} ^ C y_ilog(\\hat{y})$\n- Values: correct prediction (lower) vs incorrect (higher)\n-Loss on All Training: $log\\pi_{i=1} ^ m p(y^i | x^i) = -\\sum_{i=1} ^m (\\hat{y}^i | y^i)$\n<h3>Stochastic Gradient Descent</h3>\n-Logistic Regression: convex, one minimum, starting point unimportant\n\n-Gradient Types\n- Stochastic Gradient: choose single random example ... can fluctuate\n- Mini-batch: small batches ... loss is accumulated\n- Batch: choose entiredataset ... can take a while\n\n-Regularization\n- Logistic Regression: feature only occurs in one class ... get high weight (but might be accidental)\n- Regularization: Lasso (L1) an Ridge (L2)\n\n<h3>Neural Networks</h3>\n-Preceptrons: step function is _|-- so quick changes for weights\n\n-Activation Functions: sigmoid, tanh, ReLU (close to linear)\n\n-Feed-Forward NN: multilayer network, usually fully connected, no cycles, no backpropogation\n\n- Multiply weight matrix by input vector $x$\n- add bias vector $b$\n- apply activation function to obtain output $h = \\sigma(Wx + b)$\n\n-Training Neural Nets: loss function (cross-entropy loss), optimization algorithm (gradient descent), compute gradient of loss (error propogation)\n-Gradient Computations for one weight: $\\dfrac{\\delta LCE(w,b)}{\\delta wj} = (\\hat{y} - y)xj = (\\sigma(wx + b) - y)x_j$\n\n-Chain Rule:\n- $f(x) = u(v(x))$: $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dx}$\n- $f(x) = u(v(w(x)))$:  $\\dfrac{df}{dx} = \\dfrac{du}{dv} \\cdot \\dfrac{dv}{dw} \\cdot \\dfrac{dw}{dx}$\n\n\n## Module 14 Definitions\n* **Principle of constrast** - changes in linguistic form associated with changes in meaning\n* **Rnn** - network containing cycle with network connection (unit value dependant on earlier output)\n* **Distributional hypothesis** - waords in similar contexts have similar meanings\n* **Embeddings** - vectors that are short and dense\n* **Entailment** - definition\n* **Euclidian distance** - $\\sqrt{\\sum_{i=1} ^ N ||u_i - v_i|| ^ 2}$\n* **Information retrieval** - task of finding documents matching a query\n* **Self-supervision** - supervision without hand label\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-G3iM6v6fI0R"
      },
      "source": [
        ""
      ],
      "execution_count": 139,
      "outputs": []
    }
  ]
}