{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "54d14ce9-afea-45a3-eb5e-15125495281c"
      },
      "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": 131,
      "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": "19f48ae0-fc2f-4657-c119-dcd6e8d4ea3f"
      },
      "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": 132,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 133,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "- Decision theoretic agent can make rational decisions even when faced with uncertainty and conflicting goals (logical agents may not have a way to decide)\n",
        "- They assign a continuous range of values to states, which allow them to choose a better state even when the best state is unavailable\n",
        "- $P(s'|s, a)$ probability that performing action $a$ in state $s$ reaches state $s'$\n",
        "- Decision theoretic agent: agent that makes rational decisions based on what it believes and what it wants\n",
        "- Decision theory: choosing among actions based on the desirability of their immediate outcomes (environment is assumed episodic)\n",
        "- Agent preferences cptured by utility function $U(s)$: assigns a single number to express how desirable state $s$ is\n",
        "- Expected utility of an action is the average utility value of the outcomes , weighed by the probability of the outcome\n",
        "- MEU principle: rational agent should choose action that maximizes agent's expected utility (intelligent behavior)\n",
        "- Decision theory provides mathematical framework but does not solve the AI problem since agent still needs to estimate $P(s)$ over possible states of the world, \n",
        "which requires perception, learning, knowledge representation, and inference \n",
        "- Performance measure gives a score for history (sequence of states)\n",
        "- Utility function applies to the very next state (can be used to guide actions step by step)\n",
        "\n",
        "Flashcard: \n",
        "- MEU doesn't solve the AI problem because MEU formalizes what the agent should do but not how to do it\n",
        "- To use MEU, you need to estimate the probability distribution and a utility function that reflects the performance measure\n",
        " \"\"\"  + sample_equation\n",
        "\n",
        "chapter16_2 =  \"\"\" \n",
        "- Describe the agent's preferences: $(A > B), (A \\sim B), (A >= B)$\n",
        "- Lottery: set of outcomes for each action $L = [p_1, S_1; ... ; p_n, S_n]$\n",
        "- Each outcome $S_i$ can be atomic state or another lottery \n",
        "\n",
        "Axioms of utility (notice they are actually \"axioms about preferences\"):\n",
        "- Agent that violates axiom of utility will show irrational behavior in some situations\n",
        "\n",
        "1.) Orderability: Given two lotteries, rational agent must either prefer one or equally prefer both.\n",
        "Exactly one of $(A > B), (A \\sim B), (A >= B)$ holds.\n",
        "\n",
        "2.) Transitivity: Given any three lotteries, $(A > B)$ and $(B > C) \\implies (A > C)$\n",
        "\n",
        "3.) Continuity: If some lottery B is between A and C in preference, then there is some $p$ for which\n",
        "rational agent is indifferent between getting B for sure and the lottery with A and C with probability $p$ and $1-p$ respectively\n",
        "\n",
        "$ A > B > C \\implies \\exists p$ such that $[p, A; 1-p, C] \\sim B$ \n",
        "\n",
        "4.) Substitutability: If agent is indifferent between A and B, then agent is indifferent\n",
        "between two more complex lotteries that are the same except B is substituted for A in one of them\n",
        "\n",
        "$ A \\sim B \\implies [p, A; 1-p, C] \\sim [p, B; 1-p, C]$\n",
        "\n",
        "$ A > B \\implies [p, A; 1-p, C] > [p, B; 1-p, C]$\n",
        "\n",
        "5.) Monotonicity: If agent prefers A to B then agent must prefer lottery with higher probability for A\n",
        "\n",
        "6.) Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability. It compresses\n",
        "two consecutive lotteries into single equivalent lottery \n",
        "\n",
        "You can derive the following from axioms of utility:\n",
        "- Existence of utility function: If agent obeys axioms of utility, then there exists a function $U$ such that \n",
        "$U(A) > U(B)$ iff $A > B$ and $U(A) = U(B)$ iff $A \\sim B$\n",
        "\n",
        "- Expected utility of lottery: utility of lottery is the sum of the probability of each outcome times utility of that outcome\n",
        "$ U(L) = \\sum_{i} p_i * U(S_i)$\n",
        "\n",
        "- Once probabilities and utilities of possible outcome states are specified, utility of a compound lottery involving those states\n",
        "is completely determined\n",
        "- Outcome of a nondeterministic action is a lottery \n",
        "- Agent can act rationally (consistent with its preferences) by choosing an action that maximizes expected utility\n",
        "- Utility function exists for any rational agent \n",
        "- Deterministic environment only needs preference ranking on states (the numbers don't matter)\n",
        "- Existentence of utility function does not necessarily mean the agent is explicitly maximizing that utility function\n",
        "- By observing rational agent's behavior, you can learn about the utility function that represents\n",
        "what the agent is actually trying to achieve \n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\"\n",
        "Utility functions: \n",
        "\n",
        "- Utility functions map from lotteries to real numbers and they must obey axioms of utility \n",
        "- Agent is still allowed to have preferences that may seem unusual \n",
        "- Preference elicitation: present choices to someone and use observations to determine\n",
        "underlying utility function. This is a way to work out what someone's utility function is.\n",
        "- Fix utility of \"best prize\" at $U(S) = u_{\\\\top}$ (finite) normalized to $u_{\\\\top} = 1$\n",
        "- Fix utility of \"worst catastrophe\" at $U(S) = u_{\\\\bot}$ (finite) normalized to $u_{\\\\bot} = 0$\n",
        "- Micromort: 1/1,000,000 chance of death\n",
        "- QALY: quality adjusted life year. People are willing to accept short life to avoid disability\n",
        "\n",
        "Utility of money: \n",
        "- Monotonic preference for more money (prefer more to less, all else being equal)\n",
        "- Money does not behave as a utility function, because it says nothing about preferences\n",
        "between lotteries involving money\n",
        "- Utility is not disrectly proportional to monetary value because of diminishing returns \n",
        "- Grayson study showed that utility of money almost proportional to the logarithm of the amount\n",
        "- Utility of money is S-shaped. Positive region is \"risk averse\"; negative region is \"risk seeking\"\n",
        "- Certainty equivalent: value an agent will accept in lieu of lottery \n",
        "- Insurance premium: difference between EMV and certainty equivalent \n",
        "- Agent with linear curve is \"risk neutral\"\n",
        "\n",
        "Expected utility:\n",
        "- Rational way to choose best action is to maximize expected utility\n",
        "- In reality, model is a oversimplification, you are really working with estimated of the true\n",
        "expected utility (we assume this estimate is unbiased)\n",
        "- Optimizer's curse: tendency for the estimated expected utility of the best choice\n",
        "to be too high (taking utility estimates at face value is a bad idea)\n",
        "- Solution: Bayesian approach that uses explicit probability model of the error in the utility\n",
        "estimates. Treat utility estimate as evidence and compute posterior distribution for the true \n",
        "utility using Bayes' rule.\n",
        "\n",
        "Human judgement/irrationality:\n",
        "- Normative theory: describes how a rational agent should act\n",
        "- Descriptive theory: describes how actual agents really act\n",
        "- Certainty effect can be used to explain some irrational preferences (people attracted\n",
        "to gains that are certain)\n",
        "- Ambiguity aversion: people prefer to elect the known probability rather than the unknown\n",
        "unknowns\n",
        "- Framing effect: exact wording of a decision problem can have a big impact on agent's choice\n",
        "- Anchoring effect: people prefer to make relative utility judgements rather than absolute\n",
        "ones (200 wine vs. 55 wine)\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "Sequential decision problems:\n",
        "- Transition model: describes the outcome of each action in each state\n",
        "- Outcome is stochastic \n",
        "$P(s'|s,a) = T(s, a, s')$ is probability of reaching state $s'$ if action $a$\n",
        "is done in state $s$\n",
        "- Markovian: probability of reaching next state from current state depends only on the\n",
        "current state and not on the history of earlier states\n",
        "- Decision problem is sequential, so the utility function for the agent will depend on a sequence\n",
        "of states and actions (environment history)\n",
        "\n",
        "MDP\n",
        "- Sequential decision problem for fully observable, stochastic environment with Markovian\n",
        "transition model and additive rewards\n",
        "- Consists of set of states, set of actions, transition model, reward function\n",
        "- Methods for solving MDPs involve dynamic programming\n",
        "- Solution for MDP could be a policy: solution that specifies what the agent should do\n",
        "for any state that the agent might reach\n",
        "$\\pi(s)$ is the action recommended by policy $\\pi$ for state $s$\n",
        "- Quality of a policy is measured by the expected utility of the possible environment histories\n",
        "generated by that policy\n",
        "- Optimal policy $\\pi^{*}$ is one that yields the highest expected utility\n",
        "\n",
        "Optimal policies:\n",
        "- Utility of a history is the sum of discounted rewards\n",
        "- Can compare policies by cmoparing expected utilities obtained when executing them\n",
        "- The probability distribution over state sequences is determined by initial state, policy, \n",
        "and the transition model for the environment\n",
        "- $U^{\\pi}(s)$ is the expected utility obtained by executing $\\pi$ starting in $s$\n",
        "- Optimal policy is independent of the starting state when using discounted utilities with \n",
        "infinite horizons (BUT this does not hold for finite horizon policies or other ways\n",
        "of combining rewards over time, e.g. taking the max)\n",
        "- $U^{\\pi^{*}}(s)$ is the true utility of a state: expected sum of discounted rewards if\n",
        "agent executes optimal policy \n",
        "- $U(s)$ the utility of a state is the expected reward for the next transition plus the discounted\n",
        "utility of the next state, assuming the agent chooses the optimal action. \n",
        "\"\"\"\n",
        "\n",
        "chapter17_2 =  \"\"\" \n",
        "Algorithms for MDP:\n",
        "- Generate exact solutions: value iteration, policy iteration, linear programming\n",
        "- Approximate algorithms: Monte Carlo planning\n",
        "\n",
        "Value iteration: \n",
        "\n",
        "$V_{k+1}(s) \\\\leftarrow \\\\max_a \\sum_{s'} T(s,a,s')[R(s,a,s') + \\\\gamma V_{k}(s')]$\n",
        "\n",
        "- $n$ possible states $\\\\rightarrow n$ Bellman equations\n",
        "- $n$ equations (nonlinear) contain $n$ unknowns (utilities of the states)\n",
        "- Goal: Solve the equations to find the utilities\n",
        "- Iterative approach: update the utility of each state from the utilities of its neighbors\n",
        "- After convergence, final utility values are solutions to the Bellman equations \n",
        "- Solutions are unique and the corresponding policy is optimal\n",
        "- Value iteration is propagating information through the state space by means of local updates\n",
        "- Time $O(AS^2)$ for each iteration\n",
        "\n",
        "Policy iteration: \n",
        "- Alternates between policy evaluation and policy improvement\n",
        "\n",
        "Evaluation: $V_{k+1}^{\\\\pi_i}(s) \\\\leftarrow T(s, \\\\pi_i(s), s') [R(s, \\\\pi_i(s), s') + \\\\gamma V_{k+1}^{\\\\pi_i}(s')]$\n",
        "\n",
        "Improvement: $\\\\pi_{i+1}(s) = {\\\\argmax}_a \\\\sum_{s'} T(s,a,s') [R(s,a,s') + \\\\gamma V^{\\\\pi_i}(s')]$\n",
        "\n",
        "- Policy evaluation: Given policy $\\pi_i$ calculate $U_i = U^{\\pi_i}$ the utility of each \n",
        "state if $\\pi_i$ were to be executed\n",
        "- Policy improvement: Calculate new MEU policy $\\pi_{i+1}$ using one-step look ahead based\n",
        "on $U_i$\n",
        "- Convergence happens when policy improvement yields no change in the utilities\n",
        "- At this point $U_i$ is a solution to the Bellman equation, and $\\pi_i$ is\n",
        "an optimal policy \n",
        "- Action in each state is fixed by the policy, so the simplified Bellman equations (do what\n",
        "the policy says) are linear because the $max$ operator is removed\n",
        "- $n$ states, $n$ linear equations, $n$ unknowns can be solved in $O(n^3)$ time\n",
        "\n",
        "Online algorithms for MDPs:\n",
        "- Value iteration and policy iteration are offline algorithms: generate optimal solution\n",
        "for the problem, which can then be executed by simple agent \n",
        "- Online algorithms: agent does significant amount of computation at each decision point\n",
        "rather than operating with precomputed information  \n",
        "\n",
        "Policy evaluation:\n",
        "- Use Bellman equation with action $a$ fixed by $\\\\pi$. We can solve system of $n$\n",
        "variables and $n$ equations in $O(n^3)$ time\n",
        "- $O(S^2)$ per iteration according to slides\n",
        "\n",
        "Flashcards:\n",
        "- Asynchronous policy iteration  updates only a subset of states. \n",
        "- This can be useful because you can design heuristics about what states to update, and can reduce the time it takes to run policy iteration.\n",
        "\n",
        "Modified policy iteration (adapative DP version):\n",
        "- Policy iteration where the value iteration step updates using the learned transition probabilities and reward. \n",
        "- This lets us update the utilities concurrently with the transition and reward rather than solving them after all trials.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "```\n",
        "function VALUE-ITERATION(mdp, ε) returns a utility function\n",
        " inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a),\n",
        "      rewards R(s,a,s′), discount γ\n",
        "   ε, the maximum error allowed in the utility of any state\n",
        " local variables: U, U′, vectors of utilities for states in S, initially zero\n",
        "        δ, the maximum change in the utility of any state in an iteration\n",
        "\n",
        " repeat\n",
        "   U ← U′; δ ← 0\n",
        "   for each state s in S do\n",
        "     U′[s] ← max_a ∈ A(s) Q-VALUE(mdp,s,a,U)\n",
        "     if | U′[s] − U[s] | > δ then δ ← | U′[s] − U[s] |\n",
        " until δ < ε(1 − γ)/γ\n",
        " return U\n",
        "```\n",
        "===============================================================================\n",
        "```\n",
        "function POLICY-ITERATION(mdp) returns a policy\n",
        " inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a)\n",
        " local variables: U, a vector of utilities for states in S, initially zero\n",
        "        π, a policy vector indexed by state, initially random\n",
        "\n",
        " repeat\n",
        "   U ← POLICY-EVALUATION(π, U, mdp)\n",
        "   unchanged? ← true\n",
        "   for each state s in S do\n",
        "     a * ← argmax_a ∈ A(s) Q-VALUE(mdp,s,a,U)\n",
        "     if Q-VALUE(mdp,s,a*,U) > Q-VALUE(mdp,s,π[s],U) then do\n",
        "       π[s] ← a* ; unchanged? ← false\n",
        " until unchanged?\n",
        " return π\n",
        "```\n",
        "\n",
        "===============================================================================\n",
        "\n",
        "MDP is:\n",
        "- Sequential decision problem\n",
        "- For fully observable environment\n",
        "- With stochastic transition model\n",
        "- That has additive rewards\n",
        "\n",
        "Reward scales:\n",
        "- Scale of utilities is arbitrary (affine transformation leaves optimal decision unchanged)\n",
        "- Similarly so for the optimal policy in an MDP\n",
        "\n",
        "Representing MDPs:\n",
        "- Represent $P(s'|s, a)$ and $R(s,a,s')$ with 3 dimensional table of size $S^2 * A$\n",
        "- Usually tables are sparse, of size $O(SA)$\n",
        "\n",
        "Utilities over time:\n",
        "- With finite horizon, optimal action in a given state may depend on how much time is left\n",
        "- Nonstationary: policy that depends on time \n",
        "- infinite horizon, optimal action depends only on the current state\n",
        "- Stationary: policy does not depend on time \n",
        "- There can be finite state sequences in infinite-horizon MDP that contains a terminal state\n",
        "\n",
        "Calculate utility of state sequences:\n",
        "- Additive discounted rewards: $R(s_0, a_0, s_1) + \\gamma R(s_1, a_1, s_2) + ... $\n",
        "- Discount factor $\\gamma$ describes the preference of an agent for current rewards over future rewards\n",
        "- $\\gamma$ close to 0 means rewards in the distant future are viewed as insignificant \n",
        "(agent focused on short term)\n",
        "- $\\gamma$ close to 1 means agent is more willing to wait for long-term rewards \n",
        "- $\\gamma = 1$ is special case of purely additive rewards \n",
        "- Agent's preferences between state sequences are stationary: if you prefer one future\n",
        "to another starting tomorrow, then you should still prefer that future if it were to start\n",
        "today instead\n",
        "- With discounted rewards and $\\gamma < 1$, utility of infinite sequence is finite\n",
        "- Proper policy: guaranteed to reach a terminal state (we are able to use $\\gamma = 1$ with proper\n",
        "policies)\n",
        "- Improper policies (agent never reaching terminal state because $\\gamma > 0$) is good reason\n",
        "for using discounted rewards\n",
        "\n",
        "Q-function:\n",
        "- $Q(s,a)$ is the action-utility function: expected utility of taking a given action\n",
        "in a given state\n",
        "- Optimal policy can be extracted from Q-function by $\\pi^{*}(s) = {\\\\argmax}_{a} Q(s,a)$\n",
        "- Bellman equation for Q-function: expected total reward for taking action is its immediate reward\n",
        "plus the discounted utility of the outcome state\n",
        "- Solving the Bellman equations for $U$ or $Q$ gives us what we need to find an optimal policy\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any bolded term in the textbook, \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",
        "\"decision theoretic agent\": \"agent that makes rational decisions based on what it believes and what it wants\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 134,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "2528da35-d36e-4ccc-bb5c-1ab8fc4b846f"
      },
      "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",
        "      print(len(summary))\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": 135,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Decision theoretic agent can make rational decisions even when faced with uncertainty and conflicting goals (logical agents may not have a way to decide)\n- They assign a continuous range of values to states, which allow them to choose a better state even when the best state is unavailable\n- $P(s'|s, a)$ probability that performing action $a$ in state $s$ reaches state $s'$\n- Decision theoretic agent: agent that makes rational decisions based on what it believes and what it wants\n- Decision theory: choosing among actions based on the desirability of their immediate outcomes (environment is assumed episodic)\n- Agent preferences cptured by utility function $U(s)$: assigns a single number to express how desirable state $s$ is\n- Expected utility of an action is the average utility value of the outcomes , weighed by the probability of the outcome\n- MEU principle: rational agent should choose action that maximizes agent's expected utility (intelligent behavior)\n- Decision theory provides mathematical framework but does not solve the AI problem since agent still needs to estimate $P(s)$ over possible states of the world, \nwhich requires perception, learning, knowledge representation, and inference \n- Performance measure gives a score for history (sequence of states)\n- Utility function applies to the very next state (can be used to guide actions step by step)\n\nFlashcard: \n- MEU doesn't solve the AI problem because MEU formalizes what the agent should do but not how to do it\n- To use MEU, you need to estimate the probability distribution and a utility function that reflects the performance measure\n  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n- Describe the agent's preferences: $(A > B), (A \\sim B), (A >= B)$\n- Lottery: set of outcomes for each action $L = [p_1, S_1; ... ; p_n, S_n]$\n- Each outcome $S_i$ can be atomic state or another lottery \n\nAxioms of utility (notice they are actually \"axioms about preferences\"):\n- Agent that violates axiom of utility will show irrational behavior in some situations\n\n1.) Orderability: Given two lotteries, rational agent must either prefer one or equally prefer both.\nExactly one of $(A > B), (A \\sim B), (A >= B)$ holds.\n\n2.) Transitivity: Given any three lotteries, $(A > B)$ and $(B > C) \\implies (A > C)$\n\n3.) Continuity: If some lottery B is between A and C in preference, then there is some $p$ for which\nrational agent is indifferent between getting B for sure and the lottery with A and C with probability $p$ and $1-p$ respectively\n\n$ A > B > C \\implies \\exists p$ such that $[p, A; 1-p, C] \\sim B$ \n\n4.) Substitutability: If agent is indifferent between A and B, then agent is indifferent\nbetween two more complex lotteries that are the same except B is substituted for A in one of them\n\n$ A \\sim B \\implies [p, A; 1-p, C] \\sim [p, B; 1-p, C]$\n\n$ A > B \\implies [p, A; 1-p, C] > [p, B; 1-p, C]$\n\n5.) Monotonicity: If agent prefers A to B then agent must prefer lottery with higher probability for A\n\n6.) Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability. It compresses\ntwo consecutive lotteries into single equivalent lottery \n\nYou can derive the following from axioms of utility:\n- Existence of utility function: If agent obeys axioms of utility, then there exists a function $U$ such that \n$U(A) > U(B)$ iff $A > B$ and $U(A) = U(B)$ iff $A \\sim B$\n\n- Expected utility of lottery: utility of lottery is the sum of the probability of each outcome times utility of that outcome\n$ U(L) = \\sum_{i} p_i * U(S_i)$\n\n- Once probabilities and utilities of possible outcome states are specified, utility of a compound lottery involving those states\nis completely determined\n- Outcome of a nondeterministic action is a lottery \n- Agent can act rationally (consistent with its preferences) by choosing an action that maximizes expected utility\n- Utility function exists for any rational agent \n- Deterministic environment only needs preference ranking on states (the numbers don't matter)\n- Existentence of utility function does not necessarily mean the agent is explicitly maximizing that utility function\n- By observing rational agent's behavior, you can learn about the utility function that represents\nwhat the agent is actually trying to achieve \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nUtility functions: \n\n- Utility functions map from lotteries to real numbers and they must obey axioms of utility \n- Agent is still allowed to have preferences that may seem unusual \n- Preference elicitation: present choices to someone and use observations to determine\nunderlying utility function. This is a way to work out what someone's utility function is.\n- Fix utility of \"best prize\" at $U(S) = u_{\\top}$ (finite) normalized to $u_{\\top} = 1$\n- Fix utility of \"worst catastrophe\" at $U(S) = u_{\\bot}$ (finite) normalized to $u_{\\bot} = 0$\n- Micromort: 1/1,000,000 chance of death\n- QALY: quality adjusted life year. People are willing to accept short life to avoid disability\n\nUtility of money: \n- Monotonic preference for more money (prefer more to less, all else being equal)\n- Money does not behave as a utility function, because it says nothing about preferences\nbetween lotteries involving money\n- Utility is not disrectly proportional to monetary value because of diminishing returns \n- Grayson study showed that utility of money almost proportional to the logarithm of the amount\n- Utility of money is S-shaped. Positive region is \"risk averse\"; negative region is \"risk seeking\"\n- Certainty equivalent: value an agent will accept in lieu of lottery \n- Insurance premium: difference between EMV and certainty equivalent \n- Agent with linear curve is \"risk neutral\"\n\nExpected utility:\n- Rational way to choose best action is to maximize expected utility\n- In reality, model is a oversimplification, you are really working with estimated of the true\nexpected utility (we assume this estimate is unbiased)\n- Optimizer's curse: tendency for the estimated expected utility of the best choice\nto be too high (taking utility estimates at face value is a bad idea)\n- Solution: Bayesian approach that uses explicit probability model of the error in the utility\nestimates. Treat utility estimate as evidence and compute posterior distribution for the true \nutility using Bayes' rule.\n\nHuman judgement/irrationality:\n- Normative theory: describes how a rational agent should act\n- Descriptive theory: describes how actual agents really act\n- Certainty effect can be used to explain some irrational preferences (people attracted\nto gains that are certain)\n- Ambiguity aversion: people prefer to elect the known probability rather than the unknown\nunknowns\n- Framing effect: exact wording of a decision problem can have a big impact on agent's choice\n- Anchoring effect: people prefer to make relative utility judgements rather than absolute\nones (200 wine vs. 55 wine)\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nSequential decision problems:\n- Transition model: describes the outcome of each action in each state\n- Outcome is stochastic \n$P(s'|s,a) = T(s, a, s')$ is probability of reaching state $s'$ if action $a$\nis done in state $s$\n- Markovian: probability of reaching next state from current state depends only on the\ncurrent state and not on the history of earlier states\n- Decision problem is sequential, so the utility function for the agent will depend on a sequence\nof states and actions (environment history)\n\nMDP\n- Sequential decision problem for fully observable, stochastic environment with Markovian\ntransition model and additive rewards\n- Consists of set of states, set of actions, transition model, reward function\n- Methods for solving MDPs involve dynamic programming\n- Solution for MDP could be a policy: solution that specifies what the agent should do\nfor any state that the agent might reach\n$\\pi(s)$ is the action recommended by policy $\\pi$ for state $s$\n- Quality of a policy is measured by the expected utility of the possible environment histories\ngenerated by that policy\n- Optimal policy $\\pi^{*}$ is one that yields the highest expected utility\n\nOptimal policies:\n- Utility of a history is the sum of discounted rewards\n- Can compare policies by cmoparing expected utilities obtained when executing them\n- The probability distribution over state sequences is determined by initial state, policy, \nand the transition model for the environment\n- $U^{\\pi}(s)$ is the expected utility obtained by executing $\\pi$ starting in $s$\n- Optimal policy is independent of the starting state when using discounted utilities with \ninfinite horizons (BUT this does not hold for finite horizon policies or other ways\nof combining rewards over time, e.g. taking the max)\n- $U^{\\pi^{*}}(s)$ is the true utility of a state: expected sum of discounted rewards if\nagent executes optimal policy \n- $U(s)$ the utility of a state is the expected reward for the next transition plus the discounted\nutility of the next state, assuming the agent chooses the optimal action. \n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \nAlgorithms for MDP:\n- Generate exact solutions: value iteration, policy iteration, linear programming\n- Approximate algorithms: Monte Carlo planning\n\nValue iteration: \n\n$V_{k+1}(s) \\leftarrow \\max_a \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n\n- $n$ possible states $\\rightarrow n$ Bellman equations\n- $n$ equations (nonlinear) contain $n$ unknowns (utilities of the states)\n- Goal: Solve the equations to find the utilities\n- Iterative approach: update the utility of each state from the utilities of its neighbors\n- After convergence, final utility values are solutions to the Bellman equations \n- Solutions are unique and the corresponding policy is optimal\n- Value iteration is propagating information through the state space by means of local updates\n- Time $O(AS^2)$ for each iteration\n\nPolicy iteration: \n- Alternates between policy evaluation and policy improvement\n\nEvaluation: $V_{k+1}^{\\pi_i}(s) \\leftarrow T(s, \\pi_i(s), s') [R(s, \\pi_i(s), s') + \\gamma V_{k+1}^{\\pi_i}(s')]$\n\nImprovement: $\\pi_{i+1}(s) = {\\argmax}_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V^{\\pi_i}(s')]$\n\n- Policy evaluation: Given policy $\\pi_i$ calculate $U_i = U^{\\pi_i}$ the utility of each \nstate if $\\pi_i$ were to be executed\n- Policy improvement: Calculate new MEU policy $\\pi_{i+1}$ using one-step look ahead based\non $U_i$\n- Convergence happens when policy improvement yields no change in the utilities\n- At this point $U_i$ is a solution to the Bellman equation, and $\\pi_i$ is\nan optimal policy \n- Action in each state is fixed by the policy, so the simplified Bellman equations (do what\nthe policy says) are linear because the $max$ operator is removed\n- $n$ states, $n$ linear equations, $n$ unknowns can be solved in $O(n^3)$ time\n\nOnline algorithms for MDPs:\n- Value iteration and policy iteration are offline algorithms: generate optimal solution\nfor the problem, which can then be executed by simple agent \n- Online algorithms: agent does significant amount of computation at each decision point\nrather than operating with precomputed information  \n\nPolicy evaluation:\n- Use Bellman equation with action $a$ fixed by $\\pi$. We can solve system of $n$\nvariables and $n$ equations in $O(n^3)$ time\n- $O(S^2)$ per iteration according to slides\n\nFlashcards:\n- Asynchronous policy iteration  updates only a subset of states. \n- This can be useful because you can design heuristics about what states to update, and can reduce the time it takes to run policy iteration.\n\nModified policy iteration (adapative DP version):\n- Policy iteration where the value iteration step updates using the learned transition probabilities and reward. \n- This lets us update the utilities concurrently with the transition and reward rather than solving them after all trials.\n\n\n## Module 8 Lecture Notes\n\n```\nfunction VALUE-ITERATION(mdp, ε) returns a utility function\n inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a),\n      rewards R(s,a,s′), discount γ\n   ε, the maximum error allowed in the utility of any state\n local variables: U, U′, vectors of utilities for states in S, initially zero\n        δ, the maximum change in the utility of any state in an iteration\n\n repeat\n   U ← U′; δ ← 0\n   for each state s in S do\n     U′[s] ← max_a ∈ A(s) Q-VALUE(mdp,s,a,U)\n     if | U′[s] − U[s] | > δ then δ ← | U′[s] − U[s] |\n until δ < ε(1 − γ)/γ\n return U\n```\n===============================================================================\n```\nfunction POLICY-ITERATION(mdp) returns a policy\n inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a)\n local variables: U, a vector of utilities for states in S, initially zero\n        π, a policy vector indexed by state, initially random\n\n repeat\n   U ← POLICY-EVALUATION(π, U, mdp)\n   unchanged? ← true\n   for each state s in S do\n     a * ← argmax_a ∈ A(s) Q-VALUE(mdp,s,a,U)\n     if Q-VALUE(mdp,s,a*,U) > Q-VALUE(mdp,s,π[s],U) then do\n       π[s] ← a* ; unchanged? ← false\n until unchanged?\n return π\n```\n\n===============================================================================\n\nMDP is:\n- Sequential decision problem\n- For fully observable environment\n- With stochastic transition model\n- That has additive rewards\n\nReward scales:\n- Scale of utilities is arbitrary (affine transformation leaves optimal decision unchanged)\n- Similarly so for the optimal policy in an MDP\n\nRepresenting MDPs:\n- Represent $P(s'|s, a)$ and $R(s,a,s')$ with 3 dimensional table of size $S^2 * A$\n- Usually tables are sparse, of size $O(SA)$\n\nUtilities over time:\n- With finite horizon, optimal action in a given state may depend on how much time is left\n- Nonstationary: policy that depends on time \n- infinite horizon, optimal action depends only on the current state\n- Stationary: policy does not depend on time \n- There can be finite state sequences in infinite-horizon MDP that contains a terminal state\n\nCalculate utility of state sequences:\n- Additive discounted rewards: $R(s_0, a_0, s_1) + \\gamma R(s_1, a_1, s_2) + ... $\n- Discount factor $\\gamma$ describes the preference of an agent for current rewards over future rewards\n- $\\gamma$ close to 0 means rewards in the distant future are viewed as insignificant \n(agent focused on short term)\n- $\\gamma$ close to 1 means agent is more willing to wait for long-term rewards \n- $\\gamma = 1$ is special case of purely additive rewards \n- Agent's preferences between state sequences are stationary: if you prefer one future\nto another starting tomorrow, then you should still prefer that future if it were to start\ntoday instead\n- With discounted rewards and $\\gamma < 1$, utility of infinite sequence is finite\n- Proper policy: guaranteed to reach a terminal state (we are able to use $\\gamma = 1$ with proper\npolicies)\n- Improper policies (agent never reaching terminal state because $\\gamma > 0$) is good reason\nfor using discounted rewards\n\nQ-function:\n- $Q(s,a)$ is the action-utility function: expected utility of taking a given action\nin a given state\n- Optimal policy can be extracted from Q-function by $\\pi^{*}(s) = {\\argmax}_{a} Q(s,a)$\n- Bellman equation for Q-function: expected total reward for taking action is its immediate reward\nplus the discounted utility of the outcome state\n- Solving the Bellman equations for $U$ or $Q$ gives us what we need to find an optimal policy\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Decision theoretic agent** - agent that makes rational decisions based on what it believes and what it wants\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" \n",
        "N-Armed Bandit:\n",
        "- Exploitation: of the current best action to obtain rewards\n",
        "- Exploration of previously unknown states and actions to gain information, which\n",
        "can be converted into a better policy and better long-term rewards\n",
        "\n",
        "Bandit problems:\n",
        "- Each arm $M_i$ is a Markov reward process (MRP): MDP with only one possible action $a_i$\n",
        "- Each arm has states, transition model, reward\n",
        "- The arm defines a distribution over sequences of rewards $R_{i,0}, R_{i,1}, ..., $\n",
        "where eah reward $R_{i,t}$ is a random variable\n",
        "- Overall bandit problem is MDP\n",
        "- Pull the arm with highest Gittins index and then update the Gittins indices. This produces\n",
        "optimal policy for bandit problem \n",
        "- Bernoulli bandit: each arm $M_i$ produces a reward of 0 or 1 with fixed but unknown probability \n",
        "\n",
        "Approximately optimal bandit policies:\n",
        "- Calculating Gittin indices is not always possible for realistic problems\n",
        "- Upper confidence bound: heuristic that use the samples from each arm to establish\n",
        "confidence interval for the value of the arm\n",
        "- UCB value is not strictly an index because it depends on $N$, the total number of \n",
        "samples drawn across all arms\n",
        "- Thompson sampling: chooses an arm randomly according to the probability that the arm is\n",
        "in fact optimal, given the samples so far\n",
        "- Bandit superprocess (BSP): generalization of the bandit process. Each arm is a MDP \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" \n",
        "Sparse rewards (chess and racing): vast majority of states the agent is given no informative\n",
        "reward signal  \n",
        "\n",
        "Model-based RL:\n",
        "- Agent uses transition model of the environment to help interpret the reward signals and to\n",
        "make decisions about how to act.\n",
        "- Model maybe known or unknown\n",
        "\n",
        "Model-free RL:\n",
        "- Agent does not know and does not learn a transition model for the environment\n",
        "- It learns a direct representation of how to behave: 1.) Action utility and 2.) Policy search\n",
        "\n",
        "Action utility learning: \n",
        "- Most common form is Q-learning, where agent learns Q-function\n",
        "$Q(s,a)$ denoting the sum of rewards from state $s$ onward if action $a$ is taken \n",
        "- Given Q-function, agent can choose what to do in $s$ by finding the action with the\n",
        "highest Q-value \n",
        "\n",
        "Policy search: \n",
        "- Agent learns a policy that maps from states to actions\n",
        "\"\"\"\n",
        "\n",
        "chapter22_2 =  \"\"\" \n",
        "Passive RL:\n",
        "- Agent's policy is fixed and the task is to learn the utilities of states (or state-action pairs)\n",
        "- Agent trying to learn $U^{\\pi}(s)$ the expected total discounted reward if policy $\\pi$\n",
        "is executed beginning in state $s$\n",
        "- Agent does not know $P(s'|s,a)$ and $R(s,a,s')$\n",
        "\n",
        "Adaptive DP:\n",
        "- Agent learns the transition model that connects states and solves the corresponding\n",
        "MDP using DP\n",
        "- Plug the learned transition model $P(s'|s,\\pi(s))$ and observed rewards $R(s, \\pi(s),s')$ to\n",
        "calculate utilities of states\n",
        "- The Bellman equations are linear when the policy is fixed\n",
        "\n",
        "Temporal difference learning:\n",
        "- Use the observed transitions to adjust the utilities of observed states so that they \n",
        "agree with the constraint equations\n",
        "- When transition occurs from state $s$ to state $s'$ via action $\\pi(s)$, apply\n",
        "update to $U^{\\pi}(s)$ (formula in cheat sheet)\n",
        "\n",
        "$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\\\alpha TD term$\n",
        "\n",
        "- The update rule uses the difference in utilities between successive states/times\n",
        "- $TD term$  is an error signal, and the update is intended to reduce the error\n",
        "\n",
        "Difference between ADP and TD:\n",
        "- TD adjusts a state to agree with its observed successor\n",
        "- ADP adjusts the state to agree with all successors that might occur, weighted by their\n",
        "probabilities\n",
        "- TD makes single adjustment per observed transition\n",
        "- ADP makes as many needed to restore consistency between utility estimates $U$ and \n",
        "transition model $P$\n",
        "\"\"\"\n",
        "\n",
        "chapter22_3 =  \"\"\" \n",
        "Active RL:\n",
        "- Agent gets to decide which actions to take\n",
        "- Agent needs to learn a complete transition model with outcome probabilities for all actions\n",
        "- Needs to learn utilities defined by the optimal policy, which obey Bellman equations\n",
        "- Needs to obtain utility function $U$ that is optimal for learned model\n",
        "- With $U$, the agent can extract optimal action or use optimal policy \n",
        "\n",
        "Greedy Agent:\n",
        "- Greedily takes the action that it currently believes to be optimal at each step\n",
        "- Learned model is not the same as the true environment. What is optimal in the learned model\n",
        "can be suboptimal in the true environment.\n",
        "\n",
        "GLIE:\n",
        "- Greedy in the limit of infinite exploration\n",
        "- GLIE scheme must try each action in each state an unbounded number of times to avoid\n",
        "having a finite probability that an optimal action is missed\n",
        "- Will eventually learn the true transition model and can then use exploitation\n",
        "\n",
        "TD-difference Q-learning:\n",
        "- Q-learning avoids needs for a transition model by learning $Q(s,a)$ instead of $U(s)$\n",
        "- $Q(s,a)$ is the exoected total discounted reward if the agent takes action $a$ in state\n",
        "$s$ and acts optimally thereafter\n",
        "- Knowing Q-function allows agent to act optimally by simplying choosing ${\\\\argmax}_a Q(s,a)$\n",
        "- TD update is calculated whenever acction $a$ is executed in state $s$ leading to state $s'$\n",
        "- The TD term represents an error that the update is trying to minimize \n",
        "- Important: TD Q-learning agent does not need transition model $P(s'|s,a)$ for learning or\n",
        "for action selection\n",
        "- Q-learning is off policy\n",
        "\"\"\"\n",
        "\n",
        "chapter22_4 =  \"\"\" \n",
        "- Evaluation function: compact measure of desirability for potentially vast state spaces\n",
        "- In RL, evaluation function is an approximate utility function\n",
        "- Function approximation is the process of constructing a compact approximation of \n",
        "the true utility function or Q-function\n",
        "- Function approximation allows inductive generalization\n",
        "- We can approximate utility function using a weighted linear combination of features:\n",
        "\n",
        "$\\\\hat{U}_{\\\\theta}(s) = \\\\theta_1 f_1(s) + ... + \\\\theta_n f_n(s)$\n",
        "\n",
        "Approximate direct utility:\n",
        "- For RL, makes more sense to use online learning algorithm that updates parameters\n",
        "after each trial\n",
        "- Update parameters $\\\\theta$ by computing gradient (the usual way)\n",
        "- Changing the parameters $\\\\theta_i$ in response to one observed transition\n",
        "between two states also changes the values of $\\\\hat{U}_{\\\\theta}$ for every other\n",
        "state (this is what we mean by generalization)\n",
        "\n",
        "Approximate TD:\n",
        "- Adjust the parameters to reduce the temporal difference between successive states\n",
        "- Experience replay: retain trajectories from entire learning process to ensure\n",
        "its value function is still accurate for parts of the state space that is no\n",
        "longer visited \n",
        "- Learning a model for an observable environment is a supervised learning problem\n",
        "because the next percept gives the outcome state (label)\n",
        "- In partially observable environments, the next percept is no longer a label\n",
        "for the state prediction problem\n",
        "\n",
        "Hierarchical RL:\n",
        "- Break long action sequences into smaller pieces, until action sequences\n",
        "are short enough to make learning easy\n",
        "\"\"\"\n",
        "\n",
        "chapter22_5 =  \"\"\" \n",
        "Policy search: keep updating policy as long as performance improves, then stop\n",
        "- Policy $\\pi$ is a function that maps states to actions \n",
        "\n",
        "$\\pi(s) = {\\\\argmax}_a \\\\hat{Q}_{\\\\theta}(s, a)$\n",
        "\n",
        "- Continue adjusting parameters $\\theta$ to improve the policy\n",
        "- If policy is represented by Q-functions, then policy search will learn Q-functions\n",
        "(BUT this is NOT the same as Q-learning)\n",
        "- Q-learning finds a value of $\\theta$ such that $\\\\hat{Q}_{\\\\theta}$ is close to $Q^{*}$\n",
        "- Policy search finds a value of $\\theta$ that results in good performance\n",
        "- When actions are discrete, the policy is a discontinuous function of the parameters\n",
        "(makes gradient-based search difficult)\n",
        "- Fix: policy search methods use stochastic policy representations $\\pi_{\\theta}(s,a)$\n",
        "which specify the probability of selecting action $a$ in state $s$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "```\n",
        "function Q-Learning_Agent(percept) returns an action\n",
        " inputs: percept, a percept indicating the current state s' and reward signal r'\n",
        " persistent: Q, a table of action values indexed by state and action, initially zero\n",
        "       Nsa, a table of frequencies for state-action pairs, initially zero\n",
        "       s, a, r, the previous state, action, and reward, initially null\n",
        "\n",
        " if Terminal?(s) then Q[s, None] ← r'\n",
        " if s is not null then\n",
        "   increment Nsa[s, a]\n",
        "   Q[s, a] ← Q[s, a] + α(Nsa[s, a])(r + γ maxa' Q[s', a'] - Q[s, a])\n",
        " s, a, r ← s', argmaxa' f(Q[s', a'], Nsa[s', a']), r'\n",
        " return a\n",
        "```\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 136,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "bff8a67f-f72a-49ad-e777-5f2e03ff4d05"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 137,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \nN-Armed Bandit:\n- Exploitation: of the current best action to obtain rewards\n- Exploration of previously unknown states and actions to gain information, which\ncan be converted into a better policy and better long-term rewards\n\nBandit problems:\n- Each arm $M_i$ is a Markov reward process (MRP): MDP with only one possible action $a_i$\n- Each arm has states, transition model, reward\n- The arm defines a distribution over sequences of rewards $R_{i,0}, R_{i,1}, ..., $\nwhere eah reward $R_{i,t}$ is a random variable\n- Overall bandit problem is MDP\n- Pull the arm with highest Gittins index and then update the Gittins indices. This produces\noptimal policy for bandit problem \n- Bernoulli bandit: each arm $M_i$ produces a reward of 0 or 1 with fixed but unknown probability \n\nApproximately optimal bandit policies:\n- Calculating Gittin indices is not always possible for realistic problems\n- Upper confidence bound: heuristic that use the samples from each arm to establish\nconfidence interval for the value of the arm\n- UCB value is not strictly an index because it depends on $N$, the total number of \nsamples drawn across all arms\n- Thompson sampling: chooses an arm randomly according to the probability that the arm is\nin fact optimal, given the samples so far\n- Bandit superprocess (BSP): generalization of the bandit process. Each arm is a MDP \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n \nSparse rewards (chess and racing): vast majority of states the agent is given no informative\nreward signal  \n\nModel-based RL:\n- Agent uses transition model of the environment to help interpret the reward signals and to\nmake decisions about how to act.\n- Model maybe known or unknown\n\nModel-free RL:\n- Agent does not know and does not learn a transition model for the environment\n- It learns a direct representation of how to behave: 1.) Action utility and 2.) Policy search\n\nAction utility learning: \n- Most common form is Q-learning, where agent learns Q-function\n$Q(s,a)$ denoting the sum of rewards from state $s$ onward if action $a$ is taken \n- Given Q-function, agent can choose what to do in $s$ by finding the action with the\nhighest Q-value \n\nPolicy search: \n- Agent learns a policy that maps from states to actions\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nPassive RL:\n- Agent's policy is fixed and the task is to learn the utilities of states (or state-action pairs)\n- Agent trying to learn $U^{\\pi}(s)$ the expected total discounted reward if policy $\\pi$\nis executed beginning in state $s$\n- Agent does not know $P(s'|s,a)$ and $R(s,a,s')$\n\nAdaptive DP:\n- Agent learns the transition model that connects states and solves the corresponding\nMDP using DP\n- Plug the learned transition model $P(s'|s,\\pi(s))$ and observed rewards $R(s, \\pi(s),s')$ to\ncalculate utilities of states\n- The Bellman equations are linear when the policy is fixed\n\nTemporal difference learning:\n- Use the observed transitions to adjust the utilities of observed states so that they \nagree with the constraint equations\n- When transition occurs from state $s$ to state $s'$ via action $\\pi(s)$, apply\nupdate to $U^{\\pi}(s)$ (formula in cheat sheet)\n\n$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha TD term$\n\n- The update rule uses the difference in utilities between successive states/times\n- $TD term$  is an error signal, and the update is intended to reduce the error\n\nDifference between ADP and TD:\n- TD adjusts a state to agree with its observed successor\n- ADP adjusts the state to agree with all successors that might occur, weighted by their\nprobabilities\n- TD makes single adjustment per observed transition\n- ADP makes as many needed to restore consistency between utility estimates $U$ and \ntransition model $P$\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nActive RL:\n- Agent gets to decide which actions to take\n- Agent needs to learn a complete transition model with outcome probabilities for all actions\n- Needs to learn utilities defined by the optimal policy, which obey Bellman equations\n- Needs to obtain utility function $U$ that is optimal for learned model\n- With $U$, the agent can extract optimal action or use optimal policy \n\nGreedy Agent:\n- Greedily takes the action that it currently believes to be optimal at each step\n- Learned model is not the same as the true environment. What is optimal in the learned model\ncan be suboptimal in the true environment.\n\nGLIE:\n- Greedy in the limit of infinite exploration\n- GLIE scheme must try each action in each state an unbounded number of times to avoid\nhaving a finite probability that an optimal action is missed\n- Will eventually learn the true transition model and can then use exploitation\n\nTD-difference Q-learning:\n- Q-learning avoids needs for a transition model by learning $Q(s,a)$ instead of $U(s)$\n- $Q(s,a)$ is the exoected total discounted reward if the agent takes action $a$ in state\n$s$ and acts optimally thereafter\n- Knowing Q-function allows agent to act optimally by simplying choosing ${\\argmax}_a Q(s,a)$\n- TD update is calculated whenever acction $a$ is executed in state $s$ leading to state $s'$\n- The TD term represents an error that the update is trying to minimize \n- Important: TD Q-learning agent does not need transition model $P(s'|s,a)$ for learning or\nfor action selection\n- Q-learning is off policy\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n- Evaluation function: compact measure of desirability for potentially vast state spaces\n- In RL, evaluation function is an approximate utility function\n- Function approximation is the process of constructing a compact approximation of \nthe true utility function or Q-function\n- Function approximation allows inductive generalization\n- We can approximate utility function using a weighted linear combination of features:\n\n$\\hat{U}_{\\theta}(s) = \\theta_1 f_1(s) + ... + \\theta_n f_n(s)$\n\nApproximate direct utility:\n- For RL, makes more sense to use online learning algorithm that updates parameters\nafter each trial\n- Update parameters $\\theta$ by computing gradient (the usual way)\n- Changing the parameters $\\theta_i$ in response to one observed transition\nbetween two states also changes the values of $\\hat{U}_{\\theta}$ for every other\nstate (this is what we mean by generalization)\n\nApproximate TD:\n- Adjust the parameters to reduce the temporal difference between successive states\n- Experience replay: retain trajectories from entire learning process to ensure\nits value function is still accurate for parts of the state space that is no\nlonger visited \n- Learning a model for an observable environment is a supervised learning problem\nbecause the next percept gives the outcome state (label)\n- In partially observable environments, the next percept is no longer a label\nfor the state prediction problem\n\nHierarchical RL:\n- Break long action sequences into smaller pieces, until action sequences\nare short enough to make learning easy\n\n\n## Module 9 Lecture Notes\n \n```\nfunction Q-Learning_Agent(percept) returns an action\n inputs: percept, a percept indicating the current state s' and reward signal r'\n persistent: Q, a table of action values indexed by state and action, initially zero\n       Nsa, a table of frequencies for state-action pairs, initially zero\n       s, a, r, the previous state, action, and reward, initially null\n\n if Terminal?(s) then Q[s, None] ← r'\n if s is not null then\n   increment Nsa[s, a]\n   Q[s, a] ← Q[s, a] + α(Nsa[s, a])(r + γ maxa' Q[s', a'] - Q[s, a])\n s, a, r ← s', argmaxa' f(Q[s', a'], Nsa[s', a']), r'\n return a\n```\n\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 = \"\"\" \n",
        "- Belief state: representation of the set of all possible world states that agent\n",
        "might be in and generating a contingency plan for all of them\n",
        "- Rational decision: depends on the relative importance of the various goals\n",
        "and the likelihood that they will be achieved\n",
        "- Probability statements are made with respect to a knowledge state, not with\n",
        "respect to the real world e.g. \"the probability that the patient has a cavity, given\n",
        "that he has a toothache is $0.8$\"\n",
        "\n",
        "Uncertainty and rational decisions:\n",
        "- Agent must have preferences among different possible outcomes of different plans\n",
        "- Outcome: completely specified state\n",
        "- Utility of a state is relative to an agent (need to account for taste or preferences)\n",
        "\n",
        "Decision theory is the general theory of rational decisions:\n",
        "- $Decision theory = probability theory + utility theory$\n",
        "- Fundamental idea is that an agent is rational iff and only if it chooses the\n",
        "action that yields the highest expected utility, averaged over all possible outcomes\n",
        "of the actions (MEU principle)\n",
        "- A decision theoretic agent's belief state represents possibilities for the world\n",
        "states AND their probabilities. Agent can make probabilistic predictions\n",
        "of action outcomes and can thus select the action with the highest expected utility\n",
        "\"\"\"\n",
        "\n",
        "chapter12_2 = \"\"\" \n",
        "- Probabilistic assertions talk about how probable the various worlds are\n",
        "- Sample space: the set of all possible words\n",
        "- The possible worlds are mutually exclusive and exhaustive \n",
        "- $P(A)$ is called \"unconditional\" or \"prior probabilities\": they refer to degrees\n",
        "of belief in the absence of any other information\n",
        "- $ P(A|B)$ is the \"conditional\" or \"posterior\" probability \n",
        "- When making decisions, agent needs to condition on all the evidence observed\n",
        "- $P(cavity|toothache) = 0.6$ means \"whenever toothache is true, and we have no further\n",
        "evidence, conclude that cavity is true with probability $0.6$\n",
        "- Probability distribution for random variable: is an assignment of probability\n",
        "for each possible value of the random variable\n",
        "\n",
        "Some equations:\n",
        "\n",
        "$P(A|B) = \\\\frac{P(A \\\\land B)}{P(B)}$\n",
        "\n",
        "$P(A \\\\land B) = P(A|B)P(B)$\n",
        "\n",
        "$P(A \\\\lor B) = P(A) + P(B) - P(A \\\\land B)$\n",
        "\"\"\"\n",
        "\n",
        "chapter12_3 = \"\"\" \n",
        "Probabilistic inference: computation of posterior probabilities for queries\n",
        "given observed evidence\n",
        "- The full joint distribution is the knowledge base where answers to all questions\n",
        "are derived\n",
        "- Marginalization: sum up the probabilities for each possible value of the other variables\n",
        "\n",
        "$P(Y) = \\sum_z P(Y, Z=z) = P(Y) = \\sum_Z P(Y|Z)P(Z)$\n",
        "\n",
        "Normalization:\n",
        "- Allows us to proceed when some probability assessment is not available\n",
        "- $X$ is the query \n",
        "- $E$ is the list of evidence variables, $e$ is the list of evidence variables\n",
        "- $Y$ is the remaining unobserved values\n",
        "\n",
        "$P(X|e) = \\\\alpha P(X, e) = \\\\alpha \\sum_y P(X,e,y)$\n",
        "\n",
        "$P(cavity, toothache) = \\\\alpha P(cavity, toothache) = \\\\alpha P(cavity, toothache, catch) + P(cavity, toothache, \\\\neg catch)$\n",
        "\n",
        "Full joint probability tables:\n",
        "- For $n$ Boolean variables, it requires input table of size $O(2^n)$ and requires $O(2^n)$ time to process\n",
        "- Full joint distribution tables is usually not practical \n",
        "\"\"\"\n",
        "\n",
        "chapter12_4 = \"\"\" \n",
        "Weather and dental problems are independent:\n",
        "\n",
        "$P(D_1, D_2, D_3, W) = P(D_1, D_2, D_3)P(W)$\n",
        "\n",
        "Coin flips are independent:\n",
        "\n",
        "$P(C_1, C_2, ..., C_n) = P(C_1)P(C_2)...P(C_n)$\n",
        "\n",
        "Independent between propositions/variables $A$ and $B$ give us:\n",
        "\n",
        "$P(A|B) = P(A)$ or\n",
        "\n",
        "$P(B|A) = P(B)$ or \n",
        "\n",
        "$P(A \\\\land B) = P(A)P(B)$\n",
        "\n",
        "Independence allows full joint distributions to be factored into separate joint\n",
        "distributions on those subsets:\n",
        "\n",
        "- $n$ independent coin flips, $P(C_1,...,C_n)$ has $2^n$ entries, but can be\n",
        "represented as the product of $n$ single-variable distributions $P(C_i)$\n",
        "\"\"\"\n",
        "\n",
        "chapter12_5 = \"\"\" \n",
        "Bayes' Rule:\n",
        "\n",
        "$P(Y|X) = \\\\frac{P(X|Y)P(Y)}{P(X)}$\n",
        "\n",
        "General version of Bayes' conditioned on background evidence $e$:\n",
        "\n",
        "$P(Y|X,e) = \\\\frac{P(X|Y,e)P(Y|e)}{P(X|e)}$\n",
        "\n",
        "Bayes' rule with normalization:\n",
        "\n",
        "$P(Y|X) = \\\\alpha P(X|Y)P(Y)$\n",
        "\n",
        "Conditional independence\n",
        "- Toothache and catch are independent, given whether or not you have a cavity\n",
        "- Each is directly caused by a cavity, but neither has a direct effect on the other\n",
        "- Toothache and catch are conditionally independent, given cavity:\n",
        "\n",
        "$P(toothache \\land catch|cavity) = P(toothache|cavity)P(catch|cavity)$\n",
        "\n",
        "General definition of conditional independence of variables $X$ and $Y$ given $Z$:\n",
        "\n",
        "$P(X, Y|Z) = P(X|Z)P(Y|Z)$\n",
        "\n",
        "$P(X|Y,Z) = P(X|Z)$\n",
        "\n",
        "$P(Y|X,Z) = P(Y|Z)$\n",
        "\n",
        "- For $n$ symptons that are all conditionally independent given cavity, the table\n",
        "grows $O(n)$ instead of $O(2^n)$\n",
        "\n",
        "1.) Causal chain: $X \\\\rightarrow Y \\\\rightarrow Z$\n",
        "\n",
        "- $X$ is NOT independent of $Z$\n",
        "\n",
        "Joint: $P(x,y,z) = P(x)P(y|x)P(z|y)$\n",
        "\n",
        "- YES: $X$ is independent of $Z$ given $Y$\n",
        "\n",
        "$P(z|x,y) = \\\\frac{P(x,y,z)}{P(x,y)} = \\\\frac{P(x)P(y|x)P(z|y)}{P(x)P(y|x)} = P(z|y)$\n",
        "\n",
        "2.) Common cause: $ X \\\\leftarrow Y \\\\rightarrow Z$\n",
        "\n",
        "Joint: $P(x,y,z) = P(y)P(x|y)P(z|y)$ \n",
        "\n",
        "- $X$ is NOT independent of $Z$\n",
        "\n",
        "- YES: $X$ is independent of $Z$ given $Y$\n",
        "\n",
        "$P(z|x,y) = \\\\frac{P(x,y,z)}{P(x,y)} = \\\\frac{P(y)P(x|y)P(z|y)}{P(y)P(x|y)} = P(z|y)$\n",
        "\n",
        "3.) Common effect: $X \\\\rightarrow Z \\\\leftarrow Y$\n",
        "\n",
        "- YES: $X$ is independent of $Y$\n",
        "\n",
        "- $X$ is NOT independent of $Y$ given $Z$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter12_6 = \"\"\" \n",
        "Naive Bayes model:\n",
        "- Single cause directly influences several effects, all effects are conditionally\n",
        "independent given the cause\n",
        "- Uses conditional independence assumption\n",
        "- Linear in the number of observed effects\n",
        "\n",
        "$P(C, E_1,...E_n) = P(C) \\prod_i P(E_i|C)$\n",
        "\"\"\"\n",
        "\n",
        "chapter12_7 = \"\"\" \n",
        "\n",
        "\"\"\"\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",
        "\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "D-Separation:\n",
        "- Q: Are $X$ and $Y$ conditionally independent given evidence variables $Z$?\n",
        "- Yes if $X$ and $Y$ are d-separated by $Z$\n",
        "- A path is active if each triple (segment) is active \n",
        "\n",
        "Algorithm:\n",
        "- Query: Is $X_i$ independent $X_j$ given evidence variables?\n",
        "- Check all undirected paths between $X_i$ and $X_j$\n",
        "- If one or more paths are active (direction comes back in), then independence\n",
        "is not guaranteed\n",
        "- If no paths are active (all paths inactive) then independence is guaranteed\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 138,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6f2f16af-e04d-455e-e947-9b712a7583a6"
      },
      "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": 139,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n- Belief state: representation of the set of all possible world states that agent\nmight be in and generating a contingency plan for all of them\n- Rational decision: depends on the relative importance of the various goals\nand the likelihood that they will be achieved\n- Probability statements are made with respect to a knowledge state, not with\nrespect to the real world e.g. \"the probability that the patient has a cavity, given\nthat he has a toothache is $0.8$\"\n\nUncertainty and rational decisions:\n- Agent must have preferences among different possible outcomes of different plans\n- Outcome: completely specified state\n- Utility of a state is relative to an agent (need to account for taste or preferences)\n\nDecision theory is the general theory of rational decisions:\n- $Decision theory = probability theory + utility theory$\n- Fundamental idea is that an agent is rational iff and only if it chooses the\naction that yields the highest expected utility, averaged over all possible outcomes\nof the actions (MEU principle)\n- A decision theoretic agent's belief state represents possibilities for the world\nstates AND their probabilities. Agent can make probabilistic predictions\nof action outcomes and can thus select the action with the highest expected utility\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n- Probabilistic assertions talk about how probable the various worlds are\n- Sample space: the set of all possible words\n- The possible worlds are mutually exclusive and exhaustive \n- $P(A)$ is called \"unconditional\" or \"prior probabilities\": they refer to degrees\nof belief in the absence of any other information\n- $ P(A|B)$ is the \"conditional\" or \"posterior\" probability \n- When making decisions, agent needs to condition on all the evidence observed\n- $P(cavity|toothache) = 0.6$ means \"whenever toothache is true, and we have no further\nevidence, conclude that cavity is true with probability $0.6$\n- Probability distribution for random variable: is an assignment of probability\nfor each possible value of the random variable\n\nSome equations:\n\n$P(A|B) = \\frac{P(A \\land B)}{P(B)}$\n\n$P(A \\land B) = P(A|B)P(B)$\n\n$P(A \\lor B) = P(A) + P(B) - P(A \\land B)$\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \nProbabilistic inference: computation of posterior probabilities for queries\ngiven observed evidence\n- The full joint distribution is the knowledge base where answers to all questions\nare derived\n- Marginalization: sum up the probabilities for each possible value of the other variables\n\n$P(Y) = \\sum_z P(Y, Z=z) = P(Y) = \\sum_Z P(Y|Z)P(Z)$\n\nNormalization:\n- Allows us to proceed when some probability assessment is not available\n- $X$ is the query \n- $E$ is the list of evidence variables, $e$ is the list of evidence variables\n- $Y$ is the remaining unobserved values\n\n$P(X|e) = \\alpha P(X, e) = \\alpha \\sum_y P(X,e,y)$\n\n$P(cavity, toothache) = \\alpha P(cavity, toothache) = \\alpha P(cavity, toothache, catch) + P(cavity, toothache, \\neg catch)$\n\nFull joint probability tables:\n- For $n$ Boolean variables, it requires input table of size $O(2^n)$ and requires $O(2^n)$ time to process\n- Full joint distribution tables is usually not practical \n\n\n## AIMA Chapter 12.4 Independence\n \nWeather and dental problems are independent:\n\n$P(D_1, D_2, D_3, W) = P(D_1, D_2, D_3)P(W)$\n\nCoin flips are independent:\n\n$P(C_1, C_2, ..., C_n) = P(C_1)P(C_2)...P(C_n)$\n\nIndependent between propositions/variables $A$ and $B$ give us:\n\n$P(A|B) = P(A)$ or\n\n$P(B|A) = P(B)$ or \n\n$P(A \\land B) = P(A)P(B)$\n\nIndependence allows full joint distributions to be factored into separate joint\ndistributions on those subsets:\n\n- $n$ independent coin flips, $P(C_1,...,C_n)$ has $2^n$ entries, but can be\nrepresented as the product of $n$ single-variable distributions $P(C_i)$\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \nBayes' Rule:\n\n$P(Y|X) = \\frac{P(X|Y)P(Y)}{P(X)}$\n\nGeneral version of Bayes' conditioned on background evidence $e$:\n\n$P(Y|X,e) = \\frac{P(X|Y,e)P(Y|e)}{P(X|e)}$\n\nBayes' rule with normalization:\n\n$P(Y|X) = \\alpha P(X|Y)P(Y)$\n\nConditional independence\n- Toothache and catch are independent, given whether or not you have a cavity\n- Each is directly caused by a cavity, but neither has a direct effect on the other\n- Toothache and catch are conditionally independent, given cavity:\n\n$P(toothache \\land catch|cavity) = P(toothache|cavity)P(catch|cavity)$\n\nGeneral definition of conditional independence of variables $X$ and $Y$ given $Z$:\n\n$P(X, Y|Z) = P(X|Z)P(Y|Z)$\n\n$P(X|Y,Z) = P(X|Z)$\n\n$P(Y|X,Z) = P(Y|Z)$\n\n- For $n$ symptons that are all conditionally independent given cavity, the table\ngrows $O(n)$ instead of $O(2^n)$\n\n1.) Causal chain: $X \\rightarrow Y \\rightarrow Z$\n\n- $X$ is NOT independent of $Z$\n\nJoint: $P(x,y,z) = P(x)P(y|x)P(z|y)$\n\n- YES: $X$ is independent of $Z$ given $Y$\n\n$P(z|x,y) = \\frac{P(x,y,z)}{P(x,y)} = \\frac{P(x)P(y|x)P(z|y)}{P(x)P(y|x)} = P(z|y)$\n\n2.) Common cause: $ X \\leftarrow Y \\rightarrow Z$\n\nJoint: $P(x,y,z) = P(y)P(x|y)P(z|y)$ \n\n- $X$ is NOT independent of $Z$\n\n- YES: $X$ is independent of $Z$ given $Y$\n\n$P(z|x,y) = \\frac{P(x,y,z)}{P(x,y)} = \\frac{P(y)P(x|y)P(z|y)}{P(y)P(x|y)} = P(z|y)$\n\n3.) Common effect: $X \\rightarrow Z \\leftarrow Y$\n\n- YES: $X$ is independent of $Y$\n\n- $X$ is NOT independent of $Y$ given $Z$\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nNaive Bayes model:\n- Single cause directly influences several effects, all effects are conditionally\nindependent given the cause\n- Uses conditional independence assumption\n- Linear in the number of observed effects\n\n$P(C, E_1,...E_n) = P(C) \\prod_i P(E_i|C)$\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n \n\n\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 \nD-Separation:\n- Q: Are $X$ and $Y$ conditionally independent given evidence variables $Z$?\n- Yes if $X$ and $Y$ are d-separated by $Z$\n- A path is active if each triple (segment) is active \n\nAlgorithm:\n- Query: Is $X_i$ independent $X_j$ given evidence variables?\n- Check all undirected paths between $X_i$ and $X_j$\n- If one or more paths are active (direction comes back in), then independence\nis not guaranteed\n- If no paths are active (all paths inactive) then independence is guaranteed\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 = \"\"\" \n",
        "- Bayesian network is a data structure that represents dependencies among variables\n",
        "- They can essentially represent any full joint probability distribution concisely\n",
        "\n",
        "BN set up:\n",
        "- Each node corresponds to a random variable\n",
        "- If there is an edge $X \\\\rightarrow Y$ then $X$ is a parent of $Y$ ($X$ has\n",
        "direct influence on $Y$)\n",
        "- DAG, so no cycles\n",
        "- Each node $X_i$ has probability information $\\\\theta_i (X_i | Parents(X_i))$ that\n",
        "measures the effect of the parents on the child using finite amount of parameters\n",
        "- The topology represents the conditional independence relationships\n",
        "- Once we have topology, we only need local probability information (conditional\n",
        "distribution given its parents)\n",
        "- The full joint distribution for all variables is defined by topology\n",
        "and local probability information\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter13_2 = \"\"\" \n",
        "- Syntax of BN: DAG with local probability information for each node\n",
        "- Semantics of BN: define how syntax corresponds to joint distribution\n",
        "over the variables of the network\n",
        "- Semantics define each entry in the joint distribution:\n",
        "\n",
        "$P(x_1,...,x_n) = \\prod_i \\\\theta(x_i | parents(X_i))= \\prod_i P(x_i | parents(X_i))$\n",
        "\n",
        "Properties of BN:\n",
        "- Complete and nonredundant representation of the domain\n",
        "- Local structure (sparse) system allows it to be compact because each subcomponent\n",
        "interacts directly with a limited number of other components\n",
        "- Linear growth in complexity\n",
        "- BN can reduce size of joint distribution from $O(2^n)$ to $O(n2^k)$, where $k$ \n",
        "is some constant\n",
        "- A variable is conditionally independent of its other predecessors, given its parents\n",
        "- \"Non-descendants\" property: a variable is conditionally independent of its non-descendants,\n",
        "given its parents\n",
        "- A variable is conditionally independent of all other nodes in the network,\n",
        "given its parents, children, and children's parents (Markov blanket)\n",
        "- Markov blanket follows from the d-separation property, since a variable's Markov \n",
        "blanket d-separates it from all other variables\n",
        "\n",
        "BN with continuous variables:\n",
        "- Can handle continous variables with discretization\n",
        "- Or using one of the standard families of PDFs (i.e. Guassian distribution)\n",
        "- Nonparametric solution is to define the conditional distribution implicitly\n",
        "with a collection of instances, each with specific values of the parent and child \n",
        "variables\n",
        "- Hybrid BN: network with both discrete and continuous variables: needs conditional\n",
        "distribution for both \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter13_3 = \"\"\" \n",
        "- $X$ query, $E$ evidence, $Y$ hidden variables\n",
        "- Query asks for $P(X|e)$ the posterior probability distribution of query variables\n",
        "given observed event \n",
        "\n",
        "$P(X|e) = \\\\alpha P(X, e) = \\\\alpha \\sum_y P(X,e,y)$\n",
        "\n",
        "Inference by enumeration:\n",
        "- Query can be answered using BN by computing sums of products of conditional \n",
        "probabilities from the network\n",
        "- Space complexity $O(n)$ and time complexity $O(2^n)$ for a network with\n",
        "$n$ Boolean variables\n",
        "- Contains wasted computations (repeated subexpressions)\n",
        "\n",
        "Variable elimination:\n",
        "- Improve enumeration algorithm by getting rid of repeated calculations (using DP):\n",
        "\n",
        "Exact inference:\n",
        "- Singly connected (polytrees): at most one undirected path (ignoring directions) between \n",
        "any 2 nodes in the network \n",
        "- Time/space complexity of exact inference in polytrees is linear in the size\n",
        "of the network\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 140,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9654f9f9-f2b3-4815-d238-fda066998969"
      },
      "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": 141,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \n- Bayesian network is a data structure that represents dependencies among variables\n- They can essentially represent any full joint probability distribution concisely\n\nBN set up:\n- Each node corresponds to a random variable\n- If there is an edge $X \\rightarrow Y$ then $X$ is a parent of $Y$ ($X$ has\ndirect influence on $Y$)\n- DAG, so no cycles\n- Each node $X_i$ has probability information $\\theta_i (X_i | Parents(X_i))$ that\nmeasures the effect of the parents on the child using finite amount of parameters\n- The topology represents the conditional independence relationships\n- Once we have topology, we only need local probability information (conditional\ndistribution given its parents)\n- The full joint distribution for all variables is defined by topology\nand local probability information\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n- Syntax of BN: DAG with local probability information for each node\n- Semantics of BN: define how syntax corresponds to joint distribution\nover the variables of the network\n- Semantics define each entry in the joint distribution:\n\n$P(x_1,...,x_n) = \\prod_i \\theta(x_i | parents(X_i))= \\prod_i P(x_i | parents(X_i))$\n\nProperties of BN:\n- Complete and nonredundant representation of the domain\n- Local structure (sparse) system allows it to be compact because each subcomponent\ninteracts directly with a limited number of other components\n- Linear growth in complexity\n- BN can reduce size of joint distribution from $O(2^n)$ to $O(n2^k)$, where $k$ \nis some constant\n- A variable is conditionally independent of its other predecessors, given its parents\n- \"Non-descendants\" property: a variable is conditionally independent of its non-descendants,\ngiven its parents\n- A variable is conditionally independent of all other nodes in the network,\ngiven its parents, children, and children's parents (Markov blanket)\n- Markov blanket follows from the d-separation property, since a variable's Markov \nblanket d-separates it from all other variables\n\nBN with continuous variables:\n- Can handle continous variables with discretization\n- Or using one of the standard families of PDFs (i.e. Guassian distribution)\n- Nonparametric solution is to define the conditional distribution implicitly\nwith a collection of instances, each with specific values of the parent and child \nvariables\n- Hybrid BN: network with both discrete and continuous variables: needs conditional\ndistribution for both \n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n- $X$ query, $E$ evidence, $Y$ hidden variables\n- Query asks for $P(X|e)$ the posterior probability distribution of query variables\ngiven observed event \n\n$P(X|e) = \\alpha P(X, e) = \\alpha \\sum_y P(X,e,y)$\n\nInference by enumeration:\n- Query can be answered using BN by computing sums of products of conditional \nprobabilities from the network\n- Space complexity $O(n)$ and time complexity $O(2^n)$ for a network with\n$n$ Boolean variables\n- Contains wasted computations (repeated subexpressions)\n\nVariable elimination:\n- Improve enumeration algorithm by getting rid of repeated calculations (using DP):\n\nExact inference:\n- Singly connected (polytrees): at most one undirected path (ignoring directions) between \nany 2 nodes in the network \n- Time/space complexity of exact inference in polytrees is linear in the size\nof the network\n\n\n## Module 11 Lecture Notes\n Your summary here \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 = \"\"\" \n",
        "- NB is generative classifier: build a model of how a class could generate input\n",
        "data. \n",
        "- Log reg is a discriminative classifier: learn what features from the input\n",
        "are most useful to discriminate between different classes\n",
        "- NB is probabilistic: returns class $\\\\hat{c}$ that has maximum posterior probability\n",
        "given document\n",
        "\n",
        "$\\\\hat{c} = {\\\\argmax}_c P(c|d) = {\\\\argmax}_c \\\\frac{P(d|c)P(c)}{P(d)} = {\\\\argmax}_c P(d|c)P(c)$\n",
        "\n",
        "- NB is generative because we read the above equation as a implicit assumption about\n",
        "how a document is generated \n",
        "- Class is sampled from $P(c)$ \"prior$\n",
        "- Words generated by sampling from $P(d|c)$ \"likelihood\"\n",
        "\n",
        "$\\\\hat{c} = {\\\\argmax}_c P(d|c)P(c) = {\\\\argmax}_c P(f_1,f_2,...,f_n|c)P(c)$\n",
        "\n",
        "Naive Bayes assumption says:\n",
        "\n",
        "$P(f_1,f_2,...,f_n|c) = P(f_1|c) * P(f_2|c) * ... * P(f_n|c)$\n",
        "\n",
        "Naive Bayes final equation:\n",
        "\n",
        "$c_{NB} = {\\\\argmax}_c P(C) \\\\prod_f P(f|c)$ \n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_2 = \"\"\" \n",
        "- Estimate $P(c)$ using percentage of the documents in training set that are in each\n",
        "class $c$\n",
        "\n",
        "$\\\\hat{P}(c) = \\\\frac{N_c}{N_{doc}}$\n",
        "\n",
        "- Estimate $P(w_i|c)$ as fraction of times word $w_i$ appears in all documents\n",
        "of topic $c$\n",
        "\n",
        "$\\\\hat{P}(w_i|c) = \\\\frac{count(w_i,c)}{\\\\sum_w count(w,c)}$\n",
        "\n",
        "LaPlace Smoothing:\n",
        "$\\\\hat{P}(w_i|c) = \\\\frac{count(w_i,c)+1}{|V| + \\\\sum_w count(w,c)}$\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_3 = \"\"\" \n",
        "- Binary NB: For each doc, remove all duplicate words before you concatenate them into\n",
        "single document\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_4 = \"\"\" \n",
        "- NB can be viewed as a set of class-specific unigram language models\n",
        "- Model for each class instantiates unigram language model\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_5 = \"\"\" \n",
        "- Accuracy not a good metric when you want to discover something rare (spam emails\n",
        "are rare) or when class is imbalanced \n",
        "- Precision: measures percentage of items that were predicted positive that are\n",
        "actually positive\n",
        "- Recall: measures percentage of positive items in the input that were correctly \n",
        "identified by the system as positive \n",
        "- Precision and recall emphasize true positives i.e. finding what we are supposed\n",
        "to be looking for\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_6 = \"\"\"\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "slp_chapter4_10 = \"\"\" \n",
        "- Representational harms: harms caused by a system that demeans a social group\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 142,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "97898af2-9b05-42dd-bfe0-975717f93618"
      },
      "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": 143,
      "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 \n- NB is generative classifier: build a model of how a class could generate input\ndata. \n- Log reg is a discriminative classifier: learn what features from the input\nare most useful to discriminate between different classes\n- NB is probabilistic: returns class $\\hat{c}$ that has maximum posterior probability\ngiven document\n\n$\\hat{c} = {\\argmax}_c P(c|d) = {\\argmax}_c \\frac{P(d|c)P(c)}{P(d)} = {\\argmax}_c P(d|c)P(c)$\n\n- NB is generative because we read the above equation as a implicit assumption about\nhow a document is generated \n- Class is sampled from $P(c)$ \"prior$\n- Words generated by sampling from $P(d|c)$ \"likelihood\"\n\n$\\hat{c} = {\\argmax}_c P(d|c)P(c) = {\\argmax}_c P(f_1,f_2,...,f_n|c)P(c)$\n\nNaive Bayes assumption says:\n\n$P(f_1,f_2,...,f_n|c) = P(f_1|c) * P(f_2|c) * ... * P(f_n|c)$\n\nNaive Bayes final equation:\n\n$c_{NB} = {\\argmax}_c P(C) \\prod_f P(f|c)$ \n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \n- Estimate $P(c)$ using percentage of the documents in training set that are in each\nclass $c$\n\n$\\hat{P}(c) = \\frac{N_c}{N_{doc}}$\n\n- Estimate $P(w_i|c)$ as fraction of times word $w_i$ appears in all documents\nof topic $c$\n\n$\\hat{P}(w_i|c) = \\frac{count(w_i,c)}{\\sum_w count(w,c)}$\n\nLaPlace Smoothing:\n$\\hat{P}(w_i|c) = \\frac{count(w_i,c)+1}{|V| + \\sum_w count(w,c)}$\n\n\n## SLP Chapter 4.3 Worked Example\n \n- Binary NB: For each doc, remove all duplicate words before you concatenate them into\nsingle document\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \n- NB can be viewed as a set of class-specific unigram language models\n- Model for each class instantiates unigram language model\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n \n- Accuracy not a good metric when you want to discover something rare (spam emails\nare rare) or when class is imbalanced \n- Precision: measures percentage of items that were predicted positive that are\nactually positive\n- Recall: measures percentage of positive items in the input that were correctly \nidentified by the system as positive \n- Precision and recall emphasize true positives i.e. finding what we are supposed\nto be looking for\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n 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 \n- Representational harms: harms caused by a system that demeans a social group\n\n\n## Module 12 Lecture Notes\n Your summary here \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 = \"\"\"\n",
        "- Generative model has goal of understanding the classes (i.e. what dogs vs. cats\n",
        "look like). The model can generate (i.e. draw a dog)\n",
        "- At test time, it asks which model better fits the image\n",
        "- Discriminative model is only trying to learn to distinguish the classes (i.e.\n",
        "maybe all dogs in training data wearing collars, and cats are not)\n",
        "\n",
        "NB is generative:\n",
        "\n",
        "$\\\\hat{c} = {\\\\argmax}_c P(d|c)P(c)$\n",
        "\n",
        "- Generative model: likelihood term $P(d|c)$ expresses how to generate \n",
        "the features of a document if we knew it was of class $c$\n",
        "- Discriminative model (i.e. logistic regression) attempts to directly compute $P(c|d)$\n",
        "\n",
        "Sigmoid: \n",
        "\n",
        "$\\\\frac{1}{1+exp(-z)}$\n",
        "\n",
        "- Linear around $0$ but flattens toward the ends\n",
        "- Tends to squash outlier values toward $0$ or $1$\n",
        "- Differentiable\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_2 = \"\"\" \n",
        "- Feature interactions (combination features) need to be designed by hand\n",
        "- Large number of features can be created via feature templates: abstract\n",
        "specifications of features\n",
        "- Representation learning is a way to learn features automatically (unsupervised\n",
        "from input)\n",
        "\n",
        "Logistic regression vs. NB:\n",
        "- NB has overly strong conditional independence assumption. Can overestimate evidence\n",
        "- LR more robust to correlated features (more accurate when there are many\n",
        "correlated features)\n",
        "- LR works better on larger documents/datasets\n",
        "- NB can work well on very small datasets/short documents\n",
        "- NB easy to implement and fast to train (no optimization step)\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_3 = \"\"\" \n",
        "- Loss/cost function: the distance between system output and gold output \n",
        "- Optimization algorithm: iteratively updates the weights to minimize loss function\n",
        "\n",
        "Conditional MLE: \n",
        "- Loss function that prefers correct class labels of the training\n",
        "samples to be more likely\n",
        "- Choose parameters to maximize the log probability of the true $y$ labels in the\n",
        "training data\n",
        "- Result is \"cross-entropy loss\": negative log likelihood loss\n",
        "\n",
        "Cross-entropy loss:\n",
        "- We want to learn weights that maximize the probability of the correct label $p(y|x)$\n",
        "\n",
        "$p(y|x) = \\\\hat{y}^y * (1-\\\\hat{y})^{1-y}$\n",
        "\n",
        "- If $y=1$ then $p(y|x) = \\\\hat{y}$\n",
        "- If $y=0$ then $p(y|x) = 1-\\\\hat{y}$\n",
        "\n",
        "Log-likelihood of $p(y|x)$:\n",
        "\n",
        "- Want to maximize: $\\log(p(y|x)) = y\\log \\\\hat{y} + (1-y)\\\\log (1-\\\\hat{y})$\n",
        "- To get loss function, flip the sign:\n",
        "\n",
        "Cross entropy: \n",
        "\n",
        "$Loss(\\\\hat{y}, y) = - [ y\\log \\\\hat{y} + (1-y)\\\\log (1-\\\\hat{y}) ]$\n",
        "\n",
        "- Goes from $0$ (no loss) to infinity\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_4 = \"\"\" \n",
        "- Loss function is parametrized by $\\\\theta$ weights\n",
        "- The goal is to find weights that minimize loss function, averaged over all examples\n",
        "\n",
        "$\\\\hat{\\\\theta} = {\\\\argmin}_\\\\theta \\\\frac{1}{m} \\sum_i Loss(\\\\hat{y}_i, y_i)$\n",
        "\n",
        "- Gradient descent: method for finding the minimum by figuring out which direction\n",
        "(in the space of $\\\\theta)$ the slope is rising most steeply, and moving in the\n",
        "opposite direction\n",
        "- LR loss function is convex (function has just one minimum)\n",
        "- The gradient of a function with multiple variables is a vector that points in the\n",
        "direction of the greatest increase in a function\n",
        "- Learning rate $\\\\eta$: weighted magnitude of the amount to move in gradient descent \n",
        "\n",
        "$\\\\nabla_\\\\theta L(\\\\hat{y}, y) = [\\\\frac{\\\\partial}{\\\\partial w_1}L(\\\\hat{y}, y), \\\\frac{\\\\partial}{\\\\partial w_2}L(\\\\hat{y}, y), ..., \\\\frac{\\\\partial}{\\\\partial w_n}L(\\\\hat{y}, y)]$\n",
        "\n",
        "Final equation for updating $\\\\theta$ based on the gradient:\n",
        "\n",
        "$\\\\theta_{t+1} = \\\\theta_t - \\\\eta \\\\nabla L(\\\\hat{y}, y)$\n",
        "\n",
        "Gradient (of the loss) for logistic regression: $x_j [\\\\sigma(wx+b)-y]$\n",
        "\n",
        "SGD:\n",
        "- SGD is online algorithm: minimizes loss function by computing gradient after each\n",
        "training example\n",
        "- Chooses single random example at a time, update the weights to improve performance\n",
        "on single example\n",
        "- Batch training: compute gradient for the entire dataset\n",
        "- Mini batch: train on a group of $m$ examples $<$ whole dataset\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_5 = \"\"\" \n",
        "- Use regularization $R(\\\\theta)$ to avoid overfitting\n",
        "\n",
        "L2 regularization uses the square of the L2 norm:\n",
        "\n",
        "$R(\\\\theta) = ||\\\\theta||_{2}^{2} = \\\\sum_j \\\\theta_{j}^2$\n",
        "\n",
        "- L2 prefers weight weight vectors with small weights\n",
        "\n",
        "L1 regularization uses the L1 norm, the sum of absolute values of the weights:\n",
        "\n",
        "$R(\\\\theta) = ||\\\\theta||_{1} = \\\\sum_j |\\\\theta_{j}|$\n",
        "\n",
        "- L1 prefers sparse solutions with some larger weights, but many more weights$=0$\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_6 = \"\"\" \n",
        "- Multinomial LR uses generalization of the sigmoid, called the softmax to compute\n",
        "$p(y=c|x)$\n",
        "\n",
        "softmax$(z_i) = \\\\frac{\\\\exp(z_i)}{\\\\sum_j \\\\exp(z_j)}$ for $1 \\leq i \\leq k$\n",
        "\n",
        "- Input for the softmax is a dot product between weight vector $w$ and input vector\n",
        "$x$ and bias. Need separate weight vectors for each of the $k$ classes\n",
        "\n",
        "$p(y=c|x) = \\\\frac{\\\\exp(w_{c}x+b_c)}{\\\\sum_j \\\\exp(w_{j}x+b_j)}\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" \n",
        "Language modeling: assigning probabilities to word sequences and predicting upcoming words\n",
        "\n",
        "tanh function\n",
        "- From $-1$ to $+1$ is usually better than sigmoid function\n",
        "- Smoothly differentiable\n",
        "- Maps outlier values toward the mean\n",
        "\n",
        "$y = \\\\frac{e^z - e^{-z}}{e^z + e^{-z}}\n",
        "\n",
        "ReLU: \n",
        "- Very close to being linear\n",
        "- No problems with vanishing gradient (compared to tanh and sigmoid which have this problem)\n",
        "\n",
        "$y = max(x,0)$\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_2 = \"\"\" \n",
        "- Problem: single neural unit cannot compute certain very simple functions of its input\n",
        "- Possible for perceptron to compute logical AND and logical OR functions of its binary inputs\n",
        "- However, perceptron cannot compute logical XOR (perceptrons are purely linear)\n",
        "- Perceptron is a linear classifier: $w_1 x_1 + w_2 x_2 + b = 0$ is the equation of a line\n",
        "- The line is a decision boundary in 2-d space \n",
        "- Simply no way to draw a linear that separates positive and negative cases of XOR\n",
        "(XOR is not a linearly separable function)\n",
        "\n",
        "Solution for XOR:\n",
        "- XOR can be calculated by a layered network of units \n",
        "- Hidden layer forms a representation for the input that makes it easy to linearly\n",
        "separate positive from negative\n",
        "- This means NN can automatically learn useful representations of the input\n",
        "\n",
        "Non-linearity needed:\n",
        "- Network with only simple linear units cannot solve XOR\n",
        "- Network formed by many layers of purely linear units can always be reduced\n",
        "(computationally identical) to a single layer of linear units with appropriate weights\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_3 = \"\"\" \n",
        "FFN: \n",
        "- Multilayer network where units are connected with no cycles\n",
        "- Outputs from units in each layer are passed to units in the next layer\n",
        "- No outputs passed back to previous layer\n",
        "- Weight matrix $W_{ji}$ represents weight of the connection from $i$th input $x_i$\n",
        "to the $j$th hidden unit $h_j$\n",
        "\n",
        "Output of hidden layer $h = act(Wx+b)$\n",
        "- The result for $h$ forms a representation of the input\n",
        "- Role of output layer is to take new representation $h$ and compute a final output\n",
        "- NN with one hidden layer: can think of NN as running standard LR on the features that the network developed\n",
        "in $h$\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_4 = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_5 = \"\"\" \n",
        " \"\"\"\n",
        "\n",
        "slp_chapter7_6 = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_7 = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 144,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "35df5831-c8ea-43fc-ce0f-62a6aa7c8056"
      },
      "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": 145,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n- Generative model has goal of understanding the classes (i.e. what dogs vs. cats\nlook like). The model can generate (i.e. draw a dog)\n- At test time, it asks which model better fits the image\n- Discriminative model is only trying to learn to distinguish the classes (i.e.\nmaybe all dogs in training data wearing collars, and cats are not)\n\nNB is generative:\n\n$\\hat{c} = {\\argmax}_c P(d|c)P(c)$\n\n- Generative model: likelihood term $P(d|c)$ expresses how to generate \nthe features of a document if we knew it was of class $c$\n- Discriminative model (i.e. logistic regression) attempts to directly compute $P(c|d)$\n\nSigmoid: \n\n$\\frac{1}{1+exp(-z)}$\n\n- Linear around $0$ but flattens toward the ends\n- Tends to squash outlier values toward $0$ or $1$\n- Differentiable\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \n- Feature interactions (combination features) need to be designed by hand\n- Large number of features can be created via feature templates: abstract\nspecifications of features\n- Representation learning is a way to learn features automatically (unsupervised\nfrom input)\n\nLogistic regression vs. NB:\n- NB has overly strong conditional independence assumption. Can overestimate evidence\n- LR more robust to correlated features (more accurate when there are many\ncorrelated features)\n- LR works better on larger documents/datasets\n- NB can work well on very small datasets/short documents\n- NB easy to implement and fast to train (no optimization step)\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n \n- Loss/cost function: the distance between system output and gold output \n- Optimization algorithm: iteratively updates the weights to minimize loss function\n\nConditional MLE: \n- Loss function that prefers correct class labels of the training\nsamples to be more likely\n- Choose parameters to maximize the log probability of the true $y$ labels in the\ntraining data\n- Result is \"cross-entropy loss\": negative log likelihood loss\n\nCross-entropy loss:\n- We want to learn weights that maximize the probability of the correct label $p(y|x)$\n\n$p(y|x) = \\hat{y}^y * (1-\\hat{y})^{1-y}$\n\n- If $y=1$ then $p(y|x) = \\hat{y}$\n- If $y=0$ then $p(y|x) = 1-\\hat{y}$\n\nLog-likelihood of $p(y|x)$:\n\n- Want to maximize: $\\log(p(y|x)) = y\\log \\hat{y} + (1-y)\\log (1-\\hat{y})$\n- To get loss function, flip the sign:\n\nCross entropy: \n\n$Loss(\\hat{y}, y) = - [ y\\log \\hat{y} + (1-y)\\log (1-\\hat{y}) ]$\n\n- Goes from $0$ (no loss) to infinity\n\n\n## SLP Chapter 5.4 Gradient Descent\n \n- Loss function is parametrized by $\\theta$ weights\n- The goal is to find weights that minimize loss function, averaged over all examples\n\n$\\hat{\\theta} = {\\argmin}_\\theta \\frac{1}{m} \\sum_i Loss(\\hat{y}_i, y_i)$\n\n- Gradient descent: method for finding the minimum by figuring out which direction\n(in the space of $\\theta)$ the slope is rising most steeply, and moving in the\nopposite direction\n- LR loss function is convex (function has just one minimum)\n- The gradient of a function with multiple variables is a vector that points in the\ndirection of the greatest increase in a function\n- Learning rate $\\eta$: weighted magnitude of the amount to move in gradient descent \n\n$\\nabla_\\theta L(\\hat{y}, y) = [\\frac{\\partial}{\\partial w_1}L(\\hat{y}, y), \\frac{\\partial}{\\partial w_2}L(\\hat{y}, y), ..., \\frac{\\partial}{\\partial w_n}L(\\hat{y}, y)]$\n\nFinal equation for updating $\\theta$ based on the gradient:\n\n$\\theta_{t+1} = \\theta_t - \\eta \\nabla L(\\hat{y}, y)$\n\nGradient (of the loss) for logistic regression: $x_j [\\sigma(wx+b)-y]$\n\nSGD:\n- SGD is online algorithm: minimizes loss function by computing gradient after each\ntraining example\n- Chooses single random example at a time, update the weights to improve performance\non single example\n- Batch training: compute gradient for the entire dataset\n- Mini batch: train on a group of $m$ examples $<$ whole dataset\n\n\n## SLP Chapter 5.5 Regularization\n \n- Use regularization $R(\\theta)$ to avoid overfitting\n\nL2 regularization uses the square of the L2 norm:\n\n$R(\\theta) = ||\\theta||_{2}^{2} = \\sum_j \\theta_{j}^2$\n\n- L2 prefers weight weight vectors with small weights\n\nL1 regularization uses the L1 norm, the sum of absolute values of the weights:\n\n$R(\\theta) = ||\\theta||_{1} = \\sum_j |\\theta_{j}|$\n\n- L1 prefers sparse solutions with some larger weights, but many more weights$=0$\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n \n- Multinomial LR uses generalization of the sigmoid, called the softmax to compute\n$p(y=c|x)$\n\nsoftmax$(z_i) = \\frac{\\exp(z_i)}{\\sum_j \\exp(z_j)}$ for $1 \\leq i \\leq k$\n\n- Input for the softmax is a dot product between weight vector $w$ and input vector\n$x$ and bias. Need separate weight vectors for each of the $k$ classes\n\n$p(y=c|x) = \\frac{\\exp(w_{c}x+b_c)}{\\sum_j \\exp(w_{j}x+b_j)}\n\n\n## SLP Chapter 7.1 Units\n \nLanguage modeling: assigning probabilities to word sequences and predicting upcoming words\n\ntanh function\n- From $-1$ to $+1$ is usually better than sigmoid function\n- Smoothly differentiable\n- Maps outlier values toward the mean\n\n$y = \\frac{e^z - e^{-z}}{e^z + e^{-z}}\n\nReLU: \n- Very close to being linear\n- No problems with vanishing gradient (compared to tanh and sigmoid which have this problem)\n\n$y = max(x,0)$\n\n\n## SLP Chapter 7.2 The XOR problem\n \n- Problem: single neural unit cannot compute certain very simple functions of its input\n- Possible for perceptron to compute logical AND and logical OR functions of its binary inputs\n- However, perceptron cannot compute logical XOR (perceptrons are purely linear)\n- Perceptron is a linear classifier: $w_1 x_1 + w_2 x_2 + b = 0$ is the equation of a line\n- The line is a decision boundary in 2-d space \n- Simply no way to draw a linear that separates positive and negative cases of XOR\n(XOR is not a linearly separable function)\n\nSolution for XOR:\n- XOR can be calculated by a layered network of units \n- Hidden layer forms a representation for the input that makes it easy to linearly\nseparate positive from negative\n- This means NN can automatically learn useful representations of the input\n\nNon-linearity needed:\n- Network with only simple linear units cannot solve XOR\n- Network formed by many layers of purely linear units can always be reduced\n(computationally identical) to a single layer of linear units with appropriate weights\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n \nFFN: \n- Multilayer network where units are connected with no cycles\n- Outputs from units in each layer are passed to units in the next layer\n- No outputs passed back to previous layer\n- Weight matrix $W_{ji}$ represents weight of the connection from $i$th input $x_i$\nto the $j$th hidden unit $h_j$\n\nOutput of hidden layer $h = act(Wx+b)$\n- The result for $h$ forms a representation of the input\n- Role of output layer is to take new representation $h$ and compute a final output\n- NN with one hidden layer: can think of NN as running standard LR on the features that the network developed\nin $h$\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n \n\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n \n \n\n## SLP Chapter 7.6 Training Neural Nets\n \n\n\n\n## SLP Chapter 7.7 Training the neural language model\n \n\n\n\n## Module 13 Lecture Notes\n Your summary here \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 = \"\"\"\n",
        "- RNN and transformers can deal with sequential nature of language, can handle variable\n",
        "length inputs\n",
        "- Probabilistic language models predict the next word given some preceding context\n",
        "\n",
        "Constraint by Markov assumption: prediction is based on a fixed preceding context of size $N$:\n",
        "\n",
        "$p(w_n|w_{1:n-1}) = p(w_n|w_{(n-N+1):(n-1)})$\n",
        "\n",
        "Perplexity:\n",
        "- Evaluate language models by examining how well it predicts unseen data drawn from\n",
        "the same source as the training data\n",
        "- Good models should assign higher probabilities to unseen data\n",
        "\n",
        "$PP_\\\\theta (w_{1:n}) = $\n",
        "\"\"\"\n",
        "slp_chapter9_2 = \"\"\" \n",
        "RNN:\n",
        "- RNNs are networks that contain a cycle within its network connections (i.e. value of a unit\n",
        "is dependent on its own earlier outputs as input)\n",
        "- Sequences processed by presenting one item at a time to the network\n",
        "- Hidden layer receives as input the value of the preceding hidden layer\n",
        "- Hidden layer from previous time step is a form of memory/context\n",
        "- No fixed length limit on prior context; context includes information all the way\n",
        "back to the beginning of the sequence\n",
        "\n",
        "$h_t = g(Uh_{t-1} + Wx_t)$\n",
        "\n",
        "$y_t = f(Vh_t)$\n",
        "\n",
        "Weights to update:\n",
        "- $W$ - weights from input layer to hidden layer\n",
        "- $U$ - weights from previous hidden layer to current hidden layer\n",
        "- $V$ - weights from the hidden layer to output layer\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter9_3 = \"\"\" \n",
        "Your summary here \n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" \n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_2 = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_3 = \"\"\" \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "slp_chapter6_4 = \"\"\" \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "slp_chapter6_8 = \"\"\" \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "slp_chapter6_10 = \"\"\" \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "slp_chapter6_11 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_12 = \"\"\" \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 146,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8156afaf-539d-49f1-c914-3f8a68339c68"
      },
      "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": 147,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n- RNN and transformers can deal with sequential nature of language, can handle variable\nlength inputs\n- Probabilistic language models predict the next word given some preceding context\n\nConstraint by Markov assumption: prediction is based on a fixed preceding context of size $N$:\n\n$p(w_n|w_{1:n-1}) = p(w_n|w_{(n-N+1):(n-1)})$\n\nPerplexity:\n- Evaluate language models by examining how well it predicts unseen data drawn from\nthe same source as the training data\n- Good models should assign higher probabilities to unseen data\n\n$PP_\\theta (w_{1:n}) = $\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n \nRNN:\n- RNNs are networks that contain a cycle within its network connections (i.e. value of a unit\nis dependent on its own earlier outputs as input)\n- Sequences processed by presenting one item at a time to the network\n- Hidden layer receives as input the value of the preceding hidden layer\n- Hidden layer from previous time step is a form of memory/context\n- No fixed length limit on prior context; context includes information all the way\nback to the beginning of the sequence\n\n$h_t = g(Uh_{t-1} + Wx_t)$\n\n$y_t = f(Vh_t)$\n\nWeights to update:\n- $W$ - weights from input layer to hidden layer\n- $U$ - weights from previous hidden layer to current hidden layer\n- $V$ - weights from the hidden layer to output layer\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n \nYour summary here \n\n\n## SLP Chapter 6.1 Lexical Semantics\n \n\n \n\n## SLP Chapter 6.2 Vector Semantics\n \n\n\n\n## SLP Chapter 6.3 Words and Vectors\n \n\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n \n\n \n\n## SLP Chapter 6.8 Word2vec\n \n\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \n\n \n\n## SLP Chapter 6.11 Bias and Embeddings\n\n\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n \n\n \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "7a1571d1-0fae-42f7-e645-d46e91dda5a8"
      },
      "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": 148,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Decision theoretic agent can make rational decisions even when faced with uncertainty and conflicting goals (logical agents may not have a way to decide)\n- They assign a continuous range of values to states, which allow them to choose a better state even when the best state is unavailable\n- $P(s'|s, a)$ probability that performing action $a$ in state $s$ reaches state $s'$\n- Decision theoretic agent: agent that makes rational decisions based on what it believes and what it wants\n- Decision theory: choosing among actions based on the desirability of their immediate outcomes (environment is assumed episodic)\n- Agent preferences cptured by utility function $U(s)$: assigns a single number to express how desirable state $s$ is\n- Expected utility of an action is the average utility value of the outcomes , weighed by the probability of the outcome\n- MEU principle: rational agent should choose action that maximizes agent's expected utility (intelligent behavior)\n- Decision theory provides mathematical framework but does not solve the AI problem since agent still needs to estimate $P(s)$ over possible states of the world, \nwhich requires perception, learning, knowledge representation, and inference \n- Performance measure gives a score for history (sequence of states)\n- Utility function applies to the very next state (can be used to guide actions step by step)\n\nFlashcard: \n- MEU doesn't solve the AI problem because MEU formalizes what the agent should do but not how to do it\n- To use MEU, you need to estimate the probability distribution and a utility function that reflects the performance measure\n  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \n- Describe the agent's preferences: $(A > B), (A \\sim B), (A >= B)$\n- Lottery: set of outcomes for each action $L = [p_1, S_1; ... ; p_n, S_n]$\n- Each outcome $S_i$ can be atomic state or another lottery \n\nAxioms of utility (notice they are actually \"axioms about preferences\"):\n- Agent that violates axiom of utility will show irrational behavior in some situations\n\n1.) Orderability: Given two lotteries, rational agent must either prefer one or equally prefer both.\nExactly one of $(A > B), (A \\sim B), (A >= B)$ holds.\n\n2.) Transitivity: Given any three lotteries, $(A > B)$ and $(B > C) \\implies (A > C)$\n\n3.) Continuity: If some lottery B is between A and C in preference, then there is some $p$ for which\nrational agent is indifferent between getting B for sure and the lottery with A and C with probability $p$ and $1-p$ respectively\n\n$ A > B > C \\implies \\exists p$ such that $[p, A; 1-p, C] \\sim B$ \n\n4.) Substitutability: If agent is indifferent between A and B, then agent is indifferent\nbetween two more complex lotteries that are the same except B is substituted for A in one of them\n\n$ A \\sim B \\implies [p, A; 1-p, C] \\sim [p, B; 1-p, C]$\n\n$ A > B \\implies [p, A; 1-p, C] > [p, B; 1-p, C]$\n\n5.) Monotonicity: If agent prefers A to B then agent must prefer lottery with higher probability for A\n\n6.) Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability. It compresses\ntwo consecutive lotteries into single equivalent lottery \n\nYou can derive the following from axioms of utility:\n- Existence of utility function: If agent obeys axioms of utility, then there exists a function $U$ such that \n$U(A) > U(B)$ iff $A > B$ and $U(A) = U(B)$ iff $A \\sim B$\n\n- Expected utility of lottery: utility of lottery is the sum of the probability of each outcome times utility of that outcome\n$ U(L) = \\sum_{i} p_i * U(S_i)$\n\n- Once probabilities and utilities of possible outcome states are specified, utility of a compound lottery involving those states\nis completely determined\n- Outcome of a nondeterministic action is a lottery \n- Agent can act rationally (consistent with its preferences) by choosing an action that maximizes expected utility\n- Utility function exists for any rational agent \n- Deterministic environment only needs preference ranking on states (the numbers don't matter)\n- Existentence of utility function does not necessarily mean the agent is explicitly maximizing that utility function\n- By observing rational agent's behavior, you can learn about the utility function that represents\nwhat the agent is actually trying to achieve \n\n\n## AIMA Chapter 16.3 Utility Functions\n\nUtility functions: \n\n- Utility functions map from lotteries to real numbers and they must obey axioms of utility \n- Agent is still allowed to have preferences that may seem unusual \n- Preference elicitation: present choices to someone and use observations to determine\nunderlying utility function. This is a way to work out what someone's utility function is.\n- Fix utility of \"best prize\" at $U(S) = u_{\\top}$ (finite) normalized to $u_{\\top} = 1$\n- Fix utility of \"worst catastrophe\" at $U(S) = u_{\\bot}$ (finite) normalized to $u_{\\bot} = 0$\n- Micromort: 1/1,000,000 chance of death\n- QALY: quality adjusted life year. People are willing to accept short life to avoid disability\n\nUtility of money: \n- Monotonic preference for more money (prefer more to less, all else being equal)\n- Money does not behave as a utility function, because it says nothing about preferences\nbetween lotteries involving money\n- Utility is not disrectly proportional to monetary value because of diminishing returns \n- Grayson study showed that utility of money almost proportional to the logarithm of the amount\n- Utility of money is S-shaped. Positive region is \"risk averse\"; negative region is \"risk seeking\"\n- Certainty equivalent: value an agent will accept in lieu of lottery \n- Insurance premium: difference between EMV and certainty equivalent \n- Agent with linear curve is \"risk neutral\"\n\nExpected utility:\n- Rational way to choose best action is to maximize expected utility\n- In reality, model is a oversimplification, you are really working with estimated of the true\nexpected utility (we assume this estimate is unbiased)\n- Optimizer's curse: tendency for the estimated expected utility of the best choice\nto be too high (taking utility estimates at face value is a bad idea)\n- Solution: Bayesian approach that uses explicit probability model of the error in the utility\nestimates. Treat utility estimate as evidence and compute posterior distribution for the true \nutility using Bayes' rule.\n\nHuman judgement/irrationality:\n- Normative theory: describes how a rational agent should act\n- Descriptive theory: describes how actual agents really act\n- Certainty effect can be used to explain some irrational preferences (people attracted\nto gains that are certain)\n- Ambiguity aversion: people prefer to elect the known probability rather than the unknown\nunknowns\n- Framing effect: exact wording of a decision problem can have a big impact on agent's choice\n- Anchoring effect: people prefer to make relative utility judgements rather than absolute\nones (200 wine vs. 55 wine)\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nSequential decision problems:\n- Transition model: describes the outcome of each action in each state\n- Outcome is stochastic \n$P(s'|s,a) = T(s, a, s')$ is probability of reaching state $s'$ if action $a$\nis done in state $s$\n- Markovian: probability of reaching next state from current state depends only on the\ncurrent state and not on the history of earlier states\n- Decision problem is sequential, so the utility function for the agent will depend on a sequence\nof states and actions (environment history)\n\nMDP\n- Sequential decision problem for fully observable, stochastic environment with Markovian\ntransition model and additive rewards\n- Consists of set of states, set of actions, transition model, reward function\n- Methods for solving MDPs involve dynamic programming\n- Solution for MDP could be a policy: solution that specifies what the agent should do\nfor any state that the agent might reach\n$\\pi(s)$ is the action recommended by policy $\\pi$ for state $s$\n- Quality of a policy is measured by the expected utility of the possible environment histories\ngenerated by that policy\n- Optimal policy $\\pi^{*}$ is one that yields the highest expected utility\n\nOptimal policies:\n- Utility of a history is the sum of discounted rewards\n- Can compare policies by cmoparing expected utilities obtained when executing them\n- The probability distribution over state sequences is determined by initial state, policy, \nand the transition model for the environment\n- $U^{\\pi}(s)$ is the expected utility obtained by executing $\\pi$ starting in $s$\n- Optimal policy is independent of the starting state when using discounted utilities with \ninfinite horizons (BUT this does not hold for finite horizon policies or other ways\nof combining rewards over time, e.g. taking the max)\n- $U^{\\pi^{*}}(s)$ is the true utility of a state: expected sum of discounted rewards if\nagent executes optimal policy \n- $U(s)$ the utility of a state is the expected reward for the next transition plus the discounted\nutility of the next state, assuming the agent chooses the optimal action. \n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \nAlgorithms for MDP:\n- Generate exact solutions: value iteration, policy iteration, linear programming\n- Approximate algorithms: Monte Carlo planning\n\nValue iteration: \n\n$V_{k+1}(s) \\leftarrow \\max_a \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n\n- $n$ possible states $\\rightarrow n$ Bellman equations\n- $n$ equations (nonlinear) contain $n$ unknowns (utilities of the states)\n- Goal: Solve the equations to find the utilities\n- Iterative approach: update the utility of each state from the utilities of its neighbors\n- After convergence, final utility values are solutions to the Bellman equations \n- Solutions are unique and the corresponding policy is optimal\n- Value iteration is propagating information through the state space by means of local updates\n- Time $O(AS^2)$ for each iteration\n\nPolicy iteration: \n- Alternates between policy evaluation and policy improvement\n\nEvaluation: $V_{k+1}^{\\pi_i}(s) \\leftarrow T(s, \\pi_i(s), s') [R(s, \\pi_i(s), s') + \\gamma V_{k+1}^{\\pi_i}(s')]$\n\nImprovement: $\\pi_{i+1}(s) = {\\argmax}_a \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V^{\\pi_i}(s')]$\n\n- Policy evaluation: Given policy $\\pi_i$ calculate $U_i = U^{\\pi_i}$ the utility of each \nstate if $\\pi_i$ were to be executed\n- Policy improvement: Calculate new MEU policy $\\pi_{i+1}$ using one-step look ahead based\non $U_i$\n- Convergence happens when policy improvement yields no change in the utilities\n- At this point $U_i$ is a solution to the Bellman equation, and $\\pi_i$ is\nan optimal policy \n- Action in each state is fixed by the policy, so the simplified Bellman equations (do what\nthe policy says) are linear because the $max$ operator is removed\n- $n$ states, $n$ linear equations, $n$ unknowns can be solved in $O(n^3)$ time\n\nOnline algorithms for MDPs:\n- Value iteration and policy iteration are offline algorithms: generate optimal solution\nfor the problem, which can then be executed by simple agent \n- Online algorithms: agent does significant amount of computation at each decision point\nrather than operating with precomputed information  \n\nPolicy evaluation:\n- Use Bellman equation with action $a$ fixed by $\\pi$. We can solve system of $n$\nvariables and $n$ equations in $O(n^3)$ time\n- $O(S^2)$ per iteration according to slides\n\nFlashcards:\n- Asynchronous policy iteration  updates only a subset of states. \n- This can be useful because you can design heuristics about what states to update, and can reduce the time it takes to run policy iteration.\n\nModified policy iteration (adapative DP version):\n- Policy iteration where the value iteration step updates using the learned transition probabilities and reward. \n- This lets us update the utilities concurrently with the transition and reward rather than solving them after all trials.\n\n\n## Module 8 Lecture Notes\n\n```\nfunction VALUE-ITERATION(mdp, ε) returns a utility function\n inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a),\n      rewards R(s,a,s′), discount γ\n   ε, the maximum error allowed in the utility of any state\n local variables: U, U′, vectors of utilities for states in S, initially zero\n        δ, the maximum change in the utility of any state in an iteration\n\n repeat\n   U ← U′; δ ← 0\n   for each state s in S do\n     U′[s] ← max_a ∈ A(s) Q-VALUE(mdp,s,a,U)\n     if | U′[s] − U[s] | > δ then δ ← | U′[s] − U[s] |\n until δ < ε(1 − γ)/γ\n return U\n```\n===============================================================================\n```\nfunction POLICY-ITERATION(mdp) returns a policy\n inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a)\n local variables: U, a vector of utilities for states in S, initially zero\n        π, a policy vector indexed by state, initially random\n\n repeat\n   U ← POLICY-EVALUATION(π, U, mdp)\n   unchanged? ← true\n   for each state s in S do\n     a * ← argmax_a ∈ A(s) Q-VALUE(mdp,s,a,U)\n     if Q-VALUE(mdp,s,a*,U) > Q-VALUE(mdp,s,π[s],U) then do\n       π[s] ← a* ; unchanged? ← false\n until unchanged?\n return π\n```\n\n===============================================================================\n\nMDP is:\n- Sequential decision problem\n- For fully observable environment\n- With stochastic transition model\n- That has additive rewards\n\nReward scales:\n- Scale of utilities is arbitrary (affine transformation leaves optimal decision unchanged)\n- Similarly so for the optimal policy in an MDP\n\nRepresenting MDPs:\n- Represent $P(s'|s, a)$ and $R(s,a,s')$ with 3 dimensional table of size $S^2 * A$\n- Usually tables are sparse, of size $O(SA)$\n\nUtilities over time:\n- With finite horizon, optimal action in a given state may depend on how much time is left\n- Nonstationary: policy that depends on time \n- infinite horizon, optimal action depends only on the current state\n- Stationary: policy does not depend on time \n- There can be finite state sequences in infinite-horizon MDP that contains a terminal state\n\nCalculate utility of state sequences:\n- Additive discounted rewards: $R(s_0, a_0, s_1) + \\gamma R(s_1, a_1, s_2) + ... $\n- Discount factor $\\gamma$ describes the preference of an agent for current rewards over future rewards\n- $\\gamma$ close to 0 means rewards in the distant future are viewed as insignificant \n(agent focused on short term)\n- $\\gamma$ close to 1 means agent is more willing to wait for long-term rewards \n- $\\gamma = 1$ is special case of purely additive rewards \n- Agent's preferences between state sequences are stationary: if you prefer one future\nto another starting tomorrow, then you should still prefer that future if it were to start\ntoday instead\n- With discounted rewards and $\\gamma < 1$, utility of infinite sequence is finite\n- Proper policy: guaranteed to reach a terminal state (we are able to use $\\gamma = 1$ with proper\npolicies)\n- Improper policies (agent never reaching terminal state because $\\gamma > 0$) is good reason\nfor using discounted rewards\n\nQ-function:\n- $Q(s,a)$ is the action-utility function: expected utility of taking a given action\nin a given state\n- Optimal policy can be extracted from Q-function by $\\pi^{*}(s) = {\\argmax}_{a} Q(s,a)$\n- Bellman equation for Q-function: expected total reward for taking action is its immediate reward\nplus the discounted utility of the outcome state\n- Solving the Bellman equations for $U$ or $Q$ gives us what we need to find an optimal policy\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Decision theoretic agent** - agent that makes rational decisions based on what it believes and what it wants\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \nN-Armed Bandit:\n- Exploitation: of the current best action to obtain rewards\n- Exploration of previously unknown states and actions to gain information, which\ncan be converted into a better policy and better long-term rewards\n\nBandit problems:\n- Each arm $M_i$ is a Markov reward process (MRP): MDP with only one possible action $a_i$\n- Each arm has states, transition model, reward\n- The arm defines a distribution over sequences of rewards $R_{i,0}, R_{i,1}, ..., $\nwhere eah reward $R_{i,t}$ is a random variable\n- Overall bandit problem is MDP\n- Pull the arm with highest Gittins index and then update the Gittins indices. This produces\noptimal policy for bandit problem \n- Bernoulli bandit: each arm $M_i$ produces a reward of 0 or 1 with fixed but unknown probability \n\nApproximately optimal bandit policies:\n- Calculating Gittin indices is not always possible for realistic problems\n- Upper confidence bound: heuristic that use the samples from each arm to establish\nconfidence interval for the value of the arm\n- UCB value is not strictly an index because it depends on $N$, the total number of \nsamples drawn across all arms\n- Thompson sampling: chooses an arm randomly according to the probability that the arm is\nin fact optimal, given the samples so far\n- Bandit superprocess (BSP): generalization of the bandit process. Each arm is a MDP \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n \nSparse rewards (chess and racing): vast majority of states the agent is given no informative\nreward signal  \n\nModel-based RL:\n- Agent uses transition model of the environment to help interpret the reward signals and to\nmake decisions about how to act.\n- Model maybe known or unknown\n\nModel-free RL:\n- Agent does not know and does not learn a transition model for the environment\n- It learns a direct representation of how to behave: 1.) Action utility and 2.) Policy search\n\nAction utility learning: \n- Most common form is Q-learning, where agent learns Q-function\n$Q(s,a)$ denoting the sum of rewards from state $s$ onward if action $a$ is taken \n- Given Q-function, agent can choose what to do in $s$ by finding the action with the\nhighest Q-value \n\nPolicy search: \n- Agent learns a policy that maps from states to actions\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nPassive RL:\n- Agent's policy is fixed and the task is to learn the utilities of states (or state-action pairs)\n- Agent trying to learn $U^{\\pi}(s)$ the expected total discounted reward if policy $\\pi$\nis executed beginning in state $s$\n- Agent does not know $P(s'|s,a)$ and $R(s,a,s')$\n\nAdaptive DP:\n- Agent learns the transition model that connects states and solves the corresponding\nMDP using DP\n- Plug the learned transition model $P(s'|s,\\pi(s))$ and observed rewards $R(s, \\pi(s),s')$ to\ncalculate utilities of states\n- The Bellman equations are linear when the policy is fixed\n\nTemporal difference learning:\n- Use the observed transitions to adjust the utilities of observed states so that they \nagree with the constraint equations\n- When transition occurs from state $s$ to state $s'$ via action $\\pi(s)$, apply\nupdate to $U^{\\pi}(s)$ (formula in cheat sheet)\n\n$U^{\\pi}(s) \\leftarrow U^{\\pi}(s) + \\alpha TD term$\n\n- The update rule uses the difference in utilities between successive states/times\n- $TD term$  is an error signal, and the update is intended to reduce the error\n\nDifference between ADP and TD:\n- TD adjusts a state to agree with its observed successor\n- ADP adjusts the state to agree with all successors that might occur, weighted by their\nprobabilities\n- TD makes single adjustment per observed transition\n- ADP makes as many needed to restore consistency between utility estimates $U$ and \ntransition model $P$\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nActive RL:\n- Agent gets to decide which actions to take\n- Agent needs to learn a complete transition model with outcome probabilities for all actions\n- Needs to learn utilities defined by the optimal policy, which obey Bellman equations\n- Needs to obtain utility function $U$ that is optimal for learned model\n- With $U$, the agent can extract optimal action or use optimal policy \n\nGreedy Agent:\n- Greedily takes the action that it currently believes to be optimal at each step\n- Learned model is not the same as the true environment. What is optimal in the learned model\ncan be suboptimal in the true environment.\n\nGLIE:\n- Greedy in the limit of infinite exploration\n- GLIE scheme must try each action in each state an unbounded number of times to avoid\nhaving a finite probability that an optimal action is missed\n- Will eventually learn the true transition model and can then use exploitation\n\nTD-difference Q-learning:\n- Q-learning avoids needs for a transition model by learning $Q(s,a)$ instead of $U(s)$\n- $Q(s,a)$ is the exoected total discounted reward if the agent takes action $a$ in state\n$s$ and acts optimally thereafter\n- Knowing Q-function allows agent to act optimally by simplying choosing ${\\argmax}_a Q(s,a)$\n- TD update is calculated whenever acction $a$ is executed in state $s$ leading to state $s'$\n- The TD term represents an error that the update is trying to minimize \n- Important: TD Q-learning agent does not need transition model $P(s'|s,a)$ for learning or\nfor action selection\n- Q-learning is off policy\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n- Evaluation function: compact measure of desirability for potentially vast state spaces\n- In RL, evaluation function is an approximate utility function\n- Function approximation is the process of constructing a compact approximation of \nthe true utility function or Q-function\n- Function approximation allows inductive generalization\n- We can approximate utility function using a weighted linear combination of features:\n\n$\\hat{U}_{\\theta}(s) = \\theta_1 f_1(s) + ... + \\theta_n f_n(s)$\n\nApproximate direct utility:\n- For RL, makes more sense to use online learning algorithm that updates parameters\nafter each trial\n- Update parameters $\\theta$ by computing gradient (the usual way)\n- Changing the parameters $\\theta_i$ in response to one observed transition\nbetween two states also changes the values of $\\hat{U}_{\\theta}$ for every other\nstate (this is what we mean by generalization)\n\nApproximate TD:\n- Adjust the parameters to reduce the temporal difference between successive states\n- Experience replay: retain trajectories from entire learning process to ensure\nits value function is still accurate for parts of the state space that is no\nlonger visited \n- Learning a model for an observable environment is a supervised learning problem\nbecause the next percept gives the outcome state (label)\n- In partially observable environments, the next percept is no longer a label\nfor the state prediction problem\n\nHierarchical RL:\n- Break long action sequences into smaller pieces, until action sequences\nare short enough to make learning easy\n\n\n## Module 9 Lecture Notes\n \n```\nfunction Q-Learning_Agent(percept) returns an action\n inputs: percept, a percept indicating the current state s' and reward signal r'\n persistent: Q, a table of action values indexed by state and action, initially zero\n       Nsa, a table of frequencies for state-action pairs, initially zero\n       s, a, r, the previous state, action, and reward, initially null\n\n if Terminal?(s) then Q[s, None] ← r'\n if s is not null then\n   increment Nsa[s, a]\n   Q[s, a] ← Q[s, a] + α(Nsa[s, a])(r + γ maxa' Q[s', a'] - Q[s, a])\n s, a, r ← s', argmaxa' f(Q[s', a'], Nsa[s', a']), r'\n return a\n```\n\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 \n- Belief state: representation of the set of all possible world states that agent\nmight be in and generating a contingency plan for all of them\n- Rational decision: depends on the relative importance of the various goals\nand the likelihood that they will be achieved\n- Probability statements are made with respect to a knowledge state, not with\nrespect to the real world e.g. \"the probability that the patient has a cavity, given\nthat he has a toothache is $0.8$\"\n\nUncertainty and rational decisions:\n- Agent must have preferences among different possible outcomes of different plans\n- Outcome: completely specified state\n- Utility of a state is relative to an agent (need to account for taste or preferences)\n\nDecision theory is the general theory of rational decisions:\n- $Decision theory = probability theory + utility theory$\n- Fundamental idea is that an agent is rational iff and only if it chooses the\naction that yields the highest expected utility, averaged over all possible outcomes\nof the actions (MEU principle)\n- A decision theoretic agent's belief state represents possibilities for the world\nstates AND their probabilities. Agent can make probabilistic predictions\nof action outcomes and can thus select the action with the highest expected utility\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n- Probabilistic assertions talk about how probable the various worlds are\n- Sample space: the set of all possible words\n- The possible worlds are mutually exclusive and exhaustive \n- $P(A)$ is called \"unconditional\" or \"prior probabilities\": they refer to degrees\nof belief in the absence of any other information\n- $ P(A|B)$ is the \"conditional\" or \"posterior\" probability \n- When making decisions, agent needs to condition on all the evidence observed\n- $P(cavity|toothache) = 0.6$ means \"whenever toothache is true, and we have no further\nevidence, conclude that cavity is true with probability $0.6$\n- Probability distribution for random variable: is an assignment of probability\nfor each possible value of the random variable\n\nSome equations:\n\n$P(A|B) = \\frac{P(A \\land B)}{P(B)}$\n\n$P(A \\land B) = P(A|B)P(B)$\n\n$P(A \\lor B) = P(A) + P(B) - P(A \\land B)$\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \nProbabilistic inference: computation of posterior probabilities for queries\ngiven observed evidence\n- The full joint distribution is the knowledge base where answers to all questions\nare derived\n- Marginalization: sum up the probabilities for each possible value of the other variables\n\n$P(Y) = \\sum_z P(Y, Z=z) = P(Y) = \\sum_Z P(Y|Z)P(Z)$\n\nNormalization:\n- Allows us to proceed when some probability assessment is not available\n- $X$ is the query \n- $E$ is the list of evidence variables, $e$ is the list of evidence variables\n- $Y$ is the remaining unobserved values\n\n$P(X|e) = \\alpha P(X, e) = \\alpha \\sum_y P(X,e,y)$\n\n$P(cavity, toothache) = \\alpha P(cavity, toothache) = \\alpha P(cavity, toothache, catch) + P(cavity, toothache, \\neg catch)$\n\nFull joint probability tables:\n- For $n$ Boolean variables, it requires input table of size $O(2^n)$ and requires $O(2^n)$ time to process\n- Full joint distribution tables is usually not practical \n\n\n## AIMA Chapter 12.4 Independence\n \nWeather and dental problems are independent:\n\n$P(D_1, D_2, D_3, W) = P(D_1, D_2, D_3)P(W)$\n\nCoin flips are independent:\n\n$P(C_1, C_2, ..., C_n) = P(C_1)P(C_2)...P(C_n)$\n\nIndependent between propositions/variables $A$ and $B$ give us:\n\n$P(A|B) = P(A)$ or\n\n$P(B|A) = P(B)$ or \n\n$P(A \\land B) = P(A)P(B)$\n\nIndependence allows full joint distributions to be factored into separate joint\ndistributions on those subsets:\n\n- $n$ independent coin flips, $P(C_1,...,C_n)$ has $2^n$ entries, but can be\nrepresented as the product of $n$ single-variable distributions $P(C_i)$\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \nBayes' Rule:\n\n$P(Y|X) = \\frac{P(X|Y)P(Y)}{P(X)}$\n\nGeneral version of Bayes' conditioned on background evidence $e$:\n\n$P(Y|X,e) = \\frac{P(X|Y,e)P(Y|e)}{P(X|e)}$\n\nBayes' rule with normalization:\n\n$P(Y|X) = \\alpha P(X|Y)P(Y)$\n\nConditional independence\n- Toothache and catch are independent, given whether or not you have a cavity\n- Each is directly caused by a cavity, but neither has a direct effect on the other\n- Toothache and catch are conditionally independent, given cavity:\n\n$P(toothache \\land catch|cavity) = P(toothache|cavity)P(catch|cavity)$\n\nGeneral definition of conditional independence of variables $X$ and $Y$ given $Z$:\n\n$P(X, Y|Z) = P(X|Z)P(Y|Z)$\n\n$P(X|Y,Z) = P(X|Z)$\n\n$P(Y|X,Z) = P(Y|Z)$\n\n- For $n$ symptons that are all conditionally independent given cavity, the table\ngrows $O(n)$ instead of $O(2^n)$\n\n1.) Causal chain: $X \\rightarrow Y \\rightarrow Z$\n\n- $X$ is NOT independent of $Z$\n\nJoint: $P(x,y,z) = P(x)P(y|x)P(z|y)$\n\n- YES: $X$ is independent of $Z$ given $Y$\n\n$P(z|x,y) = \\frac{P(x,y,z)}{P(x,y)} = \\frac{P(x)P(y|x)P(z|y)}{P(x)P(y|x)} = P(z|y)$\n\n2.) Common cause: $ X \\leftarrow Y \\rightarrow Z$\n\nJoint: $P(x,y,z) = P(y)P(x|y)P(z|y)$ \n\n- $X$ is NOT independent of $Z$\n\n- YES: $X$ is independent of $Z$ given $Y$\n\n$P(z|x,y) = \\frac{P(x,y,z)}{P(x,y)} = \\frac{P(y)P(x|y)P(z|y)}{P(y)P(x|y)} = P(z|y)$\n\n3.) Common effect: $X \\rightarrow Z \\leftarrow Y$\n\n- YES: $X$ is independent of $Y$\n\n- $X$ is NOT independent of $Y$ given $Z$\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nNaive Bayes model:\n- Single cause directly influences several effects, all effects are conditionally\nindependent given the cause\n- Uses conditional independence assumption\n- Linear in the number of observed effects\n\n$P(C, E_1,...E_n) = P(C) \\prod_i P(E_i|C)$\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n \n\n\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 \nD-Separation:\n- Q: Are $X$ and $Y$ conditionally independent given evidence variables $Z$?\n- Yes if $X$ and $Y$ are d-separated by $Z$\n- A path is active if each triple (segment) is active \n\nAlgorithm:\n- Query: Is $X_i$ independent $X_j$ given evidence variables?\n- Check all undirected paths between $X_i$ and $X_j$\n- If one or more paths are active (direction comes back in), then independence\nis not guaranteed\n- If no paths are active (all paths inactive) then independence is guaranteed\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 \n- Bayesian network is a data structure that represents dependencies among variables\n- They can essentially represent any full joint probability distribution concisely\n\nBN set up:\n- Each node corresponds to a random variable\n- If there is an edge $X \\rightarrow Y$ then $X$ is a parent of $Y$ ($X$ has\ndirect influence on $Y$)\n- DAG, so no cycles\n- Each node $X_i$ has probability information $\\theta_i (X_i | Parents(X_i))$ that\nmeasures the effect of the parents on the child using finite amount of parameters\n- The topology represents the conditional independence relationships\n- Once we have topology, we only need local probability information (conditional\ndistribution given its parents)\n- The full joint distribution for all variables is defined by topology\nand local probability information\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n- Syntax of BN: DAG with local probability information for each node\n- Semantics of BN: define how syntax corresponds to joint distribution\nover the variables of the network\n- Semantics define each entry in the joint distribution:\n\n$P(x_1,...,x_n) = \\prod_i \\theta(x_i | parents(X_i))= \\prod_i P(x_i | parents(X_i))$\n\nProperties of BN:\n- Complete and nonredundant representation of the domain\n- Local structure (sparse) system allows it to be compact because each subcomponent\ninteracts directly with a limited number of other components\n- Linear growth in complexity\n- BN can reduce size of joint distribution from $O(2^n)$ to $O(n2^k)$, where $k$ \nis some constant\n- A variable is conditionally independent of its other predecessors, given its parents\n- \"Non-descendants\" property: a variable is conditionally independent of its non-descendants,\ngiven its parents\n- A variable is conditionally independent of all other nodes in the network,\ngiven its parents, children, and children's parents (Markov blanket)\n- Markov blanket follows from the d-separation property, since a variable's Markov \nblanket d-separates it from all other variables\n\nBN with continuous variables:\n- Can handle continous variables with discretization\n- Or using one of the standard families of PDFs (i.e. Guassian distribution)\n- Nonparametric solution is to define the conditional distribution implicitly\nwith a collection of instances, each with specific values of the parent and child \nvariables\n- Hybrid BN: network with both discrete and continuous variables: needs conditional\ndistribution for both \n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n- $X$ query, $E$ evidence, $Y$ hidden variables\n- Query asks for $P(X|e)$ the posterior probability distribution of query variables\ngiven observed event \n\n$P(X|e) = \\alpha P(X, e) = \\alpha \\sum_y P(X,e,y)$\n\nInference by enumeration:\n- Query can be answered using BN by computing sums of products of conditional \nprobabilities from the network\n- Space complexity $O(n)$ and time complexity $O(2^n)$ for a network with\n$n$ Boolean variables\n- Contains wasted computations (repeated subexpressions)\n\nVariable elimination:\n- Improve enumeration algorithm by getting rid of repeated calculations (using DP):\n\nExact inference:\n- Singly connected (polytrees): at most one undirected path (ignoring directions) between \nany 2 nodes in the network \n- Time/space complexity of exact inference in polytrees is linear in the size\nof the network\n\n\n## Module 11 Lecture Notes\n Your summary here \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 \n- NB is generative classifier: build a model of how a class could generate input\ndata. \n- Log reg is a discriminative classifier: learn what features from the input\nare most useful to discriminate between different classes\n- NB is probabilistic: returns class $\\hat{c}$ that has maximum posterior probability\ngiven document\n\n$\\hat{c} = {\\argmax}_c P(c|d) = {\\argmax}_c \\frac{P(d|c)P(c)}{P(d)} = {\\argmax}_c P(d|c)P(c)$\n\n- NB is generative because we read the above equation as a implicit assumption about\nhow a document is generated \n- Class is sampled from $P(c)$ \"prior$\n- Words generated by sampling from $P(d|c)$ \"likelihood\"\n\n$\\hat{c} = {\\argmax}_c P(d|c)P(c) = {\\argmax}_c P(f_1,f_2,...,f_n|c)P(c)$\n\nNaive Bayes assumption says:\n\n$P(f_1,f_2,...,f_n|c) = P(f_1|c) * P(f_2|c) * ... * P(f_n|c)$\n\nNaive Bayes final equation:\n\n$c_{NB} = {\\argmax}_c P(C) \\prod_f P(f|c)$ \n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \n- Estimate $P(c)$ using percentage of the documents in training set that are in each\nclass $c$\n\n$\\hat{P}(c) = \\frac{N_c}{N_{doc}}$\n\n- Estimate $P(w_i|c)$ as fraction of times word $w_i$ appears in all documents\nof topic $c$\n\n$\\hat{P}(w_i|c) = \\frac{count(w_i,c)}{\\sum_w count(w,c)}$\n\nLaPlace Smoothing:\n$\\hat{P}(w_i|c) = \\frac{count(w_i,c)+1}{|V| + \\sum_w count(w,c)}$\n\n\n## SLP Chapter 4.3 Worked Example\n \n- Binary NB: For each doc, remove all duplicate words before you concatenate them into\nsingle document\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \n- NB can be viewed as a set of class-specific unigram language models\n- Model for each class instantiates unigram language model\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n \n- Accuracy not a good metric when you want to discover something rare (spam emails\nare rare) or when class is imbalanced \n- Precision: measures percentage of items that were predicted positive that are\nactually positive\n- Recall: measures percentage of positive items in the input that were correctly \nidentified by the system as positive \n- Precision and recall emphasize true positives i.e. finding what we are supposed\nto be looking for\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n 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 \n- Representational harms: harms caused by a system that demeans a social group\n\n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n- Generative model has goal of understanding the classes (i.e. what dogs vs. cats\nlook like). The model can generate (i.e. draw a dog)\n- At test time, it asks which model better fits the image\n- Discriminative model is only trying to learn to distinguish the classes (i.e.\nmaybe all dogs in training data wearing collars, and cats are not)\n\nNB is generative:\n\n$\\hat{c} = {\\argmax}_c P(d|c)P(c)$\n\n- Generative model: likelihood term $P(d|c)$ expresses how to generate \nthe features of a document if we knew it was of class $c$\n- Discriminative model (i.e. logistic regression) attempts to directly compute $P(c|d)$\n\nSigmoid: \n\n$\\frac{1}{1+exp(-z)}$\n\n- Linear around $0$ but flattens toward the ends\n- Tends to squash outlier values toward $0$ or $1$\n- Differentiable\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \n- Feature interactions (combination features) need to be designed by hand\n- Large number of features can be created via feature templates: abstract\nspecifications of features\n- Representation learning is a way to learn features automatically (unsupervised\nfrom input)\n\nLogistic regression vs. NB:\n- NB has overly strong conditional independence assumption. Can overestimate evidence\n- LR more robust to correlated features (more accurate when there are many\ncorrelated features)\n- LR works better on larger documents/datasets\n- NB can work well on very small datasets/short documents\n- NB easy to implement and fast to train (no optimization step)\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n \n- Loss/cost function: the distance between system output and gold output \n- Optimization algorithm: iteratively updates the weights to minimize loss function\n\nConditional MLE: \n- Loss function that prefers correct class labels of the training\nsamples to be more likely\n- Choose parameters to maximize the log probability of the true $y$ labels in the\ntraining data\n- Result is \"cross-entropy loss\": negative log likelihood loss\n\nCross-entropy loss:\n- We want to learn weights that maximize the probability of the correct label $p(y|x)$\n\n$p(y|x) = \\hat{y}^y * (1-\\hat{y})^{1-y}$\n\n- If $y=1$ then $p(y|x) = \\hat{y}$\n- If $y=0$ then $p(y|x) = 1-\\hat{y}$\n\nLog-likelihood of $p(y|x)$:\n\n- Want to maximize: $\\log(p(y|x)) = y\\log \\hat{y} + (1-y)\\log (1-\\hat{y})$\n- To get loss function, flip the sign:\n\nCross entropy: \n\n$Loss(\\hat{y}, y) = - [ y\\log \\hat{y} + (1-y)\\log (1-\\hat{y}) ]$\n\n- Goes from $0$ (no loss) to infinity\n\n\n## SLP Chapter 5.4 Gradient Descent\n \n- Loss function is parametrized by $\\theta$ weights\n- The goal is to find weights that minimize loss function, averaged over all examples\n\n$\\hat{\\theta} = {\\argmin}_\\theta \\frac{1}{m} \\sum_i Loss(\\hat{y}_i, y_i)$\n\n- Gradient descent: method for finding the minimum by figuring out which direction\n(in the space of $\\theta)$ the slope is rising most steeply, and moving in the\nopposite direction\n- LR loss function is convex (function has just one minimum)\n- The gradient of a function with multiple variables is a vector that points in the\ndirection of the greatest increase in a function\n- Learning rate $\\eta$: weighted magnitude of the amount to move in gradient descent \n\n$\\nabla_\\theta L(\\hat{y}, y) = [\\frac{\\partial}{\\partial w_1}L(\\hat{y}, y), \\frac{\\partial}{\\partial w_2}L(\\hat{y}, y), ..., \\frac{\\partial}{\\partial w_n}L(\\hat{y}, y)]$\n\nFinal equation for updating $\\theta$ based on the gradient:\n\n$\\theta_{t+1} = \\theta_t - \\eta \\nabla L(\\hat{y}, y)$\n\nGradient (of the loss) for logistic regression: $x_j [\\sigma(wx+b)-y]$\n\nSGD:\n- SGD is online algorithm: minimizes loss function by computing gradient after each\ntraining example\n- Chooses single random example at a time, update the weights to improve performance\non single example\n- Batch training: compute gradient for the entire dataset\n- Mini batch: train on a group of $m$ examples $<$ whole dataset\n\n\n## SLP Chapter 5.5 Regularization\n \n- Use regularization $R(\\theta)$ to avoid overfitting\n\nL2 regularization uses the square of the L2 norm:\n\n$R(\\theta) = ||\\theta||_{2}^{2} = \\sum_j \\theta_{j}^2$\n\n- L2 prefers weight weight vectors with small weights\n\nL1 regularization uses the L1 norm, the sum of absolute values of the weights:\n\n$R(\\theta) = ||\\theta||_{1} = \\sum_j |\\theta_{j}|$\n\n- L1 prefers sparse solutions with some larger weights, but many more weights$=0$\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n \n- Multinomial LR uses generalization of the sigmoid, called the softmax to compute\n$p(y=c|x)$\n\nsoftmax$(z_i) = \\frac{\\exp(z_i)}{\\sum_j \\exp(z_j)}$ for $1 \\leq i \\leq k$\n\n- Input for the softmax is a dot product between weight vector $w$ and input vector\n$x$ and bias. Need separate weight vectors for each of the $k$ classes\n\n$p(y=c|x) = \\frac{\\exp(w_{c}x+b_c)}{\\sum_j \\exp(w_{j}x+b_j)}\n\n\n## SLP Chapter 7.1 Units\n \nLanguage modeling: assigning probabilities to word sequences and predicting upcoming words\n\ntanh function\n- From $-1$ to $+1$ is usually better than sigmoid function\n- Smoothly differentiable\n- Maps outlier values toward the mean\n\n$y = \\frac{e^z - e^{-z}}{e^z + e^{-z}}\n\nReLU: \n- Very close to being linear\n- No problems with vanishing gradient (compared to tanh and sigmoid which have this problem)\n\n$y = max(x,0)$\n\n\n## SLP Chapter 7.2 The XOR problem\n \n- Problem: single neural unit cannot compute certain very simple functions of its input\n- Possible for perceptron to compute logical AND and logical OR functions of its binary inputs\n- However, perceptron cannot compute logical XOR (perceptrons are purely linear)\n- Perceptron is a linear classifier: $w_1 x_1 + w_2 x_2 + b = 0$ is the equation of a line\n- The line is a decision boundary in 2-d space \n- Simply no way to draw a linear that separates positive and negative cases of XOR\n(XOR is not a linearly separable function)\n\nSolution for XOR:\n- XOR can be calculated by a layered network of units \n- Hidden layer forms a representation for the input that makes it easy to linearly\nseparate positive from negative\n- This means NN can automatically learn useful representations of the input\n\nNon-linearity needed:\n- Network with only simple linear units cannot solve XOR\n- Network formed by many layers of purely linear units can always be reduced\n(computationally identical) to a single layer of linear units with appropriate weights\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n \nFFN: \n- Multilayer network where units are connected with no cycles\n- Outputs from units in each layer are passed to units in the next layer\n- No outputs passed back to previous layer\n- Weight matrix $W_{ji}$ represents weight of the connection from $i$th input $x_i$\nto the $j$th hidden unit $h_j$\n\nOutput of hidden layer $h = act(Wx+b)$\n- The result for $h$ forms a representation of the input\n- Role of output layer is to take new representation $h$ and compute a final output\n- NN with one hidden layer: can think of NN as running standard LR on the features that the network developed\nin $h$\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n \n\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n \n \n\n## SLP Chapter 7.6 Training Neural Nets\n \n\n\n\n## SLP Chapter 7.7 Training the neural language model\n \n\n\n\n## Module 13 Lecture Notes\n Your summary here \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\n- RNN and transformers can deal with sequential nature of language, can handle variable\nlength inputs\n- Probabilistic language models predict the next word given some preceding context\n\nConstraint by Markov assumption: prediction is based on a fixed preceding context of size $N$:\n\n$p(w_n|w_{1:n-1}) = p(w_n|w_{(n-N+1):(n-1)})$\n\nPerplexity:\n- Evaluate language models by examining how well it predicts unseen data drawn from\nthe same source as the training data\n- Good models should assign higher probabilities to unseen data\n\n$PP_\\theta (w_{1:n}) = $\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n \nRNN:\n- RNNs are networks that contain a cycle within its network connections (i.e. value of a unit\nis dependent on its own earlier outputs as input)\n- Sequences processed by presenting one item at a time to the network\n- Hidden layer receives as input the value of the preceding hidden layer\n- Hidden layer from previous time step is a form of memory/context\n- No fixed length limit on prior context; context includes information all the way\nback to the beginning of the sequence\n\n$h_t = g(Uh_{t-1} + Wx_t)$\n\n$y_t = f(Vh_t)$\n\nWeights to update:\n- $W$ - weights from input layer to hidden layer\n- $U$ - weights from previous hidden layer to current hidden layer\n- $V$ - weights from the hidden layer to output layer\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n \nYour summary here \n\n\n## SLP Chapter 6.1 Lexical Semantics\n \n\n \n\n## SLP Chapter 6.2 Vector Semantics\n \n\n\n\n## SLP Chapter 6.3 Words and Vectors\n \n\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n \n\n \n\n## SLP Chapter 6.8 Word2vec\n \n\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \n\n \n\n## SLP Chapter 6.11 Bias and Embeddings\n\n\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n \n\n \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}