{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "94ad944f-0776-4328-d098-94c3325f66e6"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2e632c1a-fdde-43ce-a4fa-a16e31e92b68"
      },
      "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": 56,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "$$P(RESULT(a)=s')$$\n",
        "$$EU(a)=\\Sigma_{s'}P(RESULT(a)=s')U(s')$$\n",
        "\n",
        "MEU can be seen as intelligent behavior, however the process does not solve\n",
        "the AI problem. MEU does not describe a process for maximizing utility. Agents\n",
        "will have the highest performance if they follow MEU.\n",
        "\"\"\"\n",
        "\n",
        "chapter16_2 =  \"\"\"\n",
        "$A \\succ B$: A preferred over B\\n\n",
        "$A \\sim B$: A or B equally preferred\\n\n",
        "$A \\prec B$: B preferred over A\\n\n",
        "\n",
        "Lotteries can be represented as $L=[p_1,S_1;p_2,S_2;...p_n,S_n]$ where each (p, S)\n",
        "is the probability p of the outcome S.\\n\n",
        "\n",
        "The Axioms of Rationality:\n",
        "- Orderability: Eiter $(A \\succ B)$, $(B \\succ A)$, or $(A \\sim B)$\n",
        "- Transitivity: $(A \\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C)$\n",
        "- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p,A;1-p,C] \\sim B$\n",
        "- Substitutability: $A \\sim B \\Rightarrow [p,A;1-p,C] \\sim [p,B;1-p,C]$\n",
        "- Monotonicity: $A \\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B] \\succ\n",
        "[q,A;1-q,B]$\n",
        "- Decomposability: $[p,A;1-p,[q,B;1-q,C]] \\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "```\n",
        "def value_iteration():\n",
        "  while True:\n",
        "    old = V[s]\n",
        "    delta = 0\n",
        "    for s in states:\n",
        "      V[s] = max_a(Q(s,a))\n",
        "      if abs(V[s] - old) > delta:\n",
        "        delta = abs(V[s] - old)\n",
        "    if delta <= epsilon:\n",
        "      break\n",
        "```\\n\\n\n",
        "\n",
        "```\n",
        "def policy_iteration():\n",
        "  while True:\n",
        "    V = policy_evaluation()\n",
        "    stable = True\n",
        "    for s in states:\n",
        "      action = argmax_a(Q(s, a))\n",
        "      if Q(s, action) > Q(s, policy[s]):\n",
        "        policy[s] = action\n",
        "        stable = False\n",
        "    if stable:\n",
        "      break\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "A Markov decision process is:\n",
        "- sequential\n",
        "- fully observable\n",
        "- stochastic\n",
        "- additive rewards\n",
        "\n",
        "MDPs can be solved using expectimax.\n",
        "\n",
        "In order to define an MDP, we need the following:\n",
        "- Set of states\n",
        "- Set of actions\n",
        "- Transition function $T(s,a,s')$\n",
        "- Reward funciton $R(s,a,s')$\n",
        "- Initial state\n",
        "- (Optional) terminal states\n",
        "\n",
        "$V^*(s)$ = expected utility of state s when acting optimally.\\n\n",
        "$Q^*(s,a)$ = expected utility of taking action a from state s when acting optimally.\\n\n",
        "$\\pi^*(s)$ = optimal policy.\\n\n",
        "$$V^*(s)=max_a Q^*(s,a)$$\n",
        "$$Q^*(s,a)=\\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^*(s')]$$\n",
        "\n",
        "We can solve MDPs using value iteration:\n",
        "$$V_{k+1}(s) \\leftarrow max_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V_k(s')]$$\n",
        "Each iteration has time complexity $O(S^2A)$.\n",
        "\n",
        "We can also solve MDPs using policy iteration. This involves two steps,\n",
        "policy evaluation and policy improvement.\n",
        "Policy evaluation:\n",
        "$$V_{k+1}^\\pi \\leftarrow \\Sigma_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V_k^\\pi(s')$$\n",
        "Policy evaluation has a time complexity of $O(S^2)$.\n",
        "$$\\pi^*(s)= argmax_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^*(s')=argmax_a Q^*(s,a)$$\n",
        "\n",
        "Policy iteration:\n",
        "- Evaluation: $V^{\\pi_i}_{k+1}(s) \\leftarrow \\Sigma_{s'} T(s,\\pi_i(s),s')[R(s,\\pi_i(s),s')+\\gamma V^{\\pi_i}_k (s')]$\n",
        "- Improvement: $\\pi_{i+1}(s)=argmax_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^{\\pi_i}(s')]$\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\" : \"assigns values to states that encodes an agent's preferences\",\n",
        "  \"expected utility\" : \"average utility of states with each state weighted by \",\n",
        "  \"maximum expected utility (MEU)\": \"rational agents should choose actions that maximize expected utility\",\n",
        "  \"lottery\": \"set of possible outcomes for a given action\",\n",
        "  \"orderability\": \"an agent either prefers one lottery over another or equally prefer both of them\",\n",
        "  \"transitivity\": \"if an agent prefers A to B and B to C, then the agent prefers A to C\",\n",
        "  \"preference elicitation\": \"deducing a person's utility function\",\n",
        "  \"normalized utilities\": \"utilities scaled from 0 to 1\",\n",
        "  \"risk-averse\": \"prefer direct payment as opposed gamble\",\n",
        "  \"risk-prone\": \"more likely to take risks\",\n",
        "  \"policy\": \"set of actions for each state\",\n",
        "  \"insensitivity to monotonic transformations\": \"better states only need higher evaluations, scale is less important\",\n",
        "  \"micromort\": \"one in a million chance of death\",\n",
        "  \"QALYs\": \"quality-adjusted life years\",\n",
        "  \"monotonic preference\": \"preference that agent always wants more of\",\n",
        "  \"optimizers's curse\": \"estimated expected utilites tend to be too high\",\n",
        "  \"normative theory\": \"describes how agent should act\",\n",
        "  \"descriptive theory\": \"describes how agents act in reality\",\n",
        "  \"certainty effect\": \"certain gains are more favorable\",\n",
        "  \"ambiguity aversion\": \"agents prefer known probabilities\",\n",
        "  \"framing effect\": \"how situations are framed can change agents perception of the situations\",\n",
        "  \"anchoring effect\": \"agents tend to make judgements about utility based on other similar situations\",\n",
        "  \"markovian\": \"probability of reaching s' from s only depends on s\",\n",
        "  \"environment history\": \"sequence of states and actions\",\n",
        "  \"finite horizon\": \"environment has a time limit\",\n",
        "  \"infinite horizon\": \"environment has no time limit\",\n",
        "  \"nonstationary policy\": \"policy that depends on time\",\n",
        "  \"stationary policy\": \"policy that only depends on current state\",\n",
        "  \"proper policy\": \"policy that reaches a terminal state\",\n",
        "  \"contraction\": \"function that shrinks inputs towards some fixed point\",\n",
        "  \"asynchronous policy iteration\": \"not all states need to be updated on each iteration\",\n",
        "}"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "db77f0ee-4140-4348-e099-498ae4f56856",
        "cellView": "form"
      },
      "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": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n$$P(RESULT(a)=s')$$\n$$EU(a)=\\Sigma_{s'}P(RESULT(a)=s')U(s')$$\n\nMEU can be seen as intelligent behavior, however the process does not solve\nthe AI problem. MEU does not describe a process for maximizing utility. Agents\nwill have the highest performance if they follow MEU.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n$A \\succ B$: A preferred over B\n\n$A \\sim B$: A or B equally preferred\n\n$A \\prec B$: B preferred over A\n\n\nLotteries can be represented as $L=[p_1,S_1;p_2,S_2;...p_n,S_n]$ where each (p, S)\nis the probability p of the outcome S.\n\n\nThe Axioms of Rationality:\n- Orderability: Eiter $(A \\succ B)$, $(B \\succ A)$, or $(A \\sim B)$\n- Transitivity: $(A \\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C)$\n- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p,A;1-p,C] \\sim B$\n- Substitutability: $A \\sim B \\Rightarrow [p,A;1-p,C] \\sim [p,B;1-p,C]$\n- Monotonicity: $A \\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B] \\succ\n[q,A;1-q,B]$\n- Decomposability: $[p,A;1-p,[q,B;1-q,C]] \\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n```\ndef value_iteration():\n  while True:\n    old = V[s]\n    delta = 0\n    for s in states:\n      V[s] = max_a(Q(s,a))\n      if abs(V[s] - old) > delta:\n        delta = abs(V[s] - old)\n    if delta <= epsilon:\n      break\n```\n\n\n\n```\ndef policy_iteration():\n  while True:\n    V = policy_evaluation()\n    stable = True\n    for s in states:\n      action = argmax_a(Q(s, a))\n      if Q(s, action) > Q(s, policy[s]):\n        policy[s] = action\n        stable = False\n    if stable:\n      break\n```\n\n\n## Module 8 Lecture Notes\n\nA Markov decision process is:\n- sequential\n- fully observable\n- stochastic\n- additive rewards\n\nMDPs can be solved using expectimax.\n\nIn order to define an MDP, we need the following:\n- Set of states\n- Set of actions\n- Transition function $T(s,a,s')$\n- Reward funciton $R(s,a,s')$\n- Initial state\n- (Optional) terminal states\n\n$V^*(s)$ = expected utility of state s when acting optimally.\n\n$Q^*(s,a)$ = expected utility of taking action a from state s when acting optimally.\n\n$\\pi^*(s)$ = optimal policy.\n\n$$V^*(s)=max_a Q^*(s,a)$$\n$$Q^*(s,a)=\\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^*(s')]$$\n\nWe can solve MDPs using value iteration:\n$$V_{k+1}(s) \\leftarrow max_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V_k(s')]$$\nEach iteration has time complexity $O(S^2A)$.\n\nWe can also solve MDPs using policy iteration. This involves two steps,\npolicy evaluation and policy improvement.\nPolicy evaluation:\n$$V_{k+1}^\\pi \\leftarrow \\Sigma_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V_k^\\pi(s')$$\nPolicy evaluation has a time complexity of $O(S^2)$.\n$$\\pi^*(s)= argmax_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^*(s')=argmax_a Q^*(s,a)$$\n\nPolicy iteration:\n- Evaluation: $V^{\\pi_i}_{k+1}(s) \\leftarrow \\Sigma_{s'} T(s,\\pi_i(s),s')[R(s,\\pi_i(s),s')+\\gamma V^{\\pi_i}_k (s')]$\n- Improvement: $\\pi_{i+1}(s)=argmax_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^{\\pi_i}(s')]$\n\n\n## Module 8 Definitions\n* **Utility function** - assigns values to states that encodes an agent's preferences\n* **Expected utility** - average utility of states with each state weighted by \n* **Maximum expected utility (meu)** - rational agents should choose actions that maximize expected utility\n* **Lottery** - set of possible outcomes for a given action\n* **Orderability** - an agent either prefers one lottery over another or equally prefer both of them\n* **Transitivity** - if an agent prefers A to B and B to C, then the agent prefers A to C\n* **Preference elicitation** - deducing a person's utility function\n* **Normalized utilities** - utilities scaled from 0 to 1\n* **Risk-averse** - prefer direct payment as opposed gamble\n* **Risk-prone** - more likely to take risks\n* **Policy** - set of actions for each state\n* **Insensitivity to monotonic transformations** - better states only need higher evaluations, scale is less important\n* **Micromort** - one in a million chance of death\n* **Qalys** - quality-adjusted life years\n* **Monotonic preference** - preference that agent always wants more of\n* **Optimizers's curse** - estimated expected utilites tend to be too high\n* **Normative theory** - describes how agent should act\n* **Descriptive theory** - describes how agents act in reality\n* **Certainty effect** - certain gains are more favorable\n* **Ambiguity aversion** - agents prefer known probabilities\n* **Framing effect** - how situations are framed can change agents perception of the situations\n* **Anchoring effect** - agents tend to make judgements about utility based on other similar situations\n* **Markovian** - probability of reaching s' from s only depends on s\n* **Environment history** - sequence of states and actions\n* **Finite horizon** - environment has a time limit\n* **Infinite horizon** - environment has no time limit\n* **Nonstationary policy** - policy that depends on time\n* **Stationary policy** - policy that only depends on current state\n* **Proper policy** - policy that reaches a terminal state\n* **Contraction** - function that shrinks inputs towards some fixed point\n* **Asynchronous policy iteration** - not all states need to be updated on each iteration\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",
        "An n-armed bandit has n levers, each with some fixed unknown probability of winning.\n",
        "The gambler is responsible for choosing which lever to pull to maximize their winnings.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\"\"\"\n",
        "chapter22_2 =  \"\"\"\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "Exploration function: $f(u,n)$ = reward if $n < N_e$ else u\\n\n",
        "TD Q-learning: $Q(s,a) \\leftarrow Q(s,a) + alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') - Q(s,a)]$\\n\n",
        "SARSA update: $Q(s,a) \\leftarrow Q(s,a) + alpha [R(s,a,s') + \\gamma Q(s',a') - Q(s,a)]$\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\"\"\"\n",
        "chapter22_5 =  \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "Reinforcement learning is an MDP. However, we do not know T or R.\\n\n",
        "Temporal difference learning:\n",
        "- $sample = R(s,\\pi(s),s')+\\gamma V^{\\pi}(s')$\n",
        "- $V^\\pi(s) \\leftarrow (1-a)V^\\pi(s) + a (sample)$\n",
        "- $V^\\pi(s) \\leftarrow V^\\pi(s) + a (sample - V^\\pi(s))$\\n\n",
        "\n",
        "Exponential Moving Average: $x_n=(x_n+(1-a)x_{n-1}+(1-a)^2x_{n-2}+...)/(1+(1-a)+(1-a)^2+...)$\\n\n",
        "Temporal difference learning does not allow us to turn values into a policy, which is why\n",
        "we learn the Q-values instead.\\n\n",
        "\n",
        "Full reinforcement learning:\n",
        "- transitions unknown\n",
        "- rewards unknown\n",
        "- choose actions now\n",
        "- learn optimal policy and values\\n\n",
        "\n",
        "Q-learning: $Q_{k+1}(s,a) \\leftarrow \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma max_{a'} Q_k(s',a')]$.\n",
        "Q-learning converges to optimal policy, even if acting suboptimally. Q-learning is off-policy\n",
        "learning.\n",
        "\n",
        "Approximate Q-Learning: $Q(s,a)=w_1f_1(s,a)+w_2f_2(s,a)+...+w_nf_n(s,a)$.\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "  \"n-armed bandit\": \"bandit with n levers\",\n",
        "  \"exploitation\": \"following the current best actions\",\n",
        "  \"exploration\": \"explore unknown states and actions\",\n",
        "  \"markov reward process\": \"MDP with only one action\",\n",
        "  \"regret\": \"measure of total mistake cost, rational agents can make mistakes\",\n",
        "  \"sampling\": \"actions must be done repeatedly due to chance\",\n",
        "  \"difficulty\": \"learning is harder than solving known MDP\",\n",
        "  \"reinforcement learning\": \"agent learns to maximize expected rewards from environment\",\n",
        "  \"model-based learning\": \"use transition model to help interpret rewards\",\n",
        "  \"model-free learning\": \"agent does not know transition model or environment\",\n",
        "  \"action-utility learning\": \"type of model-free learning (q-learning)\",\n",
        "  \"policy search\": \"type of model-free learning where we learn policy pi\",\n",
        "  \"direct evaluation\": \"average observed sample values\",\n",
        "  \"opportunity cost\": \"utility that is given up by not trying another bandit arm\",\n",
        "  \"passive reinforcement learning\": \"policy is fixed, learn utilities\",\n",
        "  \"active reinforcement learning\": \"policy must also be learned with utilities\",\n",
        "  \"apprenticeship learning\": \"train using demonstrations instead of rewards\",\n",
        "  \"passive learning agent\": \"agent that tries to learn utility function for a given policy\",\n",
        "  \"active learning agent\": \"agent that can decide what actions to take\",\n",
        "  \"direct utility estimation\": \"utility of state is expected total reward from one state onwards\",\n",
        "  \"GLIE\": \"greedy in the limit of infinite exploration\",\n",
        "  \"absorbing state\": \"state with no actions or rewards once reached\",\n",
        "  \"off-policy\": \"allows exploration of actions not in current policy\",\n",
        "  \"on-policy\": \"stick to given policy\",\n",
        "  \"catastrophic forgetting\": \"agent forgets about bad outcomes and may end up repeating them\",\n",
        "  \"experience relay\": \"makes agent redo bad outcomes to help prevent catastrophic forgetting\",\n",
        "  \"reward shaping\": \"give rewards (pseudorewards) for making progress\",\n",
        "  \"hierarchical reinforcement learning\": \"break action sequences into smaller, easier pieces\",\n",
        "}"
      ],
      "execution_count": 60,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "efd01674-d14d-436e-d68f-100ddcda3eeb"
      },
      "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": 61,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nAn n-armed bandit has n levers, each with some fixed unknown probability of winning.\nThe gambler is responsible for choosing which lever to pull to maximize their winnings.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nExploration function: $f(u,n)$ = reward if $n < N_e$ else u\n\nTD Q-learning: $Q(s,a) \\leftarrow Q(s,a) + alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') - Q(s,a)]$\n\nSARSA update: $Q(s,a) \\leftarrow Q(s,a) + alpha [R(s,a,s') + \\gamma Q(s',a') - Q(s,a)]$\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n\n## Module 9 Lecture Notes\n\nReinforcement learning is an MDP. However, we do not know T or R.\n\nTemporal difference learning:\n- $sample = R(s,\\pi(s),s')+\\gamma V^{\\pi}(s')$\n- $V^\\pi(s) \\leftarrow (1-a)V^\\pi(s) + a (sample)$\n- $V^\\pi(s) \\leftarrow V^\\pi(s) + a (sample - V^\\pi(s))$\n\n\nExponential Moving Average: $x_n=(x_n+(1-a)x_{n-1}+(1-a)^2x_{n-2}+...)/(1+(1-a)+(1-a)^2+...)$\n\nTemporal difference learning does not allow us to turn values into a policy, which is why\nwe learn the Q-values instead.\n\n\nFull reinforcement learning:\n- transitions unknown\n- rewards unknown\n- choose actions now\n- learn optimal policy and values\n\n\nQ-learning: $Q_{k+1}(s,a) \\leftarrow \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma max_{a'} Q_k(s',a')]$.\nQ-learning converges to optimal policy, even if acting suboptimally. Q-learning is off-policy\nlearning.\n\nApproximate Q-Learning: $Q(s,a)=w_1f_1(s,a)+w_2f_2(s,a)+...+w_nf_n(s,a)$.\n\n\n## Module 9 Definitions\n* **N-armed bandit** - bandit with n levers\n* **Exploitation** - following the current best actions\n* **Exploration** - explore unknown states and actions\n* **Markov reward process** - MDP with only one action\n* **Regret** - measure of total mistake cost, rational agents can make mistakes\n* **Sampling** - actions must be done repeatedly due to chance\n* **Difficulty** - learning is harder than solving known MDP\n* **Reinforcement learning** - agent learns to maximize expected rewards from environment\n* **Model-based learning** - use transition model to help interpret rewards\n* **Model-free learning** - agent does not know transition model or environment\n* **Action-utility learning** - type of model-free learning (q-learning)\n* **Policy search** - type of model-free learning where we learn policy pi\n* **Direct evaluation** - average observed sample values\n* **Opportunity cost** - utility that is given up by not trying another bandit arm\n* **Passive reinforcement learning** - policy is fixed, learn utilities\n* **Active reinforcement learning** - policy must also be learned with utilities\n* **Apprenticeship learning** - train using demonstrations instead of rewards\n* **Passive learning agent** - agent that tries to learn utility function for a given policy\n* **Active learning agent** - agent that can decide what actions to take\n* **Direct utility estimation** - utility of state is expected total reward from one state onwards\n* **Glie** - greedy in the limit of infinite exploration\n* **Absorbing state** - state with no actions or rewards once reached\n* **Off-policy** - allows exploration of actions not in current policy\n* **On-policy** - stick to given policy\n* **Catastrophic forgetting** - agent forgets about bad outcomes and may end up repeating them\n* **Experience relay** - makes agent redo bad outcomes to help prevent catastrophic forgetting\n* **Reward shaping** - give rewards (pseudorewards) for making progress\n* **Hierarchical reinforcement learning** - break action sequences into smaller, easier pieces\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"\"\"\"\n",
        "chapter12_2 = \"\"\"\"\"\"\n",
        "chapter12_3 = \"\"\"\"\"\"\n",
        "chapter12_4 = \"\"\"\"\"\"\n",
        "chapter12_5 = \"\"\"\"\"\"\n",
        "chapter12_6 = \"\"\"\"\"\"\n",
        "chapter12_7 = \"\"\"\"\"\"\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",
        "SLP_chapter3_2 = \"\"\"\n",
        "Perplexity:\n",
        "$$\n",
        "PP(W)=\\sqrt[N]{\\prod_{i=1}^N \\dfrac{1}{P(w_i \\mid w_1...w_{i-1})}}\n",
        "$$\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\"\"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "Product rule: $P(y)P(x \\mid y) = P(x, y)$\\n\n",
        "Chain rule: $P(x_1,x_2,x_3,...)=P(x_1)P(x_2 \\mid x_1)P(x_3 \\mid x_1,x_2)...$\\n\n",
        "Bayes rule: $P(x \\mid y) = \\dfrac{P(y \\mid x)P(x)}{P(y)}$\\n\n",
        "\n",
        "Language models compute the probability of a sentence or sequence of words. This\n",
        "requires finding the probability of upcoming words. Therefore, language models\n",
        "compute $P(W)=P(w_1,w_2,w_3,...)$. Make the assumption (Markov Assumption) that\n",
        "each word only depends on the previous k words where k is the number of context\n",
        "words. The MLE for a bigram model is $P(w_i \\mid w_{i-1})=count(w_{i-1},w_i)/count(w_{i-1})$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "  \"belief state\" : \"representation of all possible states an agent may be in\",\n",
        "}"
      ],
      "execution_count": 62,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 984
        },
        "cellView": "form",
        "outputId": "8e462d4b-205c-410f-f619-90fe09250549"
      },
      "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": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n\n## AIMA Chapter 12.4 Independence\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nPerplexity:\n$$\nPP(W)=\\sqrt[N]{\\prod_{i=1}^N \\dfrac{1}{P(w_i \\mid w_1...w_{i-1})}}\n$$\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n\n## SLP Chapter 3.5 Smoothing\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n\n## Module 10 Lecture Notes\n\nProduct rule: $P(y)P(x \\mid y) = P(x, y)$\n\nChain rule: $P(x_1,x_2,x_3,...)=P(x_1)P(x_2 \\mid x_1)P(x_3 \\mid x_1,x_2)...$\n\nBayes rule: $P(x \\mid y) = \\dfrac{P(y \\mid x)P(x)}{P(y)}$\n\n\nLanguage models compute the probability of a sentence or sequence of words. This\nrequires finding the probability of upcoming words. Therefore, language models\ncompute $P(W)=P(w_1,w_2,w_3,...)$. Make the assumption (Markov Assumption) that\neach word only depends on the previous k words where k is the number of context\nwords. The MLE for a bigram model is $P(w_i \\mid w_{i-1})=count(w_{i-1},w_i)/count(w_{i-1})$\n\n\n## Module 10 Definitions\n* **Belief state** - representation of all possible states an agent may be in\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",
        "chapter13_2 = \"\"\"\n",
        "Bayes net definition:\n",
        "$$\n",
        "P(x_1,...,x_n) = \\prod_{i=1}^n \\Theta(x_i \\mid parents(X_i))\n",
        "$$\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "Issues with full join distribution table:\n",
        "- usually way to large\n",
        "- hard to learn from\n",
        "\n",
        "Bayes net help describe how local variables interact. Bayes nets consist of:\n",
        "- Set of nodes\n",
        "- Directed, acyclical graph\n",
        "- Conditional distribution for each node\n",
        "In general, a bayes net is a topology and local conditional probabilities. Bayes\n",
        "nets implicitly encode joint distributions.\\n\n",
        "\n",
        "There are $2^N$ possible joint distributions over N boolean variables. An N-node\n",
        "net of up to k parents is of size $O(N*2^{k+1})$\\n\n",
        "\n",
        "Active paths (O = node, X = observed node, D = node with observed descendant):\n",
        "- $O \\Rightarrow O \\Rightarrow O$\n",
        "- $O \\Leftarrow O \\Rightarrow O$\n",
        "- $O \\Rightarrow X \\Leftarrow O$\n",
        "- $O \\Rightarrow D \\Leftarrow O$\\n\n",
        "\n",
        "Inactive paths:\n",
        "- $O \\Rightarrow X \\Rightarrow O$\n",
        "- $O \\Leftarrow X \\Rightarrow O$\n",
        "- $O \\Rightarrow O \\Leftarrow O$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "  \"node\" : \"variable of bayes net\",    \n",
        "  \"arc\": \"interaction between variables in a bayes net\",\n",
        "  \"CPT\": \"conditional probability table\"\n",
        "}\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 783
        },
        "cellView": "form",
        "outputId": "f7086cc1-2747-4238-9b54-b0b7eafcb673"
      },
      "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": 65,
      "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\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nBayes net definition:\n$$\nP(x_1,...,x_n) = \\prod_{i=1}^n \\Theta(x_i \\mid parents(X_i))\n$$\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n\n## Module 11 Lecture Notes\n\nIssues with full join distribution table:\n- usually way to large\n- hard to learn from\n\nBayes net help describe how local variables interact. Bayes nets consist of:\n- Set of nodes\n- Directed, acyclical graph\n- Conditional distribution for each node\nIn general, a bayes net is a topology and local conditional probabilities. Bayes\nnets implicitly encode joint distributions.\n\n\nThere are $2^N$ possible joint distributions over N boolean variables. An N-node\nnet of up to k parents is of size $O(N*2^{k+1})$\n\n\nActive paths (O = node, X = observed node, D = node with observed descendant):\n- $O \\Rightarrow O \\Rightarrow O$\n- $O \\Leftarrow O \\Rightarrow O$\n- $O \\Rightarrow X \\Leftarrow O$\n- $O \\Rightarrow D \\Leftarrow O$\n\n\nInactive paths:\n- $O \\Rightarrow X \\Rightarrow O$\n- $O \\Leftarrow X \\Rightarrow O$\n- $O \\Rightarrow O \\Leftarrow O$\n\n\n## Module 11 Definitions\n* **Node** - variable of bayes net\n* **Arc** - interaction between variables in a bayes net\n* **Cpt** - conditional probability table\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\"\"\"\n",
        "chapter19_2 = \"\"\"\"\"\"\n",
        "chapter19_3 = \"\"\"\"\"\"\n",
        "chapter19_4 = \"\"\"\"\"\"\n",
        "chapter19_5 = \"\"\"\"\"\"\n",
        "chapter19_6 = \"\"\"\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\"\"\"\n",
        "slp_chapter4_2 = \"\"\"\"\"\"\n",
        "slp_chapter4_3 = \"\"\"\"\"\"\n",
        "slp_chapter4_4 = \"\"\"\"\"\"\n",
        "slp_chapter4_5 = \"\"\"\"\"\"\n",
        "slp_chapter4_6 = \"\"\"\"\"\"\n",
        "slp_chapter4_7 = \"\"\"\n",
        "$$\n",
        "precision=\\dfrac{tp}{tp+fp}\n",
        "$$\n",
        "$$\n",
        "recall=\\dfrac{tp}{tp+tn}\n",
        "$$\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\"\"\"\"\n",
        "slp_chapter4_9 = \"\"\"\"\"\"\n",
        "slp_chapter4_10 = \"\"\"\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "Naive Bayes assumes that given a label, all features are independent.\n",
        "General naive bayes model:\n",
        "$$\n",
        "P(Y,F_1,...,F_n)=P(Y)\\prod_i P(F_i \\mid Y)\n",
        "$$\n",
        "The above equation has $|Y|*|F|^n$ values and $n*|F|*|Y|$ parameters.\\n\n",
        "\n",
        "Naive bayes inference method:\n",
        "- start w/ a bunch of probabilities $P(Y)$ and $P(F_i \\mid Y)$ tables\n",
        "- use standard inference to compute $P(Y \\mid F_1...F_n)$\\n\n",
        "\n",
        "Generative model for naive bayes for text: $P(Y,W_1,...,W_n)=P(Y)\\prod_i P(W_i \\mid Y)$\\n\n",
        "\n",
        "$$\n",
        "P_{ML}(x)=\\dfrac{count(x)}{total samples}\n",
        "$$\n",
        "$$\n",
        "\\Theta_{ML}=argmax_\\Theta P(X \\mid \\Theta)=argmax_\\Theta \\prod_i P_\\Theta (X_i)\n",
        "$$\n",
        "\n",
        "Laplace smoothing: $P_{LAP}(x)=\\dfrac{c(x)+1}{\\sum_x [c(x)+1]}=\\dfrac{c(x)+1}{N+|X|}$\\n\n",
        "Laplace estimate: $P_{LAP,k}(x)=\\dfrac{c(x)+k}{N+k|X|}$\\n\n",
        "Laplace conditional: $P_{LAP,k}(x \\mid y)=\\dfrac{c(x,y)+k}{c(y)+k|X|}$\\n\n",
        "Linear interpolation: $P_{LIN}(x \\mid y) = alpha \\hat{P}(x \\mid y) + (1 - alpha)\\hat{P}(x)$\\n\n",
        "Confidence: $confidence(x)=max_y P(y \\mid x)$\\n\n",
        "Perceptron activation: $activation_w(x)=\\sum_i w_i f_i(x)= w f(x)$\\n\n",
        "Perceptron binary classification: $y=1$ if $wf(x) \\geq 0$ and $y=-1$ if $wf(x)<0$\n",
        "- If classification is wrong, then $w = w + y_{true} f$\\n\n",
        "Perceptron properties:\n",
        "- separability: true if some parameters get training set perfectly correct\n",
        "- convergence: if training is separable, then perceptron will converge (binary)\n",
        "- mistake bound: max number of mistakes related to margin of separability\\n\n",
        "Problems with perceptrons:\n",
        "- noise: issues with data that is not separable\n",
        "- mediocre generalization: perceptron finds barely separable solution\n",
        "- overfitting/overtraining\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "  \"induction\": \"create rule from observations\",\n",
        "  \"factored representation\": \"vector representation of data\",\n",
        "  \"supervised learning\": \"learning with feedback\",\n",
        "  \"unsupervised learning\": \"learning without feedback\",\n",
        "  \"generative classifier\": \"models how a class can generate input data\",\n",
        "  \"discriminative classifier\": \"model that learns what features are most important\",\n",
        "  \"bag-of-words\": \"unordered set of words with only the words frequencies\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 66,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8849ca10-76d7-4998-8f33-fdf02fd16020"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 67,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n$$\nprecision=\\dfrac{tp}{tp+fp}\n$$\n$$\nrecall=\\dfrac{tp}{tp+tn}\n$$\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n\n## Module 12 Lecture Notes\n\nNaive Bayes assumes that given a label, all features are independent.\nGeneral naive bayes model:\n$$\nP(Y,F_1,...,F_n)=P(Y)\\prod_i P(F_i \\mid Y)\n$$\nThe above equation has $|Y|*|F|^n$ values and $n*|F|*|Y|$ parameters.\n\n\nNaive bayes inference method:\n- start w/ a bunch of probabilities $P(Y)$ and $P(F_i \\mid Y)$ tables\n- use standard inference to compute $P(Y \\mid F_1...F_n)$\n\n\nGenerative model for naive bayes for text: $P(Y,W_1,...,W_n)=P(Y)\\prod_i P(W_i \\mid Y)$\n\n\n$$\nP_{ML}(x)=\\dfrac{count(x)}{total samples}\n$$\n$$\n\\Theta_{ML}=argmax_\\Theta P(X \\mid \\Theta)=argmax_\\Theta \\prod_i P_\\Theta (X_i)\n$$\n\nLaplace smoothing: $P_{LAP}(x)=\\dfrac{c(x)+1}{\\sum_x [c(x)+1]}=\\dfrac{c(x)+1}{N+|X|}$\n\nLaplace estimate: $P_{LAP,k}(x)=\\dfrac{c(x)+k}{N+k|X|}$\n\nLaplace conditional: $P_{LAP,k}(x \\mid y)=\\dfrac{c(x,y)+k}{c(y)+k|X|}$\n\nLinear interpolation: $P_{LIN}(x \\mid y) = alpha \\hat{P}(x \\mid y) + (1 - alpha)\\hat{P}(x)$\n\nConfidence: $confidence(x)=max_y P(y \\mid x)$\n\nPerceptron activation: $activation_w(x)=\\sum_i w_i f_i(x)= w f(x)$\n\nPerceptron binary classification: $y=1$ if $wf(x) \\geq 0$ and $y=-1$ if $wf(x)<0$\n- If classification is wrong, then $w = w + y_{true} f$\n\nPerceptron properties:\n- separability: true if some parameters get training set perfectly correct\n- convergence: if training is separable, then perceptron will converge (binary)\n- mistake bound: max number of mistakes related to margin of separability\n\nProblems with perceptrons:\n- noise: issues with data that is not separable\n- mediocre generalization: perceptron finds barely separable solution\n- overfitting/overtraining\n\n\n## Module 12 Definitions\n* **Induction** - create rule from observations\n* **Factored representation** - vector representation of data\n* **Supervised learning** - learning with feedback\n* **Unsupervised learning** - learning without feedback\n* **Generative classifier** - models how a class can generate input data\n* **Discriminative classifier** - model that learns what features are most important\n* **Bag-of-words** - unordered set of words with only the words frequencies\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",
        "slp_chapter5_2 = \"\"\"\"\"\"\n",
        "slp_chapter5_3 = \"\"\"\"\"\"\n",
        "slp_chapter5_4 = \"\"\"\"\"\"\n",
        "slp_chapter5_5 = \"\"\"\"\"\"\n",
        "slp_chapter5_6 = \"\"\"\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\"\"\"\n",
        "slp_chapter7_2 = \"\"\"\"\"\"\n",
        "slp_chapter7_3 = \"\"\"\"\"\"\n",
        "slp_chapter7_4 = \"\"\"\"\"\"\n",
        "slp_chapter7_5 = \"\"\"\"\"\"\n",
        "slp_chapter7_6 = \"\"\"\"\"\"\n",
        "slp_chapter7_7 = \"\"\"\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "Classifier components:\n",
        "- feature representation (vector)\n",
        "- classification function for estimating label\n",
        "- objective function for learning (loss)\n",
        "- optimizer\\n\n",
        "\n",
        "Sigmoid: $\\sigma(x)=\\dfrac{1}{1+e^{-z}}$\\n\n",
        "$P(y=1)=\\sigma(wx+b)=\\dfrac{1}{1+e^{-(wx+b)}}$\\n\n",
        "$L(\\hat{y},y)_{MSE}=\\dfrac{1}{2}(\\hat{y}-y)^2$\\n\n",
        "Binary cross-entropy: $p(y\\mid x)=\\hat{y}^y (1-\\hat{y})^{1-y}$\\n\n",
        "log(BCE): $logp(y\\mid x)=ylog\\hat{y}+(1-y)log(1-\\hat{y})$\\n\n",
        "$softmax(z_i)=\\dfrac{e^{z_j}}{\\sum_{j=1}^k e^{z_j}}$\\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {}\n"
      ],
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "090a6150-7e99-4976-d303-ac286fac113a"
      },
      "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": 69,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n\n## SLP Chapter 5.5 Regularization\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n\n## SLP Chapter 7.1 Units\n\n\n## SLP Chapter 7.2 The XOR problem\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n\n## SLP Chapter 7.7 Training the neural language model\n\n\n## Module 13 Lecture Notes\n\nClassifier components:\n- feature representation (vector)\n- classification function for estimating label\n- objective function for learning (loss)\n- optimizer\n\n\nSigmoid: $\\sigma(x)=\\dfrac{1}{1+e^{-z}}$\n\n$P(y=1)=\\sigma(wx+b)=\\dfrac{1}{1+e^{-(wx+b)}}$\n\n$L(\\hat{y},y)_{MSE}=\\dfrac{1}{2}(\\hat{y}-y)^2$\n\nBinary cross-entropy: $p(y\\mid x)=\\hat{y}^y (1-\\hat{y})^{1-y}$\n\nlog(BCE): $logp(y\\mid x)=ylog\\hat{y}+(1-y)log(1-\\hat{y})$\n\n$softmax(z_i)=\\dfrac{e^{z_j}}{\\sum_{j=1}^k e^{z_j}}$\n\n\n\n## Module 13 Definitions\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",
        "slp_chapter9_2 = \"\"\"\"\"\"\n",
        "slp_chapter9_3 = \"\"\"\"\"\"\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",
        "slp_chapter6_2 = \"\"\"\"\"\"\n",
        "slp_chapter6_3 = \"\"\"\"\"\"\n",
        "slp_chapter6_4 = \"\"\"\"\"\"\n",
        "slp_chapter6_8 = \"\"\"\"\"\"\n",
        "slp_chapter6_10 = \"\"\"\"\"\"\n",
        "slp_chapter6_11 = \"\"\"\"\"\"\n",
        "slp_chapter6_12 = \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "Word meaning should encode:\n",
        "- synonyms\n",
        "- antonyms\n",
        "- connotations (pos/neg)\n",
        "- semantic roles (words related to one another),\n",
        "- entailment\n",
        "\n",
        "For a term-document matrix, each column vector represents a document and\n",
        "each row represents a term. The value of each cell describes how often\n",
        "a word occurs in a document. The length of the document vectors is the\n",
        "vocabulary size. Document vectors can be sparse. Can compare documents\n",
        "by their column vectors.\n",
        "\n",
        "Euclidean distance between vectors u and v: $\\sqrt{\\sum_{i=1}^N |u_i - v_i|^2}$\\n\n",
        "L2 normalization: divide each cell in term row by $||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$\\n\n",
        "Cosine distance: $1-\\dfrac{\\sum_{i=1}^n u_i * v_i}{\\sqrt{\\sum_{i=1}^n u_i^2} * \\sqrt{\\sum_{i=1}^n v_i^2}}$\\n\n",
        "TF-IDF: Term Frequency * Inverse Document Frequency\\n\n",
        "Inverse Document Frequency: $\\dfrac{1}{Document Frequency}$\\n\n",
        "Advantages of neural language models over n-grams:\n",
        "- no smoothing needed\n",
        "- can handle longer histories\n",
        "- can generalize over contexts of similar words\n",
        "- tend to have higher predictive accuracy\\n\n",
        "Neural language models are slower to train than n-grams\\n\n",
        "Neural LM process:\n",
        "- associate each word with a vector representation, this creates the notion\n",
        "of similarity between words\n",
        "- express joint probability function of a word sequence in terms of word vectors\n",
        "- learn word vectors and parameters of probability function\n",
        "- Input: k-gram of words\n",
        "- Output: probability distribution over next word\n",
        "- each word is associated with an embedding vector\n",
        "- training creates word embeddings\\n\n",
        "Word2Vec:\n",
        "- learn embeddings\n",
        "- train classifier to predict neighboring words\n",
        "- easy to train compared to SVD\\n\n",
        "Skip-gram algorithm\n",
        "- Treat target word and surrounding words as positive examples\n",
        "- Randomly sample other words and treat them as negative samples\n",
        "- Use logistic regression to classify positive and negative samples\n",
        "- Use weights as embeddings\\n\n",
        "$P(- \\mid t,c)=1-P(+ \\mid t,c) = \\dfrac{e^{-t*c}}{1+e^{-t*c}}$\\n\n",
        "$$\n",
        "P(+ \\mid t,c_{1:k}) = \\prod_{i=1}^k \\dfrac{1}{1+e^{-t*c_i}}\n",
        "$$\\n\n",
        "Word2Vec learns embeddings automatically\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {}"
      ],
      "execution_count": 70,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "977fcfc4-bbe1-4383-d86e-88719c80562f",
        "cellView": "form"
      },
      "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 14 Lecture Notes\", module14_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": 71,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n\n## SLP Chapter 6.8 Word2vec\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n\n## Module 14 Lecture Notes\n\nWord meaning should encode:\n- synonyms\n- antonyms\n- connotations (pos/neg)\n- semantic roles (words related to one another),\n- entailment\n\nFor a term-document matrix, each column vector represents a document and\neach row represents a term. The value of each cell describes how often\na word occurs in a document. The length of the document vectors is the\nvocabulary size. Document vectors can be sparse. Can compare documents\nby their column vectors.\n\nEuclidean distance between vectors u and v: $\\sqrt{\\sum_{i=1}^N |u_i - v_i|^2}$\n\nL2 normalization: divide each cell in term row by $||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$\n\nCosine distance: $1-\\dfrac{\\sum_{i=1}^n u_i * v_i}{\\sqrt{\\sum_{i=1}^n u_i^2} * \\sqrt{\\sum_{i=1}^n v_i^2}}$\n\nTF-IDF: Term Frequency * Inverse Document Frequency\n\nInverse Document Frequency: $\\dfrac{1}{Document Frequency}$\n\nAdvantages of neural language models over n-grams:\n- no smoothing needed\n- can handle longer histories\n- can generalize over contexts of similar words\n- tend to have higher predictive accuracy\n\nNeural language models are slower to train than n-grams\n\nNeural LM process:\n- associate each word with a vector representation, this creates the notion\nof similarity between words\n- express joint probability function of a word sequence in terms of word vectors\n- learn word vectors and parameters of probability function\n- Input: k-gram of words\n- Output: probability distribution over next word\n- each word is associated with an embedding vector\n- training creates word embeddings\n\nWord2Vec:\n- learn embeddings\n- train classifier to predict neighboring words\n- easy to train compared to SVD\n\nSkip-gram algorithm\n- Treat target word and surrounding words as positive examples\n- Randomly sample other words and treat them as negative samples\n- Use logistic regression to classify positive and negative samples\n- Use weights as embeddings\n\n$P(- \\mid t,c)=1-P(+ \\mid t,c) = \\dfrac{e^{-t*c}}{1+e^{-t*c}}$\n\n$$\nP(+ \\mid t,c_{1:k}) = \\prod_{i=1}^k \\dfrac{1}{1+e^{-t*c_i}}\n$$\n\nWord2Vec learns embeddings automatically\n\n\n## Module 14 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "7ba0f0bf-6adc-40f1-ab54-5e3cd9957d22"
      },
      "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": 72,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n$$P(RESULT(a)=s')$$\n$$EU(a)=\\Sigma_{s'}P(RESULT(a)=s')U(s')$$\n\nMEU can be seen as intelligent behavior, however the process does not solve\nthe AI problem. MEU does not describe a process for maximizing utility. Agents\nwill have the highest performance if they follow MEU.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n$A \\succ B$: A preferred over B\n\n$A \\sim B$: A or B equally preferred\n\n$A \\prec B$: B preferred over A\n\n\nLotteries can be represented as $L=[p_1,S_1;p_2,S_2;...p_n,S_n]$ where each (p, S)\nis the probability p of the outcome S.\n\n\nThe Axioms of Rationality:\n- Orderability: Eiter $(A \\succ B)$, $(B \\succ A)$, or $(A \\sim B)$\n- Transitivity: $(A \\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C)$\n- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p,A;1-p,C] \\sim B$\n- Substitutability: $A \\sim B \\Rightarrow [p,A;1-p,C] \\sim [p,B;1-p,C]$\n- Monotonicity: $A \\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B] \\succ\n[q,A;1-q,B]$\n- Decomposability: $[p,A;1-p,[q,B;1-q,C]] \\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n```\ndef value_iteration():\n  while True:\n    old = V[s]\n    delta = 0\n    for s in states:\n      V[s] = max_a(Q(s,a))\n      if abs(V[s] - old) > delta:\n        delta = abs(V[s] - old)\n    if delta <= epsilon:\n      break\n```\n\n\n\n```\ndef policy_iteration():\n  while True:\n    V = policy_evaluation()\n    stable = True\n    for s in states:\n      action = argmax_a(Q(s, a))\n      if Q(s, action) > Q(s, policy[s]):\n        policy[s] = action\n        stable = False\n    if stable:\n      break\n```\n\n\n## Module 8 Lecture Notes\n\nA Markov decision process is:\n- sequential\n- fully observable\n- stochastic\n- additive rewards\n\nMDPs can be solved using expectimax.\n\nIn order to define an MDP, we need the following:\n- Set of states\n- Set of actions\n- Transition function $T(s,a,s')$\n- Reward funciton $R(s,a,s')$\n- Initial state\n- (Optional) terminal states\n\n$V^*(s)$ = expected utility of state s when acting optimally.\n\n$Q^*(s,a)$ = expected utility of taking action a from state s when acting optimally.\n\n$\\pi^*(s)$ = optimal policy.\n\n$$V^*(s)=max_a Q^*(s,a)$$\n$$Q^*(s,a)=\\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^*(s')]$$\n\nWe can solve MDPs using value iteration:\n$$V_{k+1}(s) \\leftarrow max_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V_k(s')]$$\nEach iteration has time complexity $O(S^2A)$.\n\nWe can also solve MDPs using policy iteration. This involves two steps,\npolicy evaluation and policy improvement.\nPolicy evaluation:\n$$V_{k+1}^\\pi \\leftarrow \\Sigma_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V_k^\\pi(s')$$\nPolicy evaluation has a time complexity of $O(S^2)$.\n$$\\pi^*(s)= argmax_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^*(s')=argmax_a Q^*(s,a)$$\n\nPolicy iteration:\n- Evaluation: $V^{\\pi_i}_{k+1}(s) \\leftarrow \\Sigma_{s'} T(s,\\pi_i(s),s')[R(s,\\pi_i(s),s')+\\gamma V^{\\pi_i}_k (s')]$\n- Improvement: $\\pi_{i+1}(s)=argmax_a \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma V^{\\pi_i}(s')]$\n\n\n## Module 8 Definitions\n* **Utility function** - assigns values to states that encodes an agent's preferences\n* **Expected utility** - average utility of states with each state weighted by \n* **Maximum expected utility (meu)** - rational agents should choose actions that maximize expected utility\n* **Lottery** - set of possible outcomes for a given action\n* **Orderability** - an agent either prefers one lottery over another or equally prefer both of them\n* **Transitivity** - if an agent prefers A to B and B to C, then the agent prefers A to C\n* **Preference elicitation** - deducing a person's utility function\n* **Normalized utilities** - utilities scaled from 0 to 1\n* **Risk-averse** - prefer direct payment as opposed gamble\n* **Risk-prone** - more likely to take risks\n* **Policy** - set of actions for each state\n* **Insensitivity to monotonic transformations** - better states only need higher evaluations, scale is less important\n* **Micromort** - one in a million chance of death\n* **Qalys** - quality-adjusted life years\n* **Monotonic preference** - preference that agent always wants more of\n* **Optimizers's curse** - estimated expected utilites tend to be too high\n* **Normative theory** - describes how agent should act\n* **Descriptive theory** - describes how agents act in reality\n* **Certainty effect** - certain gains are more favorable\n* **Ambiguity aversion** - agents prefer known probabilities\n* **Framing effect** - how situations are framed can change agents perception of the situations\n* **Anchoring effect** - agents tend to make judgements about utility based on other similar situations\n* **Markovian** - probability of reaching s' from s only depends on s\n* **Environment history** - sequence of states and actions\n* **Finite horizon** - environment has a time limit\n* **Infinite horizon** - environment has no time limit\n* **Nonstationary policy** - policy that depends on time\n* **Stationary policy** - policy that only depends on current state\n* **Proper policy** - policy that reaches a terminal state\n* **Contraction** - function that shrinks inputs towards some fixed point\n* **Asynchronous policy iteration** - not all states need to be updated on each iteration\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nAn n-armed bandit has n levers, each with some fixed unknown probability of winning.\nThe gambler is responsible for choosing which lever to pull to maximize their winnings.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nExploration function: $f(u,n)$ = reward if $n < N_e$ else u\n\nTD Q-learning: $Q(s,a) \\leftarrow Q(s,a) + alpha [R(s,a,s') + \\gamma max_{a'} Q(s',a') - Q(s,a)]$\n\nSARSA update: $Q(s,a) \\leftarrow Q(s,a) + alpha [R(s,a,s') + \\gamma Q(s',a') - Q(s,a)]$\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n\n## Module 9 Lecture Notes\n\nReinforcement learning is an MDP. However, we do not know T or R.\n\nTemporal difference learning:\n- $sample = R(s,\\pi(s),s')+\\gamma V^{\\pi}(s')$\n- $V^\\pi(s) \\leftarrow (1-a)V^\\pi(s) + a (sample)$\n- $V^\\pi(s) \\leftarrow V^\\pi(s) + a (sample - V^\\pi(s))$\n\n\nExponential Moving Average: $x_n=(x_n+(1-a)x_{n-1}+(1-a)^2x_{n-2}+...)/(1+(1-a)+(1-a)^2+...)$\n\nTemporal difference learning does not allow us to turn values into a policy, which is why\nwe learn the Q-values instead.\n\n\nFull reinforcement learning:\n- transitions unknown\n- rewards unknown\n- choose actions now\n- learn optimal policy and values\n\n\nQ-learning: $Q_{k+1}(s,a) \\leftarrow \\Sigma_{s'} T(s,a,s')[R(s,a,s')+\\gamma max_{a'} Q_k(s',a')]$.\nQ-learning converges to optimal policy, even if acting suboptimally. Q-learning is off-policy\nlearning.\n\nApproximate Q-Learning: $Q(s,a)=w_1f_1(s,a)+w_2f_2(s,a)+...+w_nf_n(s,a)$.\n\n\n## Module 9 Definitions\n* **N-armed bandit** - bandit with n levers\n* **Exploitation** - following the current best actions\n* **Exploration** - explore unknown states and actions\n* **Markov reward process** - MDP with only one action\n* **Regret** - measure of total mistake cost, rational agents can make mistakes\n* **Sampling** - actions must be done repeatedly due to chance\n* **Difficulty** - learning is harder than solving known MDP\n* **Reinforcement learning** - agent learns to maximize expected rewards from environment\n* **Model-based learning** - use transition model to help interpret rewards\n* **Model-free learning** - agent does not know transition model or environment\n* **Action-utility learning** - type of model-free learning (q-learning)\n* **Policy search** - type of model-free learning where we learn policy pi\n* **Direct evaluation** - average observed sample values\n* **Opportunity cost** - utility that is given up by not trying another bandit arm\n* **Passive reinforcement learning** - policy is fixed, learn utilities\n* **Active reinforcement learning** - policy must also be learned with utilities\n* **Apprenticeship learning** - train using demonstrations instead of rewards\n* **Passive learning agent** - agent that tries to learn utility function for a given policy\n* **Active learning agent** - agent that can decide what actions to take\n* **Direct utility estimation** - utility of state is expected total reward from one state onwards\n* **Glie** - greedy in the limit of infinite exploration\n* **Absorbing state** - state with no actions or rewards once reached\n* **Off-policy** - allows exploration of actions not in current policy\n* **On-policy** - stick to given policy\n* **Catastrophic forgetting** - agent forgets about bad outcomes and may end up repeating them\n* **Experience relay** - makes agent redo bad outcomes to help prevent catastrophic forgetting\n* **Reward shaping** - give rewards (pseudorewards) for making progress\n* **Hierarchical reinforcement learning** - break action sequences into smaller, easier pieces\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n\n## AIMA Chapter 12.4 Independence\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\nPerplexity:\n$$\nPP(W)=\\sqrt[N]{\\prod_{i=1}^N \\dfrac{1}{P(w_i \\mid w_1...w_{i-1})}}\n$$\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n\n## SLP Chapter 3.5 Smoothing\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n\n## Module 10 Lecture Notes\n\nProduct rule: $P(y)P(x \\mid y) = P(x, y)$\n\nChain rule: $P(x_1,x_2,x_3,...)=P(x_1)P(x_2 \\mid x_1)P(x_3 \\mid x_1,x_2)...$\n\nBayes rule: $P(x \\mid y) = \\dfrac{P(y \\mid x)P(x)}{P(y)}$\n\n\nLanguage models compute the probability of a sentence or sequence of words. This\nrequires finding the probability of upcoming words. Therefore, language models\ncompute $P(W)=P(w_1,w_2,w_3,...)$. Make the assumption (Markov Assumption) that\neach word only depends on the previous k words where k is the number of context\nwords. The MLE for a bigram model is $P(w_i \\mid w_{i-1})=count(w_{i-1},w_i)/count(w_{i-1})$\n\n\n## Module 10 Definitions\n* **Belief state** - representation of all possible states an agent may be in\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nBayes net definition:\n$$\nP(x_1,...,x_n) = \\prod_{i=1}^n \\Theta(x_i \\mid parents(X_i))\n$$\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n\n## Module 11 Lecture Notes\n\nIssues with full join distribution table:\n- usually way to large\n- hard to learn from\n\nBayes net help describe how local variables interact. Bayes nets consist of:\n- Set of nodes\n- Directed, acyclical graph\n- Conditional distribution for each node\nIn general, a bayes net is a topology and local conditional probabilities. Bayes\nnets implicitly encode joint distributions.\n\n\nThere are $2^N$ possible joint distributions over N boolean variables. An N-node\nnet of up to k parents is of size $O(N*2^{k+1})$\n\n\nActive paths (O = node, X = observed node, D = node with observed descendant):\n- $O \\Rightarrow O \\Rightarrow O$\n- $O \\Leftarrow O \\Rightarrow O$\n- $O \\Rightarrow X \\Leftarrow O$\n- $O \\Rightarrow D \\Leftarrow O$\n\n\nInactive paths:\n- $O \\Rightarrow X \\Rightarrow O$\n- $O \\Leftarrow X \\Rightarrow O$\n- $O \\Rightarrow O \\Leftarrow O$\n\n\n## Module 11 Definitions\n* **Node** - variable of bayes net\n* **Arc** - interaction between variables in a bayes net\n* **Cpt** - conditional probability table\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n$$\nprecision=\\dfrac{tp}{tp+fp}\n$$\n$$\nrecall=\\dfrac{tp}{tp+tn}\n$$\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n\n## Module 12 Lecture Notes\n\nNaive Bayes assumes that given a label, all features are independent.\nGeneral naive bayes model:\n$$\nP(Y,F_1,...,F_n)=P(Y)\\prod_i P(F_i \\mid Y)\n$$\nThe above equation has $|Y|*|F|^n$ values and $n*|F|*|Y|$ parameters.\n\n\nNaive bayes inference method:\n- start w/ a bunch of probabilities $P(Y)$ and $P(F_i \\mid Y)$ tables\n- use standard inference to compute $P(Y \\mid F_1...F_n)$\n\n\nGenerative model for naive bayes for text: $P(Y,W_1,...,W_n)=P(Y)\\prod_i P(W_i \\mid Y)$\n\n\n$$\nP_{ML}(x)=\\dfrac{count(x)}{total samples}\n$$\n$$\n\\Theta_{ML}=argmax_\\Theta P(X \\mid \\Theta)=argmax_\\Theta \\prod_i P_\\Theta (X_i)\n$$\n\nLaplace smoothing: $P_{LAP}(x)=\\dfrac{c(x)+1}{\\sum_x [c(x)+1]}=\\dfrac{c(x)+1}{N+|X|}$\n\nLaplace estimate: $P_{LAP,k}(x)=\\dfrac{c(x)+k}{N+k|X|}$\n\nLaplace conditional: $P_{LAP,k}(x \\mid y)=\\dfrac{c(x,y)+k}{c(y)+k|X|}$\n\nLinear interpolation: $P_{LIN}(x \\mid y) = alpha \\hat{P}(x \\mid y) + (1 - alpha)\\hat{P}(x)$\n\nConfidence: $confidence(x)=max_y P(y \\mid x)$\n\nPerceptron activation: $activation_w(x)=\\sum_i w_i f_i(x)= w f(x)$\n\nPerceptron binary classification: $y=1$ if $wf(x) \\geq 0$ and $y=-1$ if $wf(x)<0$\n- If classification is wrong, then $w = w + y_{true} f$\n\nPerceptron properties:\n- separability: true if some parameters get training set perfectly correct\n- convergence: if training is separable, then perceptron will converge (binary)\n- mistake bound: max number of mistakes related to margin of separability\n\nProblems with perceptrons:\n- noise: issues with data that is not separable\n- mediocre generalization: perceptron finds barely separable solution\n- overfitting/overtraining\n\n\n## Module 12 Definitions\n* **Induction** - create rule from observations\n* **Factored representation** - vector representation of data\n* **Supervised learning** - learning with feedback\n* **Unsupervised learning** - learning without feedback\n* **Generative classifier** - models how a class can generate input data\n* **Discriminative classifier** - model that learns what features are most important\n* **Bag-of-words** - unordered set of words with only the words frequencies\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n\n## SLP Chapter 5.5 Regularization\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n\n## SLP Chapter 7.1 Units\n\n\n## SLP Chapter 7.2 The XOR problem\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n\n## SLP Chapter 7.7 Training the neural language model\n\n\n## Module 13 Lecture Notes\n\nClassifier components:\n- feature representation (vector)\n- classification function for estimating label\n- objective function for learning (loss)\n- optimizer\n\n\nSigmoid: $\\sigma(x)=\\dfrac{1}{1+e^{-z}}$\n\n$P(y=1)=\\sigma(wx+b)=\\dfrac{1}{1+e^{-(wx+b)}}$\n\n$L(\\hat{y},y)_{MSE}=\\dfrac{1}{2}(\\hat{y}-y)^2$\n\nBinary cross-entropy: $p(y\\mid x)=\\hat{y}^y (1-\\hat{y})^{1-y}$\n\nlog(BCE): $logp(y\\mid x)=ylog\\hat{y}+(1-y)log(1-\\hat{y})$\n\n$softmax(z_i)=\\dfrac{e^{z_j}}{\\sum_{j=1}^k e^{z_j}}$\n\n\n\n## Module 13 Definitions\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n\n## SLP Chapter 6.8 Word2vec\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n\n## Module 14 Lecture Notes\n\nWord meaning should encode:\n- synonyms\n- antonyms\n- connotations (pos/neg)\n- semantic roles (words related to one another),\n- entailment\n\nFor a term-document matrix, each column vector represents a document and\neach row represents a term. The value of each cell describes how often\na word occurs in a document. The length of the document vectors is the\nvocabulary size. Document vectors can be sparse. Can compare documents\nby their column vectors.\n\nEuclidean distance between vectors u and v: $\\sqrt{\\sum_{i=1}^N |u_i - v_i|^2}$\n\nL2 normalization: divide each cell in term row by $||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$\n\nCosine distance: $1-\\dfrac{\\sum_{i=1}^n u_i * v_i}{\\sqrt{\\sum_{i=1}^n u_i^2} * \\sqrt{\\sum_{i=1}^n v_i^2}}$\n\nTF-IDF: Term Frequency * Inverse Document Frequency\n\nInverse Document Frequency: $\\dfrac{1}{Document Frequency}$\n\nAdvantages of neural language models over n-grams:\n- no smoothing needed\n- can handle longer histories\n- can generalize over contexts of similar words\n- tend to have higher predictive accuracy\n\nNeural language models are slower to train than n-grams\n\nNeural LM process:\n- associate each word with a vector representation, this creates the notion\nof similarity between words\n- express joint probability function of a word sequence in terms of word vectors\n- learn word vectors and parameters of probability function\n- Input: k-gram of words\n- Output: probability distribution over next word\n- each word is associated with an embedding vector\n- training creates word embeddings\n\nWord2Vec:\n- learn embeddings\n- train classifier to predict neighboring words\n- easy to train compared to SVD\n\nSkip-gram algorithm\n- Treat target word and surrounding words as positive examples\n- Randomly sample other words and treat them as negative samples\n- Use logistic regression to classify positive and negative samples\n- Use weights as embeddings\n\n$P(- \\mid t,c)=1-P(+ \\mid t,c) = \\dfrac{e^{-t*c}}{1+e^{-t*c}}$\n\n$$\nP(+ \\mid t,c_{1:k}) = \\prod_{i=1}^k \\dfrac{1}{1+e^{-t*c_i}}\n$$\n\nWord2Vec learns embeddings automatically\n\n\n## Module 14 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}