{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of lE.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 = \"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"Combining Beliefs and Desires under Uncertainty:  assume that the agent\n",
        "assigns a probability P(s) to each possible current state s, P(s\n",
        "′|s,a), the probability that action a in state s reaches state s′.\n",
        "P(RESULT(a)=s′), P(RESULT(a)=s′) = ∑sP(s)P(s′|s,a).The MEU principle formalizes the general notion that an intelligent agent should “do the\n",
        "right thing,” but does not operationalize that advice.An AI\n",
        "system acting on behalf of a human may not know the human’s true utility function, so there\n",
        "may be uncertainty about U. In summary, decision theory is not a panacea that solves the\n",
        "AI problem—but it does provide the beginnings of a basic mathematical framework that is\n",
        "general enough to define the AI problem. If an agent acts so as to maximize a utility function that \n",
        "correctly reflects the performance measure,then the agent will achieve the highest possible performance score (averaged over all the\n",
        "possible environments),transition from the\n",
        "external performance measure to an internal utility function.\n",
        "The performance measure gives\n",
        "a score for a history—a sequence of states.The utility function applies to the very next state.\n",
        " \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"The Basis of Utility Theory:\n",
        "maximizing the average utility \n",
        "16.2.1 Constraints on rational preferences  \n",
        "A ≻ B the agent prefers A over B.\n",
        "A ∼ B the agent is indifferent between A and B.\n",
        "A ≻∼ B the agent prefers A over B or is indifferent between them.\n",
        "We can think of the set of outcomes for each action\n",
        "as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1,...,Sn\n",
        "Lottery that occur with probabilities p1,..., pn is written\n",
        "L = [p1,S1; p2,S2; ... pn,Sn].  \n",
        "Orderability: Given any two lotteries, a rational agent must either prefer one or else\n",
        "rate them as equally preferable.  \n",
        "Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C,\n",
        "then the agent must prefer A to C.  \n",
        "Continuity: If some lottery B is between A and C in preference, then there is some\n",
        "probability p for which the rational agent will be indifferent between getting B for sure\n",
        "and the lottery that yields A with probability p and C with probability 1− p.  \n",
        "A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B.  \n",
        "Substitutability: If an agent is indifferent between two lotteries A and B, then the\n",
        "agent is indifferent between two more complex lotteries that are the same except that\n",
        "B is substituted for A in one of them. This holds regardless of the probabilities and the\n",
        "other outcome(s) in the lotteries.\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" 16.3 Utility Functions: Utility functions map from lotteries to real numbers. an agent can have any\n",
        "preferences it likes.  \n",
        "16.3.1 Utility assessment and utility scales:\n",
        "preference elicitation, involves presenting choices to the human and using the\n",
        "observed preferences to pin down the underlying utility function.  \n",
        "Typically, we fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible\n",
        "catastrophe” at U(S) = u⊥. (Both of these should be finite.) Normalized utilities use a scale Normalized utilities\n",
        "with u⊥ = 0 and u⊤ = 1. Given a utility scale between u⊤ and u⊥, we can assess the utility of any particular prize\n",
        "S by asking the agent to choose between S and a standard lottery [p,u⊤; (1− p),u⊥]. The Standard lottery\n",
        "probability p is adjusted until the agent is indifferent between S and the standard lottery.  \n",
        " Once this is done for each prize,\n",
        "the utilities for all lotteries involving those prizes are determined. \n",
        "16.3.2 The utility of money:\n",
        "agents with curves of this shape are risk-averse(U(L) < U(SEMV(L))): they prefer a sure thing with a\n",
        "payoff that is less than the expected monetary value of a gamble. On the other hand, in the\n",
        "“desperate” region at large negative wealth, the behavior is risk-seeking. \n",
        "The value an agent will accept in lieu of a lottery is called the certainty equivalent of the\n",
        "lottery,  Studies have shown that most people will accept about $400 in lieu of a gamble that\n",
        "gives $1000 half the time and $0 the other half—that is, the certainty equivalent of the lottery\n",
        "is $400, while the EMV is $500. Assuming the coin is fair, the expected monetary value (EMV) of the gamble is 1/2($0) + \n",
        "1/2($2,500,000) = $1,250,000  \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" making decisions in a stochastic environment.Sequential decision problems,\n",
        "in which the agent’s utility depends on a sequence of decisions  \n",
        "17.1 Sequential Decision Problems  \n",
        "We will assume that transitions are Markovian: the\n",
        "probability of reaching s'\n",
        "from s depends only on s and not on the history of earlier states.\n",
        "The decision problem is sequential, the utility function will depend\n",
        "on a sequence of states and actions—an environment history—rather than on a single state.\n",
        "we\n",
        "simply stipulate that for every transition from s to s′ via action a, the agent receives a reward \n",
        "R(s,a,s′). The rewards may be positive or negative, but they are bounded by ±Rmax.\n",
        "The utility of an environment history is just\n",
        "(for now) the sum of the rewards received.\n",
        "Terminal states (which have rewards +1 and –1). \n",
        "MDP consists of a set of states (with an initial state s0); a set ACTIONS(s) of actions\n",
        "in each state; a transition model P(s′|s,a); and a reward function R(s,a,s′).\n",
        "Methods for solving MDPs usually involve dynamic programming: simplifying a problem by recursively \n",
        "breaking it into smaller pieces and remembering the optimal solutions to the pieces.\n",
        "A solution must specify what the agent should do for any state that the agent\n",
        "might reach. A solution of this kind is called a policy. Policy: π, action recommended by the poicy π for state s: π(s). \n",
        "The quality of a policy is therefore measured by the expected utility of the possible environment histories generated by that policy. An optimal policy is a policy that yields the highest expected utility. \n",
        "We use π∗ to denote an optimal policy. A policy represents the agent function explicitly and is therefore a description of a simple reflex\n",
        "agent, computed from the information used for a utility-based agent.  In general there will often be multiple optimal policies. \n",
        "\n",
        "\n",
        " \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" In our search algorithms so far, the\n",
        "transition model was deterministic and\n",
        "described the outcome of each action in\n",
        "each state.\n",
        "The transition function is sometimes\n",
        "written as T(s, a, s’), or explicitly as a\n",
        "probability: p( s’ | s, a ).  \n",
        "Transitions are Markovian:\n",
        "the probability of arriving in\n",
        "s’ only depends on s and\n",
        "not the history of earlier\n",
        "states.\n",
        "Reward function: 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 on a\n",
        "sequence of states and actions.\n",
        "Instead of only giving a reward at the goal states, the agent can receive a reward at\n",
        "each time step, based on its transition from s to s’ via action a.\n",
        "This is defined by a reward function\n",
        "R( s, a, s’ )\n",
        "For example, we could give the Millennium Falcon a small negative reward of -0.04 for every\n",
        "transition except for entering the terminal states (+1 for entering the planet’s orbit or -1 for\n",
        "smashing into an asteroid).\n",
        "The rewards are additive, so if the Millennium Falcon takes 4 steps before entering\n",
        "the planet's orbit, it gets -0.04 + -0.04 + -0.04 + -0.04 + 1 = 0.84 for that solution.\n",
        "Markov Decision Process:\n",
        "A Markov decision process or MDP is\n",
        "• a sequential decision problem\n",
        "• for a fully observable environment\n",
        "• with a stochastic transition model\n",
        "• that has additive rewards\n",
        "MDPs are non-deterministic search\n",
        "problems. One way of solving them is via\n",
        "expectimax search. \n",
        "Expectimax node: outcome is\n",
        "uncertain. In expectimax search\n",
        "we calculate their expected utilities.\n",
        "To find a solution to an MDP, you need to define the following things:\n",
        "• A set of states s ∈ S\n",
        "• A set of actions a ∈ A\n",
        "• A transition function T(s, a, s’)\n",
        "• Probability that executing action a in s will lead to s’ P(s’ | s, a)\n",
        "• The probability is called the model\n",
        "• A reward function R(s, a, s’)\n",
        "• Sometimes just R(s) or R(s’)\n",
        "• An initial state s0\n",
        "• Optionally, one or more terminal states\n",
        "Policy: In search problems a solution was a\n",
        "sequence of action that corresponded to\n",
        "the shortest path.\n",
        "Because of the non-determinism in MDPs\n",
        "we cannot simply give a sequence of\n",
        "actions.\n",
        "Instead, the solution to an MDP is a policy.\n",
        "A policy maps from a state onto the action\n",
        "to take if the agent is in that state.\n",
        "𝝿(s) = a\n",
        "Policy 𝝿 tells the agent what\n",
        "action to take at state s.\n",
        "\n",
        "In search problems a solution was a plan:\n",
        "a sequence of action that corresponded to\n",
        "the shortest path from the start to a goal.\n",
        "Because of the non-determinism in MDPs\n",
        "we cannot simply give a sequence of\n",
        "actions.\n",
        "Instead, the solution to an MDP is a policy.\n",
        "A policy maps from a state onto the action\n",
        "to take if the agent is in that state. 𝝿(s) = a\n",
        "not guarantee actual move\n",
        "\n",
        "We will use 𝝿* to denote the optimal policy.\n",
        "Even if the same policy is executed multiple times by the\n",
        "agent, this may lead to different sequence of states and\n",
        "actions (environment history), and thus a different\n",
        "score under the reward function.\n",
        "Therefore we need to compute the expected utility of all\n",
        "the possible paths generated by a policy.\n",
        "The performance of an agent in an MDP is the sum\n",
        "of the rewards for the transitions it takes.\n",
        "Uh([s0, a0, s1, a1 …, sn]) = R(s0, a0, s1) + R(s1, a1, s2) + … + R(sn-1, an-1, sn) \n",
        "Utility function on an environment history.\n",
        "Bounce around forever,and avoid the exits … infinite rewards!!\n",
        "Discounting: It’s reasonable to maximize the sum of rewards\n",
        "It’s also reasonable to prefer rewards now to rewards later\n",
        "One solution: values of rewards decay exponentially\n",
        "How to discount?\n",
        "• Each time we descend a level, we\n",
        "multiply in the discount once\n",
        "Why discount?\n",
        "• Sooner rewards probably do have\n",
        "higher utility than later rewards\n",
        "• Also helps our algorithms converge\n",
        "Example: discount of 0.5\n",
        "• U([1,2,3]) = 0.50*1 + 0.51*2 + 0.52*3\n",
        "• U([1, 2, 3]) < U([3, 2, 1])\n",
        "Stationary Preferences:\n",
        "Theorem: if we assume stationary preferences:\n",
        "[a1, a2, ...] > [b1, b2, ...] <-> [r, a1, a2, ...] > [r, b1, b2, ...]\n",
        "Then: there are only two ways to define utilities\n",
        "• Additive utility: U([r0, r1, r2, ..]) = r0+r1+r2...\n",
        "• Discounted utility: U([r0, r1, r2, ..]) = r0+y*r1+y^2*r2...\n",
        "▪Problem: What if the game lasts forever? Do we get infinite\n",
        "rewards?\n",
        "▪Solutions:\n",
        "▪ Finite horizon: (similar to depth-limited search)\n",
        "▪ Terminate episodes after a fixed T steps (e.g. life)\n",
        "▪ Gives nonstationary policies (y depends on time left)\n",
        "▪ Discounting: use 0 < y < 1\n",
        "U([R0, ...R∞]) = sum(t=0...∞) y^t * r <= Rmax/(1-y)\n",
        "▪ Smaller y means smaller “horizon” – shorter term focus\n",
        "▪ Absorbing state: guarantee that for every policy, a terminal state will\n",
        "eventually be reached (like “overheated” for racing\n",
        "\n",
        "MDP quantities so far: • Policy = Choice of action for each state • Utility = sum of (discounted) rewards\n",
        "T(s,a,s’) = P(s’|s,a)R(s,a,s’)\n",
        "s is a state triangle -a-> (s,a) is a q-state circle -(s,a,s')-> s'\n",
        "(s,a,s’) is called a transition T(s,a,s’) = P(s’|s,a) R(s,a,s’)\n",
        "Hyperdrive Search Tree?\n",
        "Optimal Quantities\n",
        "▪ The value (utility) of a state s:\n",
        "V*(s) = expected utility starting in s and\n",
        "acting optimally\n",
        "▪ The value (utility) of a q-state (s,a):\n",
        "Q*(s,a) = expected utility starting out\n",
        "having taken action a from state s and\n",
        "(thereafter) acting optimally\n",
        "▪ The optimal policy:\n",
        "𝝿*(s) = optimal action from state s\n",
        "Values of States:\n",
        "Fundamental operation: compute the (expectimax) value of a state\n",
        "• Expected utility under optimal action\n",
        "• Average sum of (discounted) rewards\n",
        "• This is just what expectimax computed!\n",
        "Recursive definition of value:\n",
        "V*(s) = max a Q*(s,a)\n",
        "Q*(s, a) = Sum(s') T(s,a,s')[R(s,a,s') + yV*(s')]\n",
        "V*(s) = max a Sum(s')T(s,a,s')[R(s,a,s') + yV*(s')]\n",
        "\n",
        "Key idea: time-limited values\n",
        "Define Vk(s) to be the optimal value of s if the game\n",
        "ends in k more time steps\n",
        "• Equivalently, it’s what a depth-k expectimax would give\n",
        "from s\n",
        "Value Iteration\n",
        "Start with V0(s) = 0: no time steps left means an expected reward sum of zero\n",
        "Given vector of Vk(s) values, do one ply of expectimax from each state:\n",
        "Repeat until convergence\n",
        "Vk+1(s) <- max a Sum(s') T(s,a,s')[R(s,a,s')+yVk(s')]\n",
        "Complexity of each iteration: O(S^2A)\n",
        "Theorem: will converge to unique optimal values\n",
        "• Basic idea: approximations get refined towards optimal values\n",
        "• Policy may converge long before value\n",
        "\n",
        "How do we know the Vk vectors are going to converge?\n",
        "Case 1: If the tree has maximum depth M, then VM holds\n",
        "the actual untruncated values\n",
        "Case 2: If the discount is less than 1\n",
        "• Sketch: For any state Vk and Vk+1 can be viewed as depth k+1 expectimax results in nearly identical search trees\n",
        "• The difference is that on the bottom layer, Vk+1 has actual rewards while Vk has zeros\n",
        "• That last layer is at best all RMAX\n",
        "• It is at worst Rmin\n",
        "• But everything is discounted by γ^k that far out\n",
        "• So Vk and Vk+1 are at most γ^k max|R| different\n",
        "• So as k increases, the values converge\n",
        "The Bellman Equations:\n",
        "How to be optimal:\n",
        "Step 1: Take correct first action\n",
        "Step 2: Keep being optimal\n",
        "Definition of “optimal utility” via expectimax recurrence gives\n",
        "a simple one-step lookahead relationship amongst optimal\n",
        "utility values. These are the Bellman equations, and they characterize\n",
        "optimal values in a way we’ll use over and over.\n",
        "Fixed Policies: Expectimax trees max over all actions to compute the optimal values\n",
        "If we fixed some policy (s), then the tree would be simpler – only one action per state\n",
        "• … though the tree’s value would depend on which policy we fixed\n",
        "Utilities for a Fixed Policy\n",
        "Another basic operation: compute the utility of a state s under a\n",
        "fixed (generally non-optimal) policy\n",
        "Define the utility of a state s, under a fixed policy 𝝿:\n",
        "V𝝿(s) = expected total discounted rewards starting in s and following 𝝿\n",
        "Recursive relation (one-step look-ahead / Bellman equation):\n",
        "V𝝿(s) = Sum(s')T(s, 𝝿(s), s')[R(s, 𝝿(s), s') + yV^𝝿(s')]\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"goal-based agent\": \"binary distinction btw good nd bad states\",\n",
        "\"decision-throrestic agent\": \" assigns a continuous range of values to states, and thus can more easily choose a better state even when no best state is available.\",\n",
        "\"decition theory\": \"deals with choosing among actions based on the desirability of their immediate outcomes.environment is assumed to be episodic\",\n",
        "\"utility function\": \"The agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the Utility function desirability of a state\",\n",
        "\"maximum expected utility (MEU) \": \"a rational agent should choose the action that maximizes the agent’s expected utility: action = argmaxEU(a).\",\n",
        "\"certainty effect\": \"people are strongly attracted to gains that are certain\",\n",
        "\"framing effect\": \"exact wording of a decision problem can have a big impacton the agent’s choices\",\n",
        "\"anchoring effect\": \"People feel more comfortable making relative utility judgments rather than absolute one\",\n",
        "\"evolutionary psychology\":\"our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal numbers\",\n",
        "\"Markov decision process\":\"a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 36,
      "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": "ba81c344-db38-4796-a608-3247be91d816"
      },
      "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": 37,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nCombining Beliefs and Desires under Uncertainty:  assume that the agent\nassigns a probability P(s) to each possible current state s, P(s\n′|s,a), the probability that action a in state s reaches state s′.\nP(RESULT(a)=s′), P(RESULT(a)=s′) = ∑sP(s)P(s′|s,a).The MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice.An AI\nsystem acting on behalf of a human may not know the human’s true utility function, so there\nmay be uncertainty about U. In summary, decision theory is not a panacea that solves the\nAI problem—but it does provide the beginnings of a basic mathematical framework that is\ngeneral enough to define the AI problem. If an agent acts so as to maximize a utility function that \ncorrectly reflects the performance measure,then the agent will achieve the highest possible performance score (averaged over all the\npossible environments),transition from the\nexternal performance measure to an internal utility function.\nThe performance measure gives\na score for a history—a sequence of states.The utility function applies to the very next state.\n  $P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nThe Basis of Utility Theory:\nmaximizing the average utility \n16.2.1 Constraints on rational preferences  \nA ≻ B the agent prefers A over B.\nA ∼ B the agent is indifferent between A and B.\nA ≻∼ B the agent prefers A over B or is indifferent between them.\nWe can think of the set of outcomes for each action\nas a lottery—think of each action as a ticket. A lottery L with possible outcomes S1,...,Sn\nLottery that occur with probabilities p1,..., pn is written\nL = [p1,S1; p2,S2; ... pn,Sn].  \nOrderability: Given any two lotteries, a rational agent must either prefer one or else\nrate them as equally preferable.  \nTransitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C,\nthen the agent must prefer A to C.  \nContinuity: If some lottery B is between A and C in preference, then there is some\nprobability p for which the rational agent will be indifferent between getting B for sure\nand the lottery that yields A with probability p and C with probability 1− p.  \nA ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B.  \nSubstitutability: If an agent is indifferent between two lotteries A and B, then the\nagent is indifferent between two more complex lotteries that are the same except that\nB is substituted for A in one of them. This holds regardless of the probabilities and the\nother outcome(s) in the lotteries.\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n 16.3 Utility Functions: Utility functions map from lotteries to real numbers. an agent can have any\npreferences it likes.  \n16.3.1 Utility assessment and utility scales:\npreference elicitation, involves presenting choices to the human and using the\nobserved preferences to pin down the underlying utility function.  \nTypically, we fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible\ncatastrophe” at U(S) = u⊥. (Both of these should be finite.) Normalized utilities use a scale Normalized utilities\nwith u⊥ = 0 and u⊤ = 1. Given a utility scale between u⊤ and u⊥, we can assess the utility of any particular prize\nS by asking the agent to choose between S and a standard lottery [p,u⊤; (1− p),u⊥]. The Standard lottery\nprobability p is adjusted until the agent is indifferent between S and the standard lottery.  \n Once this is done for each prize,\nthe utilities for all lotteries involving those prizes are determined. \n16.3.2 The utility of money:\nagents with curves of this shape are risk-averse(U(L) < U(SEMV(L))): they prefer a sure thing with a\npayoff that is less than the expected monetary value of a gamble. On the other hand, in the\n“desperate” region at large negative wealth, the behavior is risk-seeking. \nThe value an agent will accept in lieu of a lottery is called the certainty equivalent of the\nlottery,  Studies have shown that most people will accept about $400 in lieu of a gamble that\ngives $1000 half the time and $0 the other half—that is, the certainty equivalent of the lottery\nis $400, while the EMV is $500. Assuming the coin is fair, the expected monetary value (EMV) of the gamble is 1/2($0) + \n1/2($2,500,000) = $1,250,000  \n\n\n\n\n\n\n\n\n\n\n\n\n \n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n making decisions in a stochastic environment.Sequential decision problems,\nin which the agent’s utility depends on a sequence of decisions  \n17.1 Sequential Decision Problems  \nWe will assume that transitions are Markovian: the\nprobability of reaching s'\nfrom s depends only on s and not on the history of earlier states.\nThe decision problem is sequential, the utility function will depend\non a sequence of states and actions—an environment history—rather than on a single state.\nwe\nsimply stipulate that for every transition from s to s′ via action a, the agent receives a reward \nR(s,a,s′). The rewards may be positive or negative, but they are bounded by ±Rmax.\nThe utility of an environment history is just\n(for now) the sum of the rewards received.\nTerminal states (which have rewards +1 and –1). \nMDP consists of a set of states (with an initial state s0); a set ACTIONS(s) of actions\nin each state; a transition model P(s′|s,a); and a reward function R(s,a,s′).\nMethods for solving MDPs usually involve dynamic programming: simplifying a problem by recursively \nbreaking it into smaller pieces and remembering the optimal solutions to the pieces.\nA solution must specify what the agent should do for any state that the agent\nmight reach. A solution of this kind is called a policy. Policy: π, action recommended by the poicy π for state s: π(s). \nThe quality of a policy is therefore measured by the expected utility of the possible environment histories generated by that policy. An optimal policy is a policy that yields the highest expected utility. \nWe use π∗ to denote an optimal policy. A policy represents the agent function explicitly and is therefore a description of a simple reflex\nagent, computed from the information used for a utility-based agent.  In general there will often be multiple optimal policies. \n\n\n \n\n\n\n\n\n\n\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n In our search algorithms so far, the\ntransition model was deterministic and\ndescribed the outcome of each action in\neach state.\nThe transition function is sometimes\nwritten as T(s, a, s’), or explicitly as a\nprobability: p( s’ | s, a ).  \nTransitions are Markovian:\nthe probability of arriving in\ns’ only depends on s and\nnot the history of earlier\nstates.\nReward function: 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 on a\nsequence of states and actions.\nInstead of only giving a reward at the goal states, the agent can receive a reward at\neach time step, based on its transition from s to s’ via action a.\nThis is defined by a reward function\nR( s, a, s’ )\nFor example, we could give the Millennium Falcon a small negative reward of -0.04 for every\ntransition except for entering the terminal states (+1 for entering the planet’s orbit or -1 for\nsmashing into an asteroid).\nThe rewards are additive, so if the Millennium Falcon takes 4 steps before entering\nthe planet's orbit, it gets -0.04 + -0.04 + -0.04 + -0.04 + 1 = 0.84 for that solution.\nMarkov Decision Process:\nA Markov decision process or MDP is\n• a sequential decision problem\n• for a fully observable environment\n• with a stochastic transition model\n• that has additive rewards\nMDPs are non-deterministic search\nproblems. One way of solving them is via\nexpectimax search. \nExpectimax node: outcome is\nuncertain. In expectimax search\nwe calculate their expected utilities.\nTo find a solution to an MDP, you need to define the following things:\n• A set of states s ∈ S\n• A set of actions a ∈ A\n• A transition function T(s, a, s’)\n• Probability that executing action a in s will lead to s’ P(s’ | s, a)\n• The probability is called the model\n• A reward function R(s, a, s’)\n• Sometimes just R(s) or R(s’)\n• An initial state s0\n• Optionally, one or more terminal states\nPolicy: In search problems a solution was a\nsequence of action that corresponded to\nthe shortest path.\nBecause of the non-determinism in MDPs\nwe cannot simply give a sequence of\nactions.\nInstead, the solution to an MDP is a policy.\nA policy maps from a state onto the action\nto take if the agent is in that state.\n𝝿(s) = a\nPolicy 𝝿 tells the agent what\naction to take at state s.\n\nIn search problems a solution was a plan:\na sequence of action that corresponded to\nthe shortest path from the start to a goal.\nBecause of the non-determinism in MDPs\nwe cannot simply give a sequence of\nactions.\nInstead, the solution to an MDP is a policy.\nA policy maps from a state onto the action\nto take if the agent is in that state. 𝝿(s) = a\nnot guarantee actual move\n\nWe will use 𝝿* to denote the optimal policy.\nEven if the same policy is executed multiple times by the\nagent, this may lead to different sequence of states and\nactions (environment history), and thus a different\nscore under the reward function.\nTherefore we need to compute the expected utility of all\nthe possible paths generated by a policy.\nThe performance of an agent in an MDP is the sum\nof the rewards for the transitions it takes.\nUh([s0, a0, s1, a1 …, sn]) = R(s0, a0, s1) + R(s1, a1, s2) + … + R(sn-1, an-1, sn) \nUtility function on an environment history.\nBounce around forever,and avoid the exits … infinite rewards!!\nDiscounting: It’s reasonable to maximize the sum of rewards\nIt’s also reasonable to prefer rewards now to rewards later\nOne solution: values of rewards decay exponentially\nHow to discount?\n• Each time we descend a level, we\nmultiply in the discount once\nWhy discount?\n• Sooner rewards probably do have\nhigher utility than later rewards\n• Also helps our algorithms converge\nExample: discount of 0.5\n• U([1,2,3]) = 0.50*1 + 0.51*2 + 0.52*3\n• U([1, 2, 3]) < U([3, 2, 1])\nStationary Preferences:\nTheorem: if we assume stationary preferences:\n[a1, a2, ...] > [b1, b2, ...] <-> [r, a1, a2, ...] > [r, b1, b2, ...]\nThen: there are only two ways to define utilities\n• Additive utility: U([r0, r1, r2, ..]) = r0+r1+r2...\n• Discounted utility: U([r0, r1, r2, ..]) = r0+y*r1+y^2*r2...\n▪Problem: What if the game lasts forever? Do we get infinite\nrewards?\n▪Solutions:\n▪ Finite horizon: (similar to depth-limited search)\n▪ Terminate episodes after a fixed T steps (e.g. life)\n▪ Gives nonstationary policies (y depends on time left)\n▪ Discounting: use 0 < y < 1\nU([R0, ...R∞]) = sum(t=0...∞) y^t * r <= Rmax/(1-y)\n▪ Smaller y means smaller “horizon” – shorter term focus\n▪ Absorbing state: guarantee that for every policy, a terminal state will\neventually be reached (like “overheated” for racing\n\nMDP quantities so far: • Policy = Choice of action for each state • Utility = sum of (discounted) rewards\nT(s,a,s’) = P(s’|s,a)R(s,a,s’)\ns is a state triangle -a-> (s,a) is a q-state circle -(s,a,s')-> s'\n(s,a,s’) is called a transition T(s,a,s’) = P(s’|s,a) R(s,a,s’)\nHyperdrive Search Tree?\nOptimal Quantities\n▪ The value (utility) of a state s:\nV*(s) = expected utility starting in s and\nacting optimally\n▪ The value (utility) of a q-state (s,a):\nQ*(s,a) = expected utility starting out\nhaving taken action a from state s and\n(thereafter) acting optimally\n▪ The optimal policy:\n𝝿*(s) = optimal action from state s\nValues of States:\nFundamental operation: compute the (expectimax) value of a state\n• Expected utility under optimal action\n• Average sum of (discounted) rewards\n• This is just what expectimax computed!\nRecursive definition of value:\nV*(s) = max a Q*(s,a)\nQ*(s, a) = Sum(s') T(s,a,s')[R(s,a,s') + yV*(s')]\nV*(s) = max a Sum(s')T(s,a,s')[R(s,a,s') + yV*(s')]\n\nKey idea: time-limited values\nDefine Vk(s) to be the optimal value of s if the game\nends in k more time steps\n• Equivalently, it’s what a depth-k expectimax would give\nfrom s\nValue Iteration\nStart with V0(s) = 0: no time steps left means an expected reward sum of zero\nGiven vector of Vk(s) values, do one ply of expectimax from each state:\nRepeat until convergence\nVk+1(s) <- max a Sum(s') T(s,a,s')[R(s,a,s')+yVk(s')]\nComplexity of each iteration: O(S^2A)\nTheorem: will converge to unique optimal values\n• Basic idea: approximations get refined towards optimal values\n• Policy may converge long before value\n\nHow do we know the Vk vectors are going to converge?\nCase 1: If the tree has maximum depth M, then VM holds\nthe actual untruncated values\nCase 2: If the discount is less than 1\n• Sketch: For any state Vk and Vk+1 can be viewed as depth k+1 expectimax results in nearly identical search trees\n• The difference is that on the bottom layer, Vk+1 has actual rewards while Vk has zeros\n• That last layer is at best all RMAX\n• It is at worst Rmin\n• But everything is discounted by γ^k that far out\n• So Vk and Vk+1 are at most γ^k max|R| different\n• So as k increases, the values converge\nThe Bellman Equations:\nHow to be optimal:\nStep 1: Take correct first action\nStep 2: Keep being optimal\nDefinition of “optimal utility” via expectimax recurrence gives\na simple one-step lookahead relationship amongst optimal\nutility values. These are the Bellman equations, and they characterize\noptimal values in a way we’ll use over and over.\nFixed Policies: Expectimax trees max over all actions to compute the optimal values\nIf we fixed some policy (s), then the tree would be simpler – only one action per state\n• … though the tree’s value would depend on which policy we fixed\nUtilities for a Fixed Policy\nAnother basic operation: compute the utility of a state s under a\nfixed (generally non-optimal) policy\nDefine the utility of a state s, under a fixed policy 𝝿:\nV𝝿(s) = expected total discounted rewards starting in s and following 𝝿\nRecursive relation (one-step look-ahead / Bellman equation):\nV𝝿(s) = Sum(s')T(s, 𝝿(s), s')[R(s, 𝝿(s), s') + yV^𝝿(s')]\n\n\n\n\n \n\n## Module 8 Definitions\n* **Goal-based agent** - binary distinction btw good nd bad states\n* **Decision-throrestic agent** -  assigns a continuous range of values to states, and thus can more easily choose a better state even when no best state is available.\n* **Decition theory** - deals with choosing among actions based on the desirability of their immediate outcomes.environment is assumed to be episodic\n* **Utility function** - The agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the Utility function desirability of a state\n* **Maximum expected utility (meu) ** - a rational agent should choose the action that maximizes the agent’s expected utility: action = argmaxEU(a).\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Framing effect** - exact wording of a decision problem can have a big impacton the agent’s choices\n* **Anchoring effect** - People feel more comfortable making relative utility judgments rather than absolute one\n* **Evolutionary psychology** - our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal numbers\n* **Markov decision process** - a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process\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 = \"\"\" Double-Bandit MDP:\n",
        "Offline Planning:\n",
        "Solving MDPs is offline planning.\n",
        "You determine all quantities through computation.\n",
        "You need to know the details of the MDP.\n",
        "You do not actually play the game!\n",
        "Online Planning\n",
        "Rules changed! Red’s win chance is different\n",
        "That wasn’t planning, it was learning!\n",
        "Specifically, reinforcement learning:\n",
        "There was an MDP, but you couldn’t solve it with just computation\n",
        "You needed to actually act to figure it out\n",
        "Important ideas in reinforcement learning that came up\n",
        "Exploration: you have to try unknown actions to get information\n",
        "Exploitation: eventually, you have to use what you know\n",
        "Regret: even if you learn intelligently, you make mistakes\n",
        "Sampling: because of chance, you have to try things repeatedly\n",
        "Difficulty: learning can be much harder than solving a known MDP\n",
        "Basic idea:\n",
        "Environment - state:s, reward:r -> Agent\n",
        "Agent - action:a -> Environment\n",
        "Receive feedback in the form of rewards\n",
        "Agent’s utility is defined by the reward function\n",
        "Must (learn to) act so as to maximize expected rewards\n",
        "All learning is based on observed samples of outcomes!\n",
        "Still looking for a policy π(s)\n",
        "New twist: don’t know T or R\n",
        "I.e. we don’t know which states are good or what the actions do\n",
        "Must actually try actions and states out to learn\n",
        "Model-Based Learning\n",
        "Model-Based Idea:\n",
        "Learn an approximate model based on experiences\n",
        "Solve for values as if the learned model were correct\n",
        "Step 1: Learn empirical MDP model\n",
        "Count outcomes s’ for each s, a\n",
        "Normalize to give an estimate of T^(s, a, s')\n",
        "Discover each R(s,a,s')^ when we experience (s, a, s’)\n",
        "Step 2: Solve the learned MDP\n",
        "For example, use value iteration, as before\n",
        "Input Policy π,\n",
        "Assume: γ = 1,\n",
        "Observed Episodes (Training) Learned Model.\n",
        "Model-Free Learning:\n",
        "Passive Reinforcement Learning:\n",
        "Simplified task: policy evaluation\n",
        "Input: a fixed policy π(s)\n",
        "You don’t know the transitions T(s,a,s’)\n",
        "You don’t know the rewards R(s,a,s’)\n",
        "Goal: learn the state values\n",
        "In this case:\n",
        "Learner is “along for the ride”\n",
        "No choice about what actions to take\n",
        "Just execute the policy and learn from experience\n",
        "This is NOT offline planning! You actually take actions in the world.\n",
        "Direct Evaluation:\n",
        "Goal: Compute values for each state under π\n",
        "Idea: Average together observed sample values\n",
        "Act according to π\n",
        "Every time you visit a state, write down what the\n",
        "sum of discounted rewards turned out to be\n",
        "\n",
        "Receive a sample (s,a,s’,r)\n",
        "Consider your old estimate: Q(s,a)\n",
        "Consider your new sample estimate: sample = R(s,a,s') + y max a' Q(s',a')\n",
        "Incorporate the new estimate into a running average: \n",
        "Q(s,a) <- (1-α)Q(s,a) + (α)[sample]\n",
        "Q-Learning Properties:\n",
        "Amazing result: Q-learning converges to optimal policy -- even\n",
        "if you’re acting suboptimally!\n",
        "This is called off-policy learning\n",
        "Caveats:\n",
        "You have to explore enough\n",
        "You have to eventually make the learning rate\n",
        "small enough\n",
        "… but not decrease it too quickly\n",
        "Basically, in the limit, it doesn’t matter how you select actions (!)\n",
        "Exploration vs. Exploitation\n",
        "How to Explore?\n",
        "Several schemes for forcing exploration:\n",
        "Simplest: random actions (ε-greedy)\n",
        "Every time step, flip a coin\n",
        "With (small) probability ε, act randomly, ε-> 0, greater exploitation,  ε-> 1, greater exploration\n",
        "With (large) probability 1-ε, act on current policy, \n",
        "Problems with random actions?\n",
        "You do eventually explore the space, but keep\n",
        "thrashing around once learning is done\n",
        "One solution: lower ε over time\n",
        "Another solution: exploration functions\n",
        "Exploration Functions\n",
        "When to explore?\n",
        "Random actions: explore a fixed amount\n",
        "Better idea: explore areas whose badness is not\n",
        "(yet) established, eventually stop exploring\n",
        "Exploration function\n",
        "Takes a value estimate u and a visit count n, and\n",
        "returns an optimistic utility, e.g. f(u, n) = u+k/n\n",
        "Regular Q-Update: Q(s,a) <- αR(s,a,s') + ymax a' Q(s',a')\n",
        "Modified Q-Update: Q(s,a) <- αR(s,a,s') + ymax a' f(Q(s',a'), N(s',a'))\n",
        "Note: this propagates the “bonus” back to states that lead to unknown states as\n",
        "well!\n",
        "Regret:\n",
        "Even if you learn the optimal policy,\n",
        "you still make mistakes along the way!\n",
        "Regret is a measure of your total\n",
        "mistake cost: the difference between\n",
        "your (expected) rewards, including\n",
        "youthful suboptimality, and optimal\n",
        "(expected) rewards\n",
        "Minimizing regret goes beyond\n",
        "learning to be optimal – it requires\n",
        "optimally learning to be optimal\n",
        "Example: random exploration and\n",
        "exploration functions both end up\n",
        "optimal, but random exploration has\n",
        "higher regret\n",
        "Approximate Q-Learning\n",
        "Generalizing Across States\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0587ee50-1fe4-4b0f-8822-6a530597e156"
      },
      "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": 20,
      "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 Double-Bandit MDP:\nOffline Planning:\nSolving MDPs is offline planning.\nYou determine all quantities through computation.\nYou need to know the details of the MDP.\nYou do not actually play the game!\nOnline Planning\nRules changed! Red’s win chance is different\nThat wasn’t planning, it was learning!\nSpecifically, reinforcement learning:\nThere was an MDP, but you couldn’t solve it with just computation\nYou needed to actually act to figure it out\nImportant ideas in reinforcement learning that came up\nExploration: you have to try unknown actions to get information\nExploitation: eventually, you have to use what you know\nRegret: even if you learn intelligently, you make mistakes\nSampling: because of chance, you have to try things repeatedly\nDifficulty: learning can be much harder than solving a known MDP\nBasic idea:\nEnvironment - state:s, reward:r -> Agent\nAgent - action:a -> Environment\nReceive feedback in the form of rewards\nAgent’s utility is defined by the reward function\nMust (learn to) act so as to maximize expected rewards\nAll learning is based on observed samples of outcomes!\nStill looking for a policy π(s)\nNew twist: don’t know T or R\nI.e. we don’t know which states are good or what the actions do\nMust actually try actions and states out to learn\nModel-Based Learning\nModel-Based Idea:\nLearn an approximate model based on experiences\nSolve for values as if the learned model were correct\nStep 1: Learn empirical MDP model\nCount outcomes s’ for each s, a\nNormalize to give an estimate of T^(s, a, s')\nDiscover each R(s,a,s')^ when we experience (s, a, s’)\nStep 2: Solve the learned MDP\nFor example, use value iteration, as before\nInput Policy π,\nAssume: γ = 1,\nObserved Episodes (Training) Learned Model.\nModel-Free Learning:\nPassive Reinforcement Learning:\nSimplified task: policy evaluation\nInput: a fixed policy π(s)\nYou don’t know the transitions T(s,a,s’)\nYou don’t know the rewards R(s,a,s’)\nGoal: learn the state values\nIn this case:\nLearner is “along for the ride”\nNo choice about what actions to take\nJust execute the policy and learn from experience\nThis is NOT offline planning! You actually take actions in the world.\nDirect Evaluation:\nGoal: Compute values for each state under π\nIdea: Average together observed sample values\nAct according to π\nEvery time you visit a state, write down what the\nsum of discounted rewards turned out to be\n\nReceive a sample (s,a,s’,r)\nConsider your old estimate: Q(s,a)\nConsider your new sample estimate: sample = R(s,a,s') + y max a' Q(s',a')\nIncorporate the new estimate into a running average: \nQ(s,a) <- (1-α)Q(s,a) + (α)[sample]\nQ-Learning Properties:\nAmazing result: Q-learning converges to optimal policy -- even\nif you’re acting suboptimally!\nThis is called off-policy learning\nCaveats:\nYou have to explore enough\nYou have to eventually make the learning rate\nsmall enough\n… but not decrease it too quickly\nBasically, in the limit, it doesn’t matter how you select actions (!)\nExploration vs. Exploitation\nHow to Explore?\nSeveral schemes for forcing exploration:\nSimplest: random actions (ε-greedy)\nEvery time step, flip a coin\nWith (small) probability ε, act randomly, ε-> 0, greater exploitation,  ε-> 1, greater exploration\nWith (large) probability 1-ε, act on current policy, \nProblems with random actions?\nYou do eventually explore the space, but keep\nthrashing around once learning is done\nOne solution: lower ε over time\nAnother solution: exploration functions\nExploration Functions\nWhen to explore?\nRandom actions: explore a fixed amount\nBetter idea: explore areas whose badness is not\n(yet) established, eventually stop exploring\nExploration function\nTakes a value estimate u and a visit count n, and\nreturns an optimistic utility, e.g. f(u, n) = u+k/n\nRegular Q-Update: Q(s,a) <- αR(s,a,s') + ymax a' Q(s',a')\nModified Q-Update: Q(s,a) <- αR(s,a,s') + ymax a' f(Q(s',a'), N(s',a'))\nNote: this propagates the “bonus” back to states that lead to unknown states as\nwell!\nRegret:\nEven if you learn the optimal policy,\nyou still make mistakes along the way!\nRegret is a measure of your total\nmistake cost: the difference between\nyour (expected) rewards, including\nyouthful suboptimality, and optimal\n(expected) rewards\nMinimizing regret goes beyond\nlearning to be optimal – it requires\noptimally learning to be optimal\nExample: random exploration and\nexploration functions both end up\noptimal, but random exploration has\nhigher regret\nApproximate Q-Learning\nGeneralizing Across States\n \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "Uncertainty\n",
        "General situation:\n",
        "• Observed variables (evidence): Agent knows certain things about the state of the world (e.g.,\n",
        "sensor readings or symptoms)\n",
        "• Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object\n",
        "is or what disease is present)\n",
        "• Model: Agent knows something about how the known variables relate to the unknown variables\n",
        "Probabilistic reasoning gives us a framework\n",
        "for managing our beliefs and knowledge;\n",
        "What Probabilities Are About\n",
        "Like logical assertions, probabilities are about possible worlds. Instead of strictly\n",
        "ruling out possibilities (where a logical assertion is false), probabilities quantify how\n",
        "likely a particular possible world is.\n",
        "In probability theory, the possible worlds are called the sample space, and they\n",
        "mutually exclusive and exhaustive.\n",
        "A fully specified probability model associates a probability P(w) with each possible\n",
        "world w. ;\n",
        "Random Variables\n",
        "A random variable is some aspect of the world\n",
        "about which we (may) have uncertainty\n",
        "• R = Is it raining?\n",
        "• U = Is the professor carrying an umbrella?\n",
        "We denote random variables with capital letters;\n",
        "\n",
        "Probability Distributions\n",
        "Unobserved random variables have distributions\n",
        "A distribution is a TABLE of probabilities of values\n",
        "A probability (lower case value) is a single number\n",
        "Shorthand notation:OK if all domain entries are unique\n",
        "\n",
        "Joint Distributions\n",
        "A joint distribution over a set of random variables:\n",
        "specifies a real number for each assignment (or outcome):\n",
        "• Must obey:\n",
        "Size of distribution if n variables with domain sizes d?\n",
        "• For all but the smallest distributions, impractical to write out!  \n",
        "\n",
        "Probabilistic Models\n",
        "A probabilistic model is a joint distribution\n",
        "over a set of random variables\n",
        "Probabilistic models:\n",
        "• (Random) variables with domains\n",
        "• Assignments are called outcomes\n",
        "• Joint distributions: say whether\n",
        "assignments (outcomes) are likely\n",
        "• Normalized: sum to 1.0\n",
        "• Ideally: only certain variables directly\n",
        "interact；\n",
        "\n",
        "Events\n",
        "An event is a set E of outcomes\n",
        "From a joint distribution, we can calculate\n",
        "the probability of any event\n",
        "• Probability that it’s hot AND sunny?\n",
        "• Probability that it’s hot?\n",
        "• Probability that it’s hot OR sunny?\n",
        "Typically, the events we care about are\n",
        "partial assignments, like P(T=hot)；\n",
        "\n",
        "Marginal Distributions\n",
        "Marginal distributions are sub-tables which eliminate variables\n",
        "Marginalization (summing out): Combine collapsed rows by\n",
        "adding；\n",
        "\n",
        "Conditional Probabilities\n",
        "A simple relation between joint and conditional\n",
        "probabilities\n",
        "• In fact, this is taken as the definition of a conditional probability；\n",
        "\n",
        "\n",
        "Conditional Distributions\n",
        "Conditional distributions are probability distributions\n",
        "over some variables given fixed values of others；\n",
        "\n",
        "Probabilistic Inference\n",
        "Probabilistic inference: compute a desired\n",
        "probability from other known probabilities (e.g.\n",
        "conditional from joint)\n",
        "We generally compute conditional probabilities\n",
        "• P(on time | no reported accidents) = 0.90\n",
        "• These represent the agent’s beliefs given the\n",
        "evidence\n",
        "Probabilities change with new evidence:\n",
        "• P(on time | no accidents, 5 a.m.) = 0.95\n",
        "• P(on time | no accidents, 5 a.m., raining) = 0.80\n",
        "• Observing new evidence causes beliefs to be update；\n",
        "Inference by Enumeration\n",
        "General case:\n",
        "• Evidence variables:\n",
        "• Query* variable:\n",
        "• Hidden variables: \n",
        " we want:\n",
        " Step 1: Select the\n",
        "entries consistent\n",
        "with the evidence, Step 2: Sum out H to get joint\n",
        "of Query and evidence,  Step 3: Normalize;\n",
        "The Product Rule;\n",
        "The Chain Rule\n",
        "More generally, can always write any joint distribution\n",
        "as an incremental product of conditional distributions;\n",
        "Why is this always true?;\n",
        "\n",
        "\n",
        "\n",
        "Intuition: let’s rely on the Chain Rule of Probability;\n",
        "The Chain Rule：\n",
        "Recall the definition of conditional probabilities\n",
        "p(B|A) = P(A,B)/P(A) Rewriting: P(A,B) = P(A)P(B|A)\n",
        "More variables:\n",
        "P(A,B,C,D) = P(A)P(B|A)P(C|A,B)P(D|A,B,C)\n",
        "The Chain Rule in General\n",
        "P(x1,x2,x3,…,xn) = P(x1)P(x2|x1)P(x3|x1,x2)…P(xn|x1,…,xn-1)；\n",
        "Joint probability of words in sentence：\n",
        "P(“the underdog Philadelphia Eagles won”) =\n",
        "P(the) ×\n",
        "P(underdog|the) ×\n",
        "P(Philadelphia|the underdog) ×\n",
        "P(Eagles|the underdog Philadelphia) x\n",
        "P(won|the underdog Philadelphia Eagles；\n",
        "How to estimate these probabilities\n",
        "Could we just count and divide? Maximum likelihood estimation (MLE)；\n",
        "Simplifying Assumption = Markov Assumption；\n",
        "Simplest case: Unigram model： Some automatically generated sentences from a unigram model，\n",
        "fifth an of futures the an incorporated a a the inflation most\n",
        "dollars quarter in is mass\n",
        "thrift did eighty said hard 'm july bullish\n",
        "that or limited the；\n",
        "Bigram model： Condition on the previous word；\n",
        "N-gram models\n",
        "We can extend to trigrams, 4-grams, 5-grams\n",
        "In general this is an insufficient model of language\n",
        "• because language has long-distance dependencies:\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "4df78716-396e-48d6-e377-8d55b720657f"
      },
      "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": 21,
      "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\nUncertainty\nGeneral situation:\n• Observed variables (evidence): Agent knows certain things about the state of the world (e.g.,\nsensor readings or symptoms)\n• Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object\nis or what disease is present)\n• Model: Agent knows something about how the known variables relate to the unknown variables\nProbabilistic reasoning gives us a framework\nfor managing our beliefs and knowledge;\nWhat Probabilities Are About\nLike logical assertions, probabilities are about possible worlds. Instead of strictly\nruling out possibilities (where a logical assertion is false), probabilities quantify how\nlikely a particular possible world is.\nIn probability theory, the possible worlds are called the sample space, and they\nmutually exclusive and exhaustive.\nA fully specified probability model associates a probability P(w) with each possible\nworld w. ;\nRandom Variables\nA random variable is some aspect of the world\nabout which we (may) have uncertainty\n• R = Is it raining?\n• U = Is the professor carrying an umbrella?\nWe denote random variables with capital letters;\n\nProbability Distributions\nUnobserved random variables have distributions\nA distribution is a TABLE of probabilities of values\nA probability (lower case value) is a single number\nShorthand notation:OK if all domain entries are unique\n\nJoint Distributions\nA joint distribution over a set of random variables:\nspecifies a real number for each assignment (or outcome):\n• Must obey:\nSize of distribution if n variables with domain sizes d?\n• For all but the smallest distributions, impractical to write out!  \n\nProbabilistic Models\nA probabilistic model is a joint distribution\nover a set of random variables\nProbabilistic models:\n• (Random) variables with domains\n• Assignments are called outcomes\n• Joint distributions: say whether\nassignments (outcomes) are likely\n• Normalized: sum to 1.0\n• Ideally: only certain variables directly\ninteract；\n\nEvents\nAn event is a set E of outcomes\nFrom a joint distribution, we can calculate\nthe probability of any event\n• Probability that it’s hot AND sunny?\n• Probability that it’s hot?\n• Probability that it’s hot OR sunny?\nTypically, the events we care about are\npartial assignments, like P(T=hot)；\n\nMarginal Distributions\nMarginal distributions are sub-tables which eliminate variables\nMarginalization (summing out): Combine collapsed rows by\nadding；\n\nConditional Probabilities\nA simple relation between joint and conditional\nprobabilities\n• In fact, this is taken as the definition of a conditional probability；\n\n\nConditional Distributions\nConditional distributions are probability distributions\nover some variables given fixed values of others；\n\nProbabilistic Inference\nProbabilistic inference: compute a desired\nprobability from other known probabilities (e.g.\nconditional from joint)\nWe generally compute conditional probabilities\n• P(on time | no reported accidents) = 0.90\n• These represent the agent’s beliefs given the\nevidence\nProbabilities change with new evidence:\n• P(on time | no accidents, 5 a.m.) = 0.95\n• P(on time | no accidents, 5 a.m., raining) = 0.80\n• Observing new evidence causes beliefs to be update；\nInference by Enumeration\nGeneral case:\n• Evidence variables:\n• Query* variable:\n• Hidden variables: \n we want:\n Step 1: Select the\nentries consistent\nwith the evidence, Step 2: Sum out H to get joint\nof Query and evidence,  Step 3: Normalize;\nThe Product Rule;\nThe Chain Rule\nMore generally, can always write any joint distribution\nas an incremental product of conditional distributions;\nWhy is this always true?;\n\n\n\nIntuition: let’s rely on the Chain Rule of Probability;\nThe Chain Rule：\nRecall the definition of conditional probabilities\np(B|A) = P(A,B)/P(A) Rewriting: P(A,B) = P(A)P(B|A)\nMore variables:\nP(A,B,C,D) = P(A)P(B|A)P(C|A,B)P(D|A,B,C)\nThe Chain Rule in General\nP(x1,x2,x3,…,xn) = P(x1)P(x2|x1)P(x3|x1,x2)…P(xn|x1,…,xn-1)；\nJoint probability of words in sentence：\nP(“the underdog Philadelphia Eagles won”) =\nP(the) ×\nP(underdog|the) ×\nP(Philadelphia|the underdog) ×\nP(Eagles|the underdog Philadelphia) x\nP(won|the underdog Philadelphia Eagles；\nHow to estimate these probabilities\nCould we just count and divide? Maximum likelihood estimation (MLE)；\nSimplifying Assumption = Markov Assumption；\nSimplest case: Unigram model： Some automatically generated sentences from a unigram model，\nfifth an of futures the an incorporated a a the inflation most\ndollars quarter in is mass\nthrift did eighty said hard 'm july bullish\nthat or limited the；\nBigram model： Condition on the previous word；\nN-gram models\nWe can extend to trigrams, 4-grams, 5-grams\nIn general this is an insufficient model of language\n• because language has long-distance dependencies:\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "Probabilistic Models:\n",
        "§ Models describe how (a portion of) the world works\n",
        "§ Models are always simplifications\n",
        "§ May not account for every variable\n",
        "§ May not account for all interactions between variables\n",
        "§ “All models are wrong; but some are useful.” – George E. P. Box\n",
        "§ What do we do with probabilistic models?\n",
        "§ We (or our agents) need to reason about unknown\n",
        "variables, given evidence\n",
        "§ Example: explanation (diagnostic reasoning)\n",
        "§ Example: prediction (causal reasoning)\n",
        "Review: Independence\n",
        "§ Two variables are independent if:\n",
        "any x,y: P(x,y) = P(x)P(y)\n",
        "§ This says that their joint distribution factors into a product two\n",
        "simpler distributions\n",
        "§ Another form:\n",
        "any x,y: P(x|y) = P(x)\n",
        "§ X ||- Y\n",
        "ndependence is a simplifying modeling assumption\n",
        "§ Empirical joint distributions: at best “close” to independent\n",
        "§ What could we assume for {Weather, Traffic, Cavity, Toothache}?\n",
        "Review: Conditional Independence:\n",
        "§ P(Toothache, Cavity, Detect)\n",
        "§ If I have a cavity, the probability that the probe detects it\n",
        "doesn't depend on whether I have a toothache:\n",
        "§ P(+detect | +toothache, +cavity) = P(+detect | +cavity)\n",
        "§ The same independence holds if I don’t have a cavity:\n",
        "§ P(+detect | +toothache, -cavity) = P(+detect| -cavity)\n",
        "§ Detect is conditionally independent of Toothache given\n",
        "Cavity:\n",
        "§ P(Detect | Toothache, Cavity) = P(Detect | Cavity)\n",
        "§ Equivalent statements:\n",
        "§ P(Toothache | Detect , Cavity) = P(Toothache | Cavity)\n",
        "§ P(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity)\n",
        "§ One can be derived from the other using the chain rule\n",
        "§ Unconditional (absolute) independence very rare, and it\n",
        "doesn’t help us make inferences about other variables.\n",
        "§ Conditional independence is our most basic and robust form\n",
        "of knowledge about uncertain environments.\n",
        "§ X is conditionally independent of Y given Z\n",
        "if and only if:\n",
        "  any x,y,z: P(x,y|z) = p(x|z)*P(y|z)\n",
        "or, equivalently, if and only if\n",
        "  any x,y,z: P(x|z,y) = P(x|z)\n",
        "X ||_ Y|Z\n",
        "Conditional Independence and the Chain Rule\n",
        "§ Chain rule: P(X1,X2, ..Xn)=P(X1)P(X2|X1)P(X3|X1,X2)...\n",
        "§ Trivial decomposition:\n",
        "P(Traffic, Rain,Umbrella) = P(Rain)P(Traffic|Rain)P(Umbrella| Rain, Traffic)\n",
        "§ With assumption of conditional independence:\n",
        "P(Traffic, Rain, Umbrella) = P(Rain)P(Traffic|Rain)P(Umbrella|Rain)\n",
        "§ Bayes’nets / graphical models help us express conditional independence assumptions\n",
        "Bayes’ Nets: Big Picture:\n",
        "§ Two problems with using full joint distribution tables\n",
        "as our probabilistic models:\n",
        "§ Unless there are only a few variables, the joint is WAY too\n",
        "big to represent explicitly\n",
        "§ Hard to learn (estimate) anything empirically about more\n",
        "than a few variables at a time\n",
        "§ Bayes’ nets: a technique for describing complex joint\n",
        "distributions (models) using simple, local\n",
        "distributions (conditional probabilities)\n",
        "§ More properly called graphical models\n",
        "§ We describe how variables locally interact\n",
        "§ Local interactions chain together to give global, indirect\n",
        "interactions\n",
        "Graphical Model Notation:\n",
        "§ Nodes: variables (with domains)\n",
        "§ Can be assigned (observed) or unassigned\n",
        "(unobserved)\n",
        "§ Arcs: interactions\n",
        "§ Indicate “direct influence” between variables\n",
        "§ Formally: encode conditional independence\n",
        "(more later)\n",
        "§ For now: imagine that arrows mean\n",
        "direct causation (in general, they don’t!)\n",
        "§ No interactions between variables: absolute independence(no arrors)\n",
        "Bayes’ Net Semantics:\n",
        "§ A set of nodes, one per variable X\n",
        "§ A directed, acyclic graph\n",
        "§ A conditional distribution for each node\n",
        "§ A collection of distributions over X, one for each\n",
        "combination of parents’ values\n",
        "P(X|a1,a2,....an)\n",
        "§ CPT: conditional probability table\n",
        "§ Description of a noisy “causal” process\n",
        "A Bayes net = Topology (graph) + Local Conditional Probabilities\n",
        "Probabilities in BNs\n",
        "§ Bayes’ nets implicitly encode joint distributions\n",
        "§ As a product of local conditional distributions\n",
        "§ To see what probability a BN gives to a full assignment, multiply all the\n",
        "relevant conditionals together:\n",
        "P(x1,x2, ...,xn) = product(i=1 to n) P(xi|parent(Xi))\n",
        "§ Not every BN can represent every joint distribution\n",
        "§ The topology enforces certain conditional independencies\n",
        "Only distributions whose variables are absolutely independent can be\n",
        "represented by a Bayes’ net with no arcs\n",
        "\n",
        "\n",
        "\n",
        "independence is not guaranteed.\n",
        "§ Example:\n",
        "§ Project due causes both forums busy\n",
        "and office hours full\n",
        "§ In numbers:\n",
        "P( +x | +y ) = 1, P( -x | -y ) = 1,\n",
        "P( +z | +y ) = 1, P( -z | -y ) = 1,\n",
        "Guaranteed X and Z independent given Y? yes\n",
        "§ Observing the cause blocks influence\n",
        "between effects\n",
        "Common Effect:\n",
        "Last configuration: two causes of one\n",
        "effect (v-structures)\n",
        "Are X and Y independent?\n",
        "§ Yes: the ballgame and the rain cause traffic, but\n",
        "they are not correlated\n",
        "§ Still need to prove they must be (try it!)\n",
        "§ Are X and Y independent given Z?\n",
        "§ No: seeing traffic puts the rain and the ballgame in\n",
        "competition as explanation.\n",
        "§ This is backwards from the other cases\n",
        "§ Observing an effect activates influence between\n",
        "possible causes.\n",
        "The General Case: \n",
        "§ General question: in a given BN, are two variables independent\n",
        "(given evidence)?\n",
        "§ Solution: analyze the graph\n",
        "§ Any complex example can be broken\n",
        "into repetitions of the three canonical cases\n",
        "Reachability:\n",
        "§ Recipe: shade evidence nodes, look\n",
        "for paths in the resulting graph\n",
        "§ Attempt 1: if two nodes are connected\n",
        "by an undirected path not blocked by\n",
        "a shaded node, they are conditionally\n",
        "independent\n",
        "§ Almost works, but not quite\n",
        "§ Where does it break?\n",
        "§ Answer: the v-structure at T doesn’t count\n",
        "as a link in a path unless “active”\n",
        "Active / Inactive Paths:\n",
        "§ Question: Are X and Y conditionally independent given\n",
        "evidence variables {Z}?\n",
        "§ Yes, if X and Y “d-separated” by Z\n",
        "§ Consider all (undirected) paths from X to Y\n",
        "§ No active paths = independence!\n",
        "§ A path is active if each triple is active:\n",
        "§ Causal chain A ® B ® C where B is unobserved (either direction)\n",
        "§ Common cause A ¬ B ® C where B is unobserved\n",
        "§ Common effect (aka v-structure)\n",
        "A ® B ¬ C where B or one of its descendents is observed\n",
        "§ All it takes to block a path is a single inactive segment\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "eddf01ef-7ffb-4542-a90a-95730458adc1"
      },
      "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": 23,
      "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 \nProbabilistic Models:\n§ Models describe how (a portion of) the world works\n§ Models are always simplifications\n§ May not account for every variable\n§ May not account for all interactions between variables\n§ “All models are wrong; but some are useful.” – George E. P. Box\n§ What do we do with probabilistic models?\n§ We (or our agents) need to reason about unknown\nvariables, given evidence\n§ Example: explanation (diagnostic reasoning)\n§ Example: prediction (causal reasoning)\nReview: Independence\n§ Two variables are independent if:\nany x,y: P(x,y) = P(x)P(y)\n§ This says that their joint distribution factors into a product two\nsimpler distributions\n§ Another form:\nany x,y: P(x|y) = P(x)\n§ X ||- Y\nndependence is a simplifying modeling assumption\n§ Empirical joint distributions: at best “close” to independent\n§ What could we assume for {Weather, Traffic, Cavity, Toothache}?\nReview: Conditional Independence:\n§ P(Toothache, Cavity, Detect)\n§ If I have a cavity, the probability that the probe detects it\ndoesn't depend on whether I have a toothache:\n§ P(+detect | +toothache, +cavity) = P(+detect | +cavity)\n§ The same independence holds if I don’t have a cavity:\n§ P(+detect | +toothache, -cavity) = P(+detect| -cavity)\n§ Detect is conditionally independent of Toothache given\nCavity:\n§ P(Detect | Toothache, Cavity) = P(Detect | Cavity)\n§ Equivalent statements:\n§ P(Toothache | Detect , Cavity) = P(Toothache | Cavity)\n§ P(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity)\n§ One can be derived from the other using the chain rule\n§ Unconditional (absolute) independence very rare, and it\ndoesn’t help us make inferences about other variables.\n§ Conditional independence is our most basic and robust form\nof knowledge about uncertain environments.\n§ X is conditionally independent of Y given Z\nif and only if:\n  any x,y,z: P(x,y|z) = p(x|z)*P(y|z)\nor, equivalently, if and only if\n  any x,y,z: P(x|z,y) = P(x|z)\nX ||_ Y|Z\nConditional Independence and the Chain Rule\n§ Chain rule: P(X1,X2, ..Xn)=P(X1)P(X2|X1)P(X3|X1,X2)...\n§ Trivial decomposition:\nP(Traffic, Rain,Umbrella) = P(Rain)P(Traffic|Rain)P(Umbrella| Rain, Traffic)\n§ With assumption of conditional independence:\nP(Traffic, Rain, Umbrella) = P(Rain)P(Traffic|Rain)P(Umbrella|Rain)\n§ Bayes’nets / graphical models help us express conditional independence assumptions\nBayes’ Nets: Big Picture:\n§ Two problems with using full joint distribution tables\nas our probabilistic models:\n§ Unless there are only a few variables, the joint is WAY too\nbig to represent explicitly\n§ Hard to learn (estimate) anything empirically about more\nthan a few variables at a time\n§ Bayes’ nets: a technique for describing complex joint\ndistributions (models) using simple, local\ndistributions (conditional probabilities)\n§ More properly called graphical models\n§ We describe how variables locally interact\n§ Local interactions chain together to give global, indirect\ninteractions\nGraphical Model Notation:\n§ Nodes: variables (with domains)\n§ Can be assigned (observed) or unassigned\n(unobserved)\n§ Arcs: interactions\n§ Indicate “direct influence” between variables\n§ Formally: encode conditional independence\n(more later)\n§ For now: imagine that arrows mean\ndirect causation (in general, they don’t!)\n§ No interactions between variables: absolute independence(no arrors)\nBayes’ Net Semantics:\n§ A set of nodes, one per variable X\n§ A directed, acyclic graph\n§ A conditional distribution for each node\n§ A collection of distributions over X, one for each\ncombination of parents’ values\nP(X|a1,a2,....an)\n§ CPT: conditional probability table\n§ Description of a noisy “causal” process\nA Bayes net = Topology (graph) + Local Conditional Probabilities\nProbabilities in BNs\n§ Bayes’ nets implicitly encode joint distributions\n§ As a product of local conditional distributions\n§ To see what probability a BN gives to a full assignment, multiply all the\nrelevant conditionals together:\nP(x1,x2, ...,xn) = product(i=1 to n) P(xi|parent(Xi))\n§ Not every BN can represent every joint distribution\n§ The topology enforces certain conditional independencies\nOnly distributions whose variables are absolutely independent can be\nrepresented by a Bayes’ net with no arcs\n\n\n\nindependence is not guaranteed.\n§ Example:\n§ Project due causes both forums busy\nand office hours full\n§ In numbers:\nP( +x | +y ) = 1, P( -x | -y ) = 1,\nP( +z | +y ) = 1, P( -z | -y ) = 1,\nGuaranteed X and Z independent given Y? yes\n§ Observing the cause blocks influence\nbetween effects\nCommon Effect:\nLast configuration: two causes of one\neffect (v-structures)\nAre X and Y independent?\n§ Yes: the ballgame and the rain cause traffic, but\nthey are not correlated\n§ Still need to prove they must be (try it!)\n§ Are X and Y independent given Z?\n§ No: seeing traffic puts the rain and the ballgame in\ncompetition as explanation.\n§ This is backwards from the other cases\n§ Observing an effect activates influence between\npossible causes.\nThe General Case: \n§ General question: in a given BN, are two variables independent\n(given evidence)?\n§ Solution: analyze the graph\n§ Any complex example can be broken\ninto repetitions of the three canonical cases\nReachability:\n§ Recipe: shade evidence nodes, look\nfor paths in the resulting graph\n§ Attempt 1: if two nodes are connected\nby an undirected path not blocked by\na shaded node, they are conditionally\nindependent\n§ Almost works, but not quite\n§ Where does it break?\n§ Answer: the v-structure at T doesn’t count\nas a link in a path unless “active”\nActive / Inactive Paths:\n§ Question: Are X and Y conditionally independent given\nevidence variables {Z}?\n§ Yes, if X and Y “d-separated” by Z\n§ Consider all (undirected) paths from X to Y\n§ No active paths = independence!\n§ A path is active if each triple is active:\n§ Causal chain A ® B ® C where B is unobserved (either direction)\n§ Common cause A ¬ B ® C where B is unobserved\n§ Common effect (aka v-structure)\nA ® B ¬ C where B or one of its descendents is observed\n§ All it takes to block a path is a single inactive segment\n \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Machine Learning\n",
        "Up until now: how use a model to make optimal decisions\n",
        "Machine learning: how to acquire a model from data /\n",
        "experience\n",
        "• Learning parameters (e.g. probabilities)\n",
        "• Learning structure (e.g. BN graphs)\n",
        "• Learning hidden concepts (e.g. clustering)\n",
        "Today: model-based classification with Naive Bayes and\n",
        "Perceptrons\n",
        "Spam Classification\n",
        "Input: an email\n",
        "Output: spam/ham\n",
        "Setup:\n",
        "• Get a large collection of example emails, each\n",
        "labeled “spam” or “ham”\n",
        "• Note: someone has to hand label all this data!\n",
        "• Want to learn to predict labels of new, future\n",
        "emails\n",
        "Features: The attributes used to make the\n",
        "ham / spam decision\n",
        "• Words: FREE!\n",
        "• Text Patterns: $dd, CAPS\n",
        "• Non-text: SenderInContacts\n",
        "Digit Recognition\n",
        "Input: images / pixel grids\n",
        "Output: a digit 0-9\n",
        "Setup:\n",
        "• Get a large collection of example images, each labeled with a digit\n",
        "• Note: someone has to hand label all this data!\n",
        "• Want to learn to predict labels of new, future digit images\n",
        "Features: The attributes used to make the digit decision\n",
        "• Pixels: (6,8)=ON\n",
        "• Shape Patterns: NumComponents, AspectRatio, NumLoops\n",
        "• …  \n",
        "Review Other Classification Tasks\n",
        "Classification: given inputs x, predict labels y\n",
        "Examples:\n",
        "• Spam detection (input: document,\n",
        "classes: spam / ham)\n",
        "• OCR (input: images, classes: characters)\n",
        "• Medical diagnosis (input: symptoms,\n",
        "classes: diseases)\n",
        "• Automatic essay grading (input: document,\n",
        "classes: grades)\n",
        "• Fraud detection (input: account activity,\n",
        "classes: fraud / no fraud)\n",
        "• Customer service email routing\n",
        "• … many more\n",
        "Classification is an important commercial technology\n",
        "Model-Based Classification\n",
        "Model-based approach\n",
        "• Build a model (e.g. Bayes’ net) where both the label and\n",
        "features are random variables\n",
        "• Instantiate any observed features\n",
        "• Query for the distribution of the\n",
        "label conditioned on the features\n",
        "Challenges\n",
        "• What structure should the BN\n",
        "have?\n",
        "• How should we learn its\n",
        "parameters?  \n",
        "....\n",
        "Naïve Bayes for Digits\n",
        "Naïve Bayes: Assume all features are independent effects of the label\n",
        "Simple digit recognition version:\n",
        "• One feature (variable) Fij for each grid position <i,j>\n",
        "• Feature values are on / off, based on whether intensity\n",
        "is more or less than 0.5 in underlying image\n",
        "• Each input maps to a feature vector, e.g.\n",
        "• Here: lots of features, each is binary valued\n",
        "Naïve Bayes model:\n",
        "What do we need to learn?\n",
        "General Naïve Bayes: |Y| labels, |Y| x |F|n values, n x |F| x |Y|parameters,\n",
        "We only have to specify how each feature depends on the class\n",
        "Total number of parameters is linear in number of features\n",
        "Model is very simplistic, but often works anyway  \n",
        "Inference for Naïve Bayes\n",
        "Goal: compute posterior distribution over label variable Y\n",
        "• Step 1: get joint probability of label and evidence for each label\n",
        "• Step 2: sum to get probability of evidence\n",
        "• Step 3: normalize by dividing Step 1 by Step 2\n",
        "General Naïve Bayes\n",
        "What do we need in order to use Naïve Bayes?\n",
        "• Inference method (we just saw this part)\n",
        "• Start with a bunch of probabilities: P(Y) and the P(Fi\n",
        "|Y) tables\n",
        "• Use standard inference to compute P(Y|F1…Fn)\n",
        "• Nothing new here\n",
        "• Estimates of local conditional probability tables\n",
        "• P(Y), the prior over labels\n",
        "• P(Fi\n",
        "|Y) for each feature (evidence variable)\n",
        "• These probabilities are collectively called the parameters of the\n",
        "model and denoted by q\n",
        "• Up until now, we assumed these appeared by magic, but…\n",
        "• …they typically come from training data counts: we’ll look at this\n",
        "soon  \n",
        "\n",
        "Summary\n",
        "Bayes rule lets us do diagnostic queries with causal probabilities\n",
        "The naïve Bayes assumption takes all features to be independent given\n",
        "the class label\n",
        "We can build classifiers out of a naïve Bayes model using training data\n",
        "Smoothing estimates is important in real systems\n",
        "Classifier confidences are useful, when you can get them  \n",
        "What to Do About Errors\n",
        "Problem: there’s still spam in your inbox\n",
        "Need more features – words aren’t enough!\n",
        "• Have you emailed the sender before?\n",
        "• Have 1M other people just gotten the same email?\n",
        "• Is the sending information consistent?\n",
        "• Is the email in ALL CAPS?\n",
        "• Do inline URLs point where they say they point?\n",
        "• Does the email address you by (your) name?\n",
        "Naïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are\n",
        "word occurrences)  \n",
        "Perceptrons:\n",
        "Some (Simplified) Biology\n",
        "Very loose inspiration: human neurons;\n",
        "Linear Classifiers\n",
        "Inputs are feature values\n",
        "Each feature has a weight\n",
        "Sum is the activation\n",
        "If the activation is:\n",
        "• Positive, output +1\n",
        "• Negative, output -1;\n",
        "Feature Vectors:\n",
        "Weights\n",
        "Binary case: compare features to a weight vector\n",
        "Learning: figure out the weight vector from examples  \n",
        "Dot product positive\n",
        "means the positive class\n",
        "Decision Rules:\n",
        "Binary Decision Rule\n",
        "In the space of feature vectors\n",
        "• Examples are points\n",
        "• Any weight vector is a hyperplane\n",
        "• One side corresponds to Y=+1\n",
        "• Other corresponds to Y=-1\n",
        "\n",
        "Weight Updates:\n",
        "Learning: Binary Perceptron\n",
        "Start with weights = 0\n",
        "For each training instance:\n",
        "• Classify with current weights\n",
        "• If correct (i.e., y=y*), no change!\n",
        "• If wrong: adjust the weight vector \n",
        "Learning: Binary Perceptron\n",
        "Start with weights = 0\n",
        "For each training instance:\n",
        "• Classify with current weights\n",
        "• If correct (i.e., y=y*), no change!\n",
        "• If wrong: adjust the weight vector\n",
        "by adding or subtracting the\n",
        "feature vector. Subtract if y* is -1.\n",
        "3Blue1Brown\n",
        "Need a refresher on linear algebra topics like vector addition and matrix multiplication?\n",
        "I recommend the wonderful YouTube series by Grant Sanderson. His channel is called\n",
        "3Blue1Brown.\n",
        "Grant gives intuitive visual tutorials to a ton of math concepts\n",
        "Here is his “Essence of Linear Algebra” series:\n",
        "Examples: Perceptron\n",
        "Separable Case  \n",
        "Multiclass Decision Rule\n",
        "If we have multiple classes:\n",
        "• A weight vector for each class:\n",
        "• Score (activation) of a class y:\n",
        "• Prediction highest score wins:  \n",
        "Learning: Multiclass Perceptron\n",
        "Start with all weights = 0\n",
        "Pick up training examples one by one\n",
        "Predict with current weights\n",
        "If correct, no change!\n",
        "If wrong: lower score of wrong\n",
        "answer, raise score of right answer  \n",
        "Example: Multiclass Perceptron:\n",
        "\"win the vote”\n",
        "“win the election”\n",
        "“win the game”;\n",
        "Properties of Perceptrons\n",
        "Separability: true if some parameters get the training\n",
        "set perfectly correct\n",
        "Convergence: if the training is separable, perceptron\n",
        "will eventually converge (binary case)\n",
        "Mistake Bound: the maximum number of mistakes\n",
        "(binary case) related to the margin or degree of\n",
        "separability;\n",
        "\n",
        "Examples: Perceptron\n",
        "Non-Separable Case;\n",
        "\n",
        "Improving the Perceptron;\n",
        "Problems with the Perceptron;\n",
        "Noise: if the data isn’t separable,\n",
        "weights might thrash\n",
        "• Averaging weight vectors over\n",
        "time can help (averaged\n",
        "perceptron)\n",
        "Mediocre generalization: finds a\n",
        "“barely” separating solution\n",
        "Overtraining: test / held-out\n",
        "accuracy usually rises, then falls\n",
        "• Overtraining is a kind of\n",
        "overfitting;\n",
        "Fixing the Perceptron\n",
        "Idea: adjust the weight update to mitigate these effects\n",
        "MIRA*: choose an update size that fixes the current\n",
        "mistake…\n",
        "… but, minimizes the change to w. The +1 helps to generalize.\n",
        "Guessed y instead of y*on example x with features f(x);\n",
        "Minimum Correcting Update:min not t=0, or would not have\n",
        "made an error, so min will be\n",
        "where equality holds.\n",
        "Maximum Step Size\n",
        "In practice, it’s also bad to make updates that are too large\n",
        "• Example may be labeled incorrectly\n",
        "• You may not have enough features\n",
        "• Solution: cap the maximum possible value of t with some\n",
        "constant C.\n",
        "• Corresponds to an optimization that assumes nonseparable data\n",
        "• Usually converges faster than perceptron\n",
        "• Usually better, especially on noisy data.\n",
        "Linear Separators:\n",
        "Which of these linear separators is optimal?\n",
        "Support Vector Machines\n",
        "Maximizing the margin: good according to intuition, theory, practice\n",
        "Only support vectors matter; other training examples are ignorable\n",
        "Support vector machines (SVMs) find the separator with max\n",
        "margin\n",
        "Basically, SVMs are MIRA where you optimize over all examples at\n",
        "once.\n",
        "Classification: Comparison\n",
        "Naïve Bayes\n",
        "• Builds a model training data\n",
        "• Gives prediction probabilities\n",
        "• Strong assumptions about feature independence\n",
        "• One pass through data (counting)\n",
        "Perceptrons / MIRA:\n",
        "• Makes less assumptions about data\n",
        "• Mistake-driven learning\n",
        "• Multiple passes through data (prediction)\n",
        "• Often more accurate;Perceptrons\n",
        "Perceptrons were developed in the 1950s\n",
        "and 1960s loosely inspired by the neuron;\n",
        "inputs -> weights->weighted sum -> activation function(threshold)->output\n",
        "output:0 if sum(i)wixi <= threshold\n",
        "output:1 if sum(j)wjxj > threshold\n",
        "Perceptrons for decision making\n",
        "We can think about the perceptron or the sigmoid neuron as a device that makes\n",
        "decisions by weighing up evidence.\n",
        "Example: Suppose there’s a cheese festival in your town. You like cheese.  \n",
        "Perceptrons for decision making\n",
        "You might use 3 factors to decide whether to go.\n",
        "1. Is the weather good?\n",
        "2. Can your loyal companion come with you?\n",
        "3. Is the festival near public transit?\n",
        "These can be the binary input values to a perceptron  \n",
        "Perceptrons for decision making\n",
        "By varying weights and the threshold we get different models of decision making\n",
        "Example 1: w1= 6 w2 = 2 w3 = 2, threshold = 5\n",
        "Example 2: w1= 6 w2 = 2 w3 = 2, threshold = 3;\n",
        " Notational changes\n",
        "Change\t1:\tWe\tcan\twrite\t∑jwjxj as\ta\tdot\tproduct\tof\tthe\tinput\tvector\tand\tthe\tweight\tvector:\n",
        ":\n",
        "Change\t2:\t\tWe\tcan\tmove\tthe\tthreshold\tto\tother\tother\tside\tof\tthe\tinequality.\t\tWe\tdefine\ta\t\n",
        "perceptron’s\t“bias”\tas\tthe\t-1\t*\tits\tthreshold:\n",
        "b = -threshold\n",
        "Learning weights from examples\n",
        "Perceptions can be used for all kinds of classification problems.\n",
        "Think of the inputs as features representing something we want to classify.\n",
        "The feature values for inputs are fixed, but we can choose different weight vectors.\n",
        "Depending on the weight vector that we pick, we will get a different classifier. \n",
        "Binary Decision Rule:\n",
        "In the space of feature vectors\n",
        "• Examples are points\n",
        "• Any weight vector is a hyperplane\n",
        "• One side corresponds to Y=+1\n",
        "• Other corresponds to Y=-1;\n",
        "\n",
        "Weight Updates:\n",
        "Learning: Binary Perceptron\n",
        "Start with weights = 0\n",
        "For each training instance:\n",
        "• Classify with current weights\n",
        "• If correct (i.e., y=y*), no change!\n",
        "• If wrong: adjust the weight vector;\n",
        "Learning a Binary Perceptron:\n",
        "Start with weights = 0\n",
        "For each training instance:\n",
        "• Classify with current weights\n",
        "• If correct (i.e., y=y*), no change!\n",
        "• If wrong: adjust the weight vector\n",
        "by adding or subtracting the\n",
        "feature vector. Subtract if y* is -1.\n",
        "Multiclass Decision Rule\n",
        "If we have multiple classes:\n",
        "• A weight vector for each class:\n",
        "• Score (activation) of a class y:\n",
        "• Prediction highest score wins\n",
        "\n",
        "Learning: Multiclass Perceptron\n",
        "Start with all weights = 0\n",
        "Pick up training examples one by one\n",
        "Predict with current weights\n",
        "If correct, no change!\n",
        "If wrong: lower score of wrong\n",
        "answer, raise score of right answer\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8e672980-ab99-4d6f-d3c6-dc4cb8cbc067"
      },
      "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": 32,
      "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 Machine Learning\nUp until now: how use a model to make optimal decisions\nMachine learning: how to acquire a model from data /\nexperience\n• Learning parameters (e.g. probabilities)\n• Learning structure (e.g. BN graphs)\n• Learning hidden concepts (e.g. clustering)\nToday: model-based classification with Naive Bayes and\nPerceptrons\nSpam Classification\nInput: an email\nOutput: spam/ham\nSetup:\n• Get a large collection of example emails, each\nlabeled “spam” or “ham”\n• Note: someone has to hand label all this data!\n• Want to learn to predict labels of new, future\nemails\nFeatures: The attributes used to make the\nham / spam decision\n• Words: FREE!\n• Text Patterns: $dd, CAPS\n• Non-text: SenderInContacts\nDigit Recognition\nInput: images / pixel grids\nOutput: a digit 0-9\nSetup:\n• Get a large collection of example images, each labeled with a digit\n• Note: someone has to hand label all this data!\n• Want to learn to predict labels of new, future digit images\nFeatures: The attributes used to make the digit decision\n• Pixels: (6,8)=ON\n• Shape Patterns: NumComponents, AspectRatio, NumLoops\n• …  \nReview Other Classification Tasks\nClassification: given inputs x, predict labels y\nExamples:\n• Spam detection (input: document,\nclasses: spam / ham)\n• OCR (input: images, classes: characters)\n• Medical diagnosis (input: symptoms,\nclasses: diseases)\n• Automatic essay grading (input: document,\nclasses: grades)\n• Fraud detection (input: account activity,\nclasses: fraud / no fraud)\n• Customer service email routing\n• … many more\nClassification is an important commercial technology\nModel-Based Classification\nModel-based approach\n• Build a model (e.g. Bayes’ net) where both the label and\nfeatures are random variables\n• Instantiate any observed features\n• Query for the distribution of the\nlabel conditioned on the features\nChallenges\n• What structure should the BN\nhave?\n• How should we learn its\nparameters?  \n....\nNaïve Bayes for Digits\nNaïve Bayes: Assume all features are independent effects of the label\nSimple digit recognition version:\n• One feature (variable) Fij for each grid position <i,j>\n• Feature values are on / off, based on whether intensity\nis more or less than 0.5 in underlying image\n• Each input maps to a feature vector, e.g.\n• Here: lots of features, each is binary valued\nNaïve Bayes model:\nWhat do we need to learn?\nGeneral Naïve Bayes: |Y| labels, |Y| x |F|n values, n x |F| x |Y|parameters,\nWe only have to specify how each feature depends on the class\nTotal number of parameters is linear in number of features\nModel is very simplistic, but often works anyway  \nInference for Naïve Bayes\nGoal: compute posterior distribution over label variable Y\n• Step 1: get joint probability of label and evidence for each label\n• Step 2: sum to get probability of evidence\n• Step 3: normalize by dividing Step 1 by Step 2\nGeneral Naïve Bayes\nWhat do we need in order to use Naïve Bayes?\n• Inference method (we just saw this part)\n• Start with a bunch of probabilities: P(Y) and the P(Fi\n|Y) tables\n• Use standard inference to compute P(Y|F1…Fn)\n• Nothing new here\n• Estimates of local conditional probability tables\n• P(Y), the prior over labels\n• P(Fi\n|Y) for each feature (evidence variable)\n• These probabilities are collectively called the parameters of the\nmodel and denoted by q\n• Up until now, we assumed these appeared by magic, but…\n• …they typically come from training data counts: we’ll look at this\nsoon  \n\nSummary\nBayes rule lets us do diagnostic queries with causal probabilities\nThe naïve Bayes assumption takes all features to be independent given\nthe class label\nWe can build classifiers out of a naïve Bayes model using training data\nSmoothing estimates is important in real systems\nClassifier confidences are useful, when you can get them  \nWhat to Do About Errors\nProblem: there’s still spam in your inbox\nNeed more features – words aren’t enough!\n• Have you emailed the sender before?\n• Have 1M other people just gotten the same email?\n• Is the sending information consistent?\n• Is the email in ALL CAPS?\n• Do inline URLs point where they say they point?\n• Does the email address you by (your) name?\nNaïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are\nword occurrences)  \nPerceptrons:\nSome (Simplified) Biology\nVery loose inspiration: human neurons;\nLinear Classifiers\nInputs are feature values\nEach feature has a weight\nSum is the activation\nIf the activation is:\n• Positive, output +1\n• Negative, output -1;\nFeature Vectors:\nWeights\nBinary case: compare features to a weight vector\nLearning: figure out the weight vector from examples  \nDot product positive\nmeans the positive class\nDecision Rules:\nBinary Decision Rule\nIn the space of feature vectors\n• Examples are points\n• Any weight vector is a hyperplane\n• One side corresponds to Y=+1\n• Other corresponds to Y=-1\n\nWeight Updates:\nLearning: Binary Perceptron\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector \nLearning: Binary Perceptron\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector\nby adding or subtracting the\nfeature vector. Subtract if y* is -1.\n3Blue1Brown\nNeed a refresher on linear algebra topics like vector addition and matrix multiplication?\nI recommend the wonderful YouTube series by Grant Sanderson. His channel is called\n3Blue1Brown.\nGrant gives intuitive visual tutorials to a ton of math concepts\nHere is his “Essence of Linear Algebra” series:\nExamples: Perceptron\nSeparable Case  \nMulticlass Decision Rule\nIf we have multiple classes:\n• A weight vector for each class:\n• Score (activation) of a class y:\n• Prediction highest score wins:  \nLearning: Multiclass Perceptron\nStart with all weights = 0\nPick up training examples one by one\nPredict with current weights\nIf correct, no change!\nIf wrong: lower score of wrong\nanswer, raise score of right answer  \nExample: Multiclass Perceptron:\n\"win the vote”\n“win the election”\n“win the game”;\nProperties of Perceptrons\nSeparability: true if some parameters get the training\nset perfectly correct\nConvergence: if the training is separable, perceptron\nwill eventually converge (binary case)\nMistake Bound: the maximum number of mistakes\n(binary case) related to the margin or degree of\nseparability;\n\nExamples: Perceptron\nNon-Separable Case;\n\nImproving the Perceptron;\nProblems with the Perceptron;\nNoise: if the data isn’t separable,\nweights might thrash\n• Averaging weight vectors over\ntime can help (averaged\nperceptron)\nMediocre generalization: finds a\n“barely” separating solution\nOvertraining: test / held-out\naccuracy usually rises, then falls\n• Overtraining is a kind of\noverfitting;\nFixing the Perceptron\nIdea: adjust the weight update to mitigate these effects\nMIRA*: choose an update size that fixes the current\nmistake…\n… but, minimizes the change to w. The +1 helps to generalize.\nGuessed y instead of y*on example x with features f(x);\nMinimum Correcting Update:min not t=0, or would not have\nmade an error, so min will be\nwhere equality holds.\nMaximum Step Size\nIn practice, it’s also bad to make updates that are too large\n• Example may be labeled incorrectly\n• You may not have enough features\n• Solution: cap the maximum possible value of t with some\nconstant C.\n• Corresponds to an optimization that assumes nonseparable data\n• Usually converges faster than perceptron\n• Usually better, especially on noisy data.\nLinear Separators:\nWhich of these linear separators is optimal?\nSupport Vector Machines\nMaximizing the margin: good according to intuition, theory, practice\nOnly support vectors matter; other training examples are ignorable\nSupport vector machines (SVMs) find the separator with max\nmargin\nBasically, SVMs are MIRA where you optimize over all examples at\nonce.\nClassification: Comparison\nNaïve Bayes\n• Builds a model training data\n• Gives prediction probabilities\n• Strong assumptions about feature independence\n• One pass through data (counting)\nPerceptrons / MIRA:\n• Makes less assumptions about data\n• Mistake-driven learning\n• Multiple passes through data (prediction)\n• Often more accurate;Perceptrons\nPerceptrons were developed in the 1950s\nand 1960s loosely inspired by the neuron;\ninputs -> weights->weighted sum -> activation function(threshold)->output\noutput:0 if sum(i)wixi <= threshold\noutput:1 if sum(j)wjxj > threshold\nPerceptrons for decision making\nWe can think about the perceptron or the sigmoid neuron as a device that makes\ndecisions by weighing up evidence.\nExample: Suppose there’s a cheese festival in your town. You like cheese.  \nPerceptrons for decision making\nYou might use 3 factors to decide whether to go.\n1. Is the weather good?\n2. Can your loyal companion come with you?\n3. Is the festival near public transit?\nThese can be the binary input values to a perceptron  \nPerceptrons for decision making\nBy varying weights and the threshold we get different models of decision making\nExample 1: w1= 6 w2 = 2 w3 = 2, threshold = 5\nExample 2: w1= 6 w2 = 2 w3 = 2, threshold = 3;\n Notational changes\nChange\t1:\tWe\tcan\twrite\t∑jwjxj as\ta\tdot\tproduct\tof\tthe\tinput\tvector\tand\tthe\tweight\tvector:\n:\nChange\t2:\t\tWe\tcan\tmove\tthe\tthreshold\tto\tother\tother\tside\tof\tthe\tinequality.\t\tWe\tdefine\ta\t\nperceptron’s\t“bias”\tas\tthe\t-1\t*\tits\tthreshold:\nb = -threshold\nLearning weights from examples\nPerceptions can be used for all kinds of classification problems.\nThink of the inputs as features representing something we want to classify.\nThe feature values for inputs are fixed, but we can choose different weight vectors.\nDepending on the weight vector that we pick, we will get a different classifier. \nBinary Decision Rule:\nIn the space of feature vectors\n• Examples are points\n• Any weight vector is a hyperplane\n• One side corresponds to Y=+1\n• Other corresponds to Y=-1;\n\nWeight Updates:\nLearning: Binary Perceptron\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector;\nLearning a Binary Perceptron:\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector\nby adding or subtracting the\nfeature vector. Subtract if y* is -1.\nMulticlass Decision Rule\nIf we have multiple classes:\n• A weight vector for each class:\n• Score (activation) of a class y:\n• Prediction highest score wins\n\nLearning: Multiclass Perceptron\nStart with all weights = 0\nPick up training examples one by one\nPredict with current weights\nIf correct, no change!\nIf wrong: lower score of wrong\nanswer, raise score of right answer\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\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 = \"\"\" \n",
        "Logistic Regression:\n",
        "Classifier components\n",
        "Machine learning classifiers require a training corpus of M observations\n",
        "input/output pairs (x(i),y(i)).\n",
        "1. A feature representation of the input. For each input observation\n",
        "x(i)\n",
        ", this will be a vector of features [x1,x2,...,xn].\n",
        "2. A classification function that computes the estimated class y^ via\n",
        "p(y|x).\n",
        "3. An objective function for learning, usually involving minimizing\n",
        "error on training examples.\n",
        "4. An algorithm for optimizing the objective function.;\n",
        "Sentiment classifier\n",
        "Input: \"Spiraling away from narrative control as\n",
        "its first three episodes unreel, this series, about\n",
        "a post-apocalyptic future in which nearly\n",
        "everyone is blind, wastes the time of Jason\n",
        "Momoa and Alfre Woodard, among others, on a\n",
        "story that starts from a position of fun, giddy\n",
        "strangeness and drags itself forward at a\n",
        "lugubrious pace.\"\n",
        "Output: positive (1) or negative (0);\n",
        "\n",
        "Sentiment classifier\n",
        "For sentiment classification, consider an input observation x,\n",
        "represented by a vector of features [x1,x2,...,xn]. The classifier output y\n",
        "can be 1 (positive sentiment) or 0 (negative sentiment). We want to\n",
        "estimate P(y = 1|x).\n",
        "Logistic regression solves this task by learning, from a training set, a\n",
        "vector of weights and a bias term.\n",
        "We can also write this as a dot product:\n",
        "Decision boundary\n",
        "Now we have an algorithm that given an instance x computes the\n",
        "probability P(y = 1|x). How do we make a decision? \n",
        "For a test instance x, we say yes if the probability P(y = 1|x) is more than\n",
        ".5, and no otherwise. We call .5 the decision boundary；\n",
        "Extracting Features:It's hokey. There are virtually no surprises , and the writing is\n",
        "second-rate . So why was it so enjoyable? For one thing , the cast\n",
        "is great . Another nice touch is the music . I was overcome with\n",
        "the urge to get off the couch and start dancing . It sucked me in ,\n",
        "and it'll do the same to you .\n",
        "Computing Z:\n",
        "Var Definition Value Weight Product\n",
        "x1 Count of positive lexicon words 3 2.5 7.5\n",
        "x2 Count of negative lexicon words 2 -5.0 -10\n",
        "x3 Does no appear? (binary\n",
        "feature)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "The advantage of using a single matrix W for the weights of the entire layer is the\n",
        "hidden layer computation can be done efficiently with simple matrix operations.\n",
        "The computation has three steps:\n",
        "1. multiplying the weight matrix by the input vector x,\n",
        "2. adding the bias vector b, and\n",
        "3. applying the activation function g (such as Sigmoid)\n",
        "The output of the hidden layer, the vector h, is thus the following, using the sigmoid\n",
        "function σ:\n",
        "h = σ(Wx+b) \n",
        "Equations for a feedforward network\n",
        "Like the hidden layer, the output layer has a weight matrix U.\n",
        "Its weight matrix is multiplied by its input vector (h) to produce the intermediate output z.\n",
        "z=Uh  ;\n",
        "Equations for a feedforward network\n",
        "Here are the final equations for a feedforward network with a single hidden layer,\n",
        "which takes an input vector x, outputs a probability distribution y, and is parameterized\n",
        "by weight matrices W and U and a bias vector b:\n",
        "h = σ(Wx+b)\n",
        "z = Uh\n",
        "y = softmax(z)\n",
        "Like with logistic regression, softmax normalizes the output and turns it into a\n",
        "probability distribution.;\n",
        "Training Neural Nets\n",
        "Like logistic regression, we want to learn the best parameters for the neural net to\n",
        "make its predictions y^ as close to possible as the gold standard labels in our training\n",
        "data y.\n",
        "What do we need?\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d85184c5-d99a-4fcd-d50b-e02b3a79fb88"
      },
      "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": 27,
      "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 \nLogistic Regression:\nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i),y(i)).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class y^ via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.;\nSentiment classifier\nInput: \"Spiraling away from narrative control as\nits first three episodes unreel, this series, about\na post-apocalyptic future in which nearly\neveryone is blind, wastes the time of Jason\nMomoa and Alfre Woodard, among others, on a\nstory that starts from a position of fun, giddy\nstrangeness and drags itself forward at a\nlugubrious pace.\"\nOutput: positive (1) or negative (0);\n\nSentiment classifier\nFor sentiment classification, consider an input observation x,\nrepresented by a vector of features [x1,x2,...,xn]. The classifier output y\ncan be 1 (positive sentiment) or 0 (negative sentiment). We want to\nestimate P(y = 1|x).\nLogistic regression solves this task by learning, from a training set, a\nvector of weights and a bias term.\nWe can also write this as a dot product:\nDecision boundary\nNow we have an algorithm that given an instance x computes the\nprobability P(y = 1|x). How do we make a decision? \nFor a test instance x, we say yes if the probability P(y = 1|x) is more than\n.5, and no otherwise. We call .5 the decision boundary；\nExtracting Features:It's hokey. There are virtually no surprises , and the writing is\nsecond-rate . So why was it so enjoyable? For one thing , the cast\nis great . Another nice touch is the music . I was overcome with\nthe urge to get off the couch and start dancing . It sucked me in ,\nand it'll do the same to you .\nComputing Z:\nVar Definition Value Weight Product\nx1 Count of positive lexicon words 3 2.5 7.5\nx2 Count of negative lexicon words 2 -5.0 -10\nx3 Does no appear? (binary\nfeature)\n\n\n\n\n\n\n\n\n\n\n\nThe advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\nThe computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\nThe output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ:\nh = σ(Wx+b) \nEquations for a feedforward network\nLike the hidden layer, the output layer has a weight matrix U.\nIts weight matrix is multiplied by its input vector (h) to produce the intermediate output z.\nz=Uh  ;\nEquations for a feedforward network\nHere are the final equations for a feedforward network with a single hidden layer,\nwhich takes an input vector x, outputs a probability distribution y, and is parameterized\nby weight matrices W and U and a bias vector b:\nh = σ(Wx+b)\nz = Uh\ny = softmax(z)\nLike with logistic regression, softmax normalizes the output and turns it into a\nprobability distribution.;\nTraining Neural Nets\nLike logistic regression, we want to learn the best parameters for the neural net to\nmake its predictions y^ as close to possible as the gold standard labels in our training\ndata y.\nWhat do we need?\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Word Meaning: How should we represent the meaning of a word?\n",
        "In N-gram LMs we represented words as a string of letters or as an index in a\n",
        "vocabulary list.\n",
        "Ideally, we want a meaning representation to encode:\n",
        "1. Synonyms – words that have similar meanings\n",
        "2. Antonyms – words that have opposite meanings\n",
        "3. Connotations – words that are positive or negative\n",
        "4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\n",
        "purchasing event\n",
        "5. Support for entailment;\n",
        "Entailment in formal semantics\n",
        "All animals have an ulnar artery\n",
        "⇒\n",
        "All dogs have an ulnar artery\n",
        "+ Mathematically well-understood\n",
        "+ Powerful machinery for handling logical operations\n",
        "- Knowledge must come from somewhere else;\n",
        "Lexical Semantics: wordnet,vector space models;  \n",
        "Word similarity\n",
        "Most words don’t have many synonyms, but they do have a lot of similar words. Cat is\n",
        "not a synonym of dog, but cats and dogs are certainly similar words.\n",
        "“fast” is similar to “rapid”\n",
        "“tall” is similar to “height”\n",
        "Useful for applications like question answering;\n",
        "Word similarity\n",
        "Most words don’t have many synonyms, but they do have a lot of similar words. \n",
        "Distributional Hypothesis: \n",
        "If we consider optometrist and eye-doctor we find\n",
        "that, as our corpus of utterances grows, these two\n",
        "occur in almost the same environments. In contrast,\n",
        "there are many sentence environments in which\n",
        "optometrist occurs but lawyer does not...\n",
        "It is a question of the relative frequency of such\n",
        "environments, and of what we will obtain if we ask\n",
        "an informant to substitute any word he wishes for\n",
        "optometrist (not asking what words have the same\n",
        "meaning).\n",
        "These and similar tests all measure the probability\n",
        "of particular environments occurring with particular\n",
        "elements... If A and B have almost identical\n",
        "environments we say that they are synonyms.\n",
        "–Zellig Harris (1954);\n",
        "Intuition of distributional word similarity\n",
        "Nida (1975) example:\n",
        "A bottle of tesgüino is on the table\n",
        "Everybody likes tesgüino\n",
        "Tesgüino makes you drunk\n",
        "We make tesgüino out of corn.\n",
        "From context words humans can guess tesgüino means\n",
        "an alcoholic beverage like beer\n",
        "Intuition for algorithm:\n",
        "Two words are similar if they have similar word contexts.;\n",
        "History of Vector Space Models\n",
        "Vector Space Models were initially developed in the SMART information retrieval\n",
        "system (Salton, 1971)\n",
        "Each document in a collection is represented as point in a space (a vector in a vector\n",
        "space)\n",
        "A user’s query is a pseudo-document and is represented as a point in the same space\n",
        "as the documents\n",
        "Perform IR by retrieving documents whose vectors are close together in this space to\n",
        "the query vector ;\n",
        "Term-Document Matrix: \n",
        "Each column vector represents a Document, Each row vector\n",
        "represents a Term, The value in a cell is\n",
        "based on how often that term\n",
        "occurred in that document, The length of the\n",
        "document vectors is the size of the vocabulary, Document vectors\n",
        "can be sparse\n",
        "(most values are 0), We can measure\n",
        "how similar two\n",
        "documents are\n",
        "by comparing their\n",
        "column vectors;\n",
        "What can document\n",
        "similarity let you do?\n",
        "Word similarity for plagiarism detection;\n",
        "Term-Document Matrix: What does comparing\n",
        "two row vectors do? Vector comparisons;\n",
        "docY is a positive movie review\n",
        "docx is a less positive movie review\n",
        "A = \"superb\" positive / low frequency\n",
        "B = \"good\" positive / high frequency\n",
        "C = \"disappointing\" negative / high\n",
        "frequency;\n",
        "Oh no! Good is\n",
        "closer to\n",
        "Disappointing\n",
        "than to Superb.\n",
        "Vector L2 (length)\n",
        "Normalization;Divide each vector by its L2 length;\n",
        "Cosine Distance:Cosine does the L2\n",
        "normalization too, Cosine angle between\n",
        "vectors tells us their similarity ;\n",
        "Term-Term Matrix: AKA Term-Context Matrix; \n",
        "Length of the vector is now |V|\n",
        "instead of number of documents; The value in a cell indicates how\n",
        "often abandon appears in a\n",
        "context window surrounding\n",
        "abdicate;\n",
        "Context windows:\n",
        "w-2, w-1 target_word w+1 w+2\n",
        "The government most not abdicate responsibility to non-elected\n",
        "it has led men to abdicate their family responsibilities\n",
        "other demands, but declining to abdicate his responsibility\n",
        "leaders abdicate their role and present people with no plans;\n",
        "Context windows:\n",
        "Occur in a window of +/- 2 words, in the same sentence, in the\n",
        "same document\n",
        "Instead of window of words use more complex contexts:\n",
        "dependency patters. Subj-of-verb, adj-mod, obj-of-verb\n",
        "Languages have long distance dependencies\n",
        "The pictures are beautiful.\n",
        "The pictures of the old man are beautiful.\n",
        "The pictures of the old man holding his grandchild are beautiful.;\n",
        "\n",
        "Using syntax to define a word’s context\n",
        "Zellig Harris (1968) “The meaning of entities, and the meaning of grammatical\n",
        "relations among them, is related to the restriction of combinations of these\n",
        "entities relative to other entities”\n",
        "Duty and Responsibility have similar syntactic distributions\n",
        "Modified by adjectives\n",
        "additional, administrative, assumed,\n",
        "collective, congressional, constitutional\n",
        "\n",
        "\n",
        "\n",
        "Chain rule\n",
        "In LMs we user chain rule to get the conditional probability of the next\n",
        "word in the sequence given all of the previous words:\n",
        "What assumption do we make in n-gram LMs to simplify this?\n",
        "The probability of the next word only depends on the previous n-1\n",
        "words.\n",
        "A small n makes it easier for us to get an estimate of the probability\n",
        "from data.;\n",
        "Probability tables\n",
        "We construct tables to look up the probability of\n",
        "seeing a word given a history.\n",
        "The tables only store observed sequences.\n",
        "What happens when we have a new (unseen)\n",
        "combination of n words?;\n",
        "Unseen sequences\n",
        "What happens when we have a new (unseen) combination of n words?\n",
        "1. Back-off\n",
        "2. Smoothing / interpolation\n",
        "We are basically just stitching together short sequences of observed\n",
        "words;\n",
        "Alternate idea:Let’s try generalizing.\n",
        "Intuition: Take a sentence like\n",
        "The cat is walking in the bedroom\n",
        "And use it when we assign probabilities to similar sentences like\n",
        "The dog is running around the room;\n",
        "Neural Language Models:\n",
        "Neural Language models have several advantages over n-gram LMs:\n",
        "1. They don’t need smoothing\n",
        "2. They can handle much longer histories.\n",
        "3. They can generalize over contexts of similar words.\n",
        "4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
        "Disadvantage: slower to train than traditional n-gram LMs;\n",
        "Neural LMs (Bengio et al 2003)\n",
        "1. Associate each word in the vocabulary with a vector-representation, thereby\n",
        "creating a notion of similarity between words.\n",
        "2. Express the joint probability function of a word sequence in terms of the word\n",
        "vectors for the words in that sequence.\n",
        "3. Simultaneously learn the word vectors and the parameters of the function.\n",
        "The word vectors are low-dimensional (d=30 to d=100) dense vectors, like we’ve seen\n",
        "before.\n",
        "The probability function is expressed the product of conditional probabilities of the\n",
        "next word given the previous word, using a multi-layer, feed forward neural network.;\n",
        "Neural LMs\n",
        "The input to the neural network is a k-gram of words w1:k.\n",
        "The output is a probability distribution over the next word.\n",
        "The k context words are treated as a word window. Each word is associated with an\n",
        "embedding vector:\n",
        "The input vector x just concatenates v(w) for each of the k words:;\n",
        "Neural LMs\n",
        "The input x is fed into a neural network with 1 or more hidden layers:；\n",
        "Training\n",
        "The training examples are simply word k-grams from the corpus\n",
        "The identities of the first k-1 words are used as features, and the last word is used as\n",
        "the target label for the classification.\n",
        "Conceptually, the model is trained using cross-entropy loss. ；\n",
        "Advantages of NN LMs\n",
        "Better results. They achieve better preplexity scores than SOTA n-gram LMs.\n",
        "Larger N. NN LMs can scale to much larger orders of n. This is achievable because\n",
        "parameters are associated only with individual words, and not with n-grams.\n",
        "They generalize across contexts. For example, by observing that the words blue,\n",
        "green, red, black, etc. appear in similar contexts, the model will be able to assign a\n",
        "reasonable score to the green car even though it never observed in training, because it\n",
        "did observe blue car and red car.\n",
        "A by-product of training are word embedding；\n",
        "A Neural Probabilistic LM\n",
        "1. Use a vector space model where the words are vectors with real\n",
        "values ℝm. m=30, 60, 100. This gives a way to compute word\n",
        "similarity.\n",
        "2. Define a function that returns a joint probability of words in a\n",
        "sequence based on a sequence of these vectors.\n",
        "3. Simultaneously learn the word representations and the probability\n",
        "function from data.\n",
        "Seeing one of the cat/dog sentences allows them to increase the\n",
        "probability for that sentence and its combinatorial # of “neighbor”\n",
        "sentences in vector space；\n",
        "A Neural Probabilistic LM\n",
        "Given:\n",
        "A training set w1 … wt where wt ∈V\n",
        "Learn:\n",
        "f(w1 … wt) = P(wt|w1 … wt-1)\n",
        "Subject to giving a high probability to an unseen text/dev set (e.g. minimizing\n",
        "the perplexity)\n",
        "Constraint:\n",
        "Create a proper probability distribution (e.g. sums to 1) so that we can take\n",
        "the product of conditional probabilities to get the joint probability of a\n",
        "sentence；\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "fce37184-8369-4f29-c74c-86cea9322300"
      },
      "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": 29,
      "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 \nLogistic Regression:\nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i),y(i)).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class y^ via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.;\nSentiment classifier\nInput: \"Spiraling away from narrative control as\nits first three episodes unreel, this series, about\na post-apocalyptic future in which nearly\neveryone is blind, wastes the time of Jason\nMomoa and Alfre Woodard, among others, on a\nstory that starts from a position of fun, giddy\nstrangeness and drags itself forward at a\nlugubrious pace.\"\nOutput: positive (1) or negative (0);\n\nSentiment classifier\nFor sentiment classification, consider an input observation x,\nrepresented by a vector of features [x1,x2,...,xn]. The classifier output y\ncan be 1 (positive sentiment) or 0 (negative sentiment). We want to\nestimate P(y = 1|x).\nLogistic regression solves this task by learning, from a training set, a\nvector of weights and a bias term.\nWe can also write this as a dot product:\nDecision boundary\nNow we have an algorithm that given an instance x computes the\nprobability P(y = 1|x). How do we make a decision? \nFor a test instance x, we say yes if the probability P(y = 1|x) is more than\n.5, and no otherwise. We call .5 the decision boundary；\nExtracting Features:It's hokey. There are virtually no surprises , and the writing is\nsecond-rate . So why was it so enjoyable? For one thing , the cast\nis great . Another nice touch is the music . I was overcome with\nthe urge to get off the couch and start dancing . It sucked me in ,\nand it'll do the same to you .\nComputing Z:\nVar Definition Value Weight Product\nx1 Count of positive lexicon words 3 2.5 7.5\nx2 Count of negative lexicon words 2 -5.0 -10\nx3 Does no appear? (binary\nfeature)\n\n\n\n\n\n\n\n\n\n\n\nThe advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\nThe computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\nThe output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ:\nh = σ(Wx+b) \nEquations for a feedforward network\nLike the hidden layer, the output layer has a weight matrix U.\nIts weight matrix is multiplied by its input vector (h) to produce the intermediate output z.\nz=Uh  ;\nEquations for a feedforward network\nHere are the final equations for a feedforward network with a single hidden layer,\nwhich takes an input vector x, outputs a probability distribution y, and is parameterized\nby weight matrices W and U and a bias vector b:\nh = σ(Wx+b)\nz = Uh\ny = softmax(z)\nLike with logistic regression, softmax normalizes the output and turns it into a\nprobability distribution.;\nTraining Neural Nets\nLike logistic regression, we want to learn the best parameters for the neural net to\nmake its predictions y^ as close to possible as the gold standard labels in our training\ndata y.\nWhat do we need?\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "4d7533c9-5b90-44b0-9b12-676f8dcbcc96"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nCombining Beliefs and Desires under Uncertainty:  assume that the agent\nassigns a probability P(s) to each possible current state s, P(s\n′|s,a), the probability that action a in state s reaches state s′.\nP(RESULT(a)=s′), P(RESULT(a)=s′) = ∑sP(s)P(s′|s,a).The MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice.An AI\nsystem acting on behalf of a human may not know the human’s true utility function, so there\nmay be uncertainty about U. In summary, decision theory is not a panacea that solves the\nAI problem—but it does provide the beginnings of a basic mathematical framework that is\ngeneral enough to define the AI problem. If an agent acts so as to maximize a utility function that \ncorrectly reflects the performance measure,then the agent will achieve the highest possible performance score (averaged over all the\npossible environments),transition from the\nexternal performance measure to an internal utility function.\nThe performance measure gives\na score for a history—a sequence of states.The utility function applies to the very next state.\n  $P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nThe Basis of Utility Theory:\nmaximizing the average utility \n16.2.1 Constraints on rational preferences  \nA ≻ B the agent prefers A over B.\nA ∼ B the agent is indifferent between A and B.\nA ≻∼ B the agent prefers A over B or is indifferent between them.\nWe can think of the set of outcomes for each action\nas a lottery—think of each action as a ticket. A lottery L with possible outcomes S1,...,Sn\nLottery that occur with probabilities p1,..., pn is written\nL = [p1,S1; p2,S2; ... pn,Sn].  \nOrderability: Given any two lotteries, a rational agent must either prefer one or else\nrate them as equally preferable.  \nTransitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C,\nthen the agent must prefer A to C.  \nContinuity: If some lottery B is between A and C in preference, then there is some\nprobability p for which the rational agent will be indifferent between getting B for sure\nand the lottery that yields A with probability p and C with probability 1− p.  \nA ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B.  \nSubstitutability: If an agent is indifferent between two lotteries A and B, then the\nagent is indifferent between two more complex lotteries that are the same except that\nB is substituted for A in one of them. This holds regardless of the probabilities and the\nother outcome(s) in the lotteries.\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n 16.3 Utility Functions: Utility functions map from lotteries to real numbers. an agent can have any\npreferences it likes.  \n16.3.1 Utility assessment and utility scales:\npreference elicitation, involves presenting choices to the human and using the\nobserved preferences to pin down the underlying utility function.  \nTypically, we fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible\ncatastrophe” at U(S) = u⊥. (Both of these should be finite.) Normalized utilities use a scale Normalized utilities\nwith u⊥ = 0 and u⊤ = 1. Given a utility scale between u⊤ and u⊥, we can assess the utility of any particular prize\nS by asking the agent to choose between S and a standard lottery [p,u⊤; (1− p),u⊥]. The Standard lottery\nprobability p is adjusted until the agent is indifferent between S and the standard lottery.  \n Once this is done for each prize,\nthe utilities for all lotteries involving those prizes are determined. \n16.3.2 The utility of money:\nagents with curves of this shape are risk-averse(U(L) < U(SEMV(L))): they prefer a sure thing with a\npayoff that is less than the expected monetary value of a gamble. On the other hand, in the\n“desperate” region at large negative wealth, the behavior is risk-seeking. \nThe value an agent will accept in lieu of a lottery is called the certainty equivalent of the\nlottery,  Studies have shown that most people will accept about $400 in lieu of a gamble that\ngives $1000 half the time and $0 the other half—that is, the certainty equivalent of the lottery\nis $400, while the EMV is $500. Assuming the coin is fair, the expected monetary value (EMV) of the gamble is 1/2($0) + \n1/2($2,500,000) = $1,250,000  \n\n\n\n\n\n\n\n\n\n\n\n\n \n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n making decisions in a stochastic environment.Sequential decision problems,\nin which the agent’s utility depends on a sequence of decisions  \n17.1 Sequential Decision Problems  \nWe will assume that transitions are Markovian: the\nprobability of reaching s'\nfrom s depends only on s and not on the history of earlier states.\nThe decision problem is sequential, the utility function will depend\non a sequence of states and actions—an environment history—rather than on a single state.\nwe\nsimply stipulate that for every transition from s to s′ via action a, the agent receives a reward \nR(s,a,s′). The rewards may be positive or negative, but they are bounded by ±Rmax.\nThe utility of an environment history is just\n(for now) the sum of the rewards received.\nTerminal states (which have rewards +1 and –1). \nMDP consists of a set of states (with an initial state s0); a set ACTIONS(s) of actions\nin each state; a transition model P(s′|s,a); and a reward function R(s,a,s′).\nMethods for solving MDPs usually involve dynamic programming: simplifying a problem by recursively \nbreaking it into smaller pieces and remembering the optimal solutions to the pieces.\nA solution must specify what the agent should do for any state that the agent\nmight reach. A solution of this kind is called a policy. Policy: π, action recommended by the poicy π for state s: π(s). \nThe quality of a policy is therefore measured by the expected utility of the possible environment histories generated by that policy. An optimal policy is a policy that yields the highest expected utility. \nWe use π∗ to denote an optimal policy. A policy represents the agent function explicitly and is therefore a description of a simple reflex\nagent, computed from the information used for a utility-based agent.  In general there will often be multiple optimal policies. \n\n\n \n\n\n\n\n\n\n\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n In our search algorithms so far, the\ntransition model was deterministic and\ndescribed the outcome of each action in\neach state.\nThe transition function is sometimes\nwritten as T(s, a, s’), or explicitly as a\nprobability: p( s’ | s, a ).  \nTransitions are Markovian:\nthe probability of arriving in\ns’ only depends on s and\nnot the history of earlier\nstates.\nReward function: 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 on a\nsequence of states and actions.\nInstead of only giving a reward at the goal states, the agent can receive a reward at\neach time step, based on its transition from s to s’ via action a.\nThis is defined by a reward function\nR( s, a, s’ )\nFor example, we could give the Millennium Falcon a small negative reward of -0.04 for every\ntransition except for entering the terminal states (+1 for entering the planet’s orbit or -1 for\nsmashing into an asteroid).\nThe rewards are additive, so if the Millennium Falcon takes 4 steps before entering\nthe planet's orbit, it gets -0.04 + -0.04 + -0.04 + -0.04 + 1 = 0.84 for that solution.\nMarkov Decision Process:\nA Markov decision process or MDP is\n• a sequential decision problem\n• for a fully observable environment\n• with a stochastic transition model\n• that has additive rewards\nMDPs are non-deterministic search\nproblems. One way of solving them is via\nexpectimax search. \nExpectimax node: outcome is\nuncertain. In expectimax search\nwe calculate their expected utilities.\nTo find a solution to an MDP, you need to define the following things:\n• A set of states s ∈ S\n• A set of actions a ∈ A\n• A transition function T(s, a, s’)\n• Probability that executing action a in s will lead to s’ P(s’ | s, a)\n• The probability is called the model\n• A reward function R(s, a, s’)\n• Sometimes just R(s) or R(s’)\n• An initial state s0\n• Optionally, one or more terminal states\nPolicy: In search problems a solution was a\nsequence of action that corresponded to\nthe shortest path.\nBecause of the non-determinism in MDPs\nwe cannot simply give a sequence of\nactions.\nInstead, the solution to an MDP is a policy.\nA policy maps from a state onto the action\nto take if the agent is in that state.\n𝝿(s) = a\nPolicy 𝝿 tells the agent what\naction to take at state s.\n\nIn search problems a solution was a plan:\na sequence of action that corresponded to\nthe shortest path from the start to a goal.\nBecause of the non-determinism in MDPs\nwe cannot simply give a sequence of\nactions.\nInstead, the solution to an MDP is a policy.\nA policy maps from a state onto the action\nto take if the agent is in that state. 𝝿(s) = a\nnot guarantee actual move\n\nWe will use 𝝿* to denote the optimal policy.\nEven if the same policy is executed multiple times by the\nagent, this may lead to different sequence of states and\nactions (environment history), and thus a different\nscore under the reward function.\nTherefore we need to compute the expected utility of all\nthe possible paths generated by a policy.\nThe performance of an agent in an MDP is the sum\nof the rewards for the transitions it takes.\nUh([s0, a0, s1, a1 …, sn]) = R(s0, a0, s1) + R(s1, a1, s2) + … + R(sn-1, an-1, sn) \nUtility function on an environment history.\nBounce around forever,and avoid the exits … infinite rewards!!\nDiscounting: It’s reasonable to maximize the sum of rewards\nIt’s also reasonable to prefer rewards now to rewards later\nOne solution: values of rewards decay exponentially\nHow to discount?\n• Each time we descend a level, we\nmultiply in the discount once\nWhy discount?\n• Sooner rewards probably do have\nhigher utility than later rewards\n• Also helps our algorithms converge\nExample: discount of 0.5\n• U([1,2,3]) = 0.50*1 + 0.51*2 + 0.52*3\n• U([1, 2, 3]) < U([3, 2, 1])\nStationary Preferences:\nTheorem: if we assume stationary preferences:\n[a1, a2, ...] > [b1, b2, ...] <-> [r, a1, a2, ...] > [r, b1, b2, ...]\nThen: there are only two ways to define utilities\n• Additive utility: U([r0, r1, r2, ..]) = r0+r1+r2...\n• Discounted utility: U([r0, r1, r2, ..]) = r0+y*r1+y^2*r2...\n▪Problem: What if the game lasts forever? Do we get infinite\nrewards?\n▪Solutions:\n▪ Finite horizon: (similar to depth-limited search)\n▪ Terminate episodes after a fixed T steps (e.g. life)\n▪ Gives nonstationary policies (y depends on time left)\n▪ Discounting: use 0 < y < 1\nU([R0, ...R∞]) = sum(t=0...∞) y^t * r <= Rmax/(1-y)\n▪ Smaller y means smaller “horizon” – shorter term focus\n▪ Absorbing state: guarantee that for every policy, a terminal state will\neventually be reached (like “overheated” for racing\n\nMDP quantities so far: • Policy = Choice of action for each state • Utility = sum of (discounted) rewards\nT(s,a,s’) = P(s’|s,a)R(s,a,s’)\ns is a state triangle -a-> (s,a) is a q-state circle -(s,a,s')-> s'\n(s,a,s’) is called a transition T(s,a,s’) = P(s’|s,a) R(s,a,s’)\nHyperdrive Search Tree?\nOptimal Quantities\n▪ The value (utility) of a state s:\nV*(s) = expected utility starting in s and\nacting optimally\n▪ The value (utility) of a q-state (s,a):\nQ*(s,a) = expected utility starting out\nhaving taken action a from state s and\n(thereafter) acting optimally\n▪ The optimal policy:\n𝝿*(s) = optimal action from state s\nValues of States:\nFundamental operation: compute the (expectimax) value of a state\n• Expected utility under optimal action\n• Average sum of (discounted) rewards\n• This is just what expectimax computed!\nRecursive definition of value:\nV*(s) = max a Q*(s,a)\nQ*(s, a) = Sum(s') T(s,a,s')[R(s,a,s') + yV*(s')]\nV*(s) = max a Sum(s')T(s,a,s')[R(s,a,s') + yV*(s')]\n\nKey idea: time-limited values\nDefine Vk(s) to be the optimal value of s if the game\nends in k more time steps\n• Equivalently, it’s what a depth-k expectimax would give\nfrom s\nValue Iteration\nStart with V0(s) = 0: no time steps left means an expected reward sum of zero\nGiven vector of Vk(s) values, do one ply of expectimax from each state:\nRepeat until convergence\nVk+1(s) <- max a Sum(s') T(s,a,s')[R(s,a,s')+yVk(s')]\nComplexity of each iteration: O(S^2A)\nTheorem: will converge to unique optimal values\n• Basic idea: approximations get refined towards optimal values\n• Policy may converge long before value\n\nHow do we know the Vk vectors are going to converge?\nCase 1: If the tree has maximum depth M, then VM holds\nthe actual untruncated values\nCase 2: If the discount is less than 1\n• Sketch: For any state Vk and Vk+1 can be viewed as depth k+1 expectimax results in nearly identical search trees\n• The difference is that on the bottom layer, Vk+1 has actual rewards while Vk has zeros\n• That last layer is at best all RMAX\n• It is at worst Rmin\n• But everything is discounted by γ^k that far out\n• So Vk and Vk+1 are at most γ^k max|R| different\n• So as k increases, the values converge\nThe Bellman Equations:\nHow to be optimal:\nStep 1: Take correct first action\nStep 2: Keep being optimal\nDefinition of “optimal utility” via expectimax recurrence gives\na simple one-step lookahead relationship amongst optimal\nutility values. These are the Bellman equations, and they characterize\noptimal values in a way we’ll use over and over.\nFixed Policies: Expectimax trees max over all actions to compute the optimal values\nIf we fixed some policy (s), then the tree would be simpler – only one action per state\n• … though the tree’s value would depend on which policy we fixed\nUtilities for a Fixed Policy\nAnother basic operation: compute the utility of a state s under a\nfixed (generally non-optimal) policy\nDefine the utility of a state s, under a fixed policy 𝝿:\nV𝝿(s) = expected total discounted rewards starting in s and following 𝝿\nRecursive relation (one-step look-ahead / Bellman equation):\nV𝝿(s) = Sum(s')T(s, 𝝿(s), s')[R(s, 𝝿(s), s') + yV^𝝿(s')]\n\n\n\n\n \n\n## Module 8 Definitions\n* **Goal-based agent** - binary distinction btw good nd bad states\n* **Decision-throrestic agent** -  assigns a continuous range of values to states, and thus can more easily choose a better state even when no best state is available.\n* **Decition theory** - deals with choosing among actions based on the desirability of their immediate outcomes.environment is assumed to be episodic\n* **Utility function** - The agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the Utility function desirability of a state\n* **Maximum expected utility (meu) ** - a rational agent should choose the action that maximizes the agent’s expected utility: action = argmaxEU(a).\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Framing effect** - exact wording of a decision problem can have a big impacton the agent’s choices\n* **Anchoring effect** - People feel more comfortable making relative utility judgments rather than absolute one\n* **Evolutionary psychology** - our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal numbers\n* **Markov decision process** - a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process\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 Double-Bandit MDP:\nOffline Planning:\nSolving MDPs is offline planning.\nYou determine all quantities through computation.\nYou need to know the details of the MDP.\nYou do not actually play the game!\nOnline Planning\nRules changed! Red’s win chance is different\nThat wasn’t planning, it was learning!\nSpecifically, reinforcement learning:\nThere was an MDP, but you couldn’t solve it with just computation\nYou needed to actually act to figure it out\nImportant ideas in reinforcement learning that came up\nExploration: you have to try unknown actions to get information\nExploitation: eventually, you have to use what you know\nRegret: even if you learn intelligently, you make mistakes\nSampling: because of chance, you have to try things repeatedly\nDifficulty: learning can be much harder than solving a known MDP\nBasic idea:\nEnvironment - state:s, reward:r -> Agent\nAgent - action:a -> Environment\nReceive feedback in the form of rewards\nAgent’s utility is defined by the reward function\nMust (learn to) act so as to maximize expected rewards\nAll learning is based on observed samples of outcomes!\nStill looking for a policy π(s)\nNew twist: don’t know T or R\nI.e. we don’t know which states are good or what the actions do\nMust actually try actions and states out to learn\nModel-Based Learning\nModel-Based Idea:\nLearn an approximate model based on experiences\nSolve for values as if the learned model were correct\nStep 1: Learn empirical MDP model\nCount outcomes s’ for each s, a\nNormalize to give an estimate of T^(s, a, s')\nDiscover each R(s,a,s')^ when we experience (s, a, s’)\nStep 2: Solve the learned MDP\nFor example, use value iteration, as before\nInput Policy π,\nAssume: γ = 1,\nObserved Episodes (Training) Learned Model.\nModel-Free Learning:\nPassive Reinforcement Learning:\nSimplified task: policy evaluation\nInput: a fixed policy π(s)\nYou don’t know the transitions T(s,a,s’)\nYou don’t know the rewards R(s,a,s’)\nGoal: learn the state values\nIn this case:\nLearner is “along for the ride”\nNo choice about what actions to take\nJust execute the policy and learn from experience\nThis is NOT offline planning! You actually take actions in the world.\nDirect Evaluation:\nGoal: Compute values for each state under π\nIdea: Average together observed sample values\nAct according to π\nEvery time you visit a state, write down what the\nsum of discounted rewards turned out to be\n\nReceive a sample (s,a,s’,r)\nConsider your old estimate: Q(s,a)\nConsider your new sample estimate: sample = R(s,a,s') + y max a' Q(s',a')\nIncorporate the new estimate into a running average: \nQ(s,a) <- (1-α)Q(s,a) + (α)[sample]\nQ-Learning Properties:\nAmazing result: Q-learning converges to optimal policy -- even\nif you’re acting suboptimally!\nThis is called off-policy learning\nCaveats:\nYou have to explore enough\nYou have to eventually make the learning rate\nsmall enough\n… but not decrease it too quickly\nBasically, in the limit, it doesn’t matter how you select actions (!)\nExploration vs. Exploitation\nHow to Explore?\nSeveral schemes for forcing exploration:\nSimplest: random actions (ε-greedy)\nEvery time step, flip a coin\nWith (small) probability ε, act randomly, ε-> 0, greater exploitation,  ε-> 1, greater exploration\nWith (large) probability 1-ε, act on current policy, \nProblems with random actions?\nYou do eventually explore the space, but keep\nthrashing around once learning is done\nOne solution: lower ε over time\nAnother solution: exploration functions\nExploration Functions\nWhen to explore?\nRandom actions: explore a fixed amount\nBetter idea: explore areas whose badness is not\n(yet) established, eventually stop exploring\nExploration function\nTakes a value estimate u and a visit count n, and\nreturns an optimistic utility, e.g. f(u, n) = u+k/n\nRegular Q-Update: Q(s,a) <- αR(s,a,s') + ymax a' Q(s',a')\nModified Q-Update: Q(s,a) <- αR(s,a,s') + ymax a' f(Q(s',a'), N(s',a'))\nNote: this propagates the “bonus” back to states that lead to unknown states as\nwell!\nRegret:\nEven if you learn the optimal policy,\nyou still make mistakes along the way!\nRegret is a measure of your total\nmistake cost: the difference between\nyour (expected) rewards, including\nyouthful suboptimality, and optimal\n(expected) rewards\nMinimizing regret goes beyond\nlearning to be optimal – it requires\noptimally learning to be optimal\nExample: random exploration and\nexploration functions both end up\noptimal, but random exploration has\nhigher regret\nApproximate Q-Learning\nGeneralizing Across States\n \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nUncertainty\nGeneral situation:\n• Observed variables (evidence): Agent knows certain things about the state of the world (e.g.,\nsensor readings or symptoms)\n• Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object\nis or what disease is present)\n• Model: Agent knows something about how the known variables relate to the unknown variables\nProbabilistic reasoning gives us a framework\nfor managing our beliefs and knowledge;\nWhat Probabilities Are About\nLike logical assertions, probabilities are about possible worlds. Instead of strictly\nruling out possibilities (where a logical assertion is false), probabilities quantify how\nlikely a particular possible world is.\nIn probability theory, the possible worlds are called the sample space, and they\nmutually exclusive and exhaustive.\nA fully specified probability model associates a probability P(w) with each possible\nworld w. ;\nRandom Variables\nA random variable is some aspect of the world\nabout which we (may) have uncertainty\n• R = Is it raining?\n• U = Is the professor carrying an umbrella?\nWe denote random variables with capital letters;\n\nProbability Distributions\nUnobserved random variables have distributions\nA distribution is a TABLE of probabilities of values\nA probability (lower case value) is a single number\nShorthand notation:OK if all domain entries are unique\n\nJoint Distributions\nA joint distribution over a set of random variables:\nspecifies a real number for each assignment (or outcome):\n• Must obey:\nSize of distribution if n variables with domain sizes d?\n• For all but the smallest distributions, impractical to write out!  \n\nProbabilistic Models\nA probabilistic model is a joint distribution\nover a set of random variables\nProbabilistic models:\n• (Random) variables with domains\n• Assignments are called outcomes\n• Joint distributions: say whether\nassignments (outcomes) are likely\n• Normalized: sum to 1.0\n• Ideally: only certain variables directly\ninteract；\n\nEvents\nAn event is a set E of outcomes\nFrom a joint distribution, we can calculate\nthe probability of any event\n• Probability that it’s hot AND sunny?\n• Probability that it’s hot?\n• Probability that it’s hot OR sunny?\nTypically, the events we care about are\npartial assignments, like P(T=hot)；\n\nMarginal Distributions\nMarginal distributions are sub-tables which eliminate variables\nMarginalization (summing out): Combine collapsed rows by\nadding；\n\nConditional Probabilities\nA simple relation between joint and conditional\nprobabilities\n• In fact, this is taken as the definition of a conditional probability；\n\n\nConditional Distributions\nConditional distributions are probability distributions\nover some variables given fixed values of others；\n\nProbabilistic Inference\nProbabilistic inference: compute a desired\nprobability from other known probabilities (e.g.\nconditional from joint)\nWe generally compute conditional probabilities\n• P(on time | no reported accidents) = 0.90\n• These represent the agent’s beliefs given the\nevidence\nProbabilities change with new evidence:\n• P(on time | no accidents, 5 a.m.) = 0.95\n• P(on time | no accidents, 5 a.m., raining) = 0.80\n• Observing new evidence causes beliefs to be update；\nInference by Enumeration\nGeneral case:\n• Evidence variables:\n• Query* variable:\n• Hidden variables: \n we want:\n Step 1: Select the\nentries consistent\nwith the evidence, Step 2: Sum out H to get joint\nof Query and evidence,  Step 3: Normalize;\nThe Product Rule;\nThe Chain Rule\nMore generally, can always write any joint distribution\nas an incremental product of conditional distributions;\nWhy is this always true?;\n\n\n\nIntuition: let’s rely on the Chain Rule of Probability;\nThe Chain Rule：\nRecall the definition of conditional probabilities\np(B|A) = P(A,B)/P(A) Rewriting: P(A,B) = P(A)P(B|A)\nMore variables:\nP(A,B,C,D) = P(A)P(B|A)P(C|A,B)P(D|A,B,C)\nThe Chain Rule in General\nP(x1,x2,x3,…,xn) = P(x1)P(x2|x1)P(x3|x1,x2)…P(xn|x1,…,xn-1)；\nJoint probability of words in sentence：\nP(“the underdog Philadelphia Eagles won”) =\nP(the) ×\nP(underdog|the) ×\nP(Philadelphia|the underdog) ×\nP(Eagles|the underdog Philadelphia) x\nP(won|the underdog Philadelphia Eagles；\nHow to estimate these probabilities\nCould we just count and divide? Maximum likelihood estimation (MLE)；\nSimplifying Assumption = Markov Assumption；\nSimplest case: Unigram model： Some automatically generated sentences from a unigram model，\nfifth an of futures the an incorporated a a the inflation most\ndollars quarter in is mass\nthrift did eighty said hard 'm july bullish\nthat or limited the；\nBigram model： Condition on the previous word；\nN-gram models\nWe can extend to trigrams, 4-grams, 5-grams\nIn general this is an insufficient model of language\n• because language has long-distance dependencies:\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \nProbabilistic Models:\n§ Models describe how (a portion of) the world works\n§ Models are always simplifications\n§ May not account for every variable\n§ May not account for all interactions between variables\n§ “All models are wrong; but some are useful.” – George E. P. Box\n§ What do we do with probabilistic models?\n§ We (or our agents) need to reason about unknown\nvariables, given evidence\n§ Example: explanation (diagnostic reasoning)\n§ Example: prediction (causal reasoning)\nReview: Independence\n§ Two variables are independent if:\nany x,y: P(x,y) = P(x)P(y)\n§ This says that their joint distribution factors into a product two\nsimpler distributions\n§ Another form:\nany x,y: P(x|y) = P(x)\n§ X ||- Y\nndependence is a simplifying modeling assumption\n§ Empirical joint distributions: at best “close” to independent\n§ What could we assume for {Weather, Traffic, Cavity, Toothache}?\nReview: Conditional Independence:\n§ P(Toothache, Cavity, Detect)\n§ If I have a cavity, the probability that the probe detects it\ndoesn't depend on whether I have a toothache:\n§ P(+detect | +toothache, +cavity) = P(+detect | +cavity)\n§ The same independence holds if I don’t have a cavity:\n§ P(+detect | +toothache, -cavity) = P(+detect| -cavity)\n§ Detect is conditionally independent of Toothache given\nCavity:\n§ P(Detect | Toothache, Cavity) = P(Detect | Cavity)\n§ Equivalent statements:\n§ P(Toothache | Detect , Cavity) = P(Toothache | Cavity)\n§ P(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity)\n§ One can be derived from the other using the chain rule\n§ Unconditional (absolute) independence very rare, and it\ndoesn’t help us make inferences about other variables.\n§ Conditional independence is our most basic and robust form\nof knowledge about uncertain environments.\n§ X is conditionally independent of Y given Z\nif and only if:\n  any x,y,z: P(x,y|z) = p(x|z)*P(y|z)\nor, equivalently, if and only if\n  any x,y,z: P(x|z,y) = P(x|z)\nX ||_ Y|Z\nConditional Independence and the Chain Rule\n§ Chain rule: P(X1,X2, ..Xn)=P(X1)P(X2|X1)P(X3|X1,X2)...\n§ Trivial decomposition:\nP(Traffic, Rain,Umbrella) = P(Rain)P(Traffic|Rain)P(Umbrella| Rain, Traffic)\n§ With assumption of conditional independence:\nP(Traffic, Rain, Umbrella) = P(Rain)P(Traffic|Rain)P(Umbrella|Rain)\n§ Bayes’nets / graphical models help us express conditional independence assumptions\nBayes’ Nets: Big Picture:\n§ Two problems with using full joint distribution tables\nas our probabilistic models:\n§ Unless there are only a few variables, the joint is WAY too\nbig to represent explicitly\n§ Hard to learn (estimate) anything empirically about more\nthan a few variables at a time\n§ Bayes’ nets: a technique for describing complex joint\ndistributions (models) using simple, local\ndistributions (conditional probabilities)\n§ More properly called graphical models\n§ We describe how variables locally interact\n§ Local interactions chain together to give global, indirect\ninteractions\nGraphical Model Notation:\n§ Nodes: variables (with domains)\n§ Can be assigned (observed) or unassigned\n(unobserved)\n§ Arcs: interactions\n§ Indicate “direct influence” between variables\n§ Formally: encode conditional independence\n(more later)\n§ For now: imagine that arrows mean\ndirect causation (in general, they don’t!)\n§ No interactions between variables: absolute independence(no arrors)\nBayes’ Net Semantics:\n§ A set of nodes, one per variable X\n§ A directed, acyclic graph\n§ A conditional distribution for each node\n§ A collection of distributions over X, one for each\ncombination of parents’ values\nP(X|a1,a2,....an)\n§ CPT: conditional probability table\n§ Description of a noisy “causal” process\nA Bayes net = Topology (graph) + Local Conditional Probabilities\nProbabilities in BNs\n§ Bayes’ nets implicitly encode joint distributions\n§ As a product of local conditional distributions\n§ To see what probability a BN gives to a full assignment, multiply all the\nrelevant conditionals together:\nP(x1,x2, ...,xn) = product(i=1 to n) P(xi|parent(Xi))\n§ Not every BN can represent every joint distribution\n§ The topology enforces certain conditional independencies\nOnly distributions whose variables are absolutely independent can be\nrepresented by a Bayes’ net with no arcs\n\n\n\nindependence is not guaranteed.\n§ Example:\n§ Project due causes both forums busy\nand office hours full\n§ In numbers:\nP( +x | +y ) = 1, P( -x | -y ) = 1,\nP( +z | +y ) = 1, P( -z | -y ) = 1,\nGuaranteed X and Z independent given Y? yes\n§ Observing the cause blocks influence\nbetween effects\nCommon Effect:\nLast configuration: two causes of one\neffect (v-structures)\nAre X and Y independent?\n§ Yes: the ballgame and the rain cause traffic, but\nthey are not correlated\n§ Still need to prove they must be (try it!)\n§ Are X and Y independent given Z?\n§ No: seeing traffic puts the rain and the ballgame in\ncompetition as explanation.\n§ This is backwards from the other cases\n§ Observing an effect activates influence between\npossible causes.\nThe General Case: \n§ General question: in a given BN, are two variables independent\n(given evidence)?\n§ Solution: analyze the graph\n§ Any complex example can be broken\ninto repetitions of the three canonical cases\nReachability:\n§ Recipe: shade evidence nodes, look\nfor paths in the resulting graph\n§ Attempt 1: if two nodes are connected\nby an undirected path not blocked by\na shaded node, they are conditionally\nindependent\n§ Almost works, but not quite\n§ Where does it break?\n§ Answer: the v-structure at T doesn’t count\nas a link in a path unless “active”\nActive / Inactive Paths:\n§ Question: Are X and Y conditionally independent given\nevidence variables {Z}?\n§ Yes, if X and Y “d-separated” by Z\n§ Consider all (undirected) paths from X to Y\n§ No active paths = independence!\n§ A path is active if each triple is active:\n§ Causal chain A ® B ® C where B is unobserved (either direction)\n§ Common cause A ¬ B ® C where B is unobserved\n§ Common effect (aka v-structure)\nA ® B ¬ C where B or one of its descendents is observed\n§ All it takes to block a path is a single inactive segment\n \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Machine Learning\nUp until now: how use a model to make optimal decisions\nMachine learning: how to acquire a model from data /\nexperience\n• Learning parameters (e.g. probabilities)\n• Learning structure (e.g. BN graphs)\n• Learning hidden concepts (e.g. clustering)\nToday: model-based classification with Naive Bayes and\nPerceptrons\nSpam Classification\nInput: an email\nOutput: spam/ham\nSetup:\n• Get a large collection of example emails, each\nlabeled “spam” or “ham”\n• Note: someone has to hand label all this data!\n• Want to learn to predict labels of new, future\nemails\nFeatures: The attributes used to make the\nham / spam decision\n• Words: FREE!\n• Text Patterns: $dd, CAPS\n• Non-text: SenderInContacts\nDigit Recognition\nInput: images / pixel grids\nOutput: a digit 0-9\nSetup:\n• Get a large collection of example images, each labeled with a digit\n• Note: someone has to hand label all this data!\n• Want to learn to predict labels of new, future digit images\nFeatures: The attributes used to make the digit decision\n• Pixels: (6,8)=ON\n• Shape Patterns: NumComponents, AspectRatio, NumLoops\n• …  \nReview Other Classification Tasks\nClassification: given inputs x, predict labels y\nExamples:\n• Spam detection (input: document,\nclasses: spam / ham)\n• OCR (input: images, classes: characters)\n• Medical diagnosis (input: symptoms,\nclasses: diseases)\n• Automatic essay grading (input: document,\nclasses: grades)\n• Fraud detection (input: account activity,\nclasses: fraud / no fraud)\n• Customer service email routing\n• … many more\nClassification is an important commercial technology\nModel-Based Classification\nModel-based approach\n• Build a model (e.g. Bayes’ net) where both the label and\nfeatures are random variables\n• Instantiate any observed features\n• Query for the distribution of the\nlabel conditioned on the features\nChallenges\n• What structure should the BN\nhave?\n• How should we learn its\nparameters?  \n....\nNaïve Bayes for Digits\nNaïve Bayes: Assume all features are independent effects of the label\nSimple digit recognition version:\n• One feature (variable) Fij for each grid position <i,j>\n• Feature values are on / off, based on whether intensity\nis more or less than 0.5 in underlying image\n• Each input maps to a feature vector, e.g.\n• Here: lots of features, each is binary valued\nNaïve Bayes model:\nWhat do we need to learn?\nGeneral Naïve Bayes: |Y| labels, |Y| x |F|n values, n x |F| x |Y|parameters,\nWe only have to specify how each feature depends on the class\nTotal number of parameters is linear in number of features\nModel is very simplistic, but often works anyway  \nInference for Naïve Bayes\nGoal: compute posterior distribution over label variable Y\n• Step 1: get joint probability of label and evidence for each label\n• Step 2: sum to get probability of evidence\n• Step 3: normalize by dividing Step 1 by Step 2\nGeneral Naïve Bayes\nWhat do we need in order to use Naïve Bayes?\n• Inference method (we just saw this part)\n• Start with a bunch of probabilities: P(Y) and the P(Fi\n|Y) tables\n• Use standard inference to compute P(Y|F1…Fn)\n• Nothing new here\n• Estimates of local conditional probability tables\n• P(Y), the prior over labels\n• P(Fi\n|Y) for each feature (evidence variable)\n• These probabilities are collectively called the parameters of the\nmodel and denoted by q\n• Up until now, we assumed these appeared by magic, but…\n• …they typically come from training data counts: we’ll look at this\nsoon  \n\nSummary\nBayes rule lets us do diagnostic queries with causal probabilities\nThe naïve Bayes assumption takes all features to be independent given\nthe class label\nWe can build classifiers out of a naïve Bayes model using training data\nSmoothing estimates is important in real systems\nClassifier confidences are useful, when you can get them  \nWhat to Do About Errors\nProblem: there’s still spam in your inbox\nNeed more features – words aren’t enough!\n• Have you emailed the sender before?\n• Have 1M other people just gotten the same email?\n• Is the sending information consistent?\n• Is the email in ALL CAPS?\n• Do inline URLs point where they say they point?\n• Does the email address you by (your) name?\nNaïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are\nword occurrences)  \nPerceptrons:\nSome (Simplified) Biology\nVery loose inspiration: human neurons;\nLinear Classifiers\nInputs are feature values\nEach feature has a weight\nSum is the activation\nIf the activation is:\n• Positive, output +1\n• Negative, output -1;\nFeature Vectors:\nWeights\nBinary case: compare features to a weight vector\nLearning: figure out the weight vector from examples  \nDot product positive\nmeans the positive class\nDecision Rules:\nBinary Decision Rule\nIn the space of feature vectors\n• Examples are points\n• Any weight vector is a hyperplane\n• One side corresponds to Y=+1\n• Other corresponds to Y=-1\n\nWeight Updates:\nLearning: Binary Perceptron\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector \nLearning: Binary Perceptron\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector\nby adding or subtracting the\nfeature vector. Subtract if y* is -1.\n3Blue1Brown\nNeed a refresher on linear algebra topics like vector addition and matrix multiplication?\nI recommend the wonderful YouTube series by Grant Sanderson. His channel is called\n3Blue1Brown.\nGrant gives intuitive visual tutorials to a ton of math concepts\nHere is his “Essence of Linear Algebra” series:\nExamples: Perceptron\nSeparable Case  \nMulticlass Decision Rule\nIf we have multiple classes:\n• A weight vector for each class:\n• Score (activation) of a class y:\n• Prediction highest score wins:  \nLearning: Multiclass Perceptron\nStart with all weights = 0\nPick up training examples one by one\nPredict with current weights\nIf correct, no change!\nIf wrong: lower score of wrong\nanswer, raise score of right answer  \nExample: Multiclass Perceptron:\n\"win the vote”\n“win the election”\n“win the game”;\nProperties of Perceptrons\nSeparability: true if some parameters get the training\nset perfectly correct\nConvergence: if the training is separable, perceptron\nwill eventually converge (binary case)\nMistake Bound: the maximum number of mistakes\n(binary case) related to the margin or degree of\nseparability;\n\nExamples: Perceptron\nNon-Separable Case;\n\nImproving the Perceptron;\nProblems with the Perceptron;\nNoise: if the data isn’t separable,\nweights might thrash\n• Averaging weight vectors over\ntime can help (averaged\nperceptron)\nMediocre generalization: finds a\n“barely” separating solution\nOvertraining: test / held-out\naccuracy usually rises, then falls\n• Overtraining is a kind of\noverfitting;\nFixing the Perceptron\nIdea: adjust the weight update to mitigate these effects\nMIRA*: choose an update size that fixes the current\nmistake…\n… but, minimizes the change to w. The +1 helps to generalize.\nGuessed y instead of y*on example x with features f(x);\nMinimum Correcting Update:min not t=0, or would not have\nmade an error, so min will be\nwhere equality holds.\nMaximum Step Size\nIn practice, it’s also bad to make updates that are too large\n• Example may be labeled incorrectly\n• You may not have enough features\n• Solution: cap the maximum possible value of t with some\nconstant C.\n• Corresponds to an optimization that assumes nonseparable data\n• Usually converges faster than perceptron\n• Usually better, especially on noisy data.\nLinear Separators:\nWhich of these linear separators is optimal?\nSupport Vector Machines\nMaximizing the margin: good according to intuition, theory, practice\nOnly support vectors matter; other training examples are ignorable\nSupport vector machines (SVMs) find the separator with max\nmargin\nBasically, SVMs are MIRA where you optimize over all examples at\nonce.\nClassification: Comparison\nNaïve Bayes\n• Builds a model training data\n• Gives prediction probabilities\n• Strong assumptions about feature independence\n• One pass through data (counting)\nPerceptrons / MIRA:\n• Makes less assumptions about data\n• Mistake-driven learning\n• Multiple passes through data (prediction)\n• Often more accurate;Perceptrons\nPerceptrons were developed in the 1950s\nand 1960s loosely inspired by the neuron;\ninputs -> weights->weighted sum -> activation function(threshold)->output\noutput:0 if sum(i)wixi <= threshold\noutput:1 if sum(j)wjxj > threshold\nPerceptrons for decision making\nWe can think about the perceptron or the sigmoid neuron as a device that makes\ndecisions by weighing up evidence.\nExample: Suppose there’s a cheese festival in your town. You like cheese.  \nPerceptrons for decision making\nYou might use 3 factors to decide whether to go.\n1. Is the weather good?\n2. Can your loyal companion come with you?\n3. Is the festival near public transit?\nThese can be the binary input values to a perceptron  \nPerceptrons for decision making\nBy varying weights and the threshold we get different models of decision making\nExample 1: w1= 6 w2 = 2 w3 = 2, threshold = 5\nExample 2: w1= 6 w2 = 2 w3 = 2, threshold = 3;\n Notational changes\nChange\t1:\tWe\tcan\twrite\t∑jwjxj as\ta\tdot\tproduct\tof\tthe\tinput\tvector\tand\tthe\tweight\tvector:\n:\nChange\t2:\t\tWe\tcan\tmove\tthe\tthreshold\tto\tother\tother\tside\tof\tthe\tinequality.\t\tWe\tdefine\ta\t\nperceptron’s\t“bias”\tas\tthe\t-1\t*\tits\tthreshold:\nb = -threshold\nLearning weights from examples\nPerceptions can be used for all kinds of classification problems.\nThink of the inputs as features representing something we want to classify.\nThe feature values for inputs are fixed, but we can choose different weight vectors.\nDepending on the weight vector that we pick, we will get a different classifier. \nBinary Decision Rule:\nIn the space of feature vectors\n• Examples are points\n• Any weight vector is a hyperplane\n• One side corresponds to Y=+1\n• Other corresponds to Y=-1;\n\nWeight Updates:\nLearning: Binary Perceptron\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector;\nLearning a Binary Perceptron:\nStart with weights = 0\nFor each training instance:\n• Classify with current weights\n• If correct (i.e., y=y*), no change!\n• If wrong: adjust the weight vector\nby adding or subtracting the\nfeature vector. Subtract if y* is -1.\nMulticlass Decision Rule\nIf we have multiple classes:\n• A weight vector for each class:\n• Score (activation) of a class y:\n• Prediction highest score wins\n\nLearning: Multiclass Perceptron\nStart with all weights = 0\nPick up training examples one by one\nPredict with current weights\nIf correct, no change!\nIf wrong: lower score of wrong\nanswer, raise score of right answer\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \nLogistic Regression:\nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i),y(i)).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class y^ via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.;\nSentiment classifier\nInput: \"Spiraling away from narrative control as\nits first three episodes unreel, this series, about\na post-apocalyptic future in which nearly\neveryone is blind, wastes the time of Jason\nMomoa and Alfre Woodard, among others, on a\nstory that starts from a position of fun, giddy\nstrangeness and drags itself forward at a\nlugubrious pace.\"\nOutput: positive (1) or negative (0);\n\nSentiment classifier\nFor sentiment classification, consider an input observation x,\nrepresented by a vector of features [x1,x2,...,xn]. The classifier output y\ncan be 1 (positive sentiment) or 0 (negative sentiment). We want to\nestimate P(y = 1|x).\nLogistic regression solves this task by learning, from a training set, a\nvector of weights and a bias term.\nWe can also write this as a dot product:\nDecision boundary\nNow we have an algorithm that given an instance x computes the\nprobability P(y = 1|x). How do we make a decision? \nFor a test instance x, we say yes if the probability P(y = 1|x) is more than\n.5, and no otherwise. We call .5 the decision boundary；\nExtracting Features:It's hokey. There are virtually no surprises , and the writing is\nsecond-rate . So why was it so enjoyable? For one thing , the cast\nis great . Another nice touch is the music . I was overcome with\nthe urge to get off the couch and start dancing . It sucked me in ,\nand it'll do the same to you .\nComputing Z:\nVar Definition Value Weight Product\nx1 Count of positive lexicon words 3 2.5 7.5\nx2 Count of negative lexicon words 2 -5.0 -10\nx3 Does no appear? (binary\nfeature)\n\n\n\n\n\n\n\n\n\n\n\nThe advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\nThe computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\nThe output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ:\nh = σ(Wx+b) \nEquations for a feedforward network\nLike the hidden layer, the output layer has a weight matrix U.\nIts weight matrix is multiplied by its input vector (h) to produce the intermediate output z.\nz=Uh  ;\nEquations for a feedforward network\nHere are the final equations for a feedforward network with a single hidden layer,\nwhich takes an input vector x, outputs a probability distribution y, and is parameterized\nby weight matrices W and U and a bias vector b:\nh = σ(Wx+b)\nz = Uh\ny = softmax(z)\nLike with logistic regression, softmax normalizes the output and turns it into a\nprobability distribution.;\nTraining Neural Nets\nLike logistic regression, we want to learn the best parameters for the neural net to\nmake its predictions y^ as close to possible as the gold standard labels in our training\ndata y.\nWhat do we need?\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nLogistic Regression:\nClassifier components\nMachine learning classifiers require a training corpus of M observations\ninput/output pairs (x(i),y(i)).\n1. A feature representation of the input. For each input observation\nx(i)\n, this will be a vector of features [x1,x2,...,xn].\n2. A classification function that computes the estimated class y^ via\np(y|x).\n3. An objective function for learning, usually involving minimizing\nerror on training examples.\n4. An algorithm for optimizing the objective function.;\nSentiment classifier\nInput: \"Spiraling away from narrative control as\nits first three episodes unreel, this series, about\na post-apocalyptic future in which nearly\neveryone is blind, wastes the time of Jason\nMomoa and Alfre Woodard, among others, on a\nstory that starts from a position of fun, giddy\nstrangeness and drags itself forward at a\nlugubrious pace.\"\nOutput: positive (1) or negative (0);\n\nSentiment classifier\nFor sentiment classification, consider an input observation x,\nrepresented by a vector of features [x1,x2,...,xn]. The classifier output y\ncan be 1 (positive sentiment) or 0 (negative sentiment). We want to\nestimate P(y = 1|x).\nLogistic regression solves this task by learning, from a training set, a\nvector of weights and a bias term.\nWe can also write this as a dot product:\nDecision boundary\nNow we have an algorithm that given an instance x computes the\nprobability P(y = 1|x). How do we make a decision? \nFor a test instance x, we say yes if the probability P(y = 1|x) is more than\n.5, and no otherwise. We call .5 the decision boundary；\nExtracting Features:It's hokey. There are virtually no surprises , and the writing is\nsecond-rate . So why was it so enjoyable? For one thing , the cast\nis great . Another nice touch is the music . I was overcome with\nthe urge to get off the couch and start dancing . It sucked me in ,\nand it'll do the same to you .\nComputing Z:\nVar Definition Value Weight Product\nx1 Count of positive lexicon words 3 2.5 7.5\nx2 Count of negative lexicon words 2 -5.0 -10\nx3 Does no appear? (binary\nfeature)\n\n\n\n\n\n\n\n\n\n\n\nThe advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\nThe computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\nThe output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ:\nh = σ(Wx+b) \nEquations for a feedforward network\nLike the hidden layer, the output layer has a weight matrix U.\nIts weight matrix is multiplied by its input vector (h) to produce the intermediate output z.\nz=Uh  ;\nEquations for a feedforward network\nHere are the final equations for a feedforward network with a single hidden layer,\nwhich takes an input vector x, outputs a probability distribution y, and is parameterized\nby weight matrices W and U and a bias vector b:\nh = σ(Wx+b)\nz = Uh\ny = softmax(z)\nLike with logistic regression, softmax normalizes the output and turns it into a\nprobability distribution.;\nTraining Neural Nets\nLike logistic regression, we want to learn the best parameters for the neural net to\nmake its predictions y^ as close to possible as the gold standard labels in our training\ndata y.\nWhat do we need?\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}