{
  "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": "d2903f97-df12-4954-f55a-ed5506a775de"
      },
      "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": 2,
      "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": "be6bd072-9366-4db1-e634-1975f3c5cbb8"
      },
      "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": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "33621576-0aea-42a6-a092-2d84b5fa98f7"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "Module 8: Markov Decision Processes     \n",
        "\n",
        "The transition model deterministic → Stochastic,  T(s, a, s’) output the probability of arriving in state s’ given that we are in state s and doing action a\n",
        "Transitions are Markvoain: the probability of getting t o s’ not depend on history states, only depends on s and a.\n",
        "Reward function/ Utility function: R( s, a, s’ ) , rewards are additive\n",
        "Markov Decision Process: \n",
        "Non-deterministic search problems, can use expectimax search to solve\n",
        "a sequential decision problem, fully observable environment, with a stochastic transition model, with additive rewards\n",
        "Solve MDP:\n",
        "Define: a set of states, a set of actions, transition function (the probability is called the probability model), reward function (reinforcement learning reward function is unknow, MDP is known), initial state, terminal state\n",
        "Solution: for search problem -- > a plan: a fixed sequence of actions, for MDP → a policy, what best action to take in whichever state, 𝝿(s) = a\n",
        "Discounting: values of rewards decay exponentially\n",
        "Why discount: helps our algorithms converge, discount of 0.5 → U([1,2,3]) = 0.5^0*1 + 0.5^1*2 + 0.5^2*3 \n",
        "Utilities: if the preferences are stationary, there are two ways to define utilities: Additive utility and discount utility, additive utility is actually discount utility if gamma is 1, so there is only one way to define utilities which is discount utility\n",
        "Infinite utilities: \n",
        "Finite horizon: similar to depth limited search, terminate the game after t steps, but the policies will be non stationary and policy depends on how many steps left\n",
        "Discounting: using 0 < gamma < 1, the smaller the gamma, the smaller the horizon, more focus on short term rewards\n",
        "Absorbing state: guarantee that all policy will reach terminated state\n",
        "MDP search trees:\n",
        "Difference with ExpectMax: 1. Transitions function will encode the probabilities 2. The reward will be given at each state of the tree\n",
        "Q state: when we in a state and we commit to a action but the outcome is uncertain yet\n",
        "The value (utility) of a state s: V * (s) = expected utility starting in s and acting optimally\n",
        "The value (utility) of a q-state (s,a): Q* (s,a) = expected utility starting out having taken action a from state s and (thereafter) acting optimally\n",
        "Value Iteration: Start with V0 (s) = 0: no time steps left means an expected reward sum of zero, Repeat until convergence, Complexity of each iteration: O(S^2 * A), S is number of states, A is number of actions\n",
        "Theorem: will converge to unique optimal values • Basic idea: approximations get refined towards optimal values • Policy may converge long before values do\n",
        "Policy Evalluation: \n",
        "Efficiency: O(S^2 ) per iteration\n",
        "Without the maxes, the bellman equations are just a linear system, we can just solve it\n",
        "Policy Extraction: gets the policy impied by the values\n",
        "Policy extraction from Q state: pi(s) = max_a Q(s,a), just select the best q value, very easy\n",
        "Problems with Value iteration: slow, O(S^2A), the max at each state rarely changes, the policy converge much faster\n",
        "Alternative: policy iteration\n",
        "Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n",
        "Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future values • Repeat steps until policy converges\n",
        "Comparison:\n",
        "Two iterations compute the same thing (all optimal values), they are both dynamic programming, all variations of bellman equation, all use one-step lookahead expectimax fragments\n",
        "Value iteration: update both values and the policy\n",
        "Policy iteration: We choose a fixed policy first, find all values, then update the policy\n",
        "Why average utilities, why not use max? Because the world is uncertain, a rational agent should choose the action that maximizes expected utility\n",
        "For minmax reasoning, terminal function scale doesn’t matter, the magnitude doesnt matter, the first layer chooses the bigger one, and the second layer chooses the min one. Insensitivity to monotonic transformation. \n",
        "But for average-case expectmax (for MDP), magnitude matters \n",
        "Rational Preferences for Agent: Rational preferences imply behavior describable as maximaziation of expected utilities\n",
        "MEU Principle: choose the action that maximizies expected utilities (agent can be rational without representing utilities and probabilities)\n",
        "Q&A\n",
        "Difference between utility function and performance measure of an agent: performance measure gives a score for a history, utility function only applies to next state (guide future actions)\n",
        "Orderability of preferences: agent must choose, can not refuse to bet, it either prefer one or be indifferent\n",
        "Exactly one of A > B, B > A, A ~ B holds\n",
        "If an agent's preferences are rational (i.e. follow the axioms of utility theory), what two things can we say?: The agent has a utility function and we can compute the expected utility of a lottery. \n",
        " If there exists a utility function describing an agent's preferences, it means that the agent is explicitly maximizing that utility function in its own deliberations: ​​False. A rational agent can be implemented with many different methods. Any rational agent can be described by a utiltiy function, but the implementation could be e.g. a lookup table.\n",
        "To define MDP: A set of states, Initial states, Terminal states, Transition ModelReward function\n",
        "An environment history is a sequence of states and actions\n",
        "A policy that depends on time is called Nonstationary (finite horizon → nonstationary, infinite horizon → stationary)\n",
        "Q(S,A) or action-utility function is the expected value of an action a in a given state s\n",
        "Bellman update is update the utility of a state iteratively\n",
        "3 steps for value iteration: \n",
        "Start with arbitrary initial values for each state\n",
        "Apply the bellman update\n",
        "Repeat step 2 until reaching equilibrium\n",
        "What is the intuition for why value iteration works? The Bellman update moves information locally. \n",
        "Policy iteration: Policy evaluation and policy improvement\n",
        "Asynchronous policy iterationupdates only a subset of states\n",
        "MDPs be solved using linear programming\n",
        "Large MDP can not solve using value or policy iteration\n",
        "Explore and exploit: The tradeoff between exploitation of the current best action to obtain rewards and exploration of previously unknown states and actions to gain information which might lead to better long-term rewards.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "print(\"The length in words is\", len(module8_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module8_lecture_notes))\n"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 959\n",
            "The length in characters is 6362\n"
          ]
        }
      ]
    },
    {
      "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": "87292576-8051-4610-ce99-eb8176ed3fb4"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nModule 8: Markov Decision Processes     \n\nThe transition model deterministic → Stochastic,  T(s, a, s’) output the probability of arriving in state s’ given that we are in state s and doing action a\nTransitions are Markvoain: the probability of getting t o s’ not depend on history states, only depends on s and a.\nReward function/ Utility function: R( s, a, s’ ) , rewards are additive\nMarkov Decision Process: \nNon-deterministic search problems, can use expectimax search to solve\na sequential decision problem, fully observable environment, with a stochastic transition model, with additive rewards\nSolve MDP:\nDefine: a set of states, a set of actions, transition function (the probability is called the probability model), reward function (reinforcement learning reward function is unknow, MDP is known), initial state, terminal state\nSolution: for search problem -- > a plan: a fixed sequence of actions, for MDP → a policy, what best action to take in whichever state, 𝝿(s) = a\nDiscounting: values of rewards decay exponentially\nWhy discount: helps our algorithms converge, discount of 0.5 → U([1,2,3]) = 0.5^0*1 + 0.5^1*2 + 0.5^2*3 \nUtilities: if the preferences are stationary, there are two ways to define utilities: Additive utility and discount utility, additive utility is actually discount utility if gamma is 1, so there is only one way to define utilities which is discount utility\nInfinite utilities: \nFinite horizon: similar to depth limited search, terminate the game after t steps, but the policies will be non stationary and policy depends on how many steps left\nDiscounting: using 0 < gamma < 1, the smaller the gamma, the smaller the horizon, more focus on short term rewards\nAbsorbing state: guarantee that all policy will reach terminated state\nMDP search trees:\nDifference with ExpectMax: 1. Transitions function will encode the probabilities 2. The reward will be given at each state of the tree\nQ state: when we in a state and we commit to a action but the outcome is uncertain yet\nThe value (utility) of a state s: V * (s) = expected utility starting in s and acting optimally\nThe value (utility) of a q-state (s,a): Q* (s,a) = expected utility starting out having taken action a from state s and (thereafter) acting optimally\nValue Iteration: Start with V0 (s) = 0: no time steps left means an expected reward sum of zero, Repeat until convergence, Complexity of each iteration: O(S^2 * A), S is number of states, A is number of actions\nTheorem: will converge to unique optimal values • Basic idea: approximations get refined towards optimal values • Policy may converge long before values do\nPolicy Evalluation: \nEfficiency: O(S^2 ) per iteration\nWithout the maxes, the bellman equations are just a linear system, we can just solve it\nPolicy Extraction: gets the policy impied by the values\nPolicy extraction from Q state: pi(s) = max_a Q(s,a), just select the best q value, very easy\nProblems with Value iteration: slow, O(S^2A), the max at each state rarely changes, the policy converge much faster\nAlternative: policy iteration\nPolicy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\nPolicy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future values • Repeat steps until policy converges\nComparison:\nTwo iterations compute the same thing (all optimal values), they are both dynamic programming, all variations of bellman equation, all use one-step lookahead expectimax fragments\nValue iteration: update both values and the policy\nPolicy iteration: We choose a fixed policy first, find all values, then update the policy\nWhy average utilities, why not use max? Because the world is uncertain, a rational agent should choose the action that maximizes expected utility\nFor minmax reasoning, terminal function scale doesn’t matter, the magnitude doesnt matter, the first layer chooses the bigger one, and the second layer chooses the min one. Insensitivity to monotonic transformation. \nBut for average-case expectmax (for MDP), magnitude matters \nRational Preferences for Agent: Rational preferences imply behavior describable as maximaziation of expected utilities\nMEU Principle: choose the action that maximizies expected utilities (agent can be rational without representing utilities and probabilities)\nQ&A\nDifference between utility function and performance measure of an agent: performance measure gives a score for a history, utility function only applies to next state (guide future actions)\nOrderability of preferences: agent must choose, can not refuse to bet, it either prefer one or be indifferent\nExactly one of A > B, B > A, A ~ B holds\nIf an agent's preferences are rational (i.e. follow the axioms of utility theory), what two things can we say?: The agent has a utility function and we can compute the expected utility of a lottery. \n If there exists a utility function describing an agent's preferences, it means that the agent is explicitly maximizing that utility function in its own deliberations: ​​False. A rational agent can be implemented with many different methods. Any rational agent can be described by a utiltiy function, but the implementation could be e.g. a lookup table.\nTo define MDP: A set of states, Initial states, Terminal states, Transition ModelReward function\nAn environment history is a sequence of states and actions\nA policy that depends on time is called Nonstationary (finite horizon → nonstationary, infinite horizon → stationary)\nQ(S,A) or action-utility function is the expected value of an action a in a given state s\nBellman update is update the utility of a state iteratively\n3 steps for value iteration: \nStart with arbitrary initial values for each state\nApply the bellman update\nRepeat step 2 until reaching equilibrium\nWhat is the intuition for why value iteration works? The Bellman update moves information locally. \nPolicy iteration: Policy evaluation and policy improvement\nAsynchronous policy iterationupdates only a subset of states\nMDPs be solved using linear programming\nLarge MDP can not solve using value or policy iteration\nExplore and exploit: The tradeoff between exploitation of the current best action to obtain rewards and exploration of previously unknown states and actions to gain information which might lead to better long-term rewards.\n\n\n \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning\n",
        "\n",
        "1.   List item\n",
        "2.   List item\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Module 9: Reinforcement Learning\n",
        "\n",
        "Similar to MDP but don’t know Transition function and Reward function\n",
        "Model-Based Learning (have a explicit representation of the transition function and try to learn the probability)\n",
        "learn the model by trying out transition functions, try to form a MDP problem\n",
        "Learn based on experiences\n",
        "Step 1: Learn MDP by trying\n",
        "Step 2: Solve MDP using value or policy iteration\n",
        "Model-Free Learning (never try to learn probability, ignore them and try to learn the value of states): passive reinforcement learning →  goal is learn the state values, fixed policy, simplified task is policy evaluation and No choice on what actions to take (fixed policy)\n",
        "Direct Evaluation:average together observed sample values. Bad about direct evaluation, takes a long time to learn, each state must be learned separately\n",
        "Sample-Based Policy Evaluation\n",
        "Temporal Difference Learning: bad about TDL, we only have value of state but not Q value, so we can not turn values into a new policy\n",
        "Active Reinforcement Learning: full reinforcement learning, try to find ptimal policy while don’t know transition and rewards\n",
        "Goal: learn the optimal policy\n",
        "Q-Learning: sample-based Q-value iteration\n",
        "Q-learning converges to optimal policy, even if you’re acting suboptimally! This is called off-policy learning, means that you start with a estimated policy which is not accurate\n",
        "Requirements: You have to explore enough You have to eventually make the learning rate small enough … but not decrease it too quickly\n",
        "Exploration vs. Exploitation: how to explore\n",
        "1. Randomly choose actions (epsilon-greedy) : Every time step, flip a coin With (small) probability ε, act randomly With (large) probability 1-ε, act on current policy\n",
        "Problem: already explored the space, but still keep randomly visit it\n",
        "Solution1: lower ε over time\n",
        "Solution 2: Exploration Function\n",
        "2. Exploration Function: f(u, n) = u + k/n, u = reward of this state, k = award we set, n number of visits of this state\n",
        "The more we explore this state, the less additional award we give it, this encourage explore less visited states\n",
        "Regret: Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n",
        "Approximate Q-Learning: hard to learn when you have very many states, the idea here is to generalize states, give similar states similar values without visit again and again\n",
        "Learn about some small number of training states from experience Generalize that experience to new, similar situations\n",
        "Linear regression + Q-Learning + Gradient Descent\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 929
        },
        "cellView": "form",
        "outputId": "ba957d78-8a1d-4043-aa4a-1146f70175de"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n Module 9: Reinforcement Learning\n\nSimilar to MDP but don’t know Transition function and Reward function\nModel-Based Learning (have a explicit representation of the transition function and try to learn the probability)\nlearn the model by trying out transition functions, try to form a MDP problem\nLearn based on experiences\nStep 1: Learn MDP by trying\nStep 2: Solve MDP using value or policy iteration\nModel-Free Learning (never try to learn probability, ignore them and try to learn the value of states): passive reinforcement learning →  goal is learn the state values, fixed policy, simplified task is policy evaluation and No choice on what actions to take (fixed policy)\nDirect Evaluation:average together observed sample values. Bad about direct evaluation, takes a long time to learn, each state must be learned separately\nSample-Based Policy Evaluation\nTemporal Difference Learning: bad about TDL, we only have value of state but not Q value, so we can not turn values into a new policy\nActive Reinforcement Learning: full reinforcement learning, try to find ptimal policy while don’t know transition and rewards\nGoal: learn the optimal policy\nQ-Learning: sample-based Q-value iteration\nQ-learning converges to optimal policy, even if you’re acting suboptimally! This is called off-policy learning, means that you start with a estimated policy which is not accurate\nRequirements: You have to explore enough You have to eventually make the learning rate small enough … but not decrease it too quickly\nExploration vs. Exploitation: how to explore\n1. Randomly choose actions (epsilon-greedy) : Every time step, flip a coin With (small) probability ε, act randomly With (large) probability 1-ε, act on current policy\nProblem: already explored the space, but still keep randomly visit it\nSolution1: lower ε over time\nSolution 2: Exploration Function\n2. Exploration Function: f(u, n) = u + k/n, u = reward of this state, k = award we set, n number of visits of this state\nThe more we explore this state, the less additional award we give it, this encourage explore less visited states\nRegret: Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\nApproximate Q-Learning: hard to learn when you have very many states, the idea here is to generalize states, give similar states similar values without visit again and again\nLearn about some small number of training states from experience Generalize that experience to new, similar situations\nLinear regression + Q-Learning + Gradient Descent\n\n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Module 10: Probabilies and Language Models\n",
        "probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is. \n",
        "An event is a set E of outcomes\n",
        "A probabilistic model is a joint distribution over a set of random variables\n",
        "Marginal distributions are sub-tables which eliminate variables Marginalization (summing out): Combine collapsed rows by adding\n",
        "Inference by enumeration: P(Q | e1, e2, ...), similar to linear regression, Q is y, e is x (features)\n",
        "Step1: select the entries consistent with the evidence\n",
        "Step2: Sum out H to get join of Query and evidence\n",
        "Step3: Normalize \n",
        "Product Rule: P(y) P(x|y) = P(x,y)\n",
        "Conditional Probability: P(a|b) = P(a,b) / P(b)\n",
        "Chain Rule: P(a,b,c) = P(a) P(b|a) P(c|a,b) or P(x1,x2,..,xn) = ∏i P(xi | x1, x2, x3, .., Xi-1)\n",
        "Bayes’ Rule: P(x|y) = (P(y|x) P(x))  /   P(y)\n",
        "Probabilistic Language Model: P(won|the underdog team) = Count(the underdog team won) / Count(the underdog team) \n",
        "given “the underdog team” to predict the next word, count the number of appeararence of “the underdog team”, go to the dictionary with key = “the underdog team” and count the number of appeararence of “won” before “the underdog team”\n",
        "Markov Assumption: only depends on the previous k words, not the whole context\n",
        "Unigram model: P(w1,w2,w3..wn)\n",
        "Bigram model\n",
        "How many ways are there to apply the chain rule to a joint distribution with NN random variables?: N!\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e34ad3e9-4b8b-4111-be86-f261ec569ad2"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Module 10: Probabilies and Language Models\nprobabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is. \nAn event is a set E of outcomes\nA probabilistic model is a joint distribution over a set of random variables\nMarginal distributions are sub-tables which eliminate variables Marginalization (summing out): Combine collapsed rows by adding\nInference by enumeration: P(Q | e1, e2, ...), similar to linear regression, Q is y, e is x (features)\nStep1: select the entries consistent with the evidence\nStep2: Sum out H to get join of Query and evidence\nStep3: Normalize \nProduct Rule: P(y) P(x|y) = P(x,y)\nConditional Probability: P(a|b) = P(a,b) / P(b)\nChain Rule: P(a,b,c) = P(a) P(b|a) P(c|a,b) or P(x1,x2,..,xn) = ∏i P(xi | x1, x2, x3, .., Xi-1)\nBayes’ Rule: P(x|y) = (P(y|x) P(x))  /   P(y)\nProbabilistic Language Model: P(won|the underdog team) = Count(the underdog team won) / Count(the underdog team) \ngiven “the underdog team” to predict the next word, count the number of appeararence of “the underdog team”, go to the dictionary with key = “the underdog team” and count the number of appeararence of “won” before “the underdog team”\nMarkov Assumption: only depends on the previous k words, not the whole context\nUnigram model: P(w1,w2,w3..wn)\nBigram model\nHow many ways are there to apply the chain rule to a joint distribution with NN random variables?: N!\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Two variables are independent if P(x,y) = P(x)P(y)\n",
        "Check if two variables are independent, multiply marginal probabilities to see if it’s same as joint probability\n",
        "Conditional Independence: X is conditionally independent of Y given Z, P(x,y|z) = P(x|z)P(y|Z) or P(x|z,y) = P(x|z)  (EX:Detect is conditionally independent of Toothache given Cavity)\n",
        "Umbrella is conditionally independent to Traffic given it’s raining (Because we already know it’s raining, it doesn’t matter whether we see umbrella or not)\n",
        "Conditional Independence reduces the number of probability tables\n",
        "Bayes’nets / graphical models help us express conditional independence assumptions\n",
        "a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n",
        "graphical models\n",
        "Shade graph: observed, Unshaded: unobserved, would like to make a inference (y value)\n",
        "Graphical Model Notation\n",
        "Nodes: variables, can be observed/assigned or unassigned/unobserved \n",
        "Arcs: interactions § Indicate “direct influence” between variables § Formally: encode conditional independence, Cavity -> Toothache\n",
        "                                                             | - > Catch, because toothache and catch     are conditionally independent\n",
        "Bayes’ Net: each random variable is a node, A1 -> X, A2 -> X  means P(X|A1,A2)\n",
        "Cavity -> Toothache, Cavity -> Catch, P(+cavity, +detect, -toothache) = P(ToothAche | Cavity) * P(Catch | Cavity)\n",
        "p(X1,X2,...,Xn) = Product of P(xi | parents(xi))\n",
        "Not every BN can represent every joint distribution § The topology enforces certain conditional independencies\n",
        "Casuality is not a mathmaticall necessity \n",
        "BNs need not actually be causal\n",
        "Sometimes no causal net exists\n",
        "Some arrows reflect correlation not causation\n",
        "The arrows really encodes conditional independence rather than casual structure \n",
        "Size of BN:\n",
        "Size of joint distribution over N boolean variables: 2^n\n",
        "Size of N node net if nodes have up to k parents: N * 2^(k+1)\n",
        "Pros:  Huge space savings! § Also easier to elicit local CPTs § Also faster to answer queries\n",
        "Assumptions of NB \n",
        "D-separation Algorithm: \n",
        "Show A is not independent of B, one example set of CPTs for which A is not independent of B is sufficient to show this independence is not guaranteed.\n",
        "Casual Chain: A->B->C, X: low pressure ->Y: Rain -> Z: Traffic, X and Z not independent, A independent of C given B, middle part will block A to C\n",
        "Common Cause: two children have one parent cause, Y: Project due ->X: piazza busy, Y:Project due -> Z: office hours full, X and Z is not independent because P( +x | +y ) = 1, P( -x | -y ) = 1, P( +z | +y ) = 1, P( -z | -y ) = 1,but  X is guaranteed to be independent with Z given Y because Observing the cause blocks influence between effects\n",
        "Common Effect: one child haas two parents, X: raining -> Z: traffic, Y:Ballgame -> Z: traffic, x and y is independent, X and Y is not independent given Z because seeing traffic puts the rain and the ballgame in competition as explanation and Observing an effect activates influence between possible causes.\n",
        "Any BN can be break down to the 3 cases above\n",
        "Conclusion:\n",
        "One inactive block on the path, the whole path is inactive. A path is active if each triple is active: check every triple\n",
        "All paths are Inactive paths ->  independence, if A -> B has many paths, we have to make sure all paths are inactive to achieve independence, one active path will turn the A -> B active, thus no independence\n",
        "A independent of B | C, means that C is observed, so we will shade C\n",
        "A independent of B means that no node will be shaded\n",
        "When we look at triples, only the middle node matters, whether it is observed or not matters. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 879
        },
        "cellView": "form",
        "outputId": "cadcf3d6-11de-42ca-9397-9d841e22ced4"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Two variables are independent if P(x,y) = P(x)P(y)\nCheck if two variables are independent, multiply marginal probabilities to see if it’s same as joint probability\nConditional Independence: X is conditionally independent of Y given Z, P(x,y|z) = P(x|z)P(y|Z) or P(x|z,y) = P(x|z)  (EX:Detect is conditionally independent of Toothache given Cavity)\nUmbrella is conditionally independent to Traffic given it’s raining (Because we already know it’s raining, it doesn’t matter whether we see umbrella or not)\nConditional Independence reduces the number of probability tables\nBayes’nets / graphical models help us express conditional independence assumptions\na technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\ngraphical models\nShade graph: observed, Unshaded: unobserved, would like to make a inference (y value)\nGraphical Model Notation\nNodes: variables, can be observed/assigned or unassigned/unobserved \nArcs: interactions § Indicate “direct influence” between variables § Formally: encode conditional independence, Cavity -> Toothache\n                                                             | - > Catch, because toothache and catch     are conditionally independent\nBayes’ Net: each random variable is a node, A1 -> X, A2 -> X  means P(X|A1,A2)\nCavity -> Toothache, Cavity -> Catch, P(+cavity, +detect, -toothache) = P(ToothAche | Cavity) * P(Catch | Cavity)\np(X1,X2,...,Xn) = Product of P(xi | parents(xi))\nNot every BN can represent every joint distribution § The topology enforces certain conditional independencies\nCasuality is not a mathmaticall necessity \nBNs need not actually be causal\nSometimes no causal net exists\nSome arrows reflect correlation not causation\nThe arrows really encodes conditional independence rather than casual structure \nSize of BN:\nSize of joint distribution over N boolean variables: 2^n\nSize of N node net if nodes have up to k parents: N * 2^(k+1)\nPros:  Huge space savings! § Also easier to elicit local CPTs § Also faster to answer queries\nAssumptions of NB \nD-separation Algorithm: \nShow A is not independent of B, one example set of CPTs for which A is not independent of B is sufficient to show this independence is not guaranteed.\nCasual Chain: A->B->C, X: low pressure ->Y: Rain -> Z: Traffic, X and Z not independent, A independent of C given B, middle part will block A to C\nCommon Cause: two children have one parent cause, Y: Project due ->X: piazza busy, Y:Project due -> Z: office hours full, X and Z is not independent because P( +x | +y ) = 1, P( -x | -y ) = 1, P( +z | +y ) = 1, P( -z | -y ) = 1,but  X is guaranteed to be independent with Z given Y because Observing the cause blocks influence between effects\nCommon Effect: one child haas two parents, X: raining -> Z: traffic, Y:Ballgame -> Z: traffic, x and y is independent, X and Y is not independent given Z because seeing traffic puts the rain and the ballgame in competition as explanation and Observing an effect activates influence between possible causes.\nAny BN can be break down to the 3 cases above\nConclusion:\nOne inactive block on the path, the whole path is inactive. A path is active if each triple is active: check every triple\nAll paths are Inactive paths ->  independence, if A -> B has many paths, we have to make sure all paths are inactive to achieve independence, one active path will turn the A -> B active, thus no independence\nA independent of B | C, means that C is observed, so we will shade C\nA independent of B means that no node will be shaded\nWhen we look at triples, only the middle node matters, whether it is observed or not matters. \n\n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "Module 12: Naive Bayes and Perceptrons\n",
        "Naïve Bayes: Assume all features are independent effects of the label\n",
        "We need to learn P(Features | label), to predict P(label | Features)\n",
        "Number of join tables with BN is Y * F^n but with BN, we only have to specify how each feature depends on the class Total number of parameters is linear in number of features\n",
        "After BN, number of features = n x |F| x |Y| parameters, n is number of features, F is the feature classes (2 if binary), Y is the number of labels\n",
        "Inference for Naive Bayes:\n",
        "1. Get joint probability of label and evidence for each label P(Feature i | Yi)\n",
        "2. Get P(Y), get the probability of different labels\n",
        "Generative model: P(Y | F1, F2 … Fn) = P (Y) * Product of P(Fi | Y)\n",
        "Generalization and Overfitting to deal with overfitting\n",
        "Low-frequency data or never-seen data: we can’t just give never-seen data zero probability\n",
        "To generalize better: we need to smooth or regularize the estimates\n",
        "Laplace Smoothing: \n",
        "Pretend you saw every outcome k extra times\n",
        "Deal with 0 probability samples\n",
        "Count appearance of x and add k to x_count, divided by total count + k * number of classes of x\n",
        "Laplace for conditionals: usually perform pooly for P(X|Y) when number of X is large or number of Y classes is large\n",
        "Weakness: when sample size very small, add K can make the result very different\n",
        "Linear Interpolation:\n",
        "Make sure the estimate of P(X|Y) isn’t too different from the empirical P(X)\n",
        "The confidence of a probabilistic classifier:  Posterior over the top label, the highest probability of label predicted\n",
        "Binary Perceptron: \n",
        "Start with weights = 0 For each training instance:\n",
        "Classify with current weights \n",
        "If correct (i.e., y=y*), no change! \n",
        "If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1, y* is the correct label, new_weight = old_weight + true_label * feature_vector, feature vector is the input features\n",
        "Multiclass Perceptron: \n",
        "Start with all weights = 0, a weight vector for each class\n",
        "Pick up training examples one by one \n",
        "Predict with current weights \n",
        "If correct, no change! \n",
        "If wrong: lower score of wrong answer, raise score of right answer, w_predict_label -= f(x), w_true_label += f(x)\n",
        "Convergence: if the training is separable, the perceptron will eventually converge (binary case)\n",
        "Problems: \n",
        "If the data is not separable, the decision boundary will keep changing but not converge\n",
        "Overtraining -> cause overfitting\n",
        "Fix Perceptron\n",
        "MIRA: Margin Infused Relaxed Algorithm, choose an update size that fixes the current mistake, like a learning rate\n",
        "Naïve Bayes • Builds a model training data • Gives prediction probabilities • Strong assumptions about feature independence • One pass through data (counting) \n",
        "Perceptrons / MIRA: • Makes less assumptions about data • Mistake-driven learning • Multiple passes through data (prediction) • Often more accurate\n",
        "Activation Functions Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "bad5d9c2-624b-4c40-9600-54a37d53dcf8"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \nModule 12: Naive Bayes and Perceptrons\nNaïve Bayes: Assume all features are independent effects of the label\nWe need to learn P(Features | label), to predict P(label | Features)\nNumber of join tables with BN is Y * F^n but with BN, we only have to specify how each feature depends on the class Total number of parameters is linear in number of features\nAfter BN, number of features = n x |F| x |Y| parameters, n is number of features, F is the feature classes (2 if binary), Y is the number of labels\nInference for Naive Bayes:\n1. Get joint probability of label and evidence for each label P(Feature i | Yi)\n2. Get P(Y), get the probability of different labels\nGenerative model: P(Y | F1, F2 … Fn) = P (Y) * Product of P(Fi | Y)\nGeneralization and Overfitting to deal with overfitting\nLow-frequency data or never-seen data: we can’t just give never-seen data zero probability\nTo generalize better: we need to smooth or regularize the estimates\nLaplace Smoothing: \nPretend you saw every outcome k extra times\nDeal with 0 probability samples\nCount appearance of x and add k to x_count, divided by total count + k * number of classes of x\nLaplace for conditionals: usually perform pooly for P(X|Y) when number of X is large or number of Y classes is large\nWeakness: when sample size very small, add K can make the result very different\nLinear Interpolation:\nMake sure the estimate of P(X|Y) isn’t too different from the empirical P(X)\nThe confidence of a probabilistic classifier:  Posterior over the top label, the highest probability of label predicted\nBinary Perceptron: \nStart with weights = 0 For each training instance:\nClassify with current weights \nIf correct (i.e., y=y*), no change! \nIf wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1, y* is the correct label, new_weight = old_weight + true_label * feature_vector, feature vector is the input features\nMulticlass Perceptron: \nStart with all weights = 0, a weight vector for each class\nPick up training examples one by one \nPredict with current weights \nIf correct, no change! \nIf wrong: lower score of wrong answer, raise score of right answer, w_predict_label -= f(x), w_true_label += f(x)\nConvergence: if the training is separable, the perceptron will eventually converge (binary case)\nProblems: \nIf the data is not separable, the decision boundary will keep changing but not converge\nOvertraining -> cause overfitting\nFix Perceptron\nMIRA: Margin Infused Relaxed Algorithm, choose an update size that fixes the current mistake, like a learning rate\nNaïve Bayes • Builds a model training data • Gives prediction probabilities • Strong assumptions about feature independence • One pass through data (counting) \nPerceptrons / MIRA: • Makes less assumptions about data • Mistake-driven learning • Multiple passes through data (prediction) • Often more accurate\nActivation Functions Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z\n \n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Module 13: Neural Networks\n",
        "Classifier components:\n",
        "feature representation, classification function, objective function(loss function), optimizing function\n",
        "Sigmoid Function (Logistic Regression Function): \n",
        "An objective function or loss function that tells us distance between the system output and the gold output. Ex: mean squared error\n",
        ", for each feature vector, calculate: -log(predicted probability of the correct label), then sum this for all the rows/feature vectors\n",
        "cross entropy loss: the better the prediction the smaller the loss\n",
        "Convex Function: loss function only have 1 minimum, so will not get stuck, there are no local minima, so gradient descent will be guaranteed to find the minimum\n",
        "Gradient descent: take the average gradient over the whole training set\n",
        "Stochastic Gradient Descent: Take n random training data rows, for each row, calculate gradient and update weight\n",
        "Mini-Batch Training: sgd uses 1 random sample, but Mini-Batch uses a batch of samples, and those batches can be processed in parallel\n",
        "Multiclass/Multinomial logistic regression: uses softmax instead of sigmoid function, it’s a generalization of sigmoid function\n",
        "The tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "250a2f54-200f-49a1-a510-8fb84d43a14b"
      },
      "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": 19,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Module 13: Neural Networks\nClassifier components:\nfeature representation, classification function, objective function(loss function), optimizing function\nSigmoid Function (Logistic Regression Function): \nAn objective function or loss function that tells us distance between the system output and the gold output. Ex: mean squared error\n, for each feature vector, calculate: -log(predicted probability of the correct label), then sum this for all the rows/feature vectors\ncross entropy loss: the better the prediction the smaller the loss\nConvex Function: loss function only have 1 minimum, so will not get stuck, there are no local minima, so gradient descent will be guaranteed to find the minimum\nGradient descent: take the average gradient over the whole training set\nStochastic Gradient Descent: Take n random training data rows, for each row, calculate gradient and update weight\nMini-Batch Training: sgd uses 1 random sample, but Mini-Batch uses a batch of samples, and those batches can be processed in parallel\nMulticlass/Multinomial logistic regression: uses softmax instead of sigmoid function, it’s a generalization of sigmoid function\nThe tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" \n",
        "Module 14: Natural Language Processing\n",
        "distributional word similarity: Two words are similar if they have similar word contexts.\n",
        "Term-Document Matrix: row → a word/term, column → a document, a cell → how often a word appears in a document\n",
        "Document vectors/column is sparse (most 0)\n",
        "Measure similarity between documents by compare columns vectors, \n",
        "1. Euclidean distance , sqrt of sum of (a - b)^2\n",
        "Normalize Length: if a word appear too many times, it will effect other words without normalization\n",
        "2. Cosine Distance: \n",
        "Term-Term Matrix\n",
        "L2 Normalization:\n",
        "Divide each item in the vector by the sqrt(sum(square of each item))\n",
        " ||u|| = [sqrt(3^2 + 7^2 + 2^2 + 1^2), sqrt(17898^2 + 189^2 + 798^2 + 53102^2)] = [7.94, 56043.14]\n",
        "3/7.94 = 0.38, 7/7.94 = 0.88, 2/7.94 = 0.25, 1/7.94 = 0.13\n",
        "17898/56043.14 = .32, 189/56043.14 = 0.00, 798/56043.14 = 0.01, 53102/56043.14 = 0.94\n",
        "Word2vec :\n",
        "nstead of counting how often each word w occurs near \"apricot\" \n",
        "Train a classifier on a binary prediction task\n",
        "Start with V random 300-dimensional vectors as initial embeddings Use logistic regression • Take a corpus and take pairs of words that co-occur as positive examples • Take pairs of words that don't co-occur as negative examples • Train the classifier to distinguish these by slowly adjusting all the embeddings to improve the classifier performance • Throw away the classifier code and keep the embeddings.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0d2101cc-ff1b-476a-d981-9ff118db819a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Module 13: Neural Networks\nClassifier components:\nfeature representation, classification function, objective function(loss function), optimizing function\nSigmoid Function (Logistic Regression Function): \nAn objective function or loss function that tells us distance between the system output and the gold output. Ex: mean squared error\n, for each feature vector, calculate: -log(predicted probability of the correct label), then sum this for all the rows/feature vectors\ncross entropy loss: the better the prediction the smaller the loss\nConvex Function: loss function only have 1 minimum, so will not get stuck, there are no local minima, so gradient descent will be guaranteed to find the minimum\nGradient descent: take the average gradient over the whole training set\nStochastic Gradient Descent: Take n random training data rows, for each row, calculate gradient and update weight\nMini-Batch Training: sgd uses 1 random sample, but Mini-Batch uses a batch of samples, and those batches can be processed in parallel\nMulticlass/Multinomial logistic regression: uses softmax instead of sigmoid function, it’s a generalization of sigmoid function\nThe tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "90c07409-401d-43d8-d23b-b39be1be3ee0"
      },
      "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": 22,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nModule 8: Markov Decision Processes     \n\nThe transition model deterministic → Stochastic,  T(s, a, s’) output the probability of arriving in state s’ given that we are in state s and doing action a\nTransitions are Markvoain: the probability of getting t o s’ not depend on history states, only depends on s and a.\nReward function/ Utility function: R( s, a, s’ ) , rewards are additive\nMarkov Decision Process: \nNon-deterministic search problems, can use expectimax search to solve\na sequential decision problem, fully observable environment, with a stochastic transition model, with additive rewards\nSolve MDP:\nDefine: a set of states, a set of actions, transition function (the probability is called the probability model), reward function (reinforcement learning reward function is unknow, MDP is known), initial state, terminal state\nSolution: for search problem -- > a plan: a fixed sequence of actions, for MDP → a policy, what best action to take in whichever state, 𝝿(s) = a\nDiscounting: values of rewards decay exponentially\nWhy discount: helps our algorithms converge, discount of 0.5 → U([1,2,3]) = 0.5^0*1 + 0.5^1*2 + 0.5^2*3 \nUtilities: if the preferences are stationary, there are two ways to define utilities: Additive utility and discount utility, additive utility is actually discount utility if gamma is 1, so there is only one way to define utilities which is discount utility\nInfinite utilities: \nFinite horizon: similar to depth limited search, terminate the game after t steps, but the policies will be non stationary and policy depends on how many steps left\nDiscounting: using 0 < gamma < 1, the smaller the gamma, the smaller the horizon, more focus on short term rewards\nAbsorbing state: guarantee that all policy will reach terminated state\nMDP search trees:\nDifference with ExpectMax: 1. Transitions function will encode the probabilities 2. The reward will be given at each state of the tree\nQ state: when we in a state and we commit to a action but the outcome is uncertain yet\nThe value (utility) of a state s: V * (s) = expected utility starting in s and acting optimally\nThe value (utility) of a q-state (s,a): Q* (s,a) = expected utility starting out having taken action a from state s and (thereafter) acting optimally\nValue Iteration: Start with V0 (s) = 0: no time steps left means an expected reward sum of zero, Repeat until convergence, Complexity of each iteration: O(S^2 * A), S is number of states, A is number of actions\nTheorem: will converge to unique optimal values • Basic idea: approximations get refined towards optimal values • Policy may converge long before values do\nPolicy Evalluation: \nEfficiency: O(S^2 ) per iteration\nWithout the maxes, the bellman equations are just a linear system, we can just solve it\nPolicy Extraction: gets the policy impied by the values\nPolicy extraction from Q state: pi(s) = max_a Q(s,a), just select the best q value, very easy\nProblems with Value iteration: slow, O(S^2A), the max at each state rarely changes, the policy converge much faster\nAlternative: policy iteration\nPolicy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\nPolicy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future values • Repeat steps until policy converges\nComparison:\nTwo iterations compute the same thing (all optimal values), they are both dynamic programming, all variations of bellman equation, all use one-step lookahead expectimax fragments\nValue iteration: update both values and the policy\nPolicy iteration: We choose a fixed policy first, find all values, then update the policy\nWhy average utilities, why not use max? Because the world is uncertain, a rational agent should choose the action that maximizes expected utility\nFor minmax reasoning, terminal function scale doesn’t matter, the magnitude doesnt matter, the first layer chooses the bigger one, and the second layer chooses the min one. Insensitivity to monotonic transformation. \nBut for average-case expectmax (for MDP), magnitude matters \nRational Preferences for Agent: Rational preferences imply behavior describable as maximaziation of expected utilities\nMEU Principle: choose the action that maximizies expected utilities (agent can be rational without representing utilities and probabilities)\nQ&A\nDifference between utility function and performance measure of an agent: performance measure gives a score for a history, utility function only applies to next state (guide future actions)\nOrderability of preferences: agent must choose, can not refuse to bet, it either prefer one or be indifferent\nExactly one of A > B, B > A, A ~ B holds\nIf an agent's preferences are rational (i.e. follow the axioms of utility theory), what two things can we say?: The agent has a utility function and we can compute the expected utility of a lottery. \n If there exists a utility function describing an agent's preferences, it means that the agent is explicitly maximizing that utility function in its own deliberations: ​​False. A rational agent can be implemented with many different methods. Any rational agent can be described by a utiltiy function, but the implementation could be e.g. a lookup table.\nTo define MDP: A set of states, Initial states, Terminal states, Transition ModelReward function\nAn environment history is a sequence of states and actions\nA policy that depends on time is called Nonstationary (finite horizon → nonstationary, infinite horizon → stationary)\nQ(S,A) or action-utility function is the expected value of an action a in a given state s\nBellman update is update the utility of a state iteratively\n3 steps for value iteration: \nStart with arbitrary initial values for each state\nApply the bellman update\nRepeat step 2 until reaching equilibrium\nWhat is the intuition for why value iteration works? The Bellman update moves information locally. \nPolicy iteration: Policy evaluation and policy improvement\nAsynchronous policy iterationupdates only a subset of states\nMDPs be solved using linear programming\nLarge MDP can not solve using value or policy iteration\nExplore and exploit: The tradeoff between exploitation of the current best action to obtain rewards and exploration of previously unknown states and actions to gain information which might lead to better long-term rewards.\n\n\n \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n Module 9: Reinforcement Learning\n\nSimilar to MDP but don’t know Transition function and Reward function\nModel-Based Learning (have a explicit representation of the transition function and try to learn the probability)\nlearn the model by trying out transition functions, try to form a MDP problem\nLearn based on experiences\nStep 1: Learn MDP by trying\nStep 2: Solve MDP using value or policy iteration\nModel-Free Learning (never try to learn probability, ignore them and try to learn the value of states): passive reinforcement learning →  goal is learn the state values, fixed policy, simplified task is policy evaluation and No choice on what actions to take (fixed policy)\nDirect Evaluation:average together observed sample values. Bad about direct evaluation, takes a long time to learn, each state must be learned separately\nSample-Based Policy Evaluation\nTemporal Difference Learning: bad about TDL, we only have value of state but not Q value, so we can not turn values into a new policy\nActive Reinforcement Learning: full reinforcement learning, try to find ptimal policy while don’t know transition and rewards\nGoal: learn the optimal policy\nQ-Learning: sample-based Q-value iteration\nQ-learning converges to optimal policy, even if you’re acting suboptimally! This is called off-policy learning, means that you start with a estimated policy which is not accurate\nRequirements: You have to explore enough You have to eventually make the learning rate small enough … but not decrease it too quickly\nExploration vs. Exploitation: how to explore\n1. Randomly choose actions (epsilon-greedy) : Every time step, flip a coin With (small) probability ε, act randomly With (large) probability 1-ε, act on current policy\nProblem: already explored the space, but still keep randomly visit it\nSolution1: lower ε over time\nSolution 2: Exploration Function\n2. Exploration Function: f(u, n) = u + k/n, u = reward of this state, k = award we set, n number of visits of this state\nThe more we explore this state, the less additional award we give it, this encourage explore less visited states\nRegret: Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\nApproximate Q-Learning: hard to learn when you have very many states, the idea here is to generalize states, give similar states similar values without visit again and again\nLearn about some small number of training states from experience Generalize that experience to new, similar situations\nLinear regression + Q-Learning + Gradient Descent\n\n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Module 10: Probabilies and Language Models\nprobabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is. \nAn event is a set E of outcomes\nA probabilistic model is a joint distribution over a set of random variables\nMarginal distributions are sub-tables which eliminate variables Marginalization (summing out): Combine collapsed rows by adding\nInference by enumeration: P(Q | e1, e2, ...), similar to linear regression, Q is y, e is x (features)\nStep1: select the entries consistent with the evidence\nStep2: Sum out H to get join of Query and evidence\nStep3: Normalize \nProduct Rule: P(y) P(x|y) = P(x,y)\nConditional Probability: P(a|b) = P(a,b) / P(b)\nChain Rule: P(a,b,c) = P(a) P(b|a) P(c|a,b) or P(x1,x2,..,xn) = ∏i P(xi | x1, x2, x3, .., Xi-1)\nBayes’ Rule: P(x|y) = (P(y|x) P(x))  /   P(y)\nProbabilistic Language Model: P(won|the underdog team) = Count(the underdog team won) / Count(the underdog team) \ngiven “the underdog team” to predict the next word, count the number of appeararence of “the underdog team”, go to the dictionary with key = “the underdog team” and count the number of appeararence of “won” before “the underdog team”\nMarkov Assumption: only depends on the previous k words, not the whole context\nUnigram model: P(w1,w2,w3..wn)\nBigram model\nHow many ways are there to apply the chain rule to a joint distribution with NN random variables?: N!\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Two variables are independent if P(x,y) = P(x)P(y)\nCheck if two variables are independent, multiply marginal probabilities to see if it’s same as joint probability\nConditional Independence: X is conditionally independent of Y given Z, P(x,y|z) = P(x|z)P(y|Z) or P(x|z,y) = P(x|z)  (EX:Detect is conditionally independent of Toothache given Cavity)\nUmbrella is conditionally independent to Traffic given it’s raining (Because we already know it’s raining, it doesn’t matter whether we see umbrella or not)\nConditional Independence reduces the number of probability tables\nBayes’nets / graphical models help us express conditional independence assumptions\na technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\ngraphical models\nShade graph: observed, Unshaded: unobserved, would like to make a inference (y value)\nGraphical Model Notation\nNodes: variables, can be observed/assigned or unassigned/unobserved \nArcs: interactions § Indicate “direct influence” between variables § Formally: encode conditional independence, Cavity -> Toothache\n                                                             | - > Catch, because toothache and catch     are conditionally independent\nBayes’ Net: each random variable is a node, A1 -> X, A2 -> X  means P(X|A1,A2)\nCavity -> Toothache, Cavity -> Catch, P(+cavity, +detect, -toothache) = P(ToothAche | Cavity) * P(Catch | Cavity)\np(X1,X2,...,Xn) = Product of P(xi | parents(xi))\nNot every BN can represent every joint distribution § The topology enforces certain conditional independencies\nCasuality is not a mathmaticall necessity \nBNs need not actually be causal\nSometimes no causal net exists\nSome arrows reflect correlation not causation\nThe arrows really encodes conditional independence rather than casual structure \nSize of BN:\nSize of joint distribution over N boolean variables: 2^n\nSize of N node net if nodes have up to k parents: N * 2^(k+1)\nPros:  Huge space savings! § Also easier to elicit local CPTs § Also faster to answer queries\nAssumptions of NB \nD-separation Algorithm: \nShow A is not independent of B, one example set of CPTs for which A is not independent of B is sufficient to show this independence is not guaranteed.\nCasual Chain: A->B->C, X: low pressure ->Y: Rain -> Z: Traffic, X and Z not independent, A independent of C given B, middle part will block A to C\nCommon Cause: two children have one parent cause, Y: Project due ->X: piazza busy, Y:Project due -> Z: office hours full, X and Z is not independent because P( +x | +y ) = 1, P( -x | -y ) = 1, P( +z | +y ) = 1, P( -z | -y ) = 1,but  X is guaranteed to be independent with Z given Y because Observing the cause blocks influence between effects\nCommon Effect: one child haas two parents, X: raining -> Z: traffic, Y:Ballgame -> Z: traffic, x and y is independent, X and Y is not independent given Z because seeing traffic puts the rain and the ballgame in competition as explanation and Observing an effect activates influence between possible causes.\nAny BN can be break down to the 3 cases above\nConclusion:\nOne inactive block on the path, the whole path is inactive. A path is active if each triple is active: check every triple\nAll paths are Inactive paths ->  independence, if A -> B has many paths, we have to make sure all paths are inactive to achieve independence, one active path will turn the A -> B active, thus no independence\nA independent of B | C, means that C is observed, so we will shade C\nA independent of B means that no node will be shaded\nWhen we look at triples, only the middle node matters, whether it is observed or not matters. \n\n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \nModule 12: Naive Bayes and Perceptrons\nNaïve Bayes: Assume all features are independent effects of the label\nWe need to learn P(Features | label), to predict P(label | Features)\nNumber of join tables with BN is Y * F^n but with BN, we only have to specify how each feature depends on the class Total number of parameters is linear in number of features\nAfter BN, number of features = n x |F| x |Y| parameters, n is number of features, F is the feature classes (2 if binary), Y is the number of labels\nInference for Naive Bayes:\n1. Get joint probability of label and evidence for each label P(Feature i | Yi)\n2. Get P(Y), get the probability of different labels\nGenerative model: P(Y | F1, F2 … Fn) = P (Y) * Product of P(Fi | Y)\nGeneralization and Overfitting to deal with overfitting\nLow-frequency data or never-seen data: we can’t just give never-seen data zero probability\nTo generalize better: we need to smooth or regularize the estimates\nLaplace Smoothing: \nPretend you saw every outcome k extra times\nDeal with 0 probability samples\nCount appearance of x and add k to x_count, divided by total count + k * number of classes of x\nLaplace for conditionals: usually perform pooly for P(X|Y) when number of X is large or number of Y classes is large\nWeakness: when sample size very small, add K can make the result very different\nLinear Interpolation:\nMake sure the estimate of P(X|Y) isn’t too different from the empirical P(X)\nThe confidence of a probabilistic classifier:  Posterior over the top label, the highest probability of label predicted\nBinary Perceptron: \nStart with weights = 0 For each training instance:\nClassify with current weights \nIf correct (i.e., y=y*), no change! \nIf wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1, y* is the correct label, new_weight = old_weight + true_label * feature_vector, feature vector is the input features\nMulticlass Perceptron: \nStart with all weights = 0, a weight vector for each class\nPick up training examples one by one \nPredict with current weights \nIf correct, no change! \nIf wrong: lower score of wrong answer, raise score of right answer, w_predict_label -= f(x), w_true_label += f(x)\nConvergence: if the training is separable, the perceptron will eventually converge (binary case)\nProblems: \nIf the data is not separable, the decision boundary will keep changing but not converge\nOvertraining -> cause overfitting\nFix Perceptron\nMIRA: Margin Infused Relaxed Algorithm, choose an update size that fixes the current mistake, like a learning rate\nNaïve Bayes • Builds a model training data • Gives prediction probabilities • Strong assumptions about feature independence • One pass through data (counting) \nPerceptrons / MIRA: • Makes less assumptions about data • Mistake-driven learning • Multiple passes through data (prediction) • Often more accurate\nActivation Functions Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z\n \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Module 13: Neural Networks\nClassifier components:\nfeature representation, classification function, objective function(loss function), optimizing function\nSigmoid Function (Logistic Regression Function): \nAn objective function or loss function that tells us distance between the system output and the gold output. Ex: mean squared error\n, for each feature vector, calculate: -log(predicted probability of the correct label), then sum this for all the rows/feature vectors\ncross entropy loss: the better the prediction the smaller the loss\nConvex Function: loss function only have 1 minimum, so will not get stuck, there are no local minima, so gradient descent will be guaranteed to find the minimum\nGradient descent: take the average gradient over the whole training set\nStochastic Gradient Descent: Take n random training data rows, for each row, calculate gradient and update weight\nMini-Batch Training: sgd uses 1 random sample, but Mini-Batch uses a batch of samples, and those batches can be processed in parallel\nMulticlass/Multinomial logistic regression: uses softmax instead of sigmoid function, it’s a generalization of sigmoid function\nThe tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Module 13: Neural Networks\nClassifier components:\nfeature representation, classification function, objective function(loss function), optimizing function\nSigmoid Function (Logistic Regression Function): \nAn objective function or loss function that tells us distance between the system output and the gold output. Ex: mean squared error\n, for each feature vector, calculate: -log(predicted probability of the correct label), then sum this for all the rows/feature vectors\ncross entropy loss: the better the prediction the smaller the loss\nConvex Function: loss function only have 1 minimum, so will not get stuck, there are no local minima, so gradient descent will be guaranteed to find the minimum\nGradient descent: take the average gradient over the whole training set\nStochastic Gradient Descent: Take n random training data rows, for each row, calculate gradient and update weight\nMini-Batch Training: sgd uses 1 random sample, but Mini-Batch uses a batch of samples, and those batches can be processed in parallel\nMulticlass/Multinomial logistic regression: uses softmax instead of sigmoid function, it’s a generalization of sigmoid function\nThe tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "NF0yHr1J8d7x"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}