{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "54580f1e-22eb-4657-8e14-104a615b6276"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2cd4c8a2-805b-483a-8fae-409ce38e0560"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" a decision-theoretic agent—an agent that can make rational decisions \n",
        "based on what it believes and what it wants. Such an agent can make decisions in contexts \n",
        "in which uncertainty and conflicting goals leave a logical agent with no way to decide. \n",
        "A goal-based agent has a binary distinction between good (goal) and bad (non-goal) \n",
        "states, while a decision-theoretic agent assigns a continuous range of values o \n",
        "states, and thus can more easily choose a better state even when no best state is \n",
        "available. The agent’s preferences are captured by a utility function, U(s), which \n",
        "assigns a single number to express the Utlity function desirability of a state. \n",
        "The expected utility of an action given the evidence, EU(a), is just the Expected \n",
        "utility average utility value of the outcomes, weighted by the probability that \n",
        "the outcome occurs. The principle of maximum expected utility (MEU) says that a \n",
        "rational agent should choose the action that maximizes the agent’s expected utility.\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the\n",
        "right thing,” but does not operationalize that advice. Estimating the probability \n",
        "distribution P(s) over possible states of the world, which folds into P(RESULT(a) =s'), \n",
        "requires percep- tion, learning, knowledge representation, and inference. In summary, \n",
        "decision theory is not a panacea that solves the AI problem—but it does provide \n",
        "the beginnings of a basic mathematical framework that is general enough to define \n",
        "the AT problem. The MEU principle has a clear relation to the idea of performance \n",
        "measures introduced in Chapter 2. The basic idea is simple. Consider the environments \n",
        "that could lead to an agent having a given percept history, and consider the different \n",
        "agents that we could design. If an agent acts so as to maximize a utility function \n",
        "that correctly reflects the performance measure, then the agent will achieve the \n",
        "highest possible performance score (averaged over all the possible environments). \n",
        "This is the central justification for the MEU principle itself. While the claim \n",
        "may seem tautological, it does in fact embody a very important transition from the \n",
        "external performance measure to an internal utility function. The performance measure \n",
        "gives a score for a history—a sequence of states. Thus it is applied retrospectively \n",
        "after an agent completes a sequence of actions. The utility function applies to \n",
        "the very next state, so it can be used to guide actions step by step.\"\"\"  + sample_equation\n",
        "\n",
        "# print(len(chapter16_1.split(\" \")))\n",
        "\n",
        "chapter16_2 =  \"\"\" The agent prefers A over B. The agent is indifferent between A \n",
        "and B. The agent prefers A over B or is indifferent between them. We can think of \n",
        "the set of outcomes for each action as a lottery—think of each action as a ticket. \n",
        "A lottery L with possible outcomes S1, ..., Sn, that occur with probabilities p1, \n",
        "..., pn is written L=[p1,S1;p2,S2; ... pn,Sn]. To address this issue we list six \n",
        "constraints that we require any reasonable preference relation to obey: 1. Orderability: \n",
        "Given any two lotteries, a rational agent must either prefer one or else rate them \n",
        "as equally preferable. That is, the agent cannot avoid deciding. Exactly one of \n",
        "(A > B), (B > A), (A ~ B). 2. Transitivity: Given any three lotteries, if an agent \n",
        "prefers A to B and prefers B to C, then the agent must prefer A to C. 3. Continuity: \n",
        "If some lottery B is between A and C in preference, then there is some probability \n",
        "p for which the rational agent will be indifferent between getting B for sure and \n",
        "the lottery that yields A with probability p and C with probability 1 — p. 4. Substitutability: \n",
        "If an agent is indifferent between two lotteries A and B, then the agent is indifferent \n",
        "between two more complex lotteries that are the same except that B is substituted for \n",
        "A in one of them. 5. Monotonicity: Suppose two lotteries have the same two possible \n",
        "outcomes, A and B. If an agent prefers A to B, then the agent must prefer the lottery \n",
        "that has a higher probability for A (and vice versa). 6. Decomposability: Compound \n",
        "lotteries can be reduced to simpler ones using the laws Decomposability of probability. \n",
        "Existence of Utility Function: If an agent’s preferences obey the axioms of utility, \n",
        "then there exists a function U such that U(A) > U(B) if and only if A is preferred \n",
        "to B, and U(A) = U(B) if and only if the agent is indifferent between A and B. \n",
        "Expected Utility of a Lottery: The utility of a lottery is the sum of the probability \n",
        "of each outcome times the utility of that outcome. The utility functions are not\n",
        "unique because linear transformation preserves all properties. s in game-playing, \n",
        "in a deterministic environment an agent needs only a preference ranking on states\n",
        "—the numbers don’t matter. This is called a value function or ordinal utility function.\n",
        "Transitivity: (A>B)and(B>C)yields(A>C). Continuity: (A>B>C) then exists p such that \n",
        "[p,A;1-p,C]~B. Substitutability: A~B yields [p,A;1-p,C]~[p,B;1-p,C]. Monotonicity:\n",
        "A>B yields (p>q iff [p,A;1-p,B]>[q,A;1-q,B]).\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\" If we want to build a decision-theoretic system that helps a \n",
        "human make decisions or acts on his or her behalf, we must first work out what the \n",
        "human’s utility function is. This process, often called preference elicitation, \n",
        "involves presenting choices to the human and using the Preference elicitation observed \n",
        "preferences to pin down the underlying utility function. There is no absolute scale \n",
        "for utilities, but it is helpful, nonetheless, to establish some scale on which \n",
        "utilities can be recorded and compared for any particular problem. A scale can \n",
        "be established by fixing the utilities of any two particular outcomes, just as we \n",
        "fix a temperature scale by fixing the freezing point and boiling point of water.\n",
        "Normalized utilities use a scale Normalized utilties with u_worst =0 and u_best \n",
        "= 1. Given a utility scale between u_worst and u_best , we can assess the utility \n",
        "of any particular prize S by asking the agent to choose between S and a standard lottery\n",
        "[p,u_best;1-p,u_worst]. US government uses the value of a statistical life to determine \n",
        "the costs and benefits of regulations and interventions. One common “currency” used \n",
        "in medical and safety analysis is the micromort, a one in a Micromort million chance \n",
        "of death. Another measure is the QALY or quality-adjusted life year. Patients are \n",
        "willing to accept a shorter life expectancy to avoid a disability. We say that the \n",
        "agent exhibits a monotonic preference for more money. Risk aversion: slope decreasing,\n",
        "risk seeking: slope increasing. The difference between the EMV of a lottery and \n",
        "its certainty equivalent is called the insurance premium. Bias is the difference\n",
        "between true expected utility and estimated expected utility. An order statistic, \n",
        "the distribution of any particular ranked element of a sample. This tendency for \n",
        "the estimated expected utility of the best choice to be too high is called the \n",
        "optimizer’s curse. Decision theory is a normative theory: it describes how a rational \n",
        "agent should act. A descriptive theory, on the other hand, describes how actual \n",
        "agents—for example, humans—really do act. One explanation for the apparently irrational \n",
        "preferences is the certainty effect: people are strongly attracted to gains that \n",
        "are certain. There are several reasons why this may be so. First, people may prefer \n",
        "to reduce their computational burden; by choosing certain outcomes, they don’t \n",
        "have to compute with probabilities. But the effect persists even when the computations \n",
        "involved are very easy ones. Second, people may distrust the legitimacy of the stated \n",
        "probabilities. In the presence of distrust, it might be better to go for the sure thing.\n",
        "Third, people may be accounting for their emotional state as well as their financial \n",
        "state. Ambiguity aversion is when people elect the known probability rather than \n",
        "the unknown unknowns. Framing effect is 90% survival > 10% death. Anchoring is 200\n",
        "dollars to make 55 dollars seem nice.  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" We will specify a utility or reward function for the agent.\n",
        "The rewards can be positive or negative but are bounded by some maximum value.\n",
        "Because the decision process is sequential, we must specify the utility function \n",
        "on a sequence of states and actions. Instead of only giving a reward at the goal \n",
        "states, the agent can receive a reward at each time step, based on its transition \n",
        "from s to s' via action a. The rewards are additive. A Markov decision process or \n",
        "MDP is a sequential decision problem for a fully observable environment with a stochastic \n",
        "transition model that has additive rewards. MDPs are non-deterministic search problems. \n",
        "One way of solving them is via expectimax search. Expectimax node: outcome is uncertain. \n",
        "In expectimax search we calculate their expected utilities. To find a solution to \n",
        "an MDP, you need to define the following things: A set of states s \\in S, A set \n",
        "of actions a \\in A, A transition function T(s, a, s') that has Probability that executing \n",
        "action a in s will lead to s' with P(s' | s, a) and The probability is called the model,\n",
        "A reward function R(s, a, s') that's Sometimes just R(s) or R(s'), An initial state \n",
        "s0, Optionally one or more terminal states. In search problems a solution was a \n",
        "sequence of action that corresponded to the shortest path(a plan). Because of the non-determinism \n",
        "in MDPs we cannot simply give a sequence of actions. Instead, the solution to an \n",
        "MDP is a policy. A policy maps from a state onto the action to take if the agent \n",
        "is in that state. Theorem: if we assume stationary preferences: [a1,..an] > \n",
        "[b1,..bn] iff [r,a1,..an] > [r,b1,...bn], then only two ways to define additive\n",
        "utility and discounted utility. Value iteration: recursively finds expectimax and\n",
        "taking argmax a until convergence, complexity is O(S^2 A). Discount less than 1\n",
        "yields convergence. Policy iteration calculates utilities for a fixed policy, complexity\n",
        "is O(S^2) per iteration. Without the maxes, the Bellman equations are just a linear \n",
        "system efficiently solved by matlab. Extract policy is mini-expectimass to compare Q. Step 1: \n",
        "Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) \n",
        "until convergence. Step 2: Policy improvement: update policy using one-step look-ahead \n",
        "with resulting converged (but not optimal!) utilities as future values. Repeat steps \n",
        "until policy converges. Both value and policy iteration are optimal. In value iteration:\n",
        "Every iteration updates both the values and (implicitly) the policy, We don't track \n",
        "the policy, but taking the max over actions implicitly recomputes it. In policy iteration:\n",
        "We do several passes that update utilities with fixed policy (each pass is fast \n",
        "because we consider only one action, not all of them). After the policy is evaluated, \n",
        "a new policy is chosen (slow like a value iteration pass). The new policy will be better \n",
        "(or we're done). Both are dynamic programs for solving MDPs. For worst-case minimax \n",
        "reasoning, terminal function scale doesn't matter. We just want better states to \n",
        "have higher evaluations (get the ordering right). We call this insensitivity to \n",
        "monotonic transformations. \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"MDP\": \"Set of states S, Start state s0, Set of actions A, Transitions P(s'|s,a) (or T(s,a,s)), Rewards R(s,a,s') (and discount r)\",\n",
        "\"policy\": \"Choice of action for each state\",\n",
        "\"utility\": \"sum of discounted rewards\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "aa948941-bb5a-4280-9d3f-80ea0072c6e9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n a decision-theoretic agent—an agent that can make rational decisions \nbased on what it believes and what it wants. Such an agent can make decisions in contexts \nin which uncertainty and conflicting goals leave a logical agent with no way to decide. \nA goal-based agent has a binary distinction between good (goal) and bad (non-goal) \nstates, while a decision-theoretic agent assigns a continuous range of values o \nstates, and thus can more easily choose a better state even when no best state is \navailable. The agent’s preferences are captured by a utility function, U(s), which \nassigns a single number to express the Utlity function desirability of a state. \nThe expected utility of an action given the evidence, EU(a), is just the Expected \nutility average utility value of the outcomes, weighted by the probability that \nthe outcome occurs. The principle of maximum expected utility (MEU) says that a \nrational agent should choose the action that maximizes the agent’s expected utility.\nThe MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice. Estimating the probability \ndistribution P(s) over possible states of the world, which folds into P(RESULT(a) =s'), \nrequires percep- tion, learning, knowledge representation, and inference. In summary, \ndecision theory is not a panacea that solves the AI problem—but it does provide \nthe beginnings of a basic mathematical framework that is general enough to define \nthe AT problem. The MEU principle has a clear relation to the idea of performance \nmeasures introduced in Chapter 2. The basic idea is simple. Consider the environments \nthat could lead to an agent having a given percept history, and consider the different \nagents that we could design. If an agent acts so as to maximize a utility function \nthat correctly reflects the performance measure, then the agent will achieve the \nhighest possible performance score (averaged over all the possible environments). \nThis is the central justification for the MEU principle itself. While the claim \nmay seem tautological, it does in fact embody a very important transition from the \nexternal performance measure to an internal utility function. The performance measure \ngives a score for a history—a sequence of states. Thus it is applied retrospectively \nafter an agent completes a sequence of actions. The utility function applies to \nthe very next state, so it can be used to guide actions step by step. $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 The agent prefers A over B. The agent is indifferent between A \nand B. The agent prefers A over B or is indifferent between them. We can think of \nthe set of outcomes for each action as a lottery—think of each action as a ticket. \nA lottery L with possible outcomes S1, ..., Sn, that occur with probabilities p1, \n..., pn is written L=[p1,S1;p2,S2; ... pn,Sn]. To address this issue we list six \nconstraints that we require any reasonable preference relation to obey: 1. Orderability: \nGiven any two lotteries, a rational agent must either prefer one or else rate them \nas equally preferable. That is, the agent cannot avoid deciding. Exactly one of \n(A > B), (B > A), (A ~ B). 2. Transitivity: Given any three lotteries, if an agent \nprefers A to B and prefers B to C, then the agent must prefer A to C. 3. Continuity: \nIf some lottery B is between A and C in preference, then there is some probability \np for which the rational agent will be indifferent between getting B for sure and \nthe lottery that yields A with probability p and C with probability 1 — p. 4. Substitutability: \nIf an agent is indifferent between two lotteries A and B, then the agent is indifferent \nbetween two more complex lotteries that are the same except that B is substituted for \nA in one of them. 5. Monotonicity: Suppose two lotteries have the same two possible \noutcomes, A and B. If an agent prefers A to B, then the agent must prefer the lottery \nthat has a higher probability for A (and vice versa). 6. Decomposability: Compound \nlotteries can be reduced to simpler ones using the laws Decomposability of probability. \nExistence of Utility Function: If an agent’s preferences obey the axioms of utility, \nthen there exists a function U such that U(A) > U(B) if and only if A is preferred \nto B, and U(A) = U(B) if and only if the agent is indifferent between A and B. \nExpected Utility of a Lottery: The utility of a lottery is the sum of the probability \nof each outcome times the utility of that outcome. The utility functions are not\nunique because linear transformation preserves all properties. s in game-playing, \nin a deterministic environment an agent needs only a preference ranking on states\n—the numbers don’t matter. This is called a value function or ordinal utility function.\nTransitivity: (A>B)and(B>C)yields(A>C). Continuity: (A>B>C) then exists p such that \n[p,A;1-p,C]~B. Substitutability: A~B yields [p,A;1-p,C]~[p,B;1-p,C]. Monotonicity:\nA>B yields (p>q iff [p,A;1-p,B]>[q,A;1-q,B]).\n\n\n## AIMA Chapter 16.3 Utility Functions\n If we want to build a decision-theoretic system that helps a \nhuman make decisions or acts on his or her behalf, we must first work out what the \nhuman’s utility function is. This process, often called preference elicitation, \ninvolves presenting choices to the human and using the Preference elicitation observed \npreferences to pin down the underlying utility function. There is no absolute scale \nfor utilities, but it is helpful, nonetheless, to establish some scale on which \nutilities can be recorded and compared for any particular problem. A scale can \nbe established by fixing the utilities of any two particular outcomes, just as we \nfix a temperature scale by fixing the freezing point and boiling point of water.\nNormalized utilities use a scale Normalized utilties with u_worst =0 and u_best \n= 1. Given a utility scale between u_worst and u_best , we can assess the utility \nof any particular prize S by asking the agent to choose between S and a standard lottery\n[p,u_best;1-p,u_worst]. US government uses the value of a statistical life to determine \nthe costs and benefits of regulations and interventions. One common “currency” used \nin medical and safety analysis is the micromort, a one in a Micromort million chance \nof death. Another measure is the QALY or quality-adjusted life year. Patients are \nwilling to accept a shorter life expectancy to avoid a disability. We say that the \nagent exhibits a monotonic preference for more money. Risk aversion: slope decreasing,\nrisk seeking: slope increasing. The difference between the EMV of a lottery and \nits certainty equivalent is called the insurance premium. Bias is the difference\nbetween true expected utility and estimated expected utility. An order statistic, \nthe distribution of any particular ranked element of a sample. This tendency for \nthe estimated expected utility of the best choice to be too high is called the \noptimizer’s curse. Decision theory is a normative theory: it describes how a rational \nagent should act. A descriptive theory, on the other hand, describes how actual \nagents—for example, humans—really do act. One explanation for the apparently irrational \npreferences is the certainty effect: people are strongly attracted to gains that \nare certain. There are several reasons why this may be so. First, people may prefer \nto reduce their computational burden; by choosing certain outcomes, they don’t \nhave to compute with probabilities. But the effect persists even when the computations \ninvolved are very easy ones. Second, people may distrust the legitimacy of the stated \nprobabilities. In the presence of distrust, it might be better to go for the sure thing.\nThird, people may be accounting for their emotional state as well as their financial \nstate. Ambiguity aversion is when people elect the known probability rather than \nthe unknown unknowns. Framing effect is 90% survival > 10% death. Anchoring is 200\ndollars to make 55 dollars seem nice.  \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n We will specify a utility or reward function for the agent.\nThe rewards can be positive or negative but are bounded by some maximum value.\nBecause the decision process is sequential, we must specify the utility function \non a sequence of states and actions. Instead of only giving a reward at the goal \nstates, the agent can receive a reward at each time step, based on its transition \nfrom s to s' via action a. The rewards are additive. A Markov decision process or \nMDP is a sequential decision problem for a fully observable environment with a stochastic \ntransition model that has additive rewards. MDPs are non-deterministic search problems. \nOne way of solving them is via expectimax search. Expectimax node: outcome is uncertain. \nIn expectimax search we calculate their expected utilities. To find a solution to \nan MDP, you need to define the following things: A set of states s \\in S, A set \nof actions a \\in A, A transition function T(s, a, s') that has Probability that executing \naction a in s will lead to s' with P(s' | s, a) and The probability is called the model,\nA reward function R(s, a, s') that's Sometimes just R(s) or R(s'), An initial state \ns0, Optionally one or more terminal states. In search problems a solution was a \nsequence of action that corresponded to the shortest path(a plan). Because of the non-determinism \nin MDPs we cannot simply give a sequence of actions. Instead, the solution to an \nMDP is a policy. A policy maps from a state onto the action to take if the agent \nis in that state. Theorem: if we assume stationary preferences: [a1,..an] > \n[b1,..bn] iff [r,a1,..an] > [r,b1,...bn], then only two ways to define additive\nutility and discounted utility. Value iteration: recursively finds expectimax and\ntaking argmax a until convergence, complexity is O(S^2 A). Discount less than 1\nyields convergence. Policy iteration calculates utilities for a fixed policy, complexity\nis O(S^2) per iteration. Without the maxes, the Bellman equations are just a linear \nsystem efficiently solved by matlab. Extract policy is mini-expectimass to compare Q. Step 1: \nPolicy evaluation: calculate utilities for some fixed policy (not optimal utilities!) \nuntil convergence. Step 2: Policy improvement: update policy using one-step look-ahead \nwith resulting converged (but not optimal!) utilities as future values. Repeat steps \nuntil policy converges. Both value and policy iteration are optimal. In value iteration:\nEvery iteration updates both the values and (implicitly) the policy, We don't track \nthe policy, but taking the max over actions implicitly recomputes it. In policy iteration:\nWe do several passes that update utilities with fixed policy (each pass is fast \nbecause we consider only one action, not all of them). After the policy is evaluated, \na new policy is chosen (slow like a value iteration pass). The new policy will be better \n(or we're done). Both are dynamic programs for solving MDPs. For worst-case minimax \nreasoning, terminal function scale doesn't matter. We just want better states to \nhave higher evaluations (get the ordering right). We call this insensitivity to \nmonotonic transformations. \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Mdp** - Set of states S, Start state s0, Set of actions A, Transitions P(s'|s,a) (or T(s,a,s)), Rewards R(s,a,s') (and discount r)\n* **Policy** - Choice of action for each state\n* **Utility** - sum of discounted rewards\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Solving MDPs is offline planning. You determine all \n",
        "quantities through computation. You need to know the details of the MDP. You do \n",
        "not actually play the game! Exploration: you have to try unknown actions to get \n",
        "information Exploitation: eventually, you have to use what you know. Regret: even \n",
        "if you learn intelligently, you make mistakes Sampling: because of chance, you have \n",
        "to try things repeatedly Difficulty: learning can be much harder than solving a \n",
        "known MDP. Basic idea: Receive feedback in the form of rewards, Agent’s utility \n",
        "is defined by the reward function, Must (learn to) act so as to maximize expected \n",
        "rewards, All learning is based on observed samples of outcomes. Same setting as \n",
        "MDP with Set of states S, Start state s0, Set of actions A, Transitions P(s'|s,a) \n",
        "(or T(s,a,s)), Rewards R(s,a,s') (and discount r), but P(T) and R are unknown. \n",
        "Step 1: Learn empirical MDP model. Step 2: Solve the learned MDP. Passive reinforcement\n",
        "learning is policy evaluation with a fixed policy pi without knowledge of T or R. \n",
        "Learner is “along for the ride”. No choice about what actions to take. Just execute \n",
        "the policy and learn from experience. This is NOT offline planning! You actually \n",
        "take actions in the world. Direct evaluation is to average the observed sampled\n",
        "values. Temporal difference learning is to learn from every experience. Upon receive\n",
        "a new sample, V(s) = (1-a)*V(s)+a*sample. Earlier samples are weighted by (1-a)^t. \n",
        "Forgets about the past. Decreasing learning rate alpha can give converging averages.\n",
        "TD value leaning is a model-free way to do policy evaluation, mimicking Bellman \n",
        "updates with running sample averages. However, if we want to turn values into a \n",
        "(new) policy, we’re sunk. Full reinforcement learning chooses the actions without\n",
        "T and R with goal to find optimal policy/values. Learner makes choices. Exploration\n",
        "vs. exploitation. Q-learning is to calculate and record all Q-values instead of 1\n",
        "maximized V value. Q-learning is sample-based Q-value iteration. Use (1-a) and a\n",
        "running average. But have to explore enough. Eventually alpha has to be small, but\n",
        "can't decrease too quickly. How to enforce exploration: random action, always epislon\n",
        "probability to explore. Better idea is to explore areas where badness is not yet\n",
        "established. f(u, n) = u+(k/n). Even if you learn the optimal policy, you still \n",
        "make mistakes along the way! Regret is a measure of your total mistake cost: the \n",
        "difference between your (expected) rewards, including youthful suboptimality, and \n",
        "optimal (expected) rewards. Minimizing regret goes beyond learning to be optimal \n",
        "– it requires optimally learning to be optimal. Basic Q-Learning keeps a table of \n",
        "all q-values. In realistic situations, we cannot possibly learn about every single state!\n",
        "Too many states to visit them all in training. Too many states to hold the q-tables in memory\n",
        "Instead, we want to generalize: Learn about some small number of training states from experience\n",
        "Generalize that experience to new, similar situations. Use a weight function to\n",
        "calculate dot product. Approximate Q-learning updates weights wi = wi+alpha*diff*fi(s,a). \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 864
        },
        "cellView": "form",
        "outputId": "040f43e5-fb5f-45ff-d5c6-4a4856004d6b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n Solving MDPs is offline planning. You determine all \nquantities through computation. You need to know the details of the MDP. You do \nnot actually play the game! Exploration: you have to try unknown actions to get \ninformation Exploitation: eventually, you have to use what you know. Regret: even \nif you learn intelligently, you make mistakes Sampling: because of chance, you have \nto try things repeatedly Difficulty: learning can be much harder than solving a \nknown MDP. Basic idea: Receive feedback in the form of rewards, Agent’s utility \nis defined by the reward function, Must (learn to) act so as to maximize expected \nrewards, All learning is based on observed samples of outcomes. Same setting as \nMDP with Set of states S, Start state s0, Set of actions A, Transitions P(s'|s,a) \n(or T(s,a,s)), Rewards R(s,a,s') (and discount r), but P(T) and R are unknown. \nStep 1: Learn empirical MDP model. Step 2: Solve the learned MDP. Passive reinforcement\nlearning is policy evaluation with a fixed policy pi without knowledge of T or R. \nLearner is “along for the ride”. No choice about what actions to take. Just execute \nthe policy and learn from experience. This is NOT offline planning! You actually \ntake actions in the world. Direct evaluation is to average the observed sampled\nvalues. Temporal difference learning is to learn from every experience. Upon receive\na new sample, V(s) = (1-a)*V(s)+a*sample. Earlier samples are weighted by (1-a)^t. \nForgets about the past. Decreasing learning rate alpha can give converging averages.\nTD value leaning is a model-free way to do policy evaluation, mimicking Bellman \nupdates with running sample averages. However, if we want to turn values into a \n(new) policy, we’re sunk. Full reinforcement learning chooses the actions without\nT and R with goal to find optimal policy/values. Learner makes choices. Exploration\nvs. exploitation. Q-learning is to calculate and record all Q-values instead of 1\nmaximized V value. Q-learning is sample-based Q-value iteration. Use (1-a) and a\nrunning average. But have to explore enough. Eventually alpha has to be small, but\ncan't decrease too quickly. How to enforce exploration: random action, always epislon\nprobability to explore. Better idea is to explore areas where badness is not yet\nestablished. f(u, n) = u+(k/n). Even if you learn the optimal policy, you still \nmake mistakes along the way! Regret is a measure of your total mistake cost: the \ndifference between your (expected) rewards, including youthful suboptimality, and \noptimal (expected) rewards. Minimizing regret goes beyond learning to be optimal \n– it requires optimally learning to be optimal. Basic Q-Learning keeps a table of \nall q-values. In realistic situations, we cannot possibly learn about every single state!\nToo many states to visit them all in training. Too many states to hold the q-tables in memory\nInstead, we want to generalize: Learn about some small number of training states from experience\nGeneralize that experience to new, similar situations. Use a weight function to\ncalculate dot product. Approximate Q-learning updates weights wi = wi+alpha*diff*fi(s,a). \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Observed variables (evidence): Agent knows certain \n",
        "things about the state of the world (such as sensor readings or symptoms). Unobserved \n",
        "variables (states): Agent needs to reason about other aspects (such as where an \n",
        "object is or what disease is present). Model: Agent knows something about how the \n",
        "known variables relate to the unknown variables. Probabilistic reasoning gives us \n",
        "a framework for managing our beliefs and knowledge. Like logical assertions, probabilities \n",
        "are about possible worlds. Instead of strictly ruling out possibilities (where a \n",
        "logical assertion is false), probabilities quantify how likely a particular possible \n",
        "world is. In probability theory, the possible worlds are called the sample space, \n",
        "and they mutually exclusive and exhaustive. A fully specified probability model \n",
        "associates a probability P(w) with each possible world w. Axiom of probability is \n",
        "that all w have P(w) between 0 and 1 and the sum of all P(w) = 1. Joint distribution is\n",
        "a set of random variables. An event is a set of outcomes. Marginal distribution is\n",
        "eliminate some rv in joint. Inference by enumeration is evidence variables, 1 query\n",
        "variable, and hidden varaibles. Step 1: Select the entries consistent with the evidence.\n",
        "Step 2: Sum out H to get joint of Query and evidence. Step 3: Normalize. Probabilistic\n",
        "language model: goal is assign a probability to a sentence. Goal is to calculate the\n",
        "probability of a sentence. Related task is to calculate the probability of an upcoming\n",
        "word. Either of this is a language model. MLE doesn't work. Simplifying assumption = \n",
        "Markov assumption. P(won|the underdog team) ~ P(won|team), depending on previous k\n",
        "words, not the whole context. unigram is no history. bigram is 1 word history. trigram\n",
        "is 2 words as history. Still insufficient model of language because language has \n",
        "long-distance dependencies. Problem with MLE: 0 probability for things that haven't\n",
        "seen.  \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0880464c-92c0-435f-e057-ab83eeddbcb7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Observed variables (evidence): Agent knows certain \nthings about the state of the world (such as sensor readings or symptoms). Unobserved \nvariables (states): Agent needs to reason about other aspects (such as where an \nobject is or what disease is present). Model: Agent knows something about how the \nknown variables relate to the unknown variables. Probabilistic reasoning gives us \na framework for managing our beliefs and knowledge. Like logical assertions, probabilities \nare about possible worlds. Instead of strictly ruling out possibilities (where a \nlogical assertion is false), probabilities quantify how likely a particular possible \nworld is. In probability theory, the possible worlds are called the sample space, \nand they mutually exclusive and exhaustive. A fully specified probability model \nassociates a probability P(w) with each possible world w. Axiom of probability is \nthat all w have P(w) between 0 and 1 and the sum of all P(w) = 1. Joint distribution is\na set of random variables. An event is a set of outcomes. Marginal distribution is\neliminate some rv in joint. Inference by enumeration is evidence variables, 1 query\nvariable, and hidden varaibles. Step 1: Select the entries consistent with the evidence.\nStep 2: Sum out H to get joint of Query and evidence. Step 3: Normalize. Probabilistic\nlanguage model: goal is assign a probability to a sentence. Goal is to calculate the\nprobability of a sentence. Related task is to calculate the probability of an upcoming\nword. Either of this is a language model. MLE doesn't work. Simplifying assumption = \nMarkov assumption. P(won|the underdog team) ~ P(won|team), depending on previous k\nwords, not the whole context. unigram is no history. bigram is 1 word history. trigram\nis 2 words as history. Still insufficient model of language because language has \nlong-distance dependencies. Problem with MLE: 0 probability for things that haven't\nseen.  \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Models describe how (a portion of) the world works.\n",
        "Two variables are independent if for all x,y: P(x,y)=P(x)*P(y) or p(x|y)=p(x). \n",
        "P(+detect | +toothache, +cavity) = P(+detect | +cavity). P(+detect | +toothache, -cavity) = P(+detect| -cavity).\n",
        "P(Detect | Toothache, Cavity) = P(Detect | Cavity). P(Toothache | Detect , Cavity) = P(Toothache | Cavity).\n",
        "P(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity). \n",
        "X is conditionally independent of Y given Z iff for all x,y,x, P(x,y|z)=P(x|z)*P(y|z).\n",
        "or equivalently iff P(x|z,y) = P(x|z). Nodes: variables (with domains) and can be \n",
        "assigned (observed) or unassigned (unobserved). Arcs: interactions, indicate “direct \n",
        "influence” between variables; Formally: encode conditional independence (more later)/\n",
        "P(x1,x2,...,xn)=pi_P(xi|parents(xi)). A joint distribution over N boolean variables\n",
        "is 2*N large. An N-node net if nodes have up to k parents O(N*2^(k+1)). Bayes net huge\n",
        "space savings, easier to elicit local CPTs, faster to answer queries. P(x,y,z)=P(x)*\n",
        "P(y|x)*P(z|y) is a causal chain. X is independent of Z given Y because P(z|x,y)=\n",
        "P(z|y). P(x,y,z)=P(y)*P(x|y)*P(z|y) is common cause, X is not independent of Z.\n",
        "But X and Z are independent given Y. P(z|x,y)=P(z|y). Common effect is X causes Z\n",
        "and Y causes Z. X and Y are independent. But X and Y are not independent given Z.\n",
        "X and Y are conditionally independently given evidence variables {Z} if X and Y\n",
        "are \"d-separated\" by Z. A path is active if each triple is active:\n",
        "§ Causal chain A to B to C where B is unobserved (either direction)\n",
        "§ Common cause A from B to C where B is unobserved\n",
        "§ Common effect (aka v-structure)\n",
        "A to B from C where B or one of its descendents is observed. \n",
        "All it takes to block a path is a single inactive segment.\n",
        "D-Separation: a query if xi independent xj given xk1-xkn. Check all undirected\n",
        "paths between xi and xj, if at least one active then not independent.\n",
        "Bayes nets compactly encode joint distributions. Guaranteed independencies of distributions \n",
        "can be deduced from BN graph structure. D-separation gives precise conditional independence \n",
        "guarantees from graph alone. A Bayes’ Net’s joint distribution may have further \n",
        "(conditional) independence that is not detectable until you inspect its specific \n",
        "distribution. Inference: calculating some useful quantity from a joint probability \n",
        "distribution. MLE and MAP. Inference by enumeration is slow. Advanced technique \n",
        "is variable elimination. Interleave joining and marginalizing. Still NP-hard, but \n",
        "usually much faster than inference by enumeration. See the textbook for a description.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 404
        },
        "cellView": "form",
        "outputId": "bb20c901-7476-453f-ca5d-5634317a6eef"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" 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 = \"\"\" P(Y,F1,...Fn)=P(Y)*pi(P(Fi|Y)). We have |Y| labels,\n",
        "|Y|*|F|^(n) values and n*|F|*|Y| parameters. Total number of parameters is linear\n",
        "in number of features. Inference for Naive Bayes, goal is to compute posterior \n",
        "distribution over label variable Y. Step 1 is to get joint probability of label and\n",
        "evidence for each label. Step 2: sum to get probability of evidence. Step3: normalize \n",
        "by dividing Step 1 by Step 2. Inference want to divide p(Y,f1,...,fn) by p(f1,...,fn)\n",
        "to get P(f1,...,fn). Estimates of local conditional probability tables is P(Y), \n",
        "the prior over labels; P(Fi|Y) for each feature (evidence variable). These probabilities \n",
        "are collectively called the parameters of the model and denoted by q. Relative \n",
        "frequency parameters will overfit the training data. Just because we never saw a 3 \n",
        "with pixel (15,15) on during training doesn’t mean we won’t see it at test time. \n",
        "empirical is MLE = counts/total samples. argmax_theta P_theta(X. Laplace smoothing\n",
        "is c(x)+1 divided by the sum of c(x)+1 for all x = (c(x)+1)/(N+|X|). This is once more\n",
        "than the actual. If k times more than the actual it is P_(Lap, k)(x)=(c(x)+k)/(N+k*|X|). \n",
        "k is the strength of the prior. Laplace for conditionals is P_(Lap, k)(x|y)=(c(x,y)+k)/(c(y)+k|X|).\n",
        "Another option is linear interpolation P_(lin)(x|y) = a*hat(P(x|y))+(1-a)*hat(P(x)).\n",
        "First step: get a baseline. Baselines are very simple “straw man” procedures and \n",
        "help determine how hard the task is and help know what a “good” accuracy is. Weak \n",
        "baseline is the most frequent label classifier. The confidence of a probabilistic \n",
        "classifier is the posterior over the top label. confidence(x)=max_(y)P(y|x). This is\n",
        "how sure the classifier is of the classifier. Any probabilistic model will have \n",
        "confidences and there is no guarantee confidence is correct. Weak calibration is \n",
        "higher confidences mean higher accuracy. Strong calibration is confidence predicts \n",
        "accuracy rate. Linear classifier accepts inputs as feature values and take weighted\n",
        "sum as the activation value, nonnegative is 1, negative is -1. Any weight vector is a\n",
        "hyperplane, one side is Y=+1 while the other is Y=-1. If wrong need to adjust the \n",
        "weight vector. if wrong, w = w+y_true*f. Multiclass takes the highest y. Multiclass\n",
        "perceptron start with all weight = 0 and train the weights. Mistake bound is mistake <\n",
        "k/(eta^2). Noise: if the data isn’t separable, weights might thrash. Averaging weight \n",
        "vectors over time can help (averaged perceptron). Mediocre generalization: finds \n",
        "a “barely” separating solution. MIRA*: choose an update size that fixes the current mistake \n",
        "but, minimizes the change to w. min_w of 0.5*sigma(wy-w'y)^2 with wy_true*f(x) \\geq\n",
        "wy*f(x)+1. step size is ((w'y-w'y_true)*f+1)/(2*f*f). usually has a maximum step size\n",
        "of C. take min of the two. SVM finds the separator that maximizes the margin. MIRA\n",
        "minimizes 0.5*||w-w'||^2 but SVM maximizes 0.5*||W||^2. Nonlinear separators: general \n",
        "idea is the original feature space can always be mapped to some higher-dimensional \n",
        "feature space where the training set is separable. Classification comparison:\n",
        "1. Naive Bayes: Builds a model training data; Gives prediction probabilities; Strong \n",
        "assumptions about feature independence; One pass through data (counting). Perceptrons/MIRA: \n",
        "Makes less assumptions about data; Mistake-driven learning; Multiple passes through \n",
        "data (prediction); Often more accurate. A single neural unit cannot be used to compute \n",
        "the XOR function. XOR is not linearly separable. sigmoid(z) = 1/(1+exp(-z)). tanh \n",
        "is (exp(2z)-1)/(exp(2z)+1). relu is max(0,z). \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1213e5ec-9b69-4cee-f328-3f2c2fb2186e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n P(Y,F1,...Fn)=P(Y)*pi(P(Fi|Y)). We have |Y| labels,\n|Y|*|F|^(n) values and n*|F|*|Y| parameters. Total number of parameters is linear\nin number of features. Inference for Naive Bayes, goal is to compute posterior \ndistribution over label variable Y. Step 1 is to get joint probability of label and\nevidence for each label. Step 2: sum to get probability of evidence. Step3: normalize \nby dividing Step 1 by Step 2. Inference want to divide p(Y,f1,...,fn) by p(f1,...,fn)\nto get P(f1,...,fn). Estimates of local conditional probability tables is P(Y), \nthe prior over labels; P(Fi|Y) for each feature (evidence variable). These probabilities \nare collectively called the parameters of the model and denoted by q. Relative \nfrequency parameters will overfit the training data. Just because we never saw a 3 \nwith pixel (15,15) on during training doesn’t mean we won’t see it at test time. \nempirical is MLE = counts/total samples. argmax_theta P_theta(X. Laplace smoothing\nis c(x)+1 divided by the sum of c(x)+1 for all x = (c(x)+1)/(N+|X|). This is once more\nthan the actual. If k times more than the actual it is P_(Lap, k)(x)=(c(x)+k)/(N+k*|X|). \nk is the strength of the prior. Laplace for conditionals is P_(Lap, k)(x|y)=(c(x,y)+k)/(c(y)+k|X|).\nAnother option is linear interpolation P_(lin)(x|y) = a*hat(P(x|y))+(1-a)*hat(P(x)).\nFirst step: get a baseline. Baselines are very simple “straw man” procedures and \nhelp determine how hard the task is and help know what a “good” accuracy is. Weak \nbaseline is the most frequent label classifier. The confidence of a probabilistic \nclassifier is the posterior over the top label. confidence(x)=max_(y)P(y|x). This is\nhow sure the classifier is of the classifier. Any probabilistic model will have \nconfidences and there is no guarantee confidence is correct. Weak calibration is \nhigher confidences mean higher accuracy. Strong calibration is confidence predicts \naccuracy rate. Linear classifier accepts inputs as feature values and take weighted\nsum as the activation value, nonnegative is 1, negative is -1. Any weight vector is a\nhyperplane, one side is Y=+1 while the other is Y=-1. If wrong need to adjust the \nweight vector. if wrong, w = w+y_true*f. Multiclass takes the highest y. Multiclass\nperceptron start with all weight = 0 and train the weights. Mistake bound is mistake <\nk/(eta^2). Noise: if the data isn’t separable, weights might thrash. Averaging weight \nvectors over time can help (averaged perceptron). Mediocre generalization: finds \na “barely” separating solution. MIRA*: choose an update size that fixes the current mistake \nbut, minimizes the change to w. min_w of 0.5*sigma(wy-w'y)^2 with wy_true*f(x) \\geq\nwy*f(x)+1. step size is ((w'y-w'y_true)*f+1)/(2*f*f). usually has a maximum step size\nof C. take min of the two. SVM finds the separator that maximizes the margin. MIRA\nminimizes 0.5*||w-w'||^2 but SVM maximizes 0.5*||W||^2. Nonlinear separators: general \nidea is the original feature space can always be mapped to some higher-dimensional \nfeature space where the training set is separable. Classification comparison:\n1. Naive Bayes: Builds a model training data; Gives prediction probabilities; Strong \nassumptions about feature independence; One pass through data (counting). Perceptrons/MIRA: \nMakes less assumptions about data; Mistake-driven learning; Multiple passes through \ndata (prediction); Often more accurate. A single neural unit cannot be used to compute \nthe XOR function. XOR is not linearly separable. sigmoid(z) = 1/(1+exp(-z)). tanh \nis (exp(2z)-1)/(exp(2z)+1). relu is max(0,z). \n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Classifier components are 1) a feature representation \n",
        "of the input 2) a classification function that computes the estimated class 3) an \n",
        "objective function for learning, usually involving minimizing error on training \n",
        "examples. 4) an algorithm for optimizing the objective function. For sentiment classification, \n",
        "consider an input observation x, represented by a vector of features [x1,x2,...,xn]. \n",
        "The classifier output y can be 1 (positive sentiment) or 0 (negative sentiment). \n",
        "We want to estimate P(y = 1|x). Logistic regression solves this task by learning, \n",
        "from a training set, a vector of weights and a bias term. Decision boundary for 1\n",
        "and 0 is probability = 1 over 0.5. How do we get the weights of the model? We learn \n",
        "the parameters (weights + bias) via learning. This requires 2 components:\n",
        "1. An objective function or loss function that tells us distance between the system \n",
        "output and the gold output. We will use cross-entropy loss.\n",
        "2. An algorithm for optimizing the objective function. We will use stochastic gradient \n",
        "descent to minimize the loss function. Loss function is how much estimated y differs\n",
        "from true y. One example is mean squared error L(mse) = 0.5*(hat(y)-y)^2. hat(y) \n",
        "is estimated y. p(y|x)=hat(y)^(y)*(1-hat(y))^(1-y). Cross entropy loss = -log(p(y|x)) \n",
        "= -[ylog(hat(y))+(1-y)log(1-hat(y))] = -[ylog(sigmoid(wx+b))+(1-y)log(1-sigmoid(wx+b))].\n",
        "MInimize the negative log because want loss to be smaller when estimate close to correct \n",
        "and larger when estimate confused. -log(0.69) = 0.37 for y = 1, -log(0.31) = 1.17 \n",
        "when y = 0. Good parameter theta is argmin theta sigma(Lce(y,x,theta))/m. Gradient \n",
        "descent: w_(t+1) = w_(t)-eta*df(x, w)/dw. L_(CE)(w,b) = -[y*log(sigmoid(wx+b))+(1-y)\n",
        "*log(1-sigmoid(wx+b))], dL_(CE)(w,b)/dwj = [sigmoid(wx+b)-y]*xj. Average loss is \n",
        "Cost(w,b)=sigma(L_(CE)(hat(y),y))/m=-sigma(y*log(sigmoid(wx+b))+(1-y)*log(1-sigmoid(wx+b)))/m.\n",
        "dCost(w,b)/dwj=sigma((sigmoid(wx+b)-y)*xj)/m. dL_(CE)(w,b)/dwj = (sigmoid(wx+b)-y)*xj. \n",
        "generalization of the sigmoid function is the softmax function: softmax(zi)=exp(zj)/\n",
        "(sigma(exp(zj))). The building block of a neural network is a single computational unit. \n",
        "A unit takes a set of real valued numbers as input, performs some computation. \n",
        "Feed-Forward Neural Network The simplest kind of NN is the Feed-Forward Neural Network \n",
        "Multilayer network, all units are usually fully-connected, and no cycles.\n",
        "The outputs from each layer are passed to units in the next higher layer, and no \n",
        "outputs are passed back to lower layers.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0f2b5c93-aa8c-423d-df56-f6e338176ded"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" 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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 930
        },
        "outputId": "02418688-7f1b-4a12-ac5e-d695d2403e0f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "6743ab4e-1890-4e40-9844-ed00f9cf2612"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n 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 Your summary here \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n 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 Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n 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 Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}