{
  "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",
      "execution_count": 29,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "474714e8-cbf7-4cda-8859-61e836a2c0db"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "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)))"
      ]
    },
    {
      "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",
      "execution_count": 30,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "9525148d-34d3-41bd-ef6e-93a8abeb8d1e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 31,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 32,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "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 = \"\"\" Agent assigns probability to each possible state. When agent is uncertain about the outcome of taking an action, calculate probability using\n",
        "P(Result(a)=s^' )=∑P(s)P(s^'│s,a).\n",
        " \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"Writing down constraints for rational agent and showing that MEU can be derived from it.\n",
        "Think of set of outcomes (S) for each action as a lottery L\n",
        "L=[p_1,S_1;p_2,S_2;…;p_n,S_n]\n",
        "Each S can be an atomic state or another Lottery \n",
        "For utility theory, we want to understand how the agent’s preference for a complex lottery is related to the preferences between the underlying states in those lotteries.\n",
        "\\n\n",
        " Rational Preference Lead to Utility\n",
        "•\tExpected Utility of a Lottery: sum of the probability of each outcome times the utility of the outcome.\n",
        "U([p1, S1;…; pn, Sn]) =Σ i piU(Si).\n",
        "•\tValue function or ordinal utility function: in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. \n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"16.3 Utility Functions\n",
        "\tMap from lotteries to real numbers\n",
        "16.3.1 Utility assessment and utility scales\n",
        "\tPreference elicitation: presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n",
        "\tCreate a measure for utility by first creating a scale that identifies the best and worst possible outcomes. \n",
        "\tNormalized utilities: uses a scale between 0 to 1.\n",
        "\tMicromort: one in a million chance of death\n",
        "16.3.2 The utility of money \n",
        "\tUtility is not directly proportional to monetary value because the utility of first million received is very high compared to the utility of additional money received. \n",
        "16.3.3 Expected utility and post-decision disappointment\n",
        "\tRational decision making means maximizing expected utility\n",
        "a*=argmax a EU(a)\n",
        "\tUnbiased estimate: expected value of the error is zero.\n",
        "\tOptimizer’s curse: believing that something that worked in 80% of the sample will work exactly with that efficacy in the population.\n",
        "\tAvoid this by taking a Bayesian approach that uses an explicit probability model\n",
        "16.3.4 human judgement and irrationality \n",
        "\tNormative theory: it describes how a rational agent should act.\n",
        "\tDescriptive theory: describes how actual agents really do act.\n",
        "\tFraming effect: framing the way someone states probabilities has an impact on decision making. \n",
        "\tAnchoring effect: people having an easier time making relative judgement instead of absolute ones. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\tMarkovian: the probability of reaching s’ from s depends only on s and not on the history of the earlier states. \n",
        "\tEnvironment history: When a decision problem is sequential, the utility function depends on a sequence of states and actions rather than a single state. \n",
        "\tMarkovian decision process: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards.\n",
        "\tPolicy: a solution that specify what the agent should do for any state that the agent might reach.\n",
        "\tProper Policy: a policy that is guaranteed to reach a terminal state \n",
        "\tThe introduction of uncertainty beings MDPs closer to real world than deterministic search problems. \n",
        "\tFinite horizon: there is a fixed time N after which nothing matter:the game is over. \n",
        "\tNonstationary: A policy that depends on the time. \n",
        "\tInfinite horizon: doesn’t mean that all state sequences are infinite and instead it means that there is no fixed deadline. \n",
        "\tWhen there are no fixed time limits, there is no reason to behave differently in the same state during different point in time. \n",
        "\tAdditive discounted rewards: the utility of a history is where the discounted factor is a number between 0 and 1. This discount factor describes the preference of an agent for current rewards over future rewards. \n",
        "\t1 discount reward: agent is willing to wait completely for long-term rewards.\n",
        "\t0 discount reward: rewards in the future are deemed insignificant.\n",
        "\tA way to handle infinities in the cases the agent never reaches terminal states.\n",
        "\tThe utility of a state is the expected reward for the next transition plus the discounted utility of the next state:\n",
        "\tBellman Equation: U(s)=max∑_s^'▒〖P(S^'│S,a)R(S,a,s^' )+γU(s')〗 \n",
        "\tQ-function: action-utility function or Q(s,a) is the expected utility of taking a given action in a given state. \n",
        "\tUtility: U(s) = max_a⁡〖Q(s,a)〗\n",
        "\tPolicy: π^* (s)=argmax_a Q(s,a)\n",
        "\tBellman: Q(s,a)=∑_s^'▒〖P(s^'│s,a)[R(s,a,s^' )+ γ U(s^' )] 〗 = ∑_s^'▒〖P(s'|s,a)[R(s,a,s') +γ max_a^'⁡Q(s^',a^' ) 〗\n",
        "\tSolving for U or Q lets us find the optimal policy \n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\tValue Iteration: bellman equation is the basis of this. \n",
        "\tFor n possible states, there are n bellman equations \n",
        "\tEach iteration step is called bellman update\n",
        "\tContraction: Value iteration eventually converges to a unique set of solutions of  the bellman equations. \n",
        "\tContraction has one fixed point and it is part of the proof of convergence for value iteration. \\n \n",
        "\tWhen the function is applied to any argument, the value must get closer together. \n",
        "\tValue iteration converges exponentially fast \n",
        "\tBellman update is a contraction by a factor gamma on the space of utility factor \n",
        "\tWe can use the utility factor to understand the rate of convergence \n",
        "\tRun N iterations to reach an error of at most ϵ \n",
        "\tWe can use the error and make a prediction on the number of iterations needed. \n",
        "\tWe can use |(|U_i-U|)| as the error\n",
        "\tthe estimate above can be used for a termination condition: If |(|U_(i+1)-U_i |)|<ϵ(1-γ)/γ,then |(|U_(i+1)-U|)|<ϵ  \n",
        "\tPolicy loss is U^*-U is the most agent can lose by executing a policy \n",
        "\tPolicy may become optimal way before U_i has converged. \n",
        "\tWe can bound the error in the utility estimates if we stop after a finite number of iterations. \n",
        "\tPolicy Iteration\n",
        "\tAlgorithm: iteration between two steps, beginning from some random policy and then calculate the utility of each state to be executed. Improve this policy by using one-step look-ahead and calculate a new policy for the next step.\n",
        "\tPolicy iteration: given a policy π, calculate u_i=u^π, the utility of each state given policy. \n",
        "\tPolicy improvement: calculate a new MEU policy π_(i+1), using one step look ahead based on U_i\n",
        "\tWhy must policy iteration terminate?\n",
        "\tBecause there are only finitely many policies for a finite space, and each iteration can be seen to show a better policy, iteration must terminate. \n",
        "\tImplementation is easier than solving the bellman equation. \n",
        "\tRun time: O(n^3 )\n",
        "\tFor n linear equations, there are n unknowns and using systems of equations, we can solve it in the aforementioned time.\n",
        "\tSmall state space: use this over the value iteration method. \n",
        "\tAsynchronous policy iteration: pick any subset of states and at each iteration either perform value iteration or policy iteration.\n",
        "\tWe can use this to plan better by only concentrating on updating the values of states that will be reached by a good policy, instead of planning for all states.\n",
        "\tLinear programming is solvable in polynomial time, so MDPs an also be solved in polynomial time.\n",
        "\tLP is less efficient when compared to dynamic programming when solving for MDPs.\n",
        "\tOnline algorithms for MDPs\n",
        "\tValue and policy are offline algorithms\n",
        "\tGenerate an optimal solution for the problem, which can be executed by a simple agent.\n",
        "\tFor large MDPs, like Tetris, offline solution even in polynomial time is not possible \n",
        "\tExpectimax algorithm:build a tree of alternating max and chance nodes. \n",
        "\tEvaluation function to be applied to non-terminal leaves of the tree or provide a default value. \n",
        "\tExtract a decision by backing up the utility values from the leaves where average the chance nodes and make max of the decision nodes. \n",
        "\tWe can bound the expectimax tree depth if we know what the absolute value of the error for the tree should be. \n",
        "\tAlso handle the potentially large branching factors at the chance nodes\n",
        "\tUCT (uses real time dynamic programming) has the lower average reward than the optimal policy reward because it is using a tree rather than a graph. \n",
        "\tBetter for solving a large decision space like Tetris because the agent can go into the future to get a sense of whether potentially risky move is worth it. \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\t\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"agent’s preference is captured by a utility function, which assigns a single number to express the desirability of a state (U(s)).\",\n",
        "\"expected utility\" : \"expected utility of an action given the evidence is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\",\n",
        "\"Decision theory\": \"choosing among actions based on the desirability of their immediate outcomes.\",\n",
        "\"Principle of MEU\":\" maximum expected utility says that a rational agent should choose the action that maximized the agent’s expected utility.\",\n",
        "\"Rational preferences\": \"imply behaviour describable as maximization of expected utility\",\n",
        "\"preference relation constraints\": \"\"\"1. Orderability \\n\n",
        "2. Transitivity \\n\n",
        "3. Continuity \\n\n",
        "4. Substitutability \\n\n",
        "5. Monotonocity \\n\n",
        "6. Decomposability: \n",
        "\"\"\",\n",
        "\"Orderability\": \"when given two lotteries, agent must prefer one over the other or prefer both equally.\",\n",
        "\"Transitivity\": \"given 3 Ls, if agent prefers A over B and prefers B over C, then agent will prefer A over C\",\n",
        "\"Continuity\": \"if the preference is A > B > C, then there is some probability where the agent is indifferent between getting B for sure and the lottery that yields A with prob p and C with prob 1-p.\",\n",
        "\"Substitutability\": \"if an agent is indifferent between two lotteries, then they are indifferent with two complex lotteries where A or B occur with the same probability\",\n",
        "\"Monotonocity\": \"If an agent prefers A to B, then agent must also prefer the lottery that has a higher probability of A occurring over B.\",\n",
        "\"Decomposability\": \"compressing two consecutive lotteries into a single equivalent lottery.\",\n",
        "\"Preference elicitation\": \"presenting choices to the human and using the observed preferences to pin down the underlying utility function\",\n",
        "\"Finite vs. infinite horizon\": \"agent’s optimal action will depend on how much time is left.\", \n",
        "\"Discounting\": \"\"\"preferring a reward now over later. When discount is 1, all the rewards are preferred now,\\n\n",
        "and when it is 0 all the rewards are preferred in the future. This helps converge the algorithm.\"\"\",\n",
        "\"Stationary preference\": \"\"\"policy that only depends on current state. Can only use additive \n",
        "or discounted utilities for these.\"\"\" ,\n",
        "\"stationary process\": \"the conditional probability table does not change over time\",\n",
        "\"Absorbing state\": \"guarantee that for every policy a terminal state will eventually by reached.\",\n",
        "\"Value iteration\": \"Given a vector V_k (s), do one ply of expectimax from each state. Repeat until converges.\", \n",
        "\"Bellman Equations\": \"take correct first action and then keep being optimal.\",\n",
        "\"Policy extraction\": \"getting the policy implied by the values\",\n",
        "\"worst-case vs. avg case minimax reasoning\": \"\"\"\n",
        "•\tFor worst-case minimax reasoning the scale of the terminal function doesn’t matter, just their ranking does.\n",
        "•\tFor average-case, we need the magnitude to be meaningful\n",
        "\"\"\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "70004835-4b20-4760-9220-ed8ffdb5fd4f"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your summary of 'AIMA Chapter 17.2 Algorithms for MDPs' is too long!\n",
              "## WARNING: Your definition of 'Continuity' is too long!\n",
              "WARNING: Your definition of 'Discounting' is too long!\n",
              "# Module 8: Markov Decision Processes\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Agent assigns probability to each possible state. When agent is uncertain about the outcome of taking an action, calculate probability using\n",
              "P(Result(a)=s^' )=∑P(s)P(s^'│s,a).\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",
              "Writing down constraints for rational agent and showing that MEU can be derived from it.\n",
              "Think of set of outcomes (S) for each action as a lottery L\n",
              "L=[p_1,S_1;p_2,S_2;…;p_n,S_n]\n",
              "Each S can be an atomic state or another Lottery \n",
              "For utility theory, we want to understand how the agent’s preference for a complex lottery is related to the preferences between the underlying states in those lotteries.\n",
              "\n",
              "\n",
              " Rational Preference Lead to Utility\n",
              "•\tExpected Utility of a Lottery: sum of the probability of each outcome times the utility of the outcome.\n",
              "U([p1, S1;…; pn, Sn]) =Σ i piU(Si).\n",
              "•\tValue function or ordinal utility function: in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "16.3 Utility Functions\n",
              "\tMap from lotteries to real numbers\n",
              "16.3.1 Utility assessment and utility scales\n",
              "\tPreference elicitation: presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n",
              "\tCreate a measure for utility by first creating a scale that identifies the best and worst possible outcomes. \n",
              "\tNormalized utilities: uses a scale between 0 to 1.\n",
              "\tMicromort: one in a million chance of death\n",
              "16.3.2 The utility of money \n",
              "\tUtility is not directly proportional to monetary value because the utility of first million received is very high compared to the utility of additional money received. \n",
              "16.3.3 Expected utility and post-decision disappointment\n",
              "\tRational decision making means maximizing expected utility\n",
              "a*=argmax a EU(a)\n",
              "\tUnbiased estimate: expected value of the error is zero.\n",
              "\tOptimizer’s curse: believing that something that worked in 80% of the sample will work exactly with that efficacy in the population.\n",
              "\tAvoid this by taking a Bayesian approach that uses an explicit probability model\n",
              "16.3.4 human judgement and irrationality \n",
              "\tNormative theory: it describes how a rational agent should act.\n",
              "\tDescriptive theory: describes how actual agents really do act.\n",
              "\tFraming effect: framing the way someone states probabilities has an impact on decision making. \n",
              "\tAnchoring effect: people having an easier time making relative judgement instead of absolute ones. \n",
              "\n",
              "\n",
              "## AIMA Chapter 17.1 Sequential Decision Problems\n",
              "\tMarkovian: the probability of reaching s’ from s depends only on s and not on the history of the earlier states. \n",
              "\tEnvironment history: When a decision problem is sequential, the utility function depends on a sequence of states and actions rather than a single state. \n",
              "\tMarkovian decision process: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards.\n",
              "\tPolicy: a solution that specify what the agent should do for any state that the agent might reach.\n",
              "\tProper Policy: a policy that is guaranteed to reach a terminal state \n",
              "\tThe introduction of uncertainty beings MDPs closer to real world than deterministic search problems. \n",
              "\tFinite horizon: there is a fixed time N after which nothing matter:the game is over. \n",
              "\tNonstationary: A policy that depends on the time. \n",
              "\tInfinite horizon: doesn’t mean that all state sequences are infinite and instead it means that there is no fixed deadline. \n",
              "\tWhen there are no fixed time limits, there is no reason to behave differently in the same state during different point in time. \n",
              "\tAdditive discounted rewards: the utility of a history is where the discounted factor is a number between 0 and 1. This discount factor describes the preference of an agent for current rewards over future rewards. \n",
              "\t1 discount reward: agent is willing to wait completely for long-term rewards.\n",
              "\t0 discount reward: rewards in the future are deemed insignificant.\n",
              "\tA way to handle infinities in the cases the agent never reaches terminal states.\n",
              "\tThe utility of a state is the expected reward for the next transition plus the discounted utility of the next state:\n",
              "\tBellman Equation: U(s)=max∑_s^'▒〖P(S^'│S,a)R(S,a,s^' )+γU(s')〗 \n",
              "\tQ-function: action-utility function or Q(s,a) is the expected utility of taking a given action in a given state. \n",
              "\tUtility: U(s) = max_a⁡〖Q(s,a)〗\n",
              "\tPolicy: π^* (s)=argmax_a Q(s,a)\n",
              "\tBellman: Q(s,a)=∑_s^'▒〖P(s^'│s,a)[R(s,a,s^' )+ γ U(s^' )] 〗 = ∑_s^'▒〖P(s'|s,a)[R(s,a,s') +γ max_a^'⁡Q(s^',a^' ) 〗\n",
              "\tSolving for U or Q lets us find the optimal policy \n",
              "\n",
              "\n",
              "## AIMA Chapter 17.2 Algorithms for MDPs\n",
              "\tValue Iteration: bellman equation is the basis of this. \n",
              "\tFor n possible states, there are n bellman equations \n",
              "\tEach iteration step is called bellman update\n",
              "\tContraction: Value iteration eventually converges to a unique set of solutions of  the bellman equations. \n",
              "\tContraction has one fixed point and it is part of the proof of convergence for value iteration. \n",
              " \n",
              "\tWhen the function is applied to any argument, the value must get closer together. \n",
              "\tValue iteration converges exponentially fast \n",
              "\tBellman update is a contraction by a factor gamma on the space of utility factor \n",
              "\tWe can use the utility factor to understand the rate of convergence \n",
              "\tRun N iterations to reach an error of at most ϵ \n",
              "\tWe can use the error and make a prediction on the number of iterations needed. \n",
              "\tWe can use |(|U_i-U|)| as the error\n",
              "\tthe estimate above can be used for a termination condition: If |(|U_(i+1)-U_i |)|<ϵ(1-γ)/γ,then |(|U_(i+1)-U|)|<ϵ  \n",
              "\tPolicy loss is U^*-U is the most agent can lose by executing a policy \n",
              "\tPolicy may become optimal way before U_i has converged. \n",
              "\tWe can bound the error in the utility estimates if we stop after a finite number of iterations. \n",
              "\tPolicy Iteration\n",
              "\tAlgorithm: iteration between two steps, beginning from some random policy and then calculate the utility of each state to be executed. Improve this policy by using one-step look-ahead and calculate a new policy for the next step.\n",
              "\tPolicy iteration: given a policy π, calculate u_i=u^π, the utility of each state given policy. \n",
              "\tPolicy improvement: calculate a new MEU policy π_(i+1), using one step look ahead based on U_i\n",
              "\tWhy must policy iteration terminate?\n",
              "\tBecause there are only finitely many policies for a finite space, and each iteration can be seen to show a better policy, iteration must terminate. \n",
              "\tImplementation is easier than solving the bellman equation. \n",
              "\tRun time: O(n^3 )\n",
              "\tFor n linear equations, there are n unknowns and using systems of equations, we can solve it in the aforementioned time.\n",
              "\tSmall state space: use this over the value iteration method. \n",
              "\tAsynchronous policy iteration: pick any subset of states and at each iteration either perform value iteration or policy iteration.\n",
              "\tWe can use this to plan better by only concentrating on updating the values of states that will be reached by a good policy, instead of planning for all states.\n",
              "\tLinear programming is solvable in polynomial time, so MDPs an also be solved in polynomial time.\n",
              "\tLP is less efficient when compared to dynamic programming when solving for MDPs.\n",
              "\tOnline algorithms for MDPs\n",
              "\tValue and policy are offline algorithms\n",
              "\tGenerate an optimal solution for the problem, which can be executed by a simple agent.\n",
              "\tFor large MDPs, like Tetris, offline solution even in polynomial time is not possible \n",
              "\tExpectimax algorithm:build a tree of alternating max and chance nodes. \n",
              "\tEvaluation function to be applied to non-terminal leaves of the tree or provide a default value. \n",
              "\tExtract a decision by backing up the utility values from the leaves where average the chance nodes and make max of the decision nodes. \n",
              "\tWe can bound the expectimax tree depth if we know what the absolute value of the error for the tree should be. \n",
              "\tAlso handle the potentially large branching factors at the chance nodes\n",
              "\tUCT (uses real time dynamic programming) has the lower average reward than the optimal policy reward because it is using a tree rather than a graph. \n",
              "\tBetter for solving a large decision space like Tetris because the agent can go into the future to get a sense of whether potentially risky move is worth it. \n",
              " \n",
              "\n",
              "## Module 8 Lecture Notes\n",
              "\t\n",
              "\n",
              "\n",
              "## Module 8 Definitions\n",
              "* **Utility function** - agent’s preference is captured by a utility function, which assigns a single number to express the desirability of a state (U(s)).\n",
              "* **Expected utility** - expected utility of an action given the evidence is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n",
              "* **Decision theory** - choosing among actions based on the desirability of their immediate outcomes.\n",
              "* **Principle of meu** -  maximum expected utility says that a rational agent should choose the action that maximized the agent’s expected utility.\n",
              "* **Rational preferences** - imply behaviour describable as maximization of expected utility\n",
              "* **Preference relation constraints** - 1. Orderability \n",
              "\n",
              "2. Transitivity \n",
              "\n",
              "3. Continuity \n",
              "\n",
              "4. Substitutability \n",
              "\n",
              "5. Monotonocity \n",
              "\n",
              "6. Decomposability: \n",
              "\n",
              "* **Orderability** - when given two lotteries, agent must prefer one over the other or prefer both equally.\n",
              "* **Transitivity** - given 3 Ls, if agent prefers A over B and prefers B over C, then agent will prefer A over C\n",
              "* **Continuity** - if the preference is A > B > C, then there is some probability where the agent is indifferent between getting B for sure and the lottery that yields A with prob p and C with prob 1-p.\n",
              "* **Substitutability** - if an agent is indifferent between two lotteries, then they are indifferent with two complex lotteries where A or B occur with the same probability\n",
              "* **Monotonocity** - If an agent prefers A to B, then agent must also prefer the lottery that has a higher probability of A occurring over B.\n",
              "* **Decomposability** - compressing two consecutive lotteries into a single equivalent lottery.\n",
              "* **Preference elicitation** - presenting choices to the human and using the observed preferences to pin down the underlying utility function\n",
              "* **Finite vs. infinite horizon** - agent’s optimal action will depend on how much time is left.\n",
              "* **Discounting** - preferring a reward now over later. When discount is 1, all the rewards are preferred now,\n",
              "\n",
              "and when it is 0 all the rewards are preferred in the future. This helps converge the algorithm.\n",
              "* **Stationary preference** - policy that only depends on current state. Can only use additive \n",
              "or discounted utilities for these.\n",
              "* **Stationary process** - the conditional probability table does not change over time\n",
              "* **Absorbing state** - guarantee that for every policy a terminal state will eventually by reached.\n",
              "* **Value iteration** - Given a vector V_k (s), do one ply of expectimax from each state. Repeat until converges.\n",
              "* **Bellman equations** - take correct first action and then keep being optimal.\n",
              "* **Policy extraction** - getting the policy implied by the values\n",
              "* **Worst-case vs. avg case minimax reasoning** - \n",
              "•\tFor worst-case minimax reasoning the scale of the terminal function doesn’t matter, just their ranking does.\n",
              "•\tFor average-case, we need the magnitude to be meaningful\n",
              "\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 34,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" \tN-armed bandit: has n-levers in a slot machine and each lever is a fixed by unknown probability distribution of winnings. Each pull samples from that unknown distribution. \n",
        "\tGambler’s choice is to pick which lever to pull:one that have given the best outcome or one that hasn’t been tried yet. \n",
        "\tAbove is the exploration vs. exploitation trade-off \n",
        "\tCost is the cost of not pulling the remaining levers. \n",
        "\tGittins index: measure of reward that can be achieved through a given stochastic process with certain properties. \n",
        "\tThe Bernoulli bandit: each arm M_i produces a reward of 0 or 1 with fixed but unknown probability of μ_i. \n",
        "\tThe state of each arm M_i is defined by s_i and f_i\n",
        "\tTransition prob = 1: s_i/(s_i+f_i )\n",
        "\tTransition prob = 0: f_i/(s_i+f_i ) \n",
        "\tUpper Confidence Bound: use a sample from each arm to establish a CI for the value of that arm\n",
        "\tThompson sampling: chooses an arm randomly according to probability that it is a successful arm given the samples so far. \n",
        "\tSelection problems: choosing best option under certain constraints as fast as possible. \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" •\tReinforcement learning: agent interacts with the world and periodically receives rewards that reflect how well it is doing.  \\n\n",
        "•\tModel based RL: agent uses a transition model to help interpret the reward signals and to make decisions on how to act.  \\n\n",
        "•\tModel free: agent learns a direct representation of how to behave \\n\n",
        "    o\tAction-utility: Q learning where sum of rewards is taken from state s onward if action a is taken.  \\n\n",
        "    o\tPolicy search: agent learns a policy that maps directly from states to action. Also known as a reflex agent.   \\n\n",
        "•\tPassive RL: agent’s policy is fixed and task is to learn the utilities of states. Agent is given all the states it can reach and the policy it can follow. \\n\n",
        "•\tActive RL: agent must figure out what to do and using exploration they can do so.  \\n\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" •\tSimilar to policy evaluation step from policy iteration. \\n\n",
        "•\tAgent does not know the transition model which specifies the probability of reaching s’ from s after doing a. \\n\n",
        "•\tAgent does not know the reward function\\n\n",
        "•\tAgent executes a set of trials \\n\n",
        "•\tDirect utility estimation: is the expected total required from that state onward. Doesn’t understand connections between states so misses opportunity to learn and converges slowly.\\n\n",
        "•\tAdaptive Dynamic programming: takes advantage of the constraints among utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming. \\n\n",
        "•\tModified policy iteration: using a simplified value iteration process to update utility estimates after each change to the learned model. \\n\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "•\tSolving MDPs is offline planning because we determine all quantities through computation and don’t actually have to play the game. \\n\n",
        "•\tIn reinforcement learning, we are online because we learn as we play\\n\n",
        "    o\tExploration: try unknown and get info \\n\n",
        "    o\tExploitation: use what we know to make decisions\\n\n",
        "    o\tRegret: even if you learn intelligently you make mistakes. Regret lets us quantify the relative goodness of exploration procedures\\n\n",
        "    o\tSampling: because of change, try things repeatedly \\n\n",
        "    o\tDifficulty:learning can be much harder than solving a known MDP\\n\n",
        "•\tIn RL, feedback is received as reward and agent is trying to maximize reward.\\n\n",
        "•\tAgent doesn’t know T or R\\n\n",
        "•\tModel based: learn based on experience and solve if what agent learned was correct. Creating an empirical MDP and then solving using value iteration or policy iteration as before. \\n\n",
        "•\tModel free learning: along for the ride, take actions in the real world and learn from experience. \\n\n",
        "•\tDirect evaluation: compute values for each state under policy and average together observed sample values \\n\n",
        "    o\tPros: easy to get, don’t need T or R, and eventually computes the correct avg value\\n\n",
        "    o\tCons: wastes info about state connections as each state is learned separately. Takes a long time to learn. \\n\n",
        "•\tSample based policy evaluation: average the values based on a sample of outcomes by taking certain actions. \\n\n",
        "•\tTemporal difference learning: learn from every experience and update the V each time transition is experienced. Still using a fixed policy evaluation. \\n\n",
        "    o\tExponential moving avg: emphasize values from more recent samples as avg. \\n\n",
        "    o\tLearn Q-values not values because we don’t have a great time turning the updated values into a new policy. \\n\n",
        "•\tActive RL: online model, take actions on the world. \\n\n",
        "• In RL, a deterministic policy is a mapping from states to actions. \\n\n",
        "•\tQ-learning: converges to optimal policy even if you are acting sub optimally.\\n\n",
        "    o\tOff-policy learning \\n\n",
        "    o\tHave to explore enough\\n\n",
        "    o\tHave to eventually make the learning rate small enough \\n\n",
        "•\tAgent exploration: \\n\n",
        "    o\tRandom (epsilon-greedy) : large e, act on current vs. small e take random action. As we learn more, we increase e so we can move from exploration to exploitation. \\n\n",
        "    o\tExplore where badness isn’t established by giving a bonus to states that lead to unknown states. \\n\n",
        " \\n\n",
        "•\tApproximate Q-value: basic version wants us to keep a table of all Q values but we cannot learn about every state. So generalize by keeping a small number of training states from experience. \\n\n",
        "•\tLinear Value Functions: using a feature representation, write a q function or value function for any state using a few weights. \\n\n",
        "    o\tPro: summed up experience in a few numbers\\n\n",
        "    o\tCon: states may share features but the value could be very different. \\n\n",
        "•\tQ-learning with linear Q-functions: if something bad happens, blame the features that were on. \\n\n",
        "\\t • it is not guaranteed that Q-learning with linear function approximation (weighted linear function of a set of features) will always converge to the optimal policy. For example, if Q is quadratic but the function approximator is linear.\\n\n",
        "• In both adaptive dynamic programming and temporal difference learning, the utility of the state is adjusted locally to agree with the utility of at least one successor state.\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"N-armed bandit\": \"has n-levers in a slot machine and each lever is a fixed by unknown probability distribution of winnings.\",\n",
        "\"Gittins index\": \"measure of reward that can be achieved through a given stochastic process with certain properties.\",\n",
        "\"The Bernoulli bandit\": \"each arm M_i produces a reward of 0 or 1 with fixed but unknown probability of μ_i.\",\n",
        "\"Upper Confidence Bound\": \"use a sample from each arm to establish a CI for the value of that arm\",\n",
        "\"Thompson sampling\": \"chooses an arm randomly according to probability that it is a successful arm given the samples so far.\",\n",
        "\"Selection problems\": \"choosing best option under certain constraints as fast as possible.\",\n",
        "\"Observed vars\": \"are evidence where the agent knows certain things about the world\",\n",
        "\"Unobserved vars\": \"are states where agent needs to reason about other aspects \",\n",
        "\"Model\": \"agent knows something about how the known variables relate to the unknown variables\", \n",
        "\"Probabilistic reasoning\": \"a framework for managing our beliefs and knowledge. \",\n",
        "\"Sample space\":\"possible worlds and it is mutually exclusive and collectively exhaustive\",\n",
        "\"Random Variable\":\"some aspect of the world about which we may have uncertainty.\", \n",
        "\"Probabilistic model\":\"is a joint distribution over a set of random variables\",\n",
        "\"Marginal distribution\":\"combined sub-tables that eliminate variables by summing-out.\",\n",
        "\"Model based\": \"learn based on experience and solve if what agent learned was correct. Creating an empirical MDP and then solving using value iteration or policy iteration as before.\",\n",
        "\"Model free learning\": \"along for the ride, take actions in the real world and learn from experience\",\n",
        "\"Probabilistic Inference\":\"compute desired probability from other known probabilities\",\n",
        "\"Inference by enumeration\":\"1. Select entries consistent with evidence, 2.Sum out to get joint of query and evidence, 3.Normalize\", \n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 35,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "ydOK__lwWgdp",
        "outputId": "6f21871d-c55a-486f-ce17-77da2f1d42a9"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'Model based' is too long!\n",
              "# Module 9: Reinforcement Learning\n",
              "## AIMA Chapter 17.3 Bandit Problems\n",
              " \tN-armed bandit: has n-levers in a slot machine and each lever is a fixed by unknown probability distribution of winnings. Each pull samples from that unknown distribution. \n",
              "\tGambler’s choice is to pick which lever to pull:one that have given the best outcome or one that hasn’t been tried yet. \n",
              "\tAbove is the exploration vs. exploitation trade-off \n",
              "\tCost is the cost of not pulling the remaining levers. \n",
              "\tGittins index: measure of reward that can be achieved through a given stochastic process with certain properties. \n",
              "\tThe Bernoulli bandit: each arm M_i produces a reward of 0 or 1 with fixed but unknown probability of μ_i. \n",
              "\tThe state of each arm M_i is defined by s_i and f_i\n",
              "\tTransition prob = 1: s_i/(s_i+f_i )\n",
              "\tTransition prob = 0: f_i/(s_i+f_i ) \n",
              "\tUpper Confidence Bound: use a sample from each arm to establish a CI for the value of that arm\n",
              "\tThompson sampling: chooses an arm randomly according to probability that it is a successful arm given the samples so far. \n",
              "\tSelection problems: choosing best option under certain constraints as fast as possible. \n",
              " \n",
              "\n",
              "## AIMA Chapter 22.1 Learning from Rewards\n",
              " •\tReinforcement learning: agent interacts with the world and periodically receives rewards that reflect how well it is doing.  \n",
              "\n",
              "•\tModel based RL: agent uses a transition model to help interpret the reward signals and to make decisions on how to act.  \n",
              "\n",
              "•\tModel free: agent learns a direct representation of how to behave \n",
              "\n",
              "    o\tAction-utility: Q learning where sum of rewards is taken from state s onward if action a is taken.  \n",
              "\n",
              "    o\tPolicy search: agent learns a policy that maps directly from states to action. Also known as a reflex agent.   \n",
              "\n",
              "•\tPassive RL: agent’s policy is fixed and task is to learn the utilities of states. Agent is given all the states it can reach and the policy it can follow. \n",
              "\n",
              "•\tActive RL: agent must figure out what to do and using exploration they can do so.  \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
              " •\tSimilar to policy evaluation step from policy iteration. \n",
              "\n",
              "•\tAgent does not know the transition model which specifies the probability of reaching s’ from s after doing a. \n",
              "\n",
              "•\tAgent does not know the reward function\n",
              "\n",
              "•\tAgent executes a set of trials \n",
              "\n",
              "•\tDirect utility estimation: is the expected total required from that state onward. Doesn’t understand connections between states so misses opportunity to learn and converges slowly.\n",
              "\n",
              "•\tAdaptive Dynamic programming: takes advantage of the constraints among utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming. \n",
              "\n",
              "•\tModified policy iteration: using a simplified value iteration process to update utility estimates after each change to the learned model. \n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
              " Your summary here \n",
              "\n",
              "## Module 9 Lecture Notes\n",
              " \n",
              "•\tSolving MDPs is offline planning because we determine all quantities through computation and don’t actually have to play the game. \n",
              "\n",
              "•\tIn reinforcement learning, we are online because we learn as we play\n",
              "\n",
              "    o\tExploration: try unknown and get info \n",
              "\n",
              "    o\tExploitation: use what we know to make decisions\n",
              "\n",
              "    o\tRegret: even if you learn intelligently you make mistakes. Regret lets us quantify the relative goodness of exploration procedures\n",
              "\n",
              "    o\tSampling: because of change, try things repeatedly \n",
              "\n",
              "    o\tDifficulty:learning can be much harder than solving a known MDP\n",
              "\n",
              "•\tIn RL, feedback is received as reward and agent is trying to maximize reward.\n",
              "\n",
              "•\tAgent doesn’t know T or R\n",
              "\n",
              "•\tModel based: learn based on experience and solve if what agent learned was correct. Creating an empirical MDP and then solving using value iteration or policy iteration as before. \n",
              "\n",
              "•\tModel free learning: along for the ride, take actions in the real world and learn from experience. \n",
              "\n",
              "•\tDirect evaluation: compute values for each state under policy and average together observed sample values \n",
              "\n",
              "    o\tPros: easy to get, don’t need T or R, and eventually computes the correct avg value\n",
              "\n",
              "    o\tCons: wastes info about state connections as each state is learned separately. Takes a long time to learn. \n",
              "\n",
              "•\tSample based policy evaluation: average the values based on a sample of outcomes by taking certain actions. \n",
              "\n",
              "•\tTemporal difference learning: learn from every experience and update the V each time transition is experienced. Still using a fixed policy evaluation. \n",
              "\n",
              "    o\tExponential moving avg: emphasize values from more recent samples as avg. \n",
              "\n",
              "    o\tLearn Q-values not values because we don’t have a great time turning the updated values into a new policy. \n",
              "\n",
              "•\tActive RL: online model, take actions on the world. \n",
              "\n",
              "• In RL, a deterministic policy is a mapping from states to actions. \n",
              "\n",
              "•\tQ-learning: converges to optimal policy even if you are acting sub optimally.\n",
              "\n",
              "    o\tOff-policy learning \n",
              "\n",
              "    o\tHave to explore enough\n",
              "\n",
              "    o\tHave to eventually make the learning rate small enough \n",
              "\n",
              "•\tAgent exploration: \n",
              "\n",
              "    o\tRandom (epsilon-greedy) : large e, act on current vs. small e take random action. As we learn more, we increase e so we can move from exploration to exploitation. \n",
              "\n",
              "    o\tExplore where badness isn’t established by giving a bonus to states that lead to unknown states. \n",
              "\n",
              " \n",
              "\n",
              "•\tApproximate Q-value: basic version wants us to keep a table of all Q values but we cannot learn about every state. So generalize by keeping a small number of training states from experience. \n",
              "\n",
              "•\tLinear Value Functions: using a feature representation, write a q function or value function for any state using a few weights. \n",
              "\n",
              "    o\tPro: summed up experience in a few numbers\n",
              "\n",
              "    o\tCon: states may share features but the value could be very different. \n",
              "\n",
              "•\tQ-learning with linear Q-functions: if something bad happens, blame the features that were on. \n",
              "\n",
              "\t • it is not guaranteed that Q-learning with linear function approximation (weighted linear function of a set of features) will always converge to the optimal policy. For example, if Q is quadratic but the function approximator is linear.\n",
              "\n",
              "• In both adaptive dynamic programming and temporal difference learning, the utility of the state is adjusted locally to agree with the utility of at least one successor state.\n",
              " \n",
              "\n",
              "## Module 9 Definitions\n",
              "* **N-armed bandit** - has n-levers in a slot machine and each lever is a fixed by unknown probability distribution of winnings.\n",
              "* **Gittins index** - measure of reward that can be achieved through a given stochastic process with certain properties.\n",
              "* **The bernoulli bandit** - each arm M_i produces a reward of 0 or 1 with fixed but unknown probability of μ_i.\n",
              "* **Upper confidence bound** - use a sample from each arm to establish a CI for the value of that arm\n",
              "* **Thompson sampling** - chooses an arm randomly according to probability that it is a successful arm given the samples so far.\n",
              "* **Selection problems** - choosing best option under certain constraints as fast as possible.\n",
              "* **Observed vars** - are evidence where the agent knows certain things about the world\n",
              "* **Unobserved vars** - are states where agent needs to reason about other aspects \n",
              "* **Model** - agent knows something about how the known variables relate to the unknown variables\n",
              "* **Probabilistic reasoning** - a framework for managing our beliefs and knowledge. \n",
              "* **Sample space** - possible worlds and it is mutually exclusive and collectively exhaustive\n",
              "* **Random variable** - some aspect of the world about which we may have uncertainty.\n",
              "* **Probabilistic model** - is a joint distribution over a set of random variables\n",
              "* **Marginal distribution** - combined sub-tables that eliminate variables by summing-out.\n",
              "* **Model based** - learn based on experience and solve if what agent learned was correct. Creating an empirical MDP and then solving using value iteration or policy iteration as before.\n",
              "* **Model free learning** - along for the ride, take actions in the real world and learn from experience\n",
              "* **Probabilistic inference** - compute desired probability from other known probabilities\n",
              "* **Inference by enumeration** - 1. Select entries consistent with evidence, 2.Sum out to get joint of query and evidence, 3.Normalize\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 36,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"Use chain rule to calculate the joint probability of words in sentence. \n",
        "N-gram models is insufficient model of language because language has long-distance dependencies. \n",
        "\\n\n",
        "Every variable in a Bayes net is independent of all of its descendants given its parents.\n",
        "\\n\n",
        "locally structured sparse systems grow linearly in complexity rather than exponentially. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Laziness\": \"too much work to come up with a rule and too hard to use that rule\",\n",
        "\"Theoretical Ignorance\": \"medical science has no complete theory for the domain\",\n",
        "\"Practical Ignorance\": \"Even if we know all the rules, we maybe too uncertain about a particular patient because not all the necessary tests have been or can be run. \",\n",
        "\"Probability theory\": \"dealing with an agent’s degree of belief\",\n",
        "\"Ontological commitments\": \"logic and probability theory are the same in that the world is composed of facts that do or do not hold in any particular case. \",\n",
        "\"Epistemological commitments\": \"logic and prob theory are different in that a logical agent may believe each sentence to be true or false, whereas a probabilistic agent may have numerical degree of belief between 0 and 1. \",\n",
        "\"Utility theory\": \"every state has a degree of usefulness, or utility, to an agent and that the agent will prefer states with higher utility. The utility of a state is relative to an agent. \",\n",
        "\"Decision theory\": \"probability theory + utility theory    \",\n",
        "\"Factored representations\": \"in which a possible world is represented by a set of variable/value pairs.\",\n",
        "\"Language model\": \"computes the probability of a sentence or a sequence or an upcoming word.\",\n",
        "\"Markov assumption\": \"current relies only on previous K word and not the whole context\"\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 37,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "e09bf2da-bc77-444d-8d62-b9d374e49bed"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'Practical Ignorance' is too long!\n",
              "WARNING: Your definition of 'Ontological commitments' is too long!\n",
              "WARNING: Your definition of 'Epistemological commitments' is too long!\n",
              "WARNING: Your definition of 'Utility theory' is too long!\n",
              "# Module 10: Probabilies and Language Models\n",
              "## AIMA Chapter 12.1 Acting under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.2 Basic Probability Notation\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.4 Independence\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.6 Naive Bayes Models\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.1 N-Grams\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.2 Evaluating Language Models\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.3 Sampling sentences from a language model\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.4 Generalization and Zeros\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.5 Smoothing\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
              " Your summary here \n",
              "\n",
              "## Module 10 Lecture Notes\n",
              "Use chain rule to calculate the joint probability of words in sentence. \n",
              "N-gram models is insufficient model of language because language has long-distance dependencies. \n",
              "\n",
              "\n",
              "Every variable in a Bayes net is independent of all of its descendants given its parents.\n",
              "\n",
              "\n",
              "locally structured sparse systems grow linearly in complexity rather than exponentially. \n",
              "\n",
              "\n",
              "## Module 10 Definitions\n",
              "* **Laziness** - too much work to come up with a rule and too hard to use that rule\n",
              "* **Theoretical ignorance** - medical science has no complete theory for the domain\n",
              "* **Practical ignorance** - Even if we know all the rules, we maybe too uncertain about a particular patient because not all the necessary tests have been or can be run. \n",
              "* **Probability theory** - dealing with an agent’s degree of belief\n",
              "* **Ontological commitments** - logic and probability theory are the same in that the world is composed of facts that do or do not hold in any particular case. \n",
              "* **Epistemological commitments** - logic and prob theory are different in that a logical agent may believe each sentence to be true or false, whereas a probabilistic agent may have numerical degree of belief between 0 and 1. \n",
              "* **Utility theory** - every state has a degree of usefulness, or utility, to an agent and that the agent will prefer states with higher utility. The utility of a state is relative to an agent. \n",
              "* **Decision theory** - probability theory + utility theory    \n",
              "* **Factored representations** - in which a possible world is represented by a set of variable/value pairs.\n",
              "* **Language model** - computes the probability of a sentence or a sequence or an upcoming word.\n",
              "* **Markov assumption** - current relies only on previous K word and not the whole context\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" •\tBayesian network: Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely.\n",
        "BN is a directed graph and the topology signifies the conditional dependence relationshipe \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Cons of MLE: handles unknown values poorly and assigns 0 to all sentences containing it. \\n \n",
        "•\tWhy do we do everything in log space? \\n\n",
        "  o\tAvoid underflow when values get super small \\n\n",
        "  o\tAdding is faster than multiplying \\n\n",
        "•\tX and Y are independent if P(x,y) = P(x)P(y) \\n\n",
        "•\tX and Y are conditionally independent given Z if P(x, y|z) = P(x|z)P(y|z) or P(x|z,y) = P(x|z)\\n\n",
        "•\tAny complex examples can be broken into repetitions of the three canonical cases \\n\n",
        "•\tX and Y are conditionally independent given Z if X and Y are d-separated by Z and there are no active paths. \\n\n",
        "o\tA path is active if each triple is active, all it takes to block a path is a single inactive segment. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Absolute independence\": \"rare and doesn’t provide help when making inference on the variables.\",\n",
        "\"Bayes’ Nets assumption\": \"probability of Xi is only conditional not on all the preceding variables, but only on its parents\",\n",
        "\"D-separation\": \"a condition / algorithm for studying the independence properties for triples and analyzing complex cases in terms of member \\n triples. We are using the bayes nets assumption here when expanding using chain rule and using the immediate parent before. \",\n",
        "\"Causal chain\":\"if there is one then can’t be independent\",\n",
        "\"Common effect\":\"two causes resulting in the same effect. Here observing an effect activates influence between possible causes. \\n \",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 39,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 745
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "61305be2-d49b-405b-d3a7-2c8fb4141a54"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'D-separation' is too long!\n",
              "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
              "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
              " •\tBayesian network: Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely.\n",
              "BN is a directed graph and the topology signifies the conditional dependence relationshipe \n",
              "\n",
              "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
              " Your summary here \n",
              "\n",
              "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
              " Your summary here \n",
              "\n",
              "## Module 11 Lecture Notes\n",
              " Cons of MLE: handles unknown values poorly and assigns 0 to all sentences containing it. \n",
              " \n",
              "•\tWhy do we do everything in log space? \n",
              "\n",
              "  o\tAvoid underflow when values get super small \n",
              "\n",
              "  o\tAdding is faster than multiplying \n",
              "\n",
              "•\tX and Y are independent if P(x,y) = P(x)P(y) \n",
              "\n",
              "•\tX and Y are conditionally independent given Z if P(x, y|z) = P(x|z)P(y|z) or P(x|z,y) = P(x|z)\n",
              "\n",
              "•\tAny complex examples can be broken into repetitions of the three canonical cases \n",
              "\n",
              "•\tX and Y are conditionally independent given Z if X and Y are d-separated by Z and there are no active paths. \n",
              "\n",
              "o\tA path is active if each triple is active, all it takes to block a path is a single inactive segment. \n",
              "\n",
              "\n",
              "## Module 11 Definitions\n",
              "* **Absolute independence** - rare and doesn’t provide help when making inference on the variables.\n",
              "* **Bayes’ nets assumption** - probability of Xi is only conditional not on all the preceding variables, but only on its parents\n",
              "* **D-separation** - a condition / algorithm for studying the independence properties for triples and analyzing complex cases in terms of member \n",
              " triples. We are using the bayes nets assumption here when expanding using chain rule and using the immediate parent before. \n",
              "* **Causal chain** - if there is one then can’t be independent\n",
              "* **Common effect** - two causes resulting in the same effect. Here observing an effect activates influence between possible causes. \n",
              " \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 40,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "Learning agents: \\\n",
        "1.\tMap current state to actions \\\n",
        "2.\tInfer relevant properties of the world from percepts\\\n",
        "3.\tUnderstand the result of taking an action \\\n",
        "\\n\n",
        "•\tProperties of Perceptrons: \\\n",
        "    o\tSeparability: true if params get training set perfectly correct \\\n",
        "    o\tConvergence: If training is separable then perceptron will converge \\\n",
        "    o\tMistake bound: max number of mistakes is related to the margin or degree of separability \\\n",
        "mistakes<k/δ^2\n",
        "\\n\n",
        "Cons of perceptrons:\\\n",
        "\t- Noise if data isn’t separable \\\n",
        "\t- Mediocre in that in finds a barely separable solution \\\n",
        "\t- Over training:where test or hold out set peaks and then falls \\ \n",
        "\\n \n",
        "- if a binary perceptron has a high bias value, it is easier for the perceptron to output a 1. \\n\n",
        "•\tMIRA and SVMs are where we optimize over all examples at once. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"Supervised learning\": \"Agent learns off pairs of input and output data and builds a mapping function that approximates the true underlying function. The function input is factored representation like a vector of values\",    \n",
        "\"Classification\":\"output is a finite set of values (discrete)\", \n",
        "\"Regression\":\"output can be any number (continuous)\",\n",
        "\"Binary decision rule\": \"in the space of feature vectors, weight vector is a hyperplane. One side corresponds to positive label and other is negative. Update the weight vector by adding or subtracting the feature vector if y! = y*, else no change for each training instance.\",\n",
        "\"Multiclass perceptron\": \"go through training example one by one and predict with current weights. If correct, no change but if wrong, then update by adding or subtracting\",\n",
        "\"Non-linear separators\": \"data that is not linearly separable can be augmented by mapping to a higher dimensional space so it is linearly separable. \",\n",
        "\"Support Vector Machines\": \"A supervised learning model that finds the separator with max margin. \",\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 41,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "c7f53d29-9e86-46d7-e2ee-1e831d30e1e4"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'Supervised learning' is too long!\n",
              "WARNING: Your definition of 'Binary decision rule' is too long!\n",
              "# Module 12: Naive Bayes and Perceptrons\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.3 Worked Example\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.8 Test sets and Cross-validation\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.9 Statistical Significance Testing\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
              " Your summary here \n",
              "\n",
              "## Module 12 Lecture Notes\n",
              " \n",
              "Learning agents: 1.\tMap current state to actions 2.\tInfer relevant properties of the world from percepts3.\tUnderstand the result of taking an action \n",
              "\n",
              "•\tProperties of Perceptrons:     o\tSeparability: true if params get training set perfectly correct     o\tConvergence: If training is separable then perceptron will converge     o\tMistake bound: max number of mistakes is related to the margin or degree of separability mistakes<k/δ^2\n",
              "\n",
              "\n",
              "Cons of perceptrons:\t- Noise if data isn’t separable \t- Mediocre in that in finds a barely separable solution \t- Over training:where test or hold out set peaks and then falls \\ \n",
              "\n",
              " \n",
              "- if a binary perceptron has a high bias value, it is easier for the perceptron to output a 1. \n",
              "\n",
              "•\tMIRA and SVMs are where we optimize over all examples at once. \n",
              "\n",
              "\n",
              " \n",
              "\n",
              "## Module 12 Definitions\n",
              "* **Supervised learning** - Agent learns off pairs of input and output data and builds a mapping function that approximates the true underlying function. The function input is factored representation like a vector of values\n",
              "* **Classification** - output is a finite set of values (discrete)\n",
              "* **Regression** - output can be any number (continuous)\n",
              "* **Binary decision rule** - in the space of feature vectors, weight vector is a hyperplane. One side corresponds to positive label and other is negative. Update the weight vector by adding or subtracting the feature vector if y! = y*, else no change for each training instance.\n",
              "* **Multiclass perceptron** - go through training example one by one and predict with current weights. If correct, no change but if wrong, then update by adding or subtracting\n",
              "* **Non-linear separators** - data that is not linearly separable can be augmented by mapping to a higher dimensional space so it is linearly separable. \n",
              "* **Support vector machines** - A supervised learning model that finds the separator with max margin. \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 42,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"3 common linear activation functions used: 1) sigmoid, 2) tanh 3)Rectified linear unit ReLU \\n \n",
        "• Sigmoid function maps the output into the range \\[0, 1] and it is differentiable. \\n\n",
        "•The tanh function is a variant of the sigmoid function and maps\n",
        "outlier values toward the mean.\t\\n\n",
        "• The result of ReLU for negative numbers is NOT the same as a linear function. \\n\n",
        "\\n \n",
        "The naïve Bayes assumption takes all features to be independent given the class label \\n\n",
        "•\tStochastic gradient descent:algorithm we use to minimize the loss function.  \\n\n",
        "    o\tChooses a single random example at a time and updates  \\n\n",
        "•\tBatch training: opposite of stochastic where it computes gradient of the entire data set. Give better estimate but takes longer to compute.  \\n\n",
        "    o\tCompromise with mini-batch by training on a small sample \\n\n",
        "•\tLoss is higher if prediction is incorrect \\n\n",
        "In neural networks, nonlinear activation functions: \n",
        " - Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable.\\n\n",
        " - Help to learn nonlinear decision boundaries.\n",
        "\\n \n",
        "Cross entropy: is an upper bound on the entropy. The more accurate a model is, the lower the cross entropy. \\n\n",
        "The stationary distribution of a Markov chain describes the distribution of Xt after a sufficiently long time that the distribution of Xt does not change any longer.\\n\n",
        "\\n \n",
        "A perceptron coverges to a minimum-error solution when the learning rate decreases as training time increases. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"XOR problem\": \"a single neural until cannot be used to compute the XOR function. We need one doing AND & the other doing OR\",\n",
        "\"Activation function\": \"instead of using a linear function of x, neuron units apply a non-linear function. For a multi-layer NN, we use a non-linear activation function because if we used a linear function the resulting network would be equivalent to a single-layer network.\",\n",
        "\"Bag-of-words\": \"model insensitive to word order or reordering and each position is identically distributed. All positions also share the same conditional probability P(W|Y). \",\n",
        "\"Laplace smoothing\": \"pretend we saw every outcome once more than we actually did.\",\n",
        "\"Parameters\": \"Probabilities P(X|Y) and P(Y)\",\n",
        "\"Hyperparameters\": \"the amount/ type of smoothing to do and tuning k, alpha values\",\n",
        "\"Objective function/ loss function\": \"tells us the distance between the system outout and goal output.\",\n",
        "\"Decision boundary\": \"the threshold where if the P is higher than we say yes otherwise no on a test instance.\",\n",
        "\"Gradient descent\": \"is a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction.\",\n",
        "\"Convex loss function\": \"has just one minimum so no local minima to get stuck on \",\n",
        "\"Regularization\": \"a way to penalize large weights and added to the loss function\",\n",
        "\"Softmax function\": \"generalization of the sigmoid function. Normalizes the output and turns it into a probability distribution.\",\n",
        "\"parametric models\" : \" a model in which all its information is represented within its parameters. A parametric model has a fixed size on the number of parameters.\",\n",
        "\"non-parametric models\": \"on-parametric models will frequently incorporate continuous values and are described as having infinite dimensions\",\n",
        "\"agglomerative clustering\": \", each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration.\",\n",
        "\"error backpropogation\": \"enables us to correctly update all layers in a NN\"\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 43,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "97b2f3f7-27e2-4c64-f199-4447c6d345eb"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'Activation function' is too long!\n",
              "WARNING: Your definition of 'Gradient descent' is too long!\n",
              "# Module 13: Neural Networks\n",
              "## SLP Chapter 5.1 Classification: the sigmoid\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.2 Learning in Logistic Regression\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.3 The cross-entropy loss function\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.4 Gradient Descent\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.5 Regularization\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.6 Multinomial logistic regression\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.1 Units\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.2 The XOR problem\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.3 Feedforward Neural Networks\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.6 Training Neural Nets\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.7 Training the neural language model\n",
              " Your summary here \n",
              "\n",
              "## Module 13 Lecture Notes\n",
              "3 common linear activation functions used: 1) sigmoid, 2) tanh 3)Rectified linear unit ReLU \n",
              " \n",
              "• Sigmoid function maps the output into the range \\[0, 1] and it is differentiable. \n",
              "\n",
              "•The tanh function is a variant of the sigmoid function and maps\n",
              "outlier values toward the mean.\t\n",
              "\n",
              "• The result of ReLU for negative numbers is NOT the same as a linear function. \n",
              "\n",
              "\n",
              " \n",
              "The naïve Bayes assumption takes all features to be independent given the class label \n",
              "\n",
              "•\tStochastic gradient descent:algorithm we use to minimize the loss function.  \n",
              "\n",
              "    o\tChooses a single random example at a time and updates  \n",
              "\n",
              "•\tBatch training: opposite of stochastic where it computes gradient of the entire data set. Give better estimate but takes longer to compute.  \n",
              "\n",
              "    o\tCompromise with mini-batch by training on a small sample \n",
              "\n",
              "•\tLoss is higher if prediction is incorrect \n",
              "\n",
              "In neural networks, nonlinear activation functions: \n",
              " - Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable.\n",
              "\n",
              " - Help to learn nonlinear decision boundaries.\n",
              "\n",
              " \n",
              "Cross entropy: is an upper bound on the entropy. The more accurate a model is, the lower the cross entropy. \n",
              "\n",
              "The stationary distribution of a Markov chain describes the distribution of Xt after a sufficiently long time that the distribution of Xt does not change any longer.\n",
              "\n",
              "\n",
              " \n",
              "A perceptron coverges to a minimum-error solution when the learning rate decreases as training time increases. \n",
              "\n",
              "\n",
              "\n",
              "## Module 13 Definitions\n",
              "* **Xor problem** - a single neural until cannot be used to compute the XOR function. We need one doing AND & the other doing OR\n",
              "* **Activation function** - instead of using a linear function of x, neuron units apply a non-linear function. For a multi-layer NN, we use a non-linear activation function because if we used a linear function the resulting network would be equivalent to a single-layer network.\n",
              "* **Bag-of-words** - model insensitive to word order or reordering and each position is identically distributed. All positions also share the same conditional probability P(W|Y). \n",
              "* **Laplace smoothing** - pretend we saw every outcome once more than we actually did.\n",
              "* **Parameters** - Probabilities P(X|Y) and P(Y)\n",
              "* **Hyperparameters** - the amount/ type of smoothing to do and tuning k, alpha values\n",
              "* **Objective function/ loss function** - tells us the distance between the system outout and goal output.\n",
              "* **Decision boundary** - the threshold where if the P is higher than we say yes otherwise no on a test instance.\n",
              "* **Gradient descent** - is a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction.\n",
              "* **Convex loss function** - has just one minimum so no local minima to get stuck on \n",
              "* **Regularization** - a way to penalize large weights and added to the loss function\n",
              "* **Softmax function** - generalization of the sigmoid function. Normalizes the output and turns it into a probability distribution.\n",
              "* **Parametric models** -  a model in which all its information is represented within its parameters. A parametric model has a fixed size on the number of parameters.\n",
              "* **Non-parametric models** - on-parametric models will frequently incorporate continuous values and are described as having infinite dimensions\n",
              "* **Agglomerative clustering** - , each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration.\n",
              "* **Error backpropogation** - enables us to correctly update all layers in a NN\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 44,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\t\n",
        "- Smoothness of sigma means that small change in weight and bias will produce a small change in output from neuron. \\n\n",
        "- Derivative of output will result in a linear function explaining change in weight and bias. \\n\n",
        "- Feed-forward NN: 1) Multilayer, 2) Fully connected 3) No cycles \\n\n",
        "- Calculate hidden layers using sigmoid function h=σ(Wx+b) \\n\n",
        "- Training NN: 1) a loss function 2) an optimization algorithm 3) way of computing the gradient of the loss function. \n",
        "- Neural Language Models: \n",
        "1.\tDon’t need smoothing\n",
        "2.\tCan handle longer histories\n",
        "3.\tCan generalize over context of similar words\n",
        "4.\tHigher pred accuracy than n-grams\n",
        "\\n\n",
        "- Cosine angle between vectors tells us their similarity \\n\n",
        "- Embeddings capture relational meaning; capturing similarity or analogy and can use both a sparse model or a dense model. Useful in practice but encode cultural stereotype. \\n\n",
        "\n",
        "•\tContext is represented by embeddings so can treat cat and dog in a similar manner \\n\n",
        "•\tInput:k-grams of words \\n\n",
        "•\tOutput:probability distribution over next word \\n\n",
        "•\tK context is treated as window and each word is associated with an embedding vector.  \\n\n",
        "•\tCurse of dimensionality: there are too many parameters to accurately predict  \\n\n",
        "• This vector representation could only compare words that have similar meaning, but it cannot handle the problem that single word has multiple meanings (polysemy). \\n\n",
        "• n-gram model for a corpus with a vocabulary of size V and a total of T tokens. The running time is n and T\n",
        "N-gram models used for generation draw the next word at random (proportional to their conditional probability tables). If a word doesn't occur with the context in training, then it isn't included in its conditional probability table and therefore won't be generated.\n",
        "These models are evaluated on a test set. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"Polysemy\": \"word that has multiple meaning \",\n",
        "\"Word sense disambiguation\": \"task of understanding which sense of a word is being used in a context\",\n",
        "\"Semantic field\": \"a set of words which cover a semantic domain and bear structured relation with each other.\",\n",
        "\"Term doc matrix\":\"each term on rows and doc labels on columns; value is how often the term occurred. Row size is the vocabulary size.\",\n",
        "\"TF-IDF (sparse)\": \"how often a word occurred in a document over the number of documents that it occurred in.\",\n",
        "\"Word2Vec (dense)\": \"popular embedding method, fast to learn and predicts rather than counts. \",\n",
        "\"Turning dot product into a probability\":\"throw it into the sigmoid curve\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 45,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "cd1c8853-3b4f-436c-9028-ca2380ad8c15"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 14: Natural Language Processing\n",
              "## SLP Chapter 9.1 Language Models Revisited\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 9.2 Recurrent Neural Networks\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 9.3 RNNs as Language Models\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.1 Lexical Semantics\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.2 Vector Semantics\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.3 Words and Vectors\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.4 Cosine for measuring similarity\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.8 Word2vec\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.10 Semantic properties of embeddings\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.11 Bias and Embeddings\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.12 Evaluating Vector Models\n",
              " Your summary here \n",
              "\n",
              "## Module 13 Lecture Notes\n",
              "\t\n",
              "- Smoothness of sigma means that small change in weight and bias will produce a small change in output from neuron. \n",
              "\n",
              "- Derivative of output will result in a linear function explaining change in weight and bias. \n",
              "\n",
              "- Feed-forward NN: 1) Multilayer, 2) Fully connected 3) No cycles \n",
              "\n",
              "- Calculate hidden layers using sigmoid function h=σ(Wx+b) \n",
              "\n",
              "- Training NN: 1) a loss function 2) an optimization algorithm 3) way of computing the gradient of the loss function. \n",
              "- Neural Language Models: \n",
              "1.\tDon’t need smoothing\n",
              "2.\tCan handle longer histories\n",
              "3.\tCan generalize over context of similar words\n",
              "4.\tHigher pred accuracy than n-grams\n",
              "\n",
              "\n",
              "- Cosine angle between vectors tells us their similarity \n",
              "\n",
              "- Embeddings capture relational meaning; capturing similarity or analogy and can use both a sparse model or a dense model. Useful in practice but encode cultural stereotype. \n",
              "\n",
              "\n",
              "•\tContext is represented by embeddings so can treat cat and dog in a similar manner \n",
              "\n",
              "•\tInput:k-grams of words \n",
              "\n",
              "•\tOutput:probability distribution over next word \n",
              "\n",
              "•\tK context is treated as window and each word is associated with an embedding vector.  \n",
              "\n",
              "•\tCurse of dimensionality: there are too many parameters to accurately predict  \n",
              "\n",
              "• This vector representation could only compare words that have similar meaning, but it cannot handle the problem that single word has multiple meanings (polysemy). \n",
              "\n",
              "• n-gram model for a corpus with a vocabulary of size V and a total of T tokens. The running time is n and T\n",
              "N-gram models used for generation draw the next word at random (proportional to their conditional probability tables). If a word doesn't occur with the context in training, then it isn't included in its conditional probability table and therefore won't be generated.\n",
              "These models are evaluated on a test set. \n",
              "\n",
              "\n",
              "## Module 14 Definitions\n",
              "* **Polysemy** - word that has multiple meaning \n",
              "* **Word sense disambiguation** - task of understanding which sense of a word is being used in a context\n",
              "* **Semantic field** - a set of words which cover a semantic domain and bear structured relation with each other.\n",
              "* **Term doc matrix** - each term on rows and doc labels on columns; value is how often the term occurred. Row size is the vocabulary size.\n",
              "* **Tf-idf (sparse)** - how often a word occurred in a document over the number of documents that it occurred in.\n",
              "* **Word2vec (dense)** - popular embedding method, fast to learn and predicts rather than counts. \n",
              "* **Turning dot product into a probability** - throw it into the sigmoid curve\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ]
    },
    {
      "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",
      "execution_count": 46,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "de40469e-5042-4243-e044-0513c6ecfe36"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your summary of 'AIMA Chapter 17.2 Algorithms for MDPs' is too long!\n",
              "## WARNING: Your definition of 'Continuity' is too long!\n",
              "WARNING: Your definition of 'Discounting' is too long!\n",
              "# Module 8: Markov Decision Processes\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Agent assigns probability to each possible state. When agent is uncertain about the outcome of taking an action, calculate probability using\n",
              "P(Result(a)=s^' )=∑P(s)P(s^'│s,a).\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",
              "Writing down constraints for rational agent and showing that MEU can be derived from it.\n",
              "Think of set of outcomes (S) for each action as a lottery L\n",
              "L=[p_1,S_1;p_2,S_2;…;p_n,S_n]\n",
              "Each S can be an atomic state or another Lottery \n",
              "For utility theory, we want to understand how the agent’s preference for a complex lottery is related to the preferences between the underlying states in those lotteries.\n",
              "\n",
              "\n",
              " Rational Preference Lead to Utility\n",
              "•\tExpected Utility of a Lottery: sum of the probability of each outcome times the utility of the outcome.\n",
              "U([p1, S1;…; pn, Sn]) =Σ i piU(Si).\n",
              "•\tValue function or ordinal utility function: in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "16.3 Utility Functions\n",
              "\tMap from lotteries to real numbers\n",
              "16.3.1 Utility assessment and utility scales\n",
              "\tPreference elicitation: presenting choices to the human and using the observed preferences to pin down the underlying utility function. \n",
              "\tCreate a measure for utility by first creating a scale that identifies the best and worst possible outcomes. \n",
              "\tNormalized utilities: uses a scale between 0 to 1.\n",
              "\tMicromort: one in a million chance of death\n",
              "16.3.2 The utility of money \n",
              "\tUtility is not directly proportional to monetary value because the utility of first million received is very high compared to the utility of additional money received. \n",
              "16.3.3 Expected utility and post-decision disappointment\n",
              "\tRational decision making means maximizing expected utility\n",
              "a*=argmax a EU(a)\n",
              "\tUnbiased estimate: expected value of the error is zero.\n",
              "\tOptimizer’s curse: believing that something that worked in 80% of the sample will work exactly with that efficacy in the population.\n",
              "\tAvoid this by taking a Bayesian approach that uses an explicit probability model\n",
              "16.3.4 human judgement and irrationality \n",
              "\tNormative theory: it describes how a rational agent should act.\n",
              "\tDescriptive theory: describes how actual agents really do act.\n",
              "\tFraming effect: framing the way someone states probabilities has an impact on decision making. \n",
              "\tAnchoring effect: people having an easier time making relative judgement instead of absolute ones. \n",
              "\n",
              "\n",
              "## AIMA Chapter 17.1 Sequential Decision Problems\n",
              "\tMarkovian: the probability of reaching s’ from s depends only on s and not on the history of the earlier states. \n",
              "\tEnvironment history: When a decision problem is sequential, the utility function depends on a sequence of states and actions rather than a single state. \n",
              "\tMarkovian decision process: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards.\n",
              "\tPolicy: a solution that specify what the agent should do for any state that the agent might reach.\n",
              "\tProper Policy: a policy that is guaranteed to reach a terminal state \n",
              "\tThe introduction of uncertainty beings MDPs closer to real world than deterministic search problems. \n",
              "\tFinite horizon: there is a fixed time N after which nothing matter:the game is over. \n",
              "\tNonstationary: A policy that depends on the time. \n",
              "\tInfinite horizon: doesn’t mean that all state sequences are infinite and instead it means that there is no fixed deadline. \n",
              "\tWhen there are no fixed time limits, there is no reason to behave differently in the same state during different point in time. \n",
              "\tAdditive discounted rewards: the utility of a history is where the discounted factor is a number between 0 and 1. This discount factor describes the preference of an agent for current rewards over future rewards. \n",
              "\t1 discount reward: agent is willing to wait completely for long-term rewards.\n",
              "\t0 discount reward: rewards in the future are deemed insignificant.\n",
              "\tA way to handle infinities in the cases the agent never reaches terminal states.\n",
              "\tThe utility of a state is the expected reward for the next transition plus the discounted utility of the next state:\n",
              "\tBellman Equation: U(s)=max∑_s^'▒〖P(S^'│S,a)R(S,a,s^' )+γU(s')〗 \n",
              "\tQ-function: action-utility function or Q(s,a) is the expected utility of taking a given action in a given state. \n",
              "\tUtility: U(s) = max_a⁡〖Q(s,a)〗\n",
              "\tPolicy: π^* (s)=argmax_a Q(s,a)\n",
              "\tBellman: Q(s,a)=∑_s^'▒〖P(s^'│s,a)[R(s,a,s^' )+ γ U(s^' )] 〗 = ∑_s^'▒〖P(s'|s,a)[R(s,a,s') +γ max_a^'⁡Q(s^',a^' ) 〗\n",
              "\tSolving for U or Q lets us find the optimal policy \n",
              "\n",
              "\n",
              "## AIMA Chapter 17.2 Algorithms for MDPs\n",
              "\tValue Iteration: bellman equation is the basis of this. \n",
              "\tFor n possible states, there are n bellman equations \n",
              "\tEach iteration step is called bellman update\n",
              "\tContraction: Value iteration eventually converges to a unique set of solutions of  the bellman equations. \n",
              "\tContraction has one fixed point and it is part of the proof of convergence for value iteration. \n",
              " \n",
              "\tWhen the function is applied to any argument, the value must get closer together. \n",
              "\tValue iteration converges exponentially fast \n",
              "\tBellman update is a contraction by a factor gamma on the space of utility factor \n",
              "\tWe can use the utility factor to understand the rate of convergence \n",
              "\tRun N iterations to reach an error of at most ϵ \n",
              "\tWe can use the error and make a prediction on the number of iterations needed. \n",
              "\tWe can use |(|U_i-U|)| as the error\n",
              "\tthe estimate above can be used for a termination condition: If |(|U_(i+1)-U_i |)|<ϵ(1-γ)/γ,then |(|U_(i+1)-U|)|<ϵ  \n",
              "\tPolicy loss is U^*-U is the most agent can lose by executing a policy \n",
              "\tPolicy may become optimal way before U_i has converged. \n",
              "\tWe can bound the error in the utility estimates if we stop after a finite number of iterations. \n",
              "\tPolicy Iteration\n",
              "\tAlgorithm: iteration between two steps, beginning from some random policy and then calculate the utility of each state to be executed. Improve this policy by using one-step look-ahead and calculate a new policy for the next step.\n",
              "\tPolicy iteration: given a policy π, calculate u_i=u^π, the utility of each state given policy. \n",
              "\tPolicy improvement: calculate a new MEU policy π_(i+1), using one step look ahead based on U_i\n",
              "\tWhy must policy iteration terminate?\n",
              "\tBecause there are only finitely many policies for a finite space, and each iteration can be seen to show a better policy, iteration must terminate. \n",
              "\tImplementation is easier than solving the bellman equation. \n",
              "\tRun time: O(n^3 )\n",
              "\tFor n linear equations, there are n unknowns and using systems of equations, we can solve it in the aforementioned time.\n",
              "\tSmall state space: use this over the value iteration method. \n",
              "\tAsynchronous policy iteration: pick any subset of states and at each iteration either perform value iteration or policy iteration.\n",
              "\tWe can use this to plan better by only concentrating on updating the values of states that will be reached by a good policy, instead of planning for all states.\n",
              "\tLinear programming is solvable in polynomial time, so MDPs an also be solved in polynomial time.\n",
              "\tLP is less efficient when compared to dynamic programming when solving for MDPs.\n",
              "\tOnline algorithms for MDPs\n",
              "\tValue and policy are offline algorithms\n",
              "\tGenerate an optimal solution for the problem, which can be executed by a simple agent.\n",
              "\tFor large MDPs, like Tetris, offline solution even in polynomial time is not possible \n",
              "\tExpectimax algorithm:build a tree of alternating max and chance nodes. \n",
              "\tEvaluation function to be applied to non-terminal leaves of the tree or provide a default value. \n",
              "\tExtract a decision by backing up the utility values from the leaves where average the chance nodes and make max of the decision nodes. \n",
              "\tWe can bound the expectimax tree depth if we know what the absolute value of the error for the tree should be. \n",
              "\tAlso handle the potentially large branching factors at the chance nodes\n",
              "\tUCT (uses real time dynamic programming) has the lower average reward than the optimal policy reward because it is using a tree rather than a graph. \n",
              "\tBetter for solving a large decision space like Tetris because the agent can go into the future to get a sense of whether potentially risky move is worth it. \n",
              " \n",
              "\n",
              "## Module 8 Lecture Notes\n",
              "\t\n",
              "\n",
              "\n",
              "## Module 8 Definitions\n",
              "* **Utility function** - agent’s preference is captured by a utility function, which assigns a single number to express the desirability of a state (U(s)).\n",
              "* **Expected utility** - expected utility of an action given the evidence is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n",
              "* **Decision theory** - choosing among actions based on the desirability of their immediate outcomes.\n",
              "* **Principle of meu** -  maximum expected utility says that a rational agent should choose the action that maximized the agent’s expected utility.\n",
              "* **Rational preferences** - imply behaviour describable as maximization of expected utility\n",
              "* **Preference relation constraints** - 1. Orderability \n",
              "\n",
              "2. Transitivity \n",
              "\n",
              "3. Continuity \n",
              "\n",
              "4. Substitutability \n",
              "\n",
              "5. Monotonocity \n",
              "\n",
              "6. Decomposability: \n",
              "\n",
              "* **Orderability** - when given two lotteries, agent must prefer one over the other or prefer both equally.\n",
              "* **Transitivity** - given 3 Ls, if agent prefers A over B and prefers B over C, then agent will prefer A over C\n",
              "* **Continuity** - if the preference is A > B > C, then there is some probability where the agent is indifferent between getting B for sure and the lottery that yields A with prob p and C with prob 1-p.\n",
              "* **Substitutability** - if an agent is indifferent between two lotteries, then they are indifferent with two complex lotteries where A or B occur with the same probability\n",
              "* **Monotonocity** - If an agent prefers A to B, then agent must also prefer the lottery that has a higher probability of A occurring over B.\n",
              "* **Decomposability** - compressing two consecutive lotteries into a single equivalent lottery.\n",
              "* **Preference elicitation** - presenting choices to the human and using the observed preferences to pin down the underlying utility function\n",
              "* **Finite vs. infinite horizon** - agent’s optimal action will depend on how much time is left.\n",
              "* **Discounting** - preferring a reward now over later. When discount is 1, all the rewards are preferred now,\n",
              "\n",
              "and when it is 0 all the rewards are preferred in the future. This helps converge the algorithm.\n",
              "* **Stationary preference** - policy that only depends on current state. Can only use additive \n",
              "or discounted utilities for these.\n",
              "* **Stationary process** - the conditional probability table does not change over time\n",
              "* **Absorbing state** - guarantee that for every policy a terminal state will eventually by reached.\n",
              "* **Value iteration** - Given a vector V_k (s), do one ply of expectimax from each state. Repeat until converges.\n",
              "* **Bellman equations** - take correct first action and then keep being optimal.\n",
              "* **Policy extraction** - getting the policy implied by the values\n",
              "* **Worst-case vs. avg case minimax reasoning** - \n",
              "•\tFor worst-case minimax reasoning the scale of the terminal function doesn’t matter, just their ranking does.\n",
              "•\tFor average-case, we need the magnitude to be meaningful\n",
              "\n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'Model based' is too long!\n",
              "# Module 9: Reinforcement Learning\n",
              "## AIMA Chapter 17.3 Bandit Problems\n",
              " \tN-armed bandit: has n-levers in a slot machine and each lever is a fixed by unknown probability distribution of winnings. Each pull samples from that unknown distribution. \n",
              "\tGambler’s choice is to pick which lever to pull:one that have given the best outcome or one that hasn’t been tried yet. \n",
              "\tAbove is the exploration vs. exploitation trade-off \n",
              "\tCost is the cost of not pulling the remaining levers. \n",
              "\tGittins index: measure of reward that can be achieved through a given stochastic process with certain properties. \n",
              "\tThe Bernoulli bandit: each arm M_i produces a reward of 0 or 1 with fixed but unknown probability of μ_i. \n",
              "\tThe state of each arm M_i is defined by s_i and f_i\n",
              "\tTransition prob = 1: s_i/(s_i+f_i )\n",
              "\tTransition prob = 0: f_i/(s_i+f_i ) \n",
              "\tUpper Confidence Bound: use a sample from each arm to establish a CI for the value of that arm\n",
              "\tThompson sampling: chooses an arm randomly according to probability that it is a successful arm given the samples so far. \n",
              "\tSelection problems: choosing best option under certain constraints as fast as possible. \n",
              " \n",
              "\n",
              "## AIMA Chapter 22.1 Learning from Rewards\n",
              " •\tReinforcement learning: agent interacts with the world and periodically receives rewards that reflect how well it is doing.  \n",
              "\n",
              "•\tModel based RL: agent uses a transition model to help interpret the reward signals and to make decisions on how to act.  \n",
              "\n",
              "•\tModel free: agent learns a direct representation of how to behave \n",
              "\n",
              "    o\tAction-utility: Q learning where sum of rewards is taken from state s onward if action a is taken.  \n",
              "\n",
              "    o\tPolicy search: agent learns a policy that maps directly from states to action. Also known as a reflex agent.   \n",
              "\n",
              "•\tPassive RL: agent’s policy is fixed and task is to learn the utilities of states. Agent is given all the states it can reach and the policy it can follow. \n",
              "\n",
              "•\tActive RL: agent must figure out what to do and using exploration they can do so.  \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
              " •\tSimilar to policy evaluation step from policy iteration. \n",
              "\n",
              "•\tAgent does not know the transition model which specifies the probability of reaching s’ from s after doing a. \n",
              "\n",
              "•\tAgent does not know the reward function\n",
              "\n",
              "•\tAgent executes a set of trials \n",
              "\n",
              "•\tDirect utility estimation: is the expected total required from that state onward. Doesn’t understand connections between states so misses opportunity to learn and converges slowly.\n",
              "\n",
              "•\tAdaptive Dynamic programming: takes advantage of the constraints among utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming. \n",
              "\n",
              "•\tModified policy iteration: using a simplified value iteration process to update utility estimates after each change to the learned model. \n",
              "\n",
              " \n",
              "\n",
              "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
              " Your summary here \n",
              "\n",
              "## Module 9 Lecture Notes\n",
              " \n",
              "•\tSolving MDPs is offline planning because we determine all quantities through computation and don’t actually have to play the game. \n",
              "\n",
              "•\tIn reinforcement learning, we are online because we learn as we play\n",
              "\n",
              "    o\tExploration: try unknown and get info \n",
              "\n",
              "    o\tExploitation: use what we know to make decisions\n",
              "\n",
              "    o\tRegret: even if you learn intelligently you make mistakes. Regret lets us quantify the relative goodness of exploration procedures\n",
              "\n",
              "    o\tSampling: because of change, try things repeatedly \n",
              "\n",
              "    o\tDifficulty:learning can be much harder than solving a known MDP\n",
              "\n",
              "•\tIn RL, feedback is received as reward and agent is trying to maximize reward.\n",
              "\n",
              "•\tAgent doesn’t know T or R\n",
              "\n",
              "•\tModel based: learn based on experience and solve if what agent learned was correct. Creating an empirical MDP and then solving using value iteration or policy iteration as before. \n",
              "\n",
              "•\tModel free learning: along for the ride, take actions in the real world and learn from experience. \n",
              "\n",
              "•\tDirect evaluation: compute values for each state under policy and average together observed sample values \n",
              "\n",
              "    o\tPros: easy to get, don’t need T or R, and eventually computes the correct avg value\n",
              "\n",
              "    o\tCons: wastes info about state connections as each state is learned separately. Takes a long time to learn. \n",
              "\n",
              "•\tSample based policy evaluation: average the values based on a sample of outcomes by taking certain actions. \n",
              "\n",
              "•\tTemporal difference learning: learn from every experience and update the V each time transition is experienced. Still using a fixed policy evaluation. \n",
              "\n",
              "    o\tExponential moving avg: emphasize values from more recent samples as avg. \n",
              "\n",
              "    o\tLearn Q-values not values because we don’t have a great time turning the updated values into a new policy. \n",
              "\n",
              "•\tActive RL: online model, take actions on the world. \n",
              "\n",
              "• In RL, a deterministic policy is a mapping from states to actions. \n",
              "\n",
              "•\tQ-learning: converges to optimal policy even if you are acting sub optimally.\n",
              "\n",
              "    o\tOff-policy learning \n",
              "\n",
              "    o\tHave to explore enough\n",
              "\n",
              "    o\tHave to eventually make the learning rate small enough \n",
              "\n",
              "•\tAgent exploration: \n",
              "\n",
              "    o\tRandom (epsilon-greedy) : large e, act on current vs. small e take random action. As we learn more, we increase e so we can move from exploration to exploitation. \n",
              "\n",
              "    o\tExplore where badness isn’t established by giving a bonus to states that lead to unknown states. \n",
              "\n",
              " \n",
              "\n",
              "•\tApproximate Q-value: basic version wants us to keep a table of all Q values but we cannot learn about every state. So generalize by keeping a small number of training states from experience. \n",
              "\n",
              "•\tLinear Value Functions: using a feature representation, write a q function or value function for any state using a few weights. \n",
              "\n",
              "    o\tPro: summed up experience in a few numbers\n",
              "\n",
              "    o\tCon: states may share features but the value could be very different. \n",
              "\n",
              "•\tQ-learning with linear Q-functions: if something bad happens, blame the features that were on. \n",
              "\n",
              "\t • it is not guaranteed that Q-learning with linear function approximation (weighted linear function of a set of features) will always converge to the optimal policy. For example, if Q is quadratic but the function approximator is linear.\n",
              "\n",
              "• In both adaptive dynamic programming and temporal difference learning, the utility of the state is adjusted locally to agree with the utility of at least one successor state.\n",
              " \n",
              "\n",
              "## Module 9 Definitions\n",
              "* **N-armed bandit** - has n-levers in a slot machine and each lever is a fixed by unknown probability distribution of winnings.\n",
              "* **Gittins index** - measure of reward that can be achieved through a given stochastic process with certain properties.\n",
              "* **The bernoulli bandit** - each arm M_i produces a reward of 0 or 1 with fixed but unknown probability of μ_i.\n",
              "* **Upper confidence bound** - use a sample from each arm to establish a CI for the value of that arm\n",
              "* **Thompson sampling** - chooses an arm randomly according to probability that it is a successful arm given the samples so far.\n",
              "* **Selection problems** - choosing best option under certain constraints as fast as possible.\n",
              "* **Observed vars** - are evidence where the agent knows certain things about the world\n",
              "* **Unobserved vars** - are states where agent needs to reason about other aspects \n",
              "* **Model** - agent knows something about how the known variables relate to the unknown variables\n",
              "* **Probabilistic reasoning** - a framework for managing our beliefs and knowledge. \n",
              "* **Sample space** - possible worlds and it is mutually exclusive and collectively exhaustive\n",
              "* **Random variable** - some aspect of the world about which we may have uncertainty.\n",
              "* **Probabilistic model** - is a joint distribution over a set of random variables\n",
              "* **Marginal distribution** - combined sub-tables that eliminate variables by summing-out.\n",
              "* **Model based** - learn based on experience and solve if what agent learned was correct. Creating an empirical MDP and then solving using value iteration or policy iteration as before.\n",
              "* **Model free learning** - along for the ride, take actions in the real world and learn from experience\n",
              "* **Probabilistic inference** - compute desired probability from other known probabilities\n",
              "* **Inference by enumeration** - 1. Select entries consistent with evidence, 2.Sum out to get joint of query and evidence, 3.Normalize\n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'Practical Ignorance' is too long!\n",
              "WARNING: Your definition of 'Ontological commitments' is too long!\n",
              "WARNING: Your definition of 'Epistemological commitments' is too long!\n",
              "WARNING: Your definition of 'Utility theory' is too long!\n",
              "# Module 10: Probabilies and Language Models\n",
              "## AIMA Chapter 12.1 Acting under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.2 Basic Probability Notation\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.4 Independence\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.6 Naive Bayes Models\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.1 N-Grams\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.2 Evaluating Language Models\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.3 Sampling sentences from a language model\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.4 Generalization and Zeros\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.5 Smoothing\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
              " Your summary here \n",
              "\n",
              "## Module 10 Lecture Notes\n",
              "Use chain rule to calculate the joint probability of words in sentence. \n",
              "N-gram models is insufficient model of language because language has long-distance dependencies. \n",
              "\n",
              "\n",
              "Every variable in a Bayes net is independent of all of its descendants given its parents.\n",
              "\n",
              "\n",
              "locally structured sparse systems grow linearly in complexity rather than exponentially. \n",
              "\n",
              "\n",
              "## Module 10 Definitions\n",
              "* **Laziness** - too much work to come up with a rule and too hard to use that rule\n",
              "* **Theoretical ignorance** - medical science has no complete theory for the domain\n",
              "* **Practical ignorance** - Even if we know all the rules, we maybe too uncertain about a particular patient because not all the necessary tests have been or can be run. \n",
              "* **Probability theory** - dealing with an agent’s degree of belief\n",
              "* **Ontological commitments** - logic and probability theory are the same in that the world is composed of facts that do or do not hold in any particular case. \n",
              "* **Epistemological commitments** - logic and prob theory are different in that a logical agent may believe each sentence to be true or false, whereas a probabilistic agent may have numerical degree of belief between 0 and 1. \n",
              "* **Utility theory** - every state has a degree of usefulness, or utility, to an agent and that the agent will prefer states with higher utility. The utility of a state is relative to an agent. \n",
              "* **Decision theory** - probability theory + utility theory    \n",
              "* **Factored representations** - in which a possible world is represented by a set of variable/value pairs.\n",
              "* **Language model** - computes the probability of a sentence or a sequence or an upcoming word.\n",
              "* **Markov assumption** - current relies only on previous K word and not the whole context\n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'D-separation' is too long!\n",
              "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
              "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
              " •\tBayesian network: Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely.\n",
              "BN is a directed graph and the topology signifies the conditional dependence relationshipe \n",
              "\n",
              "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
              " Your summary here \n",
              "\n",
              "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
              " Your summary here \n",
              "\n",
              "## Module 11 Lecture Notes\n",
              " Cons of MLE: handles unknown values poorly and assigns 0 to all sentences containing it. \n",
              " \n",
              "•\tWhy do we do everything in log space? \n",
              "\n",
              "  o\tAvoid underflow when values get super small \n",
              "\n",
              "  o\tAdding is faster than multiplying \n",
              "\n",
              "•\tX and Y are independent if P(x,y) = P(x)P(y) \n",
              "\n",
              "•\tX and Y are conditionally independent given Z if P(x, y|z) = P(x|z)P(y|z) or P(x|z,y) = P(x|z)\n",
              "\n",
              "•\tAny complex examples can be broken into repetitions of the three canonical cases \n",
              "\n",
              "•\tX and Y are conditionally independent given Z if X and Y are d-separated by Z and there are no active paths. \n",
              "\n",
              "o\tA path is active if each triple is active, all it takes to block a path is a single inactive segment. \n",
              "\n",
              "\n",
              "## Module 11 Definitions\n",
              "* **Absolute independence** - rare and doesn’t provide help when making inference on the variables.\n",
              "* **Bayes’ nets assumption** - probability of Xi is only conditional not on all the preceding variables, but only on its parents\n",
              "* **D-separation** - a condition / algorithm for studying the independence properties for triples and analyzing complex cases in terms of member \n",
              " triples. We are using the bayes nets assumption here when expanding using chain rule and using the immediate parent before. \n",
              "* **Causal chain** - if there is one then can’t be independent\n",
              "* **Common effect** - two causes resulting in the same effect. Here observing an effect activates influence between possible causes. \n",
              " \n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'Supervised learning' is too long!\n",
              "WARNING: Your definition of 'Binary decision rule' is too long!\n",
              "# Module 12: Naive Bayes and Perceptrons\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.3 Worked Example\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.8 Test sets and Cross-validation\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.9 Statistical Significance Testing\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
              " Your summary here \n",
              "\n",
              "## Module 12 Lecture Notes\n",
              " \n",
              "Learning agents: 1.\tMap current state to actions 2.\tInfer relevant properties of the world from percepts3.\tUnderstand the result of taking an action \n",
              "\n",
              "•\tProperties of Perceptrons:     o\tSeparability: true if params get training set perfectly correct     o\tConvergence: If training is separable then perceptron will converge     o\tMistake bound: max number of mistakes is related to the margin or degree of separability mistakes<k/δ^2\n",
              "\n",
              "\n",
              "Cons of perceptrons:\t- Noise if data isn’t separable \t- Mediocre in that in finds a barely separable solution \t- Over training:where test or hold out set peaks and then falls \\ \n",
              "\n",
              " \n",
              "- if a binary perceptron has a high bias value, it is easier for the perceptron to output a 1. \n",
              "\n",
              "•\tMIRA and SVMs are where we optimize over all examples at once. \n",
              "\n",
              "\n",
              " \n",
              "\n",
              "## Module 12 Definitions\n",
              "* **Supervised learning** - Agent learns off pairs of input and output data and builds a mapping function that approximates the true underlying function. The function input is factored representation like a vector of values\n",
              "* **Classification** - output is a finite set of values (discrete)\n",
              "* **Regression** - output can be any number (continuous)\n",
              "* **Binary decision rule** - in the space of feature vectors, weight vector is a hyperplane. One side corresponds to positive label and other is negative. Update the weight vector by adding or subtracting the feature vector if y! = y*, else no change for each training instance.\n",
              "* **Multiclass perceptron** - go through training example one by one and predict with current weights. If correct, no change but if wrong, then update by adding or subtracting\n",
              "* **Non-linear separators** - data that is not linearly separable can be augmented by mapping to a higher dimensional space so it is linearly separable. \n",
              "* **Support vector machines** - A supervised learning model that finds the separator with max margin. \n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'Activation function' is too long!\n",
              "WARNING: Your definition of 'Gradient descent' is too long!\n",
              "# Module 13: Neural Networks\n",
              "## SLP Chapter 5.1 Classification: the sigmoid\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.2 Learning in Logistic Regression\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.3 The cross-entropy loss function\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.4 Gradient Descent\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.5 Regularization\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 5.6 Multinomial logistic regression\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.1 Units\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.2 The XOR problem\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.3 Feedforward Neural Networks\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.6 Training Neural Nets\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 7.7 Training the neural language model\n",
              " Your summary here \n",
              "\n",
              "## Module 13 Lecture Notes\n",
              "3 common linear activation functions used: 1) sigmoid, 2) tanh 3)Rectified linear unit ReLU \n",
              " \n",
              "• Sigmoid function maps the output into the range \\[0, 1] and it is differentiable. \n",
              "\n",
              "•The tanh function is a variant of the sigmoid function and maps\n",
              "outlier values toward the mean.\t\n",
              "\n",
              "• The result of ReLU for negative numbers is NOT the same as a linear function. \n",
              "\n",
              "\n",
              " \n",
              "The naïve Bayes assumption takes all features to be independent given the class label \n",
              "\n",
              "•\tStochastic gradient descent:algorithm we use to minimize the loss function.  \n",
              "\n",
              "    o\tChooses a single random example at a time and updates  \n",
              "\n",
              "•\tBatch training: opposite of stochastic where it computes gradient of the entire data set. Give better estimate but takes longer to compute.  \n",
              "\n",
              "    o\tCompromise with mini-batch by training on a small sample \n",
              "\n",
              "•\tLoss is higher if prediction is incorrect \n",
              "\n",
              "In neural networks, nonlinear activation functions: \n",
              " - Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable.\n",
              "\n",
              " - Help to learn nonlinear decision boundaries.\n",
              "\n",
              " \n",
              "Cross entropy: is an upper bound on the entropy. The more accurate a model is, the lower the cross entropy. \n",
              "\n",
              "The stationary distribution of a Markov chain describes the distribution of Xt after a sufficiently long time that the distribution of Xt does not change any longer.\n",
              "\n",
              "\n",
              " \n",
              "A perceptron coverges to a minimum-error solution when the learning rate decreases as training time increases. \n",
              "\n",
              "\n",
              "\n",
              "## Module 13 Definitions\n",
              "* **Xor problem** - a single neural until cannot be used to compute the XOR function. We need one doing AND & the other doing OR\n",
              "* **Activation function** - instead of using a linear function of x, neuron units apply a non-linear function. For a multi-layer NN, we use a non-linear activation function because if we used a linear function the resulting network would be equivalent to a single-layer network.\n",
              "* **Bag-of-words** - model insensitive to word order or reordering and each position is identically distributed. All positions also share the same conditional probability P(W|Y). \n",
              "* **Laplace smoothing** - pretend we saw every outcome once more than we actually did.\n",
              "* **Parameters** - Probabilities P(X|Y) and P(Y)\n",
              "* **Hyperparameters** - the amount/ type of smoothing to do and tuning k, alpha values\n",
              "* **Objective function/ loss function** - tells us the distance between the system outout and goal output.\n",
              "* **Decision boundary** - the threshold where if the P is higher than we say yes otherwise no on a test instance.\n",
              "* **Gradient descent** - is a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction.\n",
              "* **Convex loss function** - has just one minimum so no local minima to get stuck on \n",
              "* **Regularization** - a way to penalize large weights and added to the loss function\n",
              "* **Softmax function** - generalization of the sigmoid function. Normalizes the output and turns it into a probability distribution.\n",
              "* **Parametric models** -  a model in which all its information is represented within its parameters. A parametric model has a fixed size on the number of parameters.\n",
              "* **Non-parametric models** - on-parametric models will frequently incorporate continuous values and are described as having infinite dimensions\n",
              "* **Agglomerative clustering** - , each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration.\n",
              "* **Error backpropogation** - enables us to correctly update all layers in a NN\n",
              "\n",
              "\n",
              "# Module 14: Natural Language Processing\n",
              "## SLP Chapter 9.1 Language Models Revisited\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 9.2 Recurrent Neural Networks\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 9.3 RNNs as Language Models\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.1 Lexical Semantics\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.2 Vector Semantics\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.3 Words and Vectors\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.4 Cosine for measuring similarity\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.8 Word2vec\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.10 Semantic properties of embeddings\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.11 Bias and Embeddings\n",
              " Your summary here \n",
              "\n",
              "## SLP Chapter 6.12 Evaluating Vector Models\n",
              " Your summary here \n",
              "\n",
              "## Module 13 Lecture Notes\n",
              "\t\n",
              "- Smoothness of sigma means that small change in weight and bias will produce a small change in output from neuron. \n",
              "\n",
              "- Derivative of output will result in a linear function explaining change in weight and bias. \n",
              "\n",
              "- Feed-forward NN: 1) Multilayer, 2) Fully connected 3) No cycles \n",
              "\n",
              "- Calculate hidden layers using sigmoid function h=σ(Wx+b) \n",
              "\n",
              "- Training NN: 1) a loss function 2) an optimization algorithm 3) way of computing the gradient of the loss function. \n",
              "- Neural Language Models: \n",
              "1.\tDon’t need smoothing\n",
              "2.\tCan handle longer histories\n",
              "3.\tCan generalize over context of similar words\n",
              "4.\tHigher pred accuracy than n-grams\n",
              "\n",
              "\n",
              "- Cosine angle between vectors tells us their similarity \n",
              "\n",
              "- Embeddings capture relational meaning; capturing similarity or analogy and can use both a sparse model or a dense model. Useful in practice but encode cultural stereotype. \n",
              "\n",
              "\n",
              "•\tContext is represented by embeddings so can treat cat and dog in a similar manner \n",
              "\n",
              "•\tInput:k-grams of words \n",
              "\n",
              "•\tOutput:probability distribution over next word \n",
              "\n",
              "•\tK context is treated as window and each word is associated with an embedding vector.  \n",
              "\n",
              "•\tCurse of dimensionality: there are too many parameters to accurately predict  \n",
              "\n",
              "• This vector representation could only compare words that have similar meaning, but it cannot handle the problem that single word has multiple meanings (polysemy). \n",
              "\n",
              "• n-gram model for a corpus with a vocabulary of size V and a total of T tokens. The running time is n and T\n",
              "N-gram models used for generation draw the next word at random (proportional to their conditional probability tables). If a word doesn't occur with the context in training, then it isn't included in its conditional probability table and therefore won't be generated.\n",
              "These models are evaluated on a test set. \n",
              "\n",
              "\n",
              "## Module 14 Definitions\n",
              "* **Polysemy** - word that has multiple meaning \n",
              "* **Word sense disambiguation** - task of understanding which sense of a word is being used in a context\n",
              "* **Semantic field** - a set of words which cover a semantic domain and bear structured relation with each other.\n",
              "* **Term doc matrix** - each term on rows and doc labels on columns; value is how often the term occurred. Row size is the vocabulary size.\n",
              "* **Tf-idf (sparse)** - how often a word occurred in a document over the number of documents that it occurred in.\n",
              "* **Word2vec (dense)** - popular embedding method, fast to learn and predicts rather than counts. \n",
              "* **Turning dot product into a probability** - throw it into the sigmoid curve\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "mmonzoor_CIS521_midterm_2_notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
