{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "aPtM8g7R0Pds",
        "cw5IpDLCZa4W",
        "s3Uk9gQTevcj",
        "5yG3-YncJfTB",
        "elCCgY64spuq",
        "9xRbdqDox2zD",
        "46MQLR-Gx8dZ",
        "WHREsHSSyA-h"
      ]
    },
    "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": "7daf1ae2-330f-4dfc-de08-4e6600de2d89"
      },
      "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": "4bd0736e-999c-4fe1-db59-3c88e1a4338c"
      },
      "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 = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"Agent assignts P(s) to each uncertain state. P(s'|s,a) is transition model. MEU formalizes the right thing an agent should do, but\n",
        "not how to do it: need perception, learning, knowledge representation, inference. Performance measure gives score for history--sequence of states.\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"Constraints on rational preferences: A > B = agent prefers A over B. A ~ B = agent is indifferent. A >- agent prefers A over B or is indifferent\n",
        "between them. A and B are sets of outcomes for each action as a lottery where the action is a ticket. L w/outcomes S1...Sn w/probabilities p1...pn is L = [p1, S1, ...pn, Sn].\n",
        "Six constraints that preference relations should obey: orderability (preference), transitivity, continuity (in the middle), substitutability (A and B and more complex lotteries where B\n",
        "is subbing A in one of them), monotonicity (lottery w/higher probability for A if A is preferred), decomposability (compound lotteries to simple) = axioms of utility theory. \"\"\"\n",
        "chapter16_3 =  \"\"\"Decision theory is a normmative theory--describes how rational agent should act. Descriptive theory describes how agents actually act. Certainty effect-->people are\n",
        "attracted to certainty bc to reduce computation burden; distrust legitimacy of stated probabilities; accounting for emotinoal and financial state\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"Markovian transitions are ones whose probability of reaching s' from s depeneds only on s and not history of earlier states. If decision problem is sequential, specify utility\n",
        "function by sequence of states and actions--the environment history. Reward = R(s, a, s') for s transition from s to s'. MDP: sequential decision problem for fully observable, stochastic env\n",
        "with Markovian transition model and additive rewards (solvable using DP). Finite horizons mean fixed time N and game is over (nonstationary); infinite means the optimal action depends\n",
        "nly on current state and optimal policy is stationary. Lower discount rate values closer rewards. U(s) = expected reward for next transition plus discounted utility of the next state. Action-utility function \n",
        "or Q-function Q(s,a) is the expected utility of taking a givne action in a given state. Dynamic decision networks (DDN) are factored reps that have exponential complexity advantage over atomic reps and can\n",
        "model substantial real-world problems: state St is composed of 4 state vars: Xt w/2d location on grid + orientation; Xt rate of change of X; charging when robot is plugged in; battery.\"\"\"\n",
        "chapter17_2 =  \"\"\"Value iteration, policy iteration, linear programming offer same solutions to MDP. Value iteration is iterative, and starts with initial vals for utilities, calculate RH side of equation, \n",
        "plug into LH side, updates U for every s from utility of neighbors until equilibrium. Contractions has one fixed point; if 2, wouldn't get closer. When function applied to arg, value must get closer\n",
        "to fixed point so repeated applicaton of a contraction always reaches the fixed point in the limit. Policy iteration: algo alternates between policy eval and policy improvment. Linear programming (LP) \n",
        "good for formulating constraine doptimization problems; considers U(s) of each s and notes uilities for optimal policy are the highest utilites attainable consistent with Bellman. RTDP: good for moderate\n",
        "domains like grid worlds.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"MDP: nondeterministic search problems that are applicable in a fully observable task environment where we have to make a series of actions whose outcomes are nondeterministic\n",
        "Due to nondeterminism, single sequence of actions can’t always be the solution--one way of solving: expectimax: value + policy iteration w/Additive rewards + probabilistic transition function. Intro to MDP: Navigating an asteroid field where we have a fully observable grid world\n",
        "and we pick an action at each time step--game terminates when it reaches a goal state and environment is stochastic: when action is picked, its result is uncertain. 80% of up is up; 20% of up moves to right or left Stochastic transition model as a probability:\n",
        "p(s’ | s, a): possible result state, current state, and action that gets to resulting state. The above reads as the probability of s’ given that we are in state sand we selected action a\n",
        "We ignore sequence of steps so far to end up in this state--Markovian transitions because the probability of arriving in s’ only depends on s and not the history of earlier states. Rewards can be positive or negative, bounded by some max value; Environmental history scores have a total utility = sum of instantaneous rewards\n",
        "MDP formulation: Markov Decision Process: Sequential decision problem, Fully observable environment, Stochastic transition model, Additive rewards. Expectimax nodes: outcomes are uncertain. In expectimax search we calculate their expected utilities:\n",
        "Probabilities defined over arcs: average of utilities of the outcomes weighted by probabilities: MDP formal definition: set of states, set of actions, Transition function: T(s, a, s’), Reward function: R(s, a, s’) or sometimes just R(s) or R(s’), Initial state s_0, Optionally, one or more terminal states, Solution to MDP = policy\n",
        "Policies and rewards: If we implement the same policy multiple times, this may lead to a different sequence of states and actions (environment history), and thus a different score under the reward function, so need to compute expected utility of all the possible paths generated by a policy\n",
        "Depending on reward amount, there could be a more optimal policy. Sequence of rewards: performance of an agent in an MDP is the sum of the rewards for the transitions it takes\n",
        "Utility function on an environment history: U_h([s0, a0, s1, a1,..., sn]). If the reward is positive, we can bounce around forever and avoid exits for infinite rewards!\n",
        "We prefer rewards now versus later (bc the environment is stochastic and we may not get rewards later) But what if we want greater rewards in the future?\n",
        "Discounting: values of rewards decay exponentially--every time we descend a level, we multiple in the discount once--Sooner rewards probably have higher utility than later rewards and helps algorithm coverage\n",
        "Exponentiated gamma --> bound on value of future rewards: example 0.5: U([1, 2, 3]): 0.5^0*1 + 0.5^1*2 + 0.5^2*3 = 1 + 0.5*2 + 0.25*3 so that U([1, 2, 3]) < U([3, 2, 1])\n",
        "MDP Search Tree\n",
        "MDP state projects an expectimax-like search tree\n",
        "S --> a leads to more s’, a’...\n",
        "(s,a) state action pair is a q-state\n",
        "(s, a, s’) is a transition ==> T(s, a, s’) = P(s’ | s, a) R(s, a, s’)\n",
        "Optimal quantities: \n",
        "Value (utility) of a state s:\n",
        "V*(s) = expected utility starting in s and acting optimally\n",
        "Value (utility) of a q-state (s,a):\n",
        "Q*(s, a) = expected utility starting out having taken action a from state s and thereafter acting optimally\n",
        "The optimal policy:\n",
        "pi*(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",
        "Recursive definition of value:\n",
        "Bellman = Q* is sum of T()[R(s, a, s’) + yV*(s’)]\n",
        "Racing search tree:\n",
        "Recursion can have high branching factors--we don’t need to do that much expectimax\n",
        "Problem: states are repeated so to solve that, we only compute needed quantities once\n",
        "Problem: tree goes on forever\n",
        "Idea: do depth-limited computation, but with increasing depths until change is small\n",
        "Deep parts of the tree don’t matter if y < 1\n",
        "Value iteration: \n",
        "Starting with V0(s) = 0: no time steps left means an expected reward sum of zero\n",
        "Given vector of V_k(s) state values, do one ply of expectimax from each state\n",
        "Repeat until convergence\n",
        "Complexity of each iteration: O(A * S^2)\n",
        "Theorem: will converge to unique optimal values\n",
        "Basic idea: approximations get refined towards optimal values\n",
        "Policy may converge long before values do\n",
        "V_{k+1}(s) = max_a Q*(s,a)\n",
        "        Then update values: V*(s) = V_{k+1}(s)\n",
        "Q*(s,a) = Σ_s' T(s,a,s') [R(s,a,s') + γ V*(s')]\n",
        "Policy evaluation: \n",
        "Utilities for a fixed policy:\n",
        "Compute utility of a state s under a fixed (generally non-optimal) policy\n",
        "Define the utility of a state s, under a fixed policy pi\n",
        "V^pi(s) = expected total discounted rewards starting in s and following pi\n",
        "Calculating V’s for a fixed policy pi:\n",
        "Turn recursive bellman equations into updates\n",
        "Efficiency: O(S^2) per iteration\n",
        "Linear system without the maxes \n",
        "Policy iteration:\t\n",
        "Problem with value iteration: asymptotic and max at each state rarely changes\n",
        "Approach for optimal values:\n",
        "Policy evaluation: calculate utilities for some fixed policy (not optimal utilities) until convergence\n",
        "Policy improvement: update policy using one-step look-ahead with resulting converged but not optimal utilities as future values\n",
        "Repeat until policy converges\n",
        "Policy iteration is optimal and converges faster under some conditions\n",
        "Step 1 (policy evaluation): for fixed current policy pi, find values with policy evaluation:\n",
        "Iterate until values converge\n",
        "Step 2 (policy improvement): for fixed values, get a better policy using policy extraction \n",
        "One step look ahead\n",
        "Value iteration vs policy iteration:\t\n",
        "Value iteration: \n",
        "Every iteration updates both values and policy\n",
        "Doesn’t track policy, but takes max over actions implicitly recomputes it\n",
        "Policy iteration:\n",
        "Do several passes that update utilities w/fixed policy (each pass is fast bc we consider only one action, not all of them)\n",
        "After policy is evaluated, a new policy is chosen\n",
        "New policy will be better, or we’re done\n",
        "To compute optimal values: value iteration or policy terationi\n",
        "Compute values for a particular policy: policy evaluation\n",
        "Turn values to policy: policy extraction (one-step lookahead)\n",
        "Maximum expected utility:\n",
        "Principle of MEU: rational agent should choose the action that maximizes its expected utility, given its knowledge\n",
        "For worst-case minimax reasoning, terminal function scale doesn’t matter\n",
        "Better states to have higher evaluations--> insensitivity to monotonic transformations (average case reasoning)\n",
        "For average-case expectimax reasoning, we need magnitudes to be meaningful\n",
        "Utilities are functions from outcomes (states of the world) to real numbers that describe an agent’s performance\n",
        "Utilities summarize the agent's goals\n",
        "Theorem: any rational preferences can be summarized as a utility function\n",
        "We hard-wire utilities and let behaviors emerge\n",
        "Preferences:\n",
        "Agent must have preferences among:\n",
        "Prizes (A, B, etc)\n",
        "Lotteries: situations with uncertain prizes\n",
        "L= [p, A; (1-p), B] \n",
        "Notation:\n",
        "Preference: A > B\n",
        "Indifference: A ~ B\n",
        "Fulfills axiom of transitivity\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"U(s) assigns single number indicating desirability of state\",\n",
        "\"expected utility\" : \"average utility value of outcomes weighted by probability that outcome occurs\",\n",
        "\"MEU\": \"rational agent should choose aaction that maximize's agent's EU\",\n",
        "\"Existence of utility function\": \"agent's preferences obey axioms of utility and U(A) > U(B) iff A > B; U(A) = U(B) iff A ~ B.\", \n",
        "\"expected utility of a lottery\": \"utility of lottery is sum of probability of each outocme x utility of that outcome\",\n",
        "\"value function\": \"ordinal utlity function/preference ranking on states w/o need for nums\",\n",
        "\"preference elicitation\": \"presents choices to human and uses observed preferences to pin utility function\",\n",
        "\"normalized utilites\": \"0,1 scale\",\n",
        "\"monotonicity\": \"where more is better\",\n",
        "\"certainty equivalent\": \"value in lieu of a lottery\",\n",
        "\"insurance premium\": \"differenc ebetween EMV of lottery and certainty equivalent\",\n",
        "\"risk neutral\": \"linear curve\",\n",
        "\"optimizer's curse\": \"estimated expected tuility of best choice = too high\",\n",
        "\"framing effect\": \"wording of decision problem impacting agent's choice\",\n",
        "\"anchoring effect\": \"idea of something being relatively cheap\",\n",
        "\"policy\": \"solution that specifies what agent does for any state it can reach (optimal = highest expected utility)\",\n",
        "\"proper policy\": \"solution that is guaranteed to reach a terminal state\", \n",
        "\"contraction\": \"function of one arg when applied to two diff inputs, produces 22 output vals that are close together than original inputs\", \n",
        "\"asynchronous policy iteration\": \"given certian conditions, async policy iteration is guaranteed to converge to an optimal policy\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "71554d4d-e35a-47a3-bd53-3355cd05607b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nAgent assignts P(s) to each uncertain state. P(s'|s,a) is transition model. MEU formalizes the right thing an agent should do, but\nnot how to do it: need perception, learning, knowledge representation, inference. Performance measure gives score for history--sequence of states.\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\nConstraints on rational preferences: A > B = agent prefers A over B. A ~ B = agent is indifferent. A >- agent prefers A over B or is indifferent\nbetween them. A and B are sets of outcomes for each action as a lottery where the action is a ticket. L w/outcomes S1...Sn w/probabilities p1...pn is L = [p1, S1, ...pn, Sn].\nSix constraints that preference relations should obey: orderability (preference), transitivity, continuity (in the middle), substitutability (A and B and more complex lotteries where B\nis subbing A in one of them), monotonicity (lottery w/higher probability for A if A is preferred), decomposability (compound lotteries to simple) = axioms of utility theory. \n\n## AIMA Chapter 16.3 Utility Functions\nDecision theory is a normmative theory--describes how rational agent should act. Descriptive theory describes how agents actually act. Certainty effect-->people are\nattracted to certainty bc to reduce computation burden; distrust legitimacy of stated probabilities; accounting for emotinoal and financial state\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nMarkovian transitions are ones whose probability of reaching s' from s depeneds only on s and not history of earlier states. If decision problem is sequential, specify utility\nfunction by sequence of states and actions--the environment history. Reward = R(s, a, s') for s transition from s to s'. MDP: sequential decision problem for fully observable, stochastic env\nwith Markovian transition model and additive rewards (solvable using DP). Finite horizons mean fixed time N and game is over (nonstationary); infinite means the optimal action depends\nnly on current state and optimal policy is stationary. Lower discount rate values closer rewards. U(s) = expected reward for next transition plus discounted utility of the next state. Action-utility function \nor Q-function Q(s,a) is the expected utility of taking a givne action in a given state. Dynamic decision networks (DDN) are factored reps that have exponential complexity advantage over atomic reps and can\nmodel substantial real-world problems: state St is composed of 4 state vars: Xt w/2d location on grid + orientation; Xt rate of change of X; charging when robot is plugged in; battery.\n\n## AIMA Chapter 17.2 Algorithms for MDPs\nValue iteration, policy iteration, linear programming offer same solutions to MDP. Value iteration is iterative, and starts with initial vals for utilities, calculate RH side of equation, \nplug into LH side, updates U for every s from utility of neighbors until equilibrium. Contractions has one fixed point; if 2, wouldn't get closer. When function applied to arg, value must get closer\nto fixed point so repeated applicaton of a contraction always reaches the fixed point in the limit. Policy iteration: algo alternates between policy eval and policy improvment. Linear programming (LP) \ngood for formulating constraine doptimization problems; considers U(s) of each s and notes uilities for optimal policy are the highest utilites attainable consistent with Bellman. RTDP: good for moderate\ndomains like grid worlds.\n\n## Module 8 Lecture Notes\nMDP: nondeterministic search problems that are applicable in a fully observable task environment where we have to make a series of actions whose outcomes are nondeterministic\nDue to nondeterminism, single sequence of actions can’t always be the solution--one way of solving: expectimax: value + policy iteration w/Additive rewards + probabilistic transition function. Intro to MDP: Navigating an asteroid field where we have a fully observable grid world\nand we pick an action at each time step--game terminates when it reaches a goal state and environment is stochastic: when action is picked, its result is uncertain. 80% of up is up; 20% of up moves to right or left Stochastic transition model as a probability:\np(s’ | s, a): possible result state, current state, and action that gets to resulting state. The above reads as the probability of s’ given that we are in state sand we selected action a\nWe ignore sequence of steps so far to end up in this state--Markovian transitions because the probability of arriving in s’ only depends on s and not the history of earlier states. Rewards can be positive or negative, bounded by some max value; Environmental history scores have a total utility = sum of instantaneous rewards\nMDP formulation: Markov Decision Process: Sequential decision problem, Fully observable environment, Stochastic transition model, Additive rewards. Expectimax nodes: outcomes are uncertain. In expectimax search we calculate their expected utilities:\nProbabilities defined over arcs: average of utilities of the outcomes weighted by probabilities: MDP formal definition: set of states, set of actions, Transition function: T(s, a, s’), Reward function: R(s, a, s’) or sometimes just R(s) or R(s’), Initial state s_0, Optionally, one or more terminal states, Solution to MDP = policy\nPolicies and rewards: If we implement the same policy multiple times, this may lead to a different sequence of states and actions (environment history), and thus a different score under the reward function, so need to compute expected utility of all the possible paths generated by a policy\nDepending on reward amount, there could be a more optimal policy. Sequence of rewards: performance of an agent in an MDP is the sum of the rewards for the transitions it takes\nUtility function on an environment history: U_h([s0, a0, s1, a1,..., sn]). If the reward is positive, we can bounce around forever and avoid exits for infinite rewards!\nWe prefer rewards now versus later (bc the environment is stochastic and we may not get rewards later) But what if we want greater rewards in the future?\nDiscounting: values of rewards decay exponentially--every time we descend a level, we multiple in the discount once--Sooner rewards probably have higher utility than later rewards and helps algorithm coverage\nExponentiated gamma --> bound on value of future rewards: example 0.5: U([1, 2, 3]): 0.5^0*1 + 0.5^1*2 + 0.5^2*3 = 1 + 0.5*2 + 0.25*3 so that U([1, 2, 3]) < U([3, 2, 1])\nMDP Search Tree\nMDP state projects an expectimax-like search tree\nS --> a leads to more s’, a’...\n(s,a) state action pair is a q-state\n(s, a, s’) is a transition ==> T(s, a, s’) = P(s’ | s, a) R(s, a, s’)\nOptimal quantities: \nValue (utility) of a state s:\nV*(s) = expected utility starting in s and acting optimally\nValue (utility) of a q-state (s,a):\nQ*(s, a) = expected utility starting out having taken action a from state s and thereafter acting optimally\nThe optimal policy:\npi*(s) = optimal action from state s\nValues of states:\nFundamental operation: compute the expectimax value of a state\nExpected utility under optimal action\nAverage sum of discounted rewards\nRecursive definition of value:\nBellman = Q* is sum of T()[R(s, a, s’) + yV*(s’)]\nRacing search tree:\nRecursion can have high branching factors--we don’t need to do that much expectimax\nProblem: states are repeated so to solve that, we only compute needed quantities once\nProblem: tree goes on forever\nIdea: do depth-limited computation, but with increasing depths until change is small\nDeep parts of the tree don’t matter if y < 1\nValue iteration: \nStarting with V0(s) = 0: no time steps left means an expected reward sum of zero\nGiven vector of V_k(s) state values, do one ply of expectimax from each state\nRepeat until convergence\nComplexity of each iteration: O(A * S^2)\nTheorem: will converge to unique optimal values\nBasic idea: approximations get refined towards optimal values\nPolicy may converge long before values do\nV_{k+1}(s) = max_a Q*(s,a)\n        Then update values: V*(s) = V_{k+1}(s)\nQ*(s,a) = Σ_s' T(s,a,s') [R(s,a,s') + γ V*(s')]\nPolicy evaluation: \nUtilities for a fixed policy:\nCompute utility of a state s under a fixed (generally non-optimal) policy\nDefine the utility of a state s, under a fixed policy pi\nV^pi(s) = expected total discounted rewards starting in s and following pi\nCalculating V’s for a fixed policy pi:\nTurn recursive bellman equations into updates\nEfficiency: O(S^2) per iteration\nLinear system without the maxes \nPolicy iteration:\t\nProblem with value iteration: asymptotic and max at each state rarely changes\nApproach for optimal values:\nPolicy evaluation: calculate utilities for some fixed policy (not optimal utilities) until convergence\nPolicy improvement: update policy using one-step look-ahead with resulting converged but not optimal utilities as future values\nRepeat until policy converges\nPolicy iteration is optimal and converges faster under some conditions\nStep 1 (policy evaluation): for fixed current policy pi, find values with policy evaluation:\nIterate until values converge\nStep 2 (policy improvement): for fixed values, get a better policy using policy extraction \nOne step look ahead\nValue iteration vs policy iteration:\t\nValue iteration: \nEvery iteration updates both values and policy\nDoesn’t track policy, but takes max over actions implicitly recomputes it\nPolicy iteration:\nDo several passes that update utilities w/fixed policy (each pass is fast bc we consider only one action, not all of them)\nAfter policy is evaluated, a new policy is chosen\nNew policy will be better, or we’re done\nTo compute optimal values: value iteration or policy terationi\nCompute values for a particular policy: policy evaluation\nTurn values to policy: policy extraction (one-step lookahead)\nMaximum expected utility:\nPrinciple of MEU: rational agent should choose the action that maximizes its expected utility, given its knowledge\nFor worst-case minimax reasoning, terminal function scale doesn’t matter\nBetter states to have higher evaluations--> insensitivity to monotonic transformations (average case reasoning)\nFor average-case expectimax reasoning, we need magnitudes to be meaningful\nUtilities are functions from outcomes (states of the world) to real numbers that describe an agent’s performance\nUtilities summarize the agent's goals\nTheorem: any rational preferences can be summarized as a utility function\nWe hard-wire utilities and let behaviors emerge\nPreferences:\nAgent must have preferences among:\nPrizes (A, B, etc)\nLotteries: situations with uncertain prizes\nL= [p, A; (1-p), B] \nNotation:\nPreference: A > B\nIndifference: A ~ B\nFulfills axiom of transitivity\n\n\n\n## Module 8 Definitions\n* **Utility function** - U(s) assigns single number indicating desirability of state\n* **Expected utility** - average utility value of outcomes weighted by probability that outcome occurs\n* **Meu** - rational agent should choose aaction that maximize's agent's EU\n* **Existence of utility function** - agent's preferences obey axioms of utility and U(A) > U(B) iff A > B; U(A) = U(B) iff A ~ B.\n* **Expected utility of a lottery** - utility of lottery is sum of probability of each outocme x utility of that outcome\n* **Value function** - ordinal utlity function/preference ranking on states w/o need for nums\n* **Preference elicitation** - presents choices to human and uses observed preferences to pin utility function\n* **Normalized utilites** - 0,1 scale\n* **Monotonicity** - where more is better\n* **Certainty equivalent** - value in lieu of a lottery\n* **Insurance premium** - differenc ebetween EMV of lottery and certainty equivalent\n* **Risk neutral** - linear curve\n* **Optimizer's curse** - estimated expected tuility of best choice = too high\n* **Framing effect** - wording of decision problem impacting agent's choice\n* **Anchoring effect** - idea of something being relatively cheap\n* **Policy** - solution that specifies what agent does for any state it can reach (optimal = highest expected utility)\n* **Proper policy** - solution that is guaranteed to reach a terminal state\n* **Contraction** - function of one arg when applied to two diff inputs, produces 22 output vals that are close together than original inputs\n* **Asynchronous policy iteration** - given certian conditions, async policy iteration is guaranteed to converge to an optimal policy\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 =  \"\"\"Exploitation vs exploration decision. Bandit problem: each arm M is a Markov reward process w/one possible action a (has states, TM, reward). Overall bandit problem \n",
        "is MDP--state space is given by Cartesian product, actions a. Gittens index: simple optimal policy for bandit: pull arm whighest Gittins index and update Gittins indices. Bernoulli bandit\n",
        "has each arm M produce reward of 0/1 w/fixed but unknown probability\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"Win/loss rewards are sparse for chess and racing, while tennis and cricket are the opposite. Intermediate rewards help the agent\n",
        "learn. In model-based RL the agent uses a transition model of the environment to help interpret the reward signals and make decisions about how to act. The model may be initially unknown, \n",
        "in which case the agent learns the model from observations. Model-based reinforcement learning systems often learn a utility function in terms of the sum of rewards from state onward.\n",
        "In model-free RL, the agent neither knows nor learns a transition model for the environment--it learns either action-utility learning (Q-learning/do something in state s based on highest Q-value) \n",
        "or policy search (policy that maps from states to actions). Passive RL--policy is fixed and learn U(s) and is blind. Active RL--agent must figure out what to do--must explore.\"\"\"\n",
        "chapter22_2 =  \"\"\"Passive reinforcement learning: policy is fixed and learn U(s) starting in state s--similar to policy evaluation, but we don't know reward or transition functions. Agent executes\n",
        "set of trials using policy pi. U(s) determined by the reward and the expected utility of the successor states. Ignores connections between states. Modified policy iteration: simplified value iteration\n",
        "process to update utility estimates after each change to learned model. A prioritized sweeping heuristic makes adjustments to states whose likely successors who have had huge changes in utility. \"\"\"\n",
        "chapter22_3 =  \"\"\"Active RL allows agents to choose the action they take--agent learns complete transition model w/outcome probabilities for all actions. Agent is greedy and will make whatever it thinks is\n",
        "the best move. Will make tradeoffs between exploitation and exploration. Temporal difference q-learning avoids learning models--instead, it learns an action-utility function Q(s, a) instead of a utility function.\n",
        "TD Q-learning agent does not use a transition model for learning or action selection--it's off-policy learning. SARSA is on-policy. \"\"\"\n",
        "chapter22_4 =  \"\"\"Reward shaping and pseudorewrds to speed up training--potential downfall to maximize on those and not goal rewards. Hierarchical reinforcement learning breaks up long action seqeunces into \n",
        "smaller pieces until they are short enough to make learning easy (soccer and keepaway). Partial programs outline hierarchical structure for agent's behavior, which we use in learning--agent can choose any action from \n",
        "specified set. HRL based on concept of joint state space where state (s, m) for physical and machine states. Sovles Markovian decision problem w/choice states of joint\n",
        "state space; actions according to the partial program; reward function = expected sum of rewards for all physical transitions occurring between the choice states; transition model. \"\"\"\n",
        "chapter22_5 =  \"\"\"Policy search: twiddling w/policy while performance still improves. Follow empirical + policy gradient and evaluate change in policy value for small incremenets in each param.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"Important ideas in reinforcement learning: exploration: try unknown actions to get information; xploitation: eventually, using what you know\n",
        "regret: even if you learn intelligently, you make mistakes;sampling: bc of chance, you must try things iteratively;difficulty: learning can be harder than solving a known MDP\n",
        "Intro to reinforcement learning II:\n",
        "Basic idea:\n",
        "Agent who is always acting w/set of available actions\n",
        "Receives feedback in the form of rewards\n",
        "Utility defined by reward function\n",
        "Must act so as to maximize expected rewards\n",
        "All learning based on observed samples of outcomes\n",
        "Still governed by MDP:\n",
        "Process contains:\n",
        "Set of states s in S\n",
        "Set of actions per state A\n",
        "Model T(s, a, s’)\n",
        "Reward function R(s, a, s’)\n",
        "Still looking for a policy pi\n",
        "Twist: we don’t know T or R\n",
        "Must try actions to figure these out\n",
        "This is online learning (vs MDP being offline learning)\n",
        "We can’t compute things in our head and we don’t know much in advance\n",
        "Model-based learning:\n",
        "Learn an approximate model based on experiences\n",
        "Solve for values as if the learned model was correct\n",
        "Step 1: learn empirical MDP model\n",
        "Count outcomes s’ for each s, a\n",
        "Normalize to get an estimate of the transition model\n",
        "Discover each reward function for each (s, a, s’)\n",
        "Step 2: solve the learned MDP\n",
        "Can use value iteration, for example, to get the best policy\n",
        "Passive Reinforcement Learning\n",
        "Model-free learning\n",
        "Once an action is taken, we compare our expected results with the actual ones\n",
        "Passive reinforcement learning: letting someone else choose the policy for us and we evaluate the reward\n",
        "Simplified task: policy evaluation\n",
        "Input: a fixed policy\n",
        "Goal is to learn the state values given unknown transitions and rewards\n",
        "In this case, the learner is along for the ride and they don’t get to choose their actions\n",
        "Direct evaluation\n",
        "Goal: compute values for each state under pi policy\n",
        "Ideal: average together observed sample values\n",
        "Act accordingly to pi policy\n",
        "Record sum of discounted rewards for each state\n",
        "Average samples \n",
        "Pros and cons:\n",
        "Pros: easy to understand, no knowledge of T, R required, eventually computes the correct average values using only sample transitions\n",
        "Cons: wastes information about state connections, each state must be learned separately--> takes a long time to learn\n",
        "Cannot use policy evaluation bc we need T and R to do it\n",
        "Improve estimate of V by providing by computing averages\n",
        "Take samples of outcomes s’ by doing the action and average\n",
        "Temporal difference learning\n",
        "Big difference: learn from every experience -- update V(s) every time we experience a transition (s, a, s’, r)\n",
        "Likely outcomes s’ will contribute updates more often\n",
        "Temporal difference learning of values\n",
        "Policy fixed, still doing evaluation\n",
        "Move values toward value of whatever successor occurs: running average\n",
        "Sample of V(s): sample = R(s, pi(s), s’ + yV^pi(s’)\n",
        "Update to V(s): (1-alpha)V^pi(s) + (alpha)sample OR V^pi(s) + alpha(sample - V^pi(s))\n",
        "Temporal difference learning bc we are comparing current estimates against a value we’re actually sampling\n",
        "Exponential moving average\n",
        "More recent samples are more important, as 1 - alpha term exponentially decays\n",
        "Decreasing learning rate (alpha) can give converging averages\n",
        "Forgets about the past (distant past values were wrong anyway, so this is good)\n",
        "Problems with TD value learning\n",
        "TD value learning is model-free way to do policy evaluation, mimikcing bellman updates w/running sample averages\n",
        "If we want to turn values into a new policy, we’re sunk bc we need to learn Q-values directly, not values themselves in order to have action selection be model-freeas well\n",
        "Active reinforcement Learning (Q-learning)\n",
        "Full reinforcement learning: optimal polices (like value iteration)\n",
        "Don’t know T or S, but we choose the actions now\n",
        "Goal: learn the optimal policy/values\n",
        "In this case: the learner makes the choices\n",
        "Exploration vs exploitation\n",
        "NOT offline planning, as we take actions in the world and find out what happens\n",
        "Detour: Q-value iteration\n",
        "Value iteration: find successive depth-limited values up to k + 1 values for all states given Vk:\n",
        "We are going to use Q-values instead, so that the best policy is directly observable from those Q-values\n",
        "Thus, given Qk, we calculate the depth k + 1 q-values for all q-states\n",
        "Move expectimax to the Q-value of the Qk+1 function\n",
        "Q-learning: sample-based Q-value iteration\n",
        "Must take a lot of samples in order to gain certainty about the transition function and reward function\n",
        "Learn Q(s, a) values as you go\n",
        "Receive a sample (s, a, s’, r)\n",
        "Consider old estimate Q(s, a)\n",
        "Consider your new sample estimate = R(s, a, s’) + ymaxQ(s’, a’)\n",
        "Incorporate the new estimate into a running average: Q(s, a) <-- (1-alpha)*Q(s, a) + alpha[sample]\n",
        "As alpha gets closer to 1, we put more weight on the sample, and as alpha gets closer to 0, we put more weight on our previous estimates\n",
        "We are able to update values as we go and our estimates for a particular Q-state improve\n",
        "Even though we don’t know the correct Q-values intially, we converge to the optimal policy\n",
        "Q-learning properties:\n",
        "Converges to optimal policy even when acting suboptimally--> off-policy learning\n",
        "Caveats: \n",
        "Have to explore enough\n",
        "Have to eventually make the learning rate small enough, but not decrease it too quickly\n",
        "In the limit, it doesn’t matter how you select actions\n",
        "Can tweak learning rate to trust previous history more than recent history\n",
        "Exploration vs exploitation: \n",
        "Exploration: have to try new things + make some mistakes\n",
        "Forcing exploration:\n",
        "Simplest: random actions (e-greedy)\n",
        "Every time step, flip a coin\n",
        "w/small probability e, act randomly\n",
        "w/large probability 1 - e, act on current policy\n",
        "Problems with random actions? \n",
        "Keeps trhashing once learning is done\n",
        "Solution: lower e over time, or exploration functions\n",
        "When to explore? (exploration function addresses this)\n",
        "Random actions: explore a fixed amount or\n",
        "Explore ares whose badness is not established yet, eventually stop exploring-->xplore areas of uncertainty, be optimistic \n",
        "Exploration function:\n",
        "Takes value estimate u and visit count n and returns an optimistic utility f(u, n) = u + k/n\n",
        "Modified q-update: plugin exploration function instead of normal maxQ(s’, a’) function\n",
        "Regret:\n",
        "Event if learn the optimal policy, you still make mistakes along the way\n",
        "Measures total mistake cost: difference between your expected rewards, including youthful suboptimality, and optimal (expected) rewards\n",
        "Minimizing regret goes beyond learning to be optimal--requires optimally learning to be optimal\n",
        "Ex: random exploration and exploration functions both end up optimal, but random exploration has higher regret\n",
        "Approximate Q-learning:\n",
        "Generalizing across states:\n",
        "Basic q-learning keps a table of all q-values\n",
        "In realistic scenarios, we can’t learn about every single state\n",
        "Too many states to visit in training + hold the q-tables in memory\n",
        "Need to generalize:\n",
        "Learn about small number of training states from experience\n",
        "Generalize experience to new, similar situations\n",
        "Fundamental idea in ML\n",
        "Flashback: eval functions\n",
        "Score non-terminals in depth-limited search\n",
        "Ideal function: returns actual minimax value of position\n",
        "In practice: typically weighted linear sum of features\n",
        "Ex: f1(s) = num white queens - num black queens\n",
        "Linear value functions\n",
        "Can write q function for any state using weights + feature representation\n",
        "Advantage: experience summed up in a few powerful nums\n",
        "Disadvantage: states may share features but be different in value\n",
        "Approximate q-learning\n",
        "Transition = (s, a, r, s’)\n",
        "Difference = [r + ymaxQ(s’, a’)] - Q(s, a)\n",
        "What we thought we would get - what we actually get\n",
        "Exact Q’s: Q(s, a) <-- Q(s, a) + alpha[difference]\n",
        "Approximate Q’s: wi<-- wi + alpha[difference] fi(s, a)\n",
        "Update weight in linear function if feature value is active\n",
        "Intuitively:\n",
        "Adjust weights of active features\n",
        "E.g. if something bad happens, blame features that were on and disprefer all states w/that state’s features\n",
        "Formal justification: online least squares\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"reinforcement learning\" : \"agent interacts w/world and receives periodic rewards\",\n",
        "\"direct utility estimation (reward to-go)\": \"U(s) = expected total reward from that state onward; each trial provides sample of this quantity for each state visited to maintain running avg\",\n",
        "\"adaptive dynamic programming\": \"uses constraints among each U(s) by learning the transition model that connects them and solving the corresponding MDP using DP\", \n",
        "\"pseudoexperience\": \"created by simulating current transition model\",\n",
        "\"GLIE\": \"“greedy in the limit of infinite exploration\", \n",
        "\"additive decomposition\": \"sum of rewards over time\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2a080b99-d5cc-4360-b689-5bdb9acab327"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nExploitation vs exploration decision. Bandit problem: each arm M is a Markov reward process w/one possible action a (has states, TM, reward). Overall bandit problem \nis MDP--state space is given by Cartesian product, actions a. Gittens index: simple optimal policy for bandit: pull arm whighest Gittins index and update Gittins indices. Bernoulli bandit\nhas each arm M produce reward of 0/1 w/fixed but unknown probability\n\n## AIMA Chapter 22.1 Learning from Rewards\nWin/loss rewards are sparse for chess and racing, while tennis and cricket are the opposite. Intermediate rewards help the agent\nlearn. In model-based RL the agent uses a transition model of the environment to help interpret the reward signals and make decisions about how to act. The model may be initially unknown, \nin which case the agent learns the model from observations. Model-based reinforcement learning systems often learn a utility function in terms of the sum of rewards from state onward.\nIn model-free RL, the agent neither knows nor learns a transition model for the environment--it learns either action-utility learning (Q-learning/do something in state s based on highest Q-value) \nor policy search (policy that maps from states to actions). Passive RL--policy is fixed and learn U(s) and is blind. Active RL--agent must figure out what to do--must explore.\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nPassive reinforcement learning: policy is fixed and learn U(s) starting in state s--similar to policy evaluation, but we don't know reward or transition functions. Agent executes\nset of trials using policy pi. U(s) determined by the reward and the expected utility of the successor states. Ignores connections between states. Modified policy iteration: simplified value iteration\nprocess to update utility estimates after each change to learned model. A prioritized sweeping heuristic makes adjustments to states whose likely successors who have had huge changes in utility. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nActive RL allows agents to choose the action they take--agent learns complete transition model w/outcome probabilities for all actions. Agent is greedy and will make whatever it thinks is\nthe best move. Will make tradeoffs between exploitation and exploration. Temporal difference q-learning avoids learning models--instead, it learns an action-utility function Q(s, a) instead of a utility function.\nTD Q-learning agent does not use a transition model for learning or action selection--it's off-policy learning. SARSA is on-policy. \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nReward shaping and pseudorewrds to speed up training--potential downfall to maximize on those and not goal rewards. Hierarchical reinforcement learning breaks up long action seqeunces into \nsmaller pieces until they are short enough to make learning easy (soccer and keepaway). Partial programs outline hierarchical structure for agent's behavior, which we use in learning--agent can choose any action from \nspecified set. HRL based on concept of joint state space where state (s, m) for physical and machine states. Sovles Markovian decision problem w/choice states of joint\nstate space; actions according to the partial program; reward function = expected sum of rewards for all physical transitions occurring between the choice states; transition model. \n\n## Module 9 Lecture Notes\nImportant ideas in reinforcement learning: exploration: try unknown actions to get information; xploitation: eventually, using what you know\nregret: even if you learn intelligently, you make mistakes;sampling: bc of chance, you must try things iteratively;difficulty: learning can be harder than solving a known MDP\nIntro to reinforcement learning II:\nBasic idea:\nAgent who is always acting w/set of available actions\nReceives feedback in the form of rewards\nUtility defined by reward function\nMust act so as to maximize expected rewards\nAll learning based on observed samples of outcomes\nStill governed by MDP:\nProcess contains:\nSet of states s in S\nSet of actions per state A\nModel T(s, a, s’)\nReward function R(s, a, s’)\nStill looking for a policy pi\nTwist: we don’t know T or R\nMust try actions to figure these out\nThis is online learning (vs MDP being offline learning)\nWe can’t compute things in our head and we don’t know much in advance\nModel-based learning:\nLearn an approximate model based on experiences\nSolve for values as if the learned model was correct\nStep 1: learn empirical MDP model\nCount outcomes s’ for each s, a\nNormalize to get an estimate of the transition model\nDiscover each reward function for each (s, a, s’)\nStep 2: solve the learned MDP\nCan use value iteration, for example, to get the best policy\nPassive Reinforcement Learning\nModel-free learning\nOnce an action is taken, we compare our expected results with the actual ones\nPassive reinforcement learning: letting someone else choose the policy for us and we evaluate the reward\nSimplified task: policy evaluation\nInput: a fixed policy\nGoal is to learn the state values given unknown transitions and rewards\nIn this case, the learner is along for the ride and they don’t get to choose their actions\nDirect evaluation\nGoal: compute values for each state under pi policy\nIdeal: average together observed sample values\nAct accordingly to pi policy\nRecord sum of discounted rewards for each state\nAverage samples \nPros and cons:\nPros: easy to understand, no knowledge of T, R required, eventually computes the correct average values using only sample transitions\nCons: wastes information about state connections, each state must be learned separately--> takes a long time to learn\nCannot use policy evaluation bc we need T and R to do it\nImprove estimate of V by providing by computing averages\nTake samples of outcomes s’ by doing the action and average\nTemporal difference learning\nBig difference: learn from every experience -- update V(s) every time we experience a transition (s, a, s’, r)\nLikely outcomes s’ will contribute updates more often\nTemporal difference learning of values\nPolicy fixed, still doing evaluation\nMove values toward value of whatever successor occurs: running average\nSample of V(s): sample = R(s, pi(s), s’ + yV^pi(s’)\nUpdate to V(s): (1-alpha)V^pi(s) + (alpha)sample OR V^pi(s) + alpha(sample - V^pi(s))\nTemporal difference learning bc we are comparing current estimates against a value we’re actually sampling\nExponential moving average\nMore recent samples are more important, as 1 - alpha term exponentially decays\nDecreasing learning rate (alpha) can give converging averages\nForgets about the past (distant past values were wrong anyway, so this is good)\nProblems with TD value learning\nTD value learning is model-free way to do policy evaluation, mimikcing bellman updates w/running sample averages\nIf we want to turn values into a new policy, we’re sunk bc we need to learn Q-values directly, not values themselves in order to have action selection be model-freeas well\nActive reinforcement Learning (Q-learning)\nFull reinforcement learning: optimal polices (like value iteration)\nDon’t know T or S, but we choose the actions now\nGoal: learn the optimal policy/values\nIn this case: the learner makes the choices\nExploration vs exploitation\nNOT offline planning, as we take actions in the world and find out what happens\nDetour: Q-value iteration\nValue iteration: find successive depth-limited values up to k + 1 values for all states given Vk:\nWe are going to use Q-values instead, so that the best policy is directly observable from those Q-values\nThus, given Qk, we calculate the depth k + 1 q-values for all q-states\nMove expectimax to the Q-value of the Qk+1 function\nQ-learning: sample-based Q-value iteration\nMust take a lot of samples in order to gain certainty about the transition function and reward function\nLearn Q(s, a) values as you go\nReceive a sample (s, a, s’, r)\nConsider old estimate Q(s, a)\nConsider your new sample estimate = R(s, a, s’) + ymaxQ(s’, a’)\nIncorporate the new estimate into a running average: Q(s, a) <-- (1-alpha)*Q(s, a) + alpha[sample]\nAs alpha gets closer to 1, we put more weight on the sample, and as alpha gets closer to 0, we put more weight on our previous estimates\nWe are able to update values as we go and our estimates for a particular Q-state improve\nEven though we don’t know the correct Q-values intially, we converge to the optimal policy\nQ-learning properties:\nConverges to optimal policy even when acting suboptimally--> off-policy learning\nCaveats: \nHave to explore enough\nHave to eventually make the learning rate small enough, but not decrease it too quickly\nIn the limit, it doesn’t matter how you select actions\nCan tweak learning rate to trust previous history more than recent history\nExploration vs exploitation: \nExploration: have to try new things + make some mistakes\nForcing exploration:\nSimplest: random actions (e-greedy)\nEvery time step, flip a coin\nw/small probability e, act randomly\nw/large probability 1 - e, act on current policy\nProblems with random actions? \nKeeps trhashing once learning is done\nSolution: lower e over time, or exploration functions\nWhen to explore? (exploration function addresses this)\nRandom actions: explore a fixed amount or\nExplore ares whose badness is not established yet, eventually stop exploring-->xplore areas of uncertainty, be optimistic \nExploration function:\nTakes value estimate u and visit count n and returns an optimistic utility f(u, n) = u + k/n\nModified q-update: plugin exploration function instead of normal maxQ(s’, a’) function\nRegret:\nEvent if learn the optimal policy, you still make mistakes along the way\nMeasures total mistake cost: difference between your expected rewards, including youthful suboptimality, and optimal (expected) rewards\nMinimizing regret goes beyond learning to be optimal--requires optimally learning to be optimal\nEx: random exploration and exploration functions both end up optimal, but random exploration has higher regret\nApproximate Q-learning:\nGeneralizing across states:\nBasic q-learning keps a table of all q-values\nIn realistic scenarios, we can’t learn about every single state\nToo many states to visit in training + hold the q-tables in memory\nNeed to generalize:\nLearn about small number of training states from experience\nGeneralize experience to new, similar situations\nFundamental idea in ML\nFlashback: eval functions\nScore non-terminals in depth-limited search\nIdeal function: returns actual minimax value of position\nIn practice: typically weighted linear sum of features\nEx: f1(s) = num white queens - num black queens\nLinear value functions\nCan write q function for any state using weights + feature representation\nAdvantage: experience summed up in a few powerful nums\nDisadvantage: states may share features but be different in value\nApproximate q-learning\nTransition = (s, a, r, s’)\nDifference = [r + ymaxQ(s’, a’)] - Q(s, a)\nWhat we thought we would get - what we actually get\nExact Q’s: Q(s, a) <-- Q(s, a) + alpha[difference]\nApproximate Q’s: wi<-- wi + alpha[difference] fi(s, a)\nUpdate weight in linear function if feature value is active\nIntuitively:\nAdjust weights of active features\nE.g. if something bad happens, blame features that were on and disprefer all states w/that state’s features\nFormal justification: online least squares\n\n\n## Module 9 Definitions\n* **Reinforcement learning** - agent interacts w/world and receives periodic rewards\n* **Direct utility estimation (reward to-go)** - U(s) = expected total reward from that state onward; each trial provides sample of this quantity for each state visited to maintain running avg\n* **Adaptive dynamic programming** - uses constraints among each U(s) by learning the transition model that connects them and solving the corresponding MDP using DP\n* **Pseudoexperience** - created by simulating current transition model\n* **Glie** - “greedy in the limit of infinite exploration\n* **Additive decomposition** - sum of rewards over time\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 = \"\"\"Acting under uncertainty: need to keep track of belief state--represents setof all possible worlds. Drawbacks are that agent\n",
        "must consider every possible explanation fro sensor observations; correct contingent plan can grow too large and considers unlikely contingencies\n",
        "as welll; no plan guaranteed to achieve goal but agent must act--need way to compare merits of plans that are not guaranteed. Qualification problem: weak conclusions\n",
        "when can be simplified. Right thing to do--rational decision--depends on relative importance of various goals and likelihood and degree to which they will achieved. To use\n",
        "only logic  hard when diagnosing: laziness, theoretical ignorance, practical ignorance. Agent knowledge can only provide degree of belief. Theory of probability\n",
        "provides a way of summarizing the uncertainty that comes from our laziness and ignorance--solves qualification problem. Agent must have preferences amongst outcom--use utility theory to reason \n",
        "quantitatively. Decision theory = prob theory + utility theory.\"\"\"\n",
        "chapter12_2 = \"\"\"Sample space: set of all possible worlds--they are mutually exclusive and exhaustive. Cannot both be the case and one possible world must be the case. Fully specified\n",
        "probability model associates a numerical probability P(w) w/each possible world. In prob theory, sets are events, and in logic, set of world correspond to a proposition in a formal language.\n",
        "Factored representation: possible world rep by a set of variable/value pairs. Structured representation is more expression. Random vars are vars in probability theory--functio that maps from domain\n",
        "of possible world to some range (possible values it can take on).\"\"\"\n",
        "chapter12_3 = \"\"\"Inference using full join distributions: probabilistic inference = computation of posterior probabilities for query propositionis given observer evidence.\"\"\"\n",
        "chapter12_4 = \"\"\"INndependence: marginal vs absolute.\"\"\"\n",
        "chapter12_5 = \"\"\"Bayes = P(b|a) = P(a|b)P(b)/P(a); P(effect | cause) = causal vs P(cause | effect) diagnostic (more fragile than causal).\"\"\"\n",
        "chapter12_6 = \"\"\"Naive Bayes = used in cases where effect variables are not strictly indpeendent. \n",
        "\n",
        "\"\"\"\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 = \"\"\"speech recognition--example of noisy, ambiguous input that requires probabiliteies to distinguish. Also used in spell correct and grammar verifiction. Probabilities\n",
        "are important augmentative and alternative communication systems. Language models are models that assign probabilties to sequences of words. An n-gram is a sequence of words. Relative frequency is the ratio of the n-gram probability\n",
        "to the observed frequency of a particular sequence by the observed frequency of a prefix.\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"Eval LMs through extrinsic evaluation--know if a particular improvement in a component is going to help the task at hand--embed in applicatino and measure application \n",
        "improvement. Instrinsic evaluation is one that measures the quality of a model independent of any application: need training set/corpus, test set. Models fit such test sets if model assigns a higher probability \n",
        "to the test set--it more accurately predicts the test set. Given 2 probabilistic models, better model has a tighter fit to tset data. Training on test set introduces bias tha makes all prob look too hig and causes inccuracies in\n",
        "perplexity (inverse probability of the test set, normalized by number of words).\"\"\"\n",
        "SLP_chapter3_3 = \"\"\"sampling sentences from a lanugage model: choose random points according to their likelihood. \"\"\"\n",
        "SLP_chapter3_4 = \"\"\"Generalization and zeros: use training corpus when building n-gram models in a similar genre as to what we're doing. Need it in an appropriate dialect/variety \n",
        "related to our LM. Still can encounter sparsity in a closed vocabulary bc corpus is limited. Zeros: things that don't occur in training set but are in test set. Unknown words/OOV words are words we have never seen before. \n",
        "OOV rate is percentage of OOV words that appear in test set--open vocab system is one where we model these potential unknown words in the test set by adding a pseudo-word called UNK. Can train probabilites of the UNK by turning problem back\n",
        "into closed vocab one and choosing a fixed vocab in advance: 1) choose vocab 2) convert training set any word not in set to UNK 3) estimate probabilities for UNK; can instead replace words in training data by UNK based \n",
        "on frequency.\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"Smoothing/discounting is shaving off a bit of probability mass for more freuqent events. Laplace smoothing: add one to all n-gram counts\n",
        "before normalizing them into probabiltiies--practical for text classificationn. Add k-smoothing is adding a fractional count k--we choose k by optimizing\n",
        "on a devset. Backoff + interpolation uses the trigram if the evidence is sufficient--otherwise use bigram, else unigram. Go to lower-order n-gram iif there is 0 evidence for higher-order n-gram. \n",
        "Interpolation mixes probability estimates from all n-gram estimators, weighing and combining 3-2-1gram counts\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"stupid backoff: doesnt discount higher-order prbabilities--just backoff to a lower order ng-ram if higher-order n-gram has a zero count. Doesn't produce a prob distribution.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"Review of Probabilities:\n",
        "General situation:\n",
        "Two components: observed variables (evidence) and unobserved variables (states)\n",
        "Underlying that, probabilities are attributed to these variables (model)\n",
        "Probabilistic reasoning gives us a framework for managing our beliefs and knowledge\n",
        "Probabilities are about possible worlds--quantifies how likely a world is\n",
        "Possible worlds = sample space and are mutually exclusive and exhaustive\n",
        "Fully specified probability model associates a probability P(w) w/each possible world w\n",
        "Random variables: important in probability model\n",
        "Some aspect of world for which we can have uncertainty\n",
        "Denote random vars w/capital letters\n",
        "Axioms of probability:\n",
        "Probability of any world is between 0 and 1 for every world w (inclusive\n",
        "Totally probability of the set of all possible worlds is 1\n",
        "Distributions\n",
        "Unobserved random vars have distributions\n",
        "Distribution: table of probabilities of values\n",
        "Probability (lower case value) is a single number\n",
        "Joint probability distributsion:\n",
        "Over sets of random variables x_1, ..., x_n\n",
        "Specifies real number for each assignment, or outcome\n",
        "p(X1 = x1, ..., Xn = xn)\n",
        "Size of joint distribution if n variables w/domain sizes d? D to the power of n\n",
        "For all but smallest distributions, impractical to write out--should be a very large table\n",
        "Can make this more manageable by making assumptions about independence to reduce size of tables to a bunch of smaller tables\n",
        "Probabilistic model: joint distribution over a set of random variables\n",
        "Contains: random vars with domains, assignments are called outcomes, joint distributions (whether outcomes are likely)\n",
        "Domains are set of values that a variable can take out\n",
        "Sum of assignments sum to one\n",
        "Only certain variables directly interact w/each other--independence is common\n",
        "Events: event is a set E of outcomes\n",
        "\n",
        "Can sum these values together (ORs and ANDs)\n",
        "Events are usually partial assignments (like P(T=hot) vs P(T=hot, S=sunny)\n",
        "Marginal distributions\n",
        "Subtables that eliminate variables that we don’t care about atm\n",
        "Marginalization: summing out by combining collapsed rows by adding\n",
        "Conditional probabilities: simple relation between joint and conditional\n",
        "Tells us what we didn’t get to measure \n",
        "Give joint probability distribution, we need to get more info about one of the variables and its outcome\n",
        "Conditional distribution: probability distributions over some vars given fixed values of others \n",
        "Extracted from joint distribution\n",
        "Probabilistic Inference and Rules\n",
        "Compute desired probability from other known probabilities (eg conditional from joint)\n",
        "Generally compute conditional probabilities, which represent the agent’s beliefs given the evidence\n",
        "Probabilities change w/new evidence: new evidence causes beliefs to update \n",
        "A method: inference by enumeration:\n",
        "Split variables into three: evidence variables (things we have observed), query variables (outcomes we want to reason about), hidden variables (vars we are not observing/actively reasoning about)\n",
        "3 steps:\n",
        "Can write probability distribution for query variables after separating all variables\n",
        "Take big joint probability and select entries consistent with evidence\n",
        "Sum out H to get joint of query and evidence\n",
        "Normalize by summing over all Q, which will give us the Z term/denominator\n",
        "A method: the product rule\n",
        "Given subtables/conditional probability--> construct big joint probability table\n",
        "Reverse of inference by enumeration\n",
        "The chain rule\n",
        "Product rule to more than two vars--joint distribution as increment product of conditional distributions\n",
        "Bayes’ rule: two diff ways to factor a joint distribution over two variables\n",
        "Lets us build one conditional from its reverse\n",
        "Foundation of many systems--often one conditoinal is trickier to derive than the other\n",
        "Probabilistic Language Models\n",
        "Probabilistic model: take each word positions as discrete, random var where the possible outcomes is the set of all vocab in the English dictionary\n",
        "Given a few observations, estimate probability distribution over all assignments of words in the English dictionary\n",
        "One goal: assign probability to a sentence\n",
        "Autocomplete for texting\n",
        "Machine translation: input sentence in one languagae and translate to other\t\n",
        "Bayes: probability of english given foreign and probability of english\n",
        "Spell check\n",
        "Speech recognition\n",
        "Goals: compute probability fo a sentence or sequence of words\n",
        "Related task: probability of an upcoming word (autcomplete)--> language model (LM)\n",
        "Language model: P(W) or P(wn|w1, w2...wn-1)\n",
        "Ex: computing probability of a sentence/sequence of words\n",
        "W/sentence of n words in length, each of n words are going to correspond to a random var, so what is the probability that the sentence exists in the english language?\n",
        "Computing P(W): use chain rule (sort of transitive in a way)--> need probability esimate for each component of the probability\n",
        "Maximum likelihood estimation: counting up probabilities for conditional / probability for more general part\n",
        "Never have enough data to estimate whole sentence\n",
        "Simplifying assumption: Markov assumption\n",
        "Limit history and only let previous k number of environment history/observations to make more accurate estimations\n",
        "Amount of history taken into account defines the model\n",
        "Predictably, unigram models are nonsensical--> as we increase to n-grams, text becomes useful\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"ontological commitment\": \"world is composed of facts that do not hold in any particular case\",\n",
        "\"epistemological commitements\": \"logical agent believes each sentence to be true/false/no opinion, whereas prob agent might have numerical degree belief\",\n",
        "\"prob density function\": \"probability that rnaod var takes on some x as parameterized function of x\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "27d94afa-5b94-423a-dd8b-5bb4909d9b1e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nActing under uncertainty: need to keep track of belief state--represents setof all possible worlds. Drawbacks are that agent\nmust consider every possible explanation fro sensor observations; correct contingent plan can grow too large and considers unlikely contingencies\nas welll; no plan guaranteed to achieve goal but agent must act--need way to compare merits of plans that are not guaranteed. Qualification problem: weak conclusions\nwhen can be simplified. Right thing to do--rational decision--depends on relative importance of various goals and likelihood and degree to which they will achieved. To use\nonly logic  hard when diagnosing: laziness, theoretical ignorance, practical ignorance. Agent knowledge can only provide degree of belief. Theory of probability\nprovides a way of summarizing the uncertainty that comes from our laziness and ignorance--solves qualification problem. Agent must have preferences amongst outcom--use utility theory to reason \nquantitatively. Decision theory = prob theory + utility theory.\n\n## AIMA Chapter 12.2 Basic Probability Notation\nSample space: set of all possible worlds--they are mutually exclusive and exhaustive. Cannot both be the case and one possible world must be the case. Fully specified\nprobability model associates a numerical probability P(w) w/each possible world. In prob theory, sets are events, and in logic, set of world correspond to a proposition in a formal language.\nFactored representation: possible world rep by a set of variable/value pairs. Structured representation is more expression. Random vars are vars in probability theory--functio that maps from domain\nof possible world to some range (possible values it can take on).\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nInference using full join distributions: probabilistic inference = computation of posterior probabilities for query propositionis given observer evidence.\n\n## AIMA Chapter 12.4 Independence\nINndependence: marginal vs absolute.\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\nBayes = P(b|a) = P(a|b)P(b)/P(a); P(effect | cause) = causal vs P(cause | effect) diagnostic (more fragile than causal).\n\n## AIMA Chapter 12.6 Naive Bayes Models\nNaive Bayes = used in cases where effect variables are not strictly indpeendent. \n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\nspeech recognition--example of noisy, ambiguous input that requires probabiliteies to distinguish. Also used in spell correct and grammar verifiction. Probabilities\nare important augmentative and alternative communication systems. Language models are models that assign probabilties to sequences of words. An n-gram is a sequence of words. Relative frequency is the ratio of the n-gram probability\nto the observed frequency of a particular sequence by the observed frequency of a prefix.\n\n## SLP Chapter 3.2 Evaluating Language Models\nEval LMs through extrinsic evaluation--know if a particular improvement in a component is going to help the task at hand--embed in applicatino and measure application \nimprovement. Instrinsic evaluation is one that measures the quality of a model independent of any application: need training set/corpus, test set. Models fit such test sets if model assigns a higher probability \nto the test set--it more accurately predicts the test set. Given 2 probabilistic models, better model has a tighter fit to tset data. Training on test set introduces bias tha makes all prob look too hig and causes inccuracies in\nperplexity (inverse probability of the test set, normalized by number of words).\n\n## SLP Chapter 3.3 Sampling sentences from a language model\nsampling sentences from a lanugage model: choose random points according to their likelihood. \n\n## SLP Chapter 3.4 Generalization and Zeros\nGeneralization and zeros: use training corpus when building n-gram models in a similar genre as to what we're doing. Need it in an appropriate dialect/variety \nrelated to our LM. Still can encounter sparsity in a closed vocabulary bc corpus is limited. Zeros: things that don't occur in training set but are in test set. Unknown words/OOV words are words we have never seen before. \nOOV rate is percentage of OOV words that appear in test set--open vocab system is one where we model these potential unknown words in the test set by adding a pseudo-word called UNK. Can train probabilites of the UNK by turning problem back\ninto closed vocab one and choosing a fixed vocab in advance: 1) choose vocab 2) convert training set any word not in set to UNK 3) estimate probabilities for UNK; can instead replace words in training data by UNK based \non frequency.\n\n## SLP Chapter 3.5 Smoothing\nSmoothing/discounting is shaving off a bit of probability mass for more freuqent events. Laplace smoothing: add one to all n-gram counts\nbefore normalizing them into probabiltiies--practical for text classificationn. Add k-smoothing is adding a fractional count k--we choose k by optimizing\non a devset. Backoff + interpolation uses the trigram if the evidence is sufficient--otherwise use bigram, else unigram. Go to lower-order n-gram iif there is 0 evidence for higher-order n-gram. \nInterpolation mixes probability estimates from all n-gram estimators, weighing and combining 3-2-1gram counts\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nstupid backoff: doesnt discount higher-order prbabilities--just backoff to a lower order ng-ram if higher-order n-gram has a zero count. Doesn't produce a prob distribution.\n\n## Module 10 Lecture Notes\nReview of Probabilities:\nGeneral situation:\nTwo components: observed variables (evidence) and unobserved variables (states)\nUnderlying that, probabilities are attributed to these variables (model)\nProbabilistic reasoning gives us a framework for managing our beliefs and knowledge\nProbabilities are about possible worlds--quantifies how likely a world is\nPossible worlds = sample space and are mutually exclusive and exhaustive\nFully specified probability model associates a probability P(w) w/each possible world w\nRandom variables: important in probability model\nSome aspect of world for which we can have uncertainty\nDenote random vars w/capital letters\nAxioms of probability:\nProbability of any world is between 0 and 1 for every world w (inclusive\nTotally probability of the set of all possible worlds is 1\nDistributions\nUnobserved random vars have distributions\nDistribution: table of probabilities of values\nProbability (lower case value) is a single number\nJoint probability distributsion:\nOver sets of random variables x_1, ..., x_n\nSpecifies real number for each assignment, or outcome\np(X1 = x1, ..., Xn = xn)\nSize of joint distribution if n variables w/domain sizes d? D to the power of n\nFor all but smallest distributions, impractical to write out--should be a very large table\nCan make this more manageable by making assumptions about independence to reduce size of tables to a bunch of smaller tables\nProbabilistic model: joint distribution over a set of random variables\nContains: random vars with domains, assignments are called outcomes, joint distributions (whether outcomes are likely)\nDomains are set of values that a variable can take out\nSum of assignments sum to one\nOnly certain variables directly interact w/each other--independence is common\nEvents: event is a set E of outcomes\n\nCan sum these values together (ORs and ANDs)\nEvents are usually partial assignments (like P(T=hot) vs P(T=hot, S=sunny)\nMarginal distributions\nSubtables that eliminate variables that we don’t care about atm\nMarginalization: summing out by combining collapsed rows by adding\nConditional probabilities: simple relation between joint and conditional\nTells us what we didn’t get to measure \nGive joint probability distribution, we need to get more info about one of the variables and its outcome\nConditional distribution: probability distributions over some vars given fixed values of others \nExtracted from joint distribution\nProbabilistic Inference and Rules\nCompute desired probability from other known probabilities (eg conditional from joint)\nGenerally compute conditional probabilities, which represent the agent’s beliefs given the evidence\nProbabilities change w/new evidence: new evidence causes beliefs to update \nA method: inference by enumeration:\nSplit variables into three: evidence variables (things we have observed), query variables (outcomes we want to reason about), hidden variables (vars we are not observing/actively reasoning about)\n3 steps:\nCan write probability distribution for query variables after separating all variables\nTake big joint probability and select entries consistent with evidence\nSum out H to get joint of query and evidence\nNormalize by summing over all Q, which will give us the Z term/denominator\nA method: the product rule\nGiven subtables/conditional probability--> construct big joint probability table\nReverse of inference by enumeration\nThe chain rule\nProduct rule to more than two vars--joint distribution as increment product of conditional distributions\nBayes’ rule: two diff ways to factor a joint distribution over two variables\nLets us build one conditional from its reverse\nFoundation of many systems--often one conditoinal is trickier to derive than the other\nProbabilistic Language Models\nProbabilistic model: take each word positions as discrete, random var where the possible outcomes is the set of all vocab in the English dictionary\nGiven a few observations, estimate probability distribution over all assignments of words in the English dictionary\nOne goal: assign probability to a sentence\nAutocomplete for texting\nMachine translation: input sentence in one languagae and translate to other\t\nBayes: probability of english given foreign and probability of english\nSpell check\nSpeech recognition\nGoals: compute probability fo a sentence or sequence of words\nRelated task: probability of an upcoming word (autcomplete)--> language model (LM)\nLanguage model: P(W) or P(wn|w1, w2...wn-1)\nEx: computing probability of a sentence/sequence of words\nW/sentence of n words in length, each of n words are going to correspond to a random var, so what is the probability that the sentence exists in the english language?\nComputing P(W): use chain rule (sort of transitive in a way)--> need probability esimate for each component of the probability\nMaximum likelihood estimation: counting up probabilities for conditional / probability for more general part\nNever have enough data to estimate whole sentence\nSimplifying assumption: Markov assumption\nLimit history and only let previous k number of environment history/observations to make more accurate estimations\nAmount of history taken into account defines the model\nPredictably, unigram models are nonsensical--> as we increase to n-grams, text becomes useful\n\n\n## Module 10 Definitions\n* **Ontological commitment** - world is composed of facts that do not hold in any particular case\n* **Epistemological commitements** - logical agent believes each sentence to be true/false/no opinion, whereas prob agent might have numerical degree belief\n* **Prob density function** - probability that rnaod var takes on some x as parameterized function of x\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 = \"\"\"Bayesian networks can represent depenedencies among variables + any full joint prob distribution--directed graph in which\n",
        "each node is annotated w/quantitative prob info: 1) each node corresponds to a random var, discrete or continuous 2)directed links/arrows connect pairs of nodes and the graph\n",
        "is a DAG 3) each node has associated probabiltiy info that quantifies effect of parents on the node using finite num of params. Local probability info attached to each node is in the form \n",
        "of a conditional probability table (discrete)--each row contains conditional prob of each node value for a conditioning case. Probs summarize a potentially infinite set of circumstances\n",
        "in which something happens==a small agent can cope w/large world. \"\"\"\n",
        "chapter13_2 = \"\"\"Bayesian netowrk is correpct rep of domain if each node is conditionally independent of its other predeecssors in the in the node ordering, given its parents. Methodology:\n",
        "nodes = set of variables required to model the domain; links = for i in range n choose minimal set of parents, insert link from parent to Xi for each parent, CPTs write down DPT for P(Xi|Parents(Xi)). \n",
        "Compactness of Bayesian networks is an example of general property of locally structured/sparse systems--grows linearly, not exponentially. Each variable is conditionally independent of its\n",
        "non-descendants, given its parents; variable is conditionally independent if all other nodes in the network, given parents, children, and children's parents--give Markov blanket (allows for local\n",
        "and distributed stochastic sampling processes). check for d-seapration by 1) consdiering ancestral subgraph XYZ and ancestors 2) add links between any unlinked pair of nodes that share a common child to get\n",
        "moral graph 3) replace all directed links by undirected links 4) if Z blocks all paths between X and Y in resulting graph, Z d-separates X and Y such that X is conditionally indepnedent of Y given Z. Else, original\n",
        "Bayes net does not require conditional independence. Bayes net can include hidden vars that are essential for structuring network\"\"\"\n",
        "chapter13_3 = \"\"\"task for any probabilistic inference system is to compute psoterior proabbility distribution for set of query vars given an observed event (assignment of values to a set of evidece vars.\n",
        "A query can be answered using Bayes net by computing sums of products of conditional probabilities  from the network. Variable elimination evaluates expressions in right to left/bottom up order and \n",
        "intermediate results are stored w/summations over each variable done for portions of expression that depend on the variable. Time + space complexity fo exact inference in polytrees is linear in the size of the network.\n",
        "For multiply connected netowkrs (insurance), variable elimination can have exponential complexity since it includes inference in propositoinal logic as a special case--thus NP hard. Clustering algos like join tree algo can reduce\n",
        "time of Bayes net to O(n).\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"Review of Independence\n",
        "For two random vars x and y are independent if joint probability of x and y is equal to the marginal probabilities of x and y\n",
        "Conditional probability: x and y are independent given Z--ex: alarm, fire, smoke\n",
        "Absolute independence is rare--doesn’t help us make inferences about other variables\n",
        "Conditional independence is our most basic and robust form of knowledge about uncertain envrionments\n",
        "Bayes Net Assumptions\n",
        "Assumptions needed to define Bayes net given graph: Probability of xi | only conditional on its parents\n",
        "Beyond the chain rule--> Bayes net conditional independence assumptinos\n",
        "Additional conditional independences\n",
        "Can be read off the graph\n",
        "Important for modeling: understand assumptions made when choosing a Bayes net graph\n",
        "Tool for us to model the world\n",
        "D-separation (descendants): outline\n",
        "Algo to determine independence between variables\n",
        "Causal chain:\n",
        "Low pressure--> rain--> traffic such that P(x, y, z) = P(x)P(y|x)P(z|y)\n",
        "No guarantee that X is independent of Z\n",
        "Can guarantee X is independent of Z given Y\n",
        "Common cause:\n",
        " \n",
        "X not independent of Z\n",
        "\n",
        "Common effect: \n",
        "\n",
        "Reachability and Paths:\n",
        "Given bayes net graph, are two variables in BN independent? (given evidenc)\n",
        "Solution: analyze the graph\n",
        "Any complex example can be broken into repetitions of the three canonical cases\n",
        "Reachability:\n",
        "Recipe: shade evidence nodes, look for paths in the resulting graph\n",
        "Attempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent--> doesn’t work\n",
        "Path is active if each triple is active:\n",
        "Causal chain A-->B-->C where B is unobserved\n",
        "Common cause A<--B-->C where B is unobserved\n",
        "Common effect\n",
        "All it takes to block a path is a single inactive segment\n",
        "D-separation algorithm:\n",
        "Query: all undirected paths from i to j and check if all triples are inactive--this would be independent, otherwise it’ll not be independent\n",
        "inactive so independence is guaranteed\n",
        "active path so no guarantee to be independent\n",
        "active and not guaranteed independence\n",
        "Inference\n",
        "Calculating some userful quantity from a joint probability distribution\n",
        "Given query Q and evidence variables observed, what is the probability of the assignments?\n",
        "Inference by enumeration\n",
        "General case: we want probability of query variable given all observed vairables\n",
        "Select all entries consistent with evidence-->sum out H to get joint of query and evidence---> normalize\n",
        "Inference by enumeration in Bayes’ Net\n",
        "Given unlimited time, inference in BNs is easy\n",
        "Reminder of inference by enumeration by example:\n",
        "But takes too long: destroyed our Bayes simplified summation\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "b56f99a6-f250-4466-d5e0-79bc810a12bc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\nBayesian networks can represent depenedencies among variables + any full joint prob distribution--directed graph in which\neach node is annotated w/quantitative prob info: 1) each node corresponds to a random var, discrete or continuous 2)directed links/arrows connect pairs of nodes and the graph\nis a DAG 3) each node has associated probabiltiy info that quantifies effect of parents on the node using finite num of params. Local probability info attached to each node is in the form \nof a conditional probability table (discrete)--each row contains conditional prob of each node value for a conditioning case. Probs summarize a potentially infinite set of circumstances\nin which something happens==a small agent can cope w/large world. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nBayesian netowrk is correpct rep of domain if each node is conditionally independent of its other predeecssors in the in the node ordering, given its parents. Methodology:\nnodes = set of variables required to model the domain; links = for i in range n choose minimal set of parents, insert link from parent to Xi for each parent, CPTs write down DPT for P(Xi|Parents(Xi)). \nCompactness of Bayesian networks is an example of general property of locally structured/sparse systems--grows linearly, not exponentially. Each variable is conditionally independent of its\nnon-descendants, given its parents; variable is conditionally independent if all other nodes in the network, given parents, children, and children's parents--give Markov blanket (allows for local\nand distributed stochastic sampling processes). check for d-seapration by 1) consdiering ancestral subgraph XYZ and ancestors 2) add links between any unlinked pair of nodes that share a common child to get\nmoral graph 3) replace all directed links by undirected links 4) if Z blocks all paths between X and Y in resulting graph, Z d-separates X and Y such that X is conditionally indepnedent of Y given Z. Else, original\nBayes net does not require conditional independence. Bayes net can include hidden vars that are essential for structuring network\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\ntask for any probabilistic inference system is to compute psoterior proabbility distribution for set of query vars given an observed event (assignment of values to a set of evidece vars.\nA query can be answered using Bayes net by computing sums of products of conditional probabilities  from the network. Variable elimination evaluates expressions in right to left/bottom up order and \nintermediate results are stored w/summations over each variable done for portions of expression that depend on the variable. Time + space complexity fo exact inference in polytrees is linear in the size of the network.\nFor multiply connected netowkrs (insurance), variable elimination can have exponential complexity since it includes inference in propositoinal logic as a special case--thus NP hard. Clustering algos like join tree algo can reduce\ntime of Bayes net to O(n).\n\n## Module 11 Lecture Notes\nReview of Independence\nFor two random vars x and y are independent if joint probability of x and y is equal to the marginal probabilities of x and y\nConditional probability: x and y are independent given Z--ex: alarm, fire, smoke\nAbsolute independence is rare--doesn’t help us make inferences about other variables\nConditional independence is our most basic and robust form of knowledge about uncertain envrionments\nBayes Net Assumptions\nAssumptions needed to define Bayes net given graph: Probability of xi | only conditional on its parents\nBeyond the chain rule--> Bayes net conditional independence assumptinos\nAdditional conditional independences\nCan be read off the graph\nImportant for modeling: understand assumptions made when choosing a Bayes net graph\nTool for us to model the world\nD-separation (descendants): outline\nAlgo to determine independence between variables\nCausal chain:\nLow pressure--> rain--> traffic such that P(x, y, z) = P(x)P(y|x)P(z|y)\nNo guarantee that X is independent of Z\nCan guarantee X is independent of Z given Y\nCommon cause:\n \nX not independent of Z\n\nCommon effect: \n\nReachability and Paths:\nGiven bayes net graph, are two variables in BN independent? (given evidenc)\nSolution: analyze the graph\nAny complex example can be broken into repetitions of the three canonical cases\nReachability:\nRecipe: shade evidence nodes, look for paths in the resulting graph\nAttempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent--> doesn’t work\nPath is active if each triple is active:\nCausal chain A-->B-->C where B is unobserved\nCommon cause A<--B-->C where B is unobserved\nCommon effect\nAll it takes to block a path is a single inactive segment\nD-separation algorithm:\nQuery: all undirected paths from i to j and check if all triples are inactive--this would be independent, otherwise it’ll not be independent\ninactive so independence is guaranteed\nactive path so no guarantee to be independent\nactive and not guaranteed independence\nInference\nCalculating some userful quantity from a joint probability distribution\nGiven query Q and evidence variables observed, what is the probability of the assignments?\nInference by enumeration\nGeneral case: we want probability of query variable given all observed vairables\nSelect all entries consistent with evidence-->sum out H to get joint of query and evidence---> normalize\nInference by enumeration in Bayes’ Net\nGiven unlimited time, inference in BNs is easy\nReminder of inference by enumeration by example:\nBut takes too long: destroyed our Bayes simplified summation\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 = \"\"\"Improvement in learning depends on component to be improved, prior knowledgethe agent has, and data + feedback on that data.\n",
        "components of agents are direct mapping from condition on curr state to actions; means to infer relevant properties ofthe world from percept sequence; \n",
        "info about way the world evolves and about the results of possible actions agent can take; utility info indicating desirability of actions;\n",
        "goals that describe most desirable states; problem generator, critic, learning el that enable the system to improve. Three types of feedback: supervised learnin, agent observes\n",
        "input-output pairs and learns a function that maps from input to output--inputs could be camera images, each accompanied by output/label; unsupervised learning is when agent\n",
        "learns patterns in input w/o explicit feedback (clustering as an example--detecting maybe useful clusters of input examples); reinforcement learning is when agent \n",
        "learns from series of reinforcements--rewards and punishments.\"\"\"\n",
        "chapter19_2 = \"\"\"Supervised learning is given a training set of N example input-output pairs where each pair was generated by a function f(x), discover functoin h that approximates true function f; h is \n",
        "hyptohesis about hte world drawn from hypothesis space. h can be called a model of the data drawn from model class H and output y = ground truth (true answer asking model to predict).Choose hypothesis space by\n",
        "performing exporatory data analysis and choose good hypthesis by hoping for a consistent hypothesis--h such taht each xi in training set has h(xi) = yi. Look for best-fit function for which each h(x) is close to y. h generalizes well if it predicts\n",
        "output of test set. Bias is tendency of a predictive hypothesis to deviate from expected value when average voer diff training sets. hypothesis underfitting when it fails to find a pattern in the data; overfitting \n",
        "iis when it pays too much attention to the particular data set it's trained on.  Bias-variance tradeoff is a choice between more complex, low-bias hypotheses that fit training data well and simpler, lower-variance hypotheses that may generalize better.\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\"Decision tree = rep of a function that maps a vector of attribute values to a single output value--decision. REaches decision by performing a sequence of tets from root until a leaf is reached. Simplistic values and outputs are true or \n",
        "false (boolean classification, pos/neg). Four cases when considring recursive subproblems 1) if remaining examples are all pos/neg, done 2) some post + neg, choose best attribute to split them 3) no examples left means\n",
        "no example has been observed for this combination of attibute values and we return the most common output value from the set of examples that were used in constructing parent node 4) no attributes left but some pos + neg examples mean examples \n",
        "have same description but different classification; error/noise in data/domain is nondeterminstic/can't observe an attr that would distinguish examples. Decision tree pruning combats overfitting. \"\"\"\n",
        "chapter19_4 = \"\"\"Stationarity assumption: given example E that has same prior probability distribution and is indpenedent of previous exampes, examples that\n",
        "satisfy this are independent + identically distributed. Optimal fit is hypothesis that minimizes error rate. Need three data sets: training set to train, validation set to eval models and choose best, test set to do final unbiased eval of best model.\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\"Comoputational learning theory: any hypothesis is seriously will will be found out with hgh probability after a small num of examples. Hypothesis that is consistent w/larget set of training eamples \n",
        "is unlikley to be wrong--probably approx correct (PAC). PAC learning applys to a new hypothesis space-decision lists.\"\"\"\n",
        "chapter19_6 = \"\"\"linear functions of continuous-valued inputs--> linear regression.  Find values of weights to minimize empirical loss to fit a line in data. Many forms of learning involve adjusting weights to minimize loss--> use weight space.\n",
        "Decision boundary is line that separates two classes-linear decision boundary = linear separator and data that admit a spearator are called linearly separable.\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"Multinomial naive Bayes classifier makes naive assumption about how features interact. TExt doc as bag of words; Bayesian inference breaks down conditional probability into other probabilities. Naive Bayes is a generative model--makes\n",
        "implicit assumption about how a doc is generated. Most probable class by returning the highest product of two probabilities: prior probability of the class P(c) and likelihood ofthe doc P(d|c))\"\"\"\n",
        "slp_chapter4_2 = \"\"\"Solution for unkown words is to ignore them--also ignore stop words\"\"\"\n",
        "slp_chapter4_3 =\"\"\" hi\"\"\"\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"Previous focus on models for optimal decision: now we focus on how to acquire a model from data/experience\n",
        "Learning params, structs, hidden concepts\n",
        "Ex for text example: pam/ham binary classification for text input\n",
        "Someone has to label the features of spam, including caps, dollar signs\n",
        "Ex for digit recognition (digital imaging):\n",
        "Given some images labeled with digits, we want to predict future labeling on images\n",
        "Ex for other classification tasks: automatic grading, medical diagnoses, fraud detection\n",
        "What structure for BN and how to learn params for model-based learning?\n",
        "Naive Bayes\n",
        "Naive bayes for digits:\n",
        "All feats are independent of the label\n",
        "Simple digit recognition version:\n",
        "For each feature, the label causes that feature to be active or inactive\n",
        "One feature var for each grid position\n",
        "Input maps to feature vector\n",
        "Can be binary valued\n",
        "Every feature is conditionally independent of every other feature given the class label\n",
        "We can easily find the probability of a feature given a particular label\n",
        "General naive Bayes model: joint probability of a vector of features given a class label is the probability of a label times the product of all the probabilities of a particular feature given that label\n",
        "Number of params is linear in number of features\n",
        "Only have to specify how each feature depends on the class\n",
        "Model simplistic but works anyways\n",
        "General naive bayes requires:\n",
        "Inference method: need P(Y) and P(Fi|Y) tables\n",
        "Estimates of local conditional probabilities table\n",
        "Naive Bayes for text:\n",
        "What is the probability of piazza in a spam email?\n",
        "Probability of word at position i (vs not being the ith word in the dictionary)\n",
        "Bag of words bayes:\n",
        "Features are conditionally independent given email\n",
        "Model is insensitive to word ordering/reordering\n",
        "Given labeled instances, we have a training set, held out set, test set\n",
        "Training: how to estimate params\n",
        "Held out: how to estimate hyperparms of model\n",
        "Test: determine how well system is doing\n",
        "Can never peek at the test set!!\n",
        "Eval: accuracy is the fraction of instances predicted correctly\n",
        "Overfitting and generalization: we want a classifier which does well on test data\n",
        "Overfitting: fitting data closely, not generalizing well\n",
        "Overfitting: probs(2) given “3.” example\n",
        "Fits 2 better than 3 because of the period\n",
        "Generalization and overfitting:\n",
        "Relative frequency params will overfit training data\n",
        "Just bc we don’t see 3 (example) during training doesn't mean it doesn’t happen at test time\n",
        "Need to smooth/regularize estimates\n",
        "Ex: red + blue jelly bean jar\n",
        "For each outcome x, look at the empirical rate of that value too\n",
        "Estimate that maximizes likelihood of the data\n",
        "What is the likelihood of seeing our training data \n",
        "Laplace smoothing:\n",
        "Reserves estimates for never seen before events\n",
        "P_ML(x) = <2/3, 1/3>\n",
        "P_LAP(X) = <3/5, 2/5>\n",
        "Pretend we see every outcome once more than you actually did\n",
        "Never assigns a zero probability to anything\n",
        "We can extend this by saying we saw every outcome an extra k times\n",
        "K = hyperparm (external)\n",
        "K is the strength of the prior\n",
        "K = 0 means that ML\n",
        "P_LAP,0(X) = same as ML\n",
        "P_LAP,1(X) = same as LAP\n",
        "P_LAP,100(X) = <102/203, 101/203>\n",
        "Estimation: linear interpolation\t\n",
        "Get empirical P(X) from data\n",
        "Makes sure the estimate of P(X|Y) isn’t too different from the empirical P(X)\n",
        "PLIN(x|y) = alphaP(x|y) + (1 - alpha)P(x)\n",
        "Tuning on held-out data\n",
        "Unknowns: params (probabilities of P(X|Y), P(Y)), hyperparams (e.g. type of smoothing)\n",
        "Learn params from training data\n",
        "Learn hyperparams on different data (held-out data)\n",
        "Train and test on the held-out data\n",
        "Choose best value and final test on test data\n",
        "Baseline\n",
        "Simplest thing to get results on a particular task\n",
        "Lower bound on task difficulty\n",
        "Weak baseline: most frequent label classifier\n",
        "Gives all test instances whatever label was most common in the training set\n",
        "Strong baseline: previous work -- often used in real research\n",
        "Confidence (of a model)\n",
        "Probabilistic classifier\n",
        "Represents how sure classifier is of the classification\n",
        "No guarantee that it’s correct\n",
        "Ex: probability of mail being spam\n",
        "Perceptrons\n",
        "Error driven model that takes training data, randomly inits params, and for every item in training data, tweaks params to make them a better fit\n",
        "Initially inspired by a neuron\n",
        "Contains:\n",
        "Set of inputs\n",
        "Set of weights\n",
        "Weighted sum: summation of product of inputs and associated weights\n",
        "Activation function: if sum is greater than threshold, there will be an output\n",
        "Perceptrons for decision making:\n",
        "Different factors (inputs) contribute to a decision \n",
        "Can be described as dot product of input vector and weight vector\n",
        "Learning weights from examples:\n",
        "Inputs as features--feature values are fixed, but weight vectors can change to get a different classifier\n",
        "Learning: binary perceptron\n",
        "Start with weights = 0\n",
        "For each training instance, classify with current weights and if correct, no change\n",
        "Otherwise, adjust the weight vector by adding/subtracting\n",
        "Subtract if y* is -1\n",
        "W = w + y* dot f\n",
        "Multiclass decision rule\n",
        "Each class has own weight vector \n",
        "Takes score of a particular input and pick the weight vector with maximum activation\n",
        "Aka prediction highest score wins\n",
        "Start with all weights and pick up training experience one by one\n",
        "Predict w/current weights and if correct, there’s not change\n",
        "Else, lower score of wrong answer, raise score of right answer\n",
        " Properties\n",
        "Separability\n",
        "Convergence \n",
        "Mistake bound\n",
        "delta^2 = margin\n",
        "Problems with perceptrons:\n",
        "Noise: if data isn’t separable, weights might thrash (averaging weight vectors over time can help)\n",
        "Mediocre generalization: finds a barely separating solution\n",
        "Overtraining: a kind of overfitting in which test/held-out accuracy rises for awhile, then falls\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"induction\": \"specific set of observations to general rule\",\n",
        "\"classification\": \"learning problem when output is a finite set of values\",\n",
        "\"regression\": \"when it's a number\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "337a8e3b-d92f-4b97-97e4-70d88fe3a24d"
      },
      "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",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nImprovement in learning depends on component to be improved, prior knowledgethe agent has, and data + feedback on that data.\ncomponents of agents are direct mapping from condition on curr state to actions; means to infer relevant properties ofthe world from percept sequence; \ninfo about way the world evolves and about the results of possible actions agent can take; utility info indicating desirability of actions;\ngoals that describe most desirable states; problem generator, critic, learning el that enable the system to improve. Three types of feedback: supervised learnin, agent observes\ninput-output pairs and learns a function that maps from input to output--inputs could be camera images, each accompanied by output/label; unsupervised learning is when agent\nlearns patterns in input w/o explicit feedback (clustering as an example--detecting maybe useful clusters of input examples); reinforcement learning is when agent \nlearns from series of reinforcements--rewards and punishments.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nSupervised learning is given a training set of N example input-output pairs where each pair was generated by a function f(x), discover functoin h that approximates true function f; h is \nhyptohesis about hte world drawn from hypothesis space. h can be called a model of the data drawn from model class H and output y = ground truth (true answer asking model to predict).Choose hypothesis space by\nperforming exporatory data analysis and choose good hypthesis by hoping for a consistent hypothesis--h such taht each xi in training set has h(xi) = yi. Look for best-fit function for which each h(x) is close to y. h generalizes well if it predicts\noutput of test set. Bias is tendency of a predictive hypothesis to deviate from expected value when average voer diff training sets. hypothesis underfitting when it fails to find a pattern in the data; overfitting \niis when it pays too much attention to the particular data set it's trained on.  Bias-variance tradeoff is a choice between more complex, low-bias hypotheses that fit training data well and simpler, lower-variance hypotheses that may generalize better.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nDecision tree = rep of a function that maps a vector of attribute values to a single output value--decision. REaches decision by performing a sequence of tets from root until a leaf is reached. Simplistic values and outputs are true or \nfalse (boolean classification, pos/neg). Four cases when considring recursive subproblems 1) if remaining examples are all pos/neg, done 2) some post + neg, choose best attribute to split them 3) no examples left means\nno example has been observed for this combination of attibute values and we return the most common output value from the set of examples that were used in constructing parent node 4) no attributes left but some pos + neg examples mean examples \nhave same description but different classification; error/noise in data/domain is nondeterminstic/can't observe an attr that would distinguish examples. Decision tree pruning combats overfitting. \n\n## AIMA Chapter 5.5 Stochastic Games\nStationarity assumption: given example E that has same prior probability distribution and is indpenedent of previous exampes, examples that\nsatisfy this are independent + identically distributed. Optimal fit is hypothesis that minimizes error rate. Need three data sets: training set to train, validation set to eval models and choose best, test set to do final unbiased eval of best model.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nComoputational learning theory: any hypothesis is seriously will will be found out with hgh probability after a small num of examples. Hypothesis that is consistent w/larget set of training eamples \nis unlikley to be wrong--probably approx correct (PAC). PAC learning applys to a new hypothesis space-decision lists.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nlinear functions of continuous-valued inputs--> linear regression.  Find values of weights to minimize empirical loss to fit a line in data. Many forms of learning involve adjusting weights to minimize loss--> use weight space.\nDecision boundary is line that separates two classes-linear decision boundary = linear separator and data that admit a spearator are called linearly separable.\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\nMultinomial naive Bayes classifier makes naive assumption about how features interact. TExt doc as bag of words; Bayesian inference breaks down conditional probability into other probabilities. Naive Bayes is a generative model--makes\nimplicit assumption about how a doc is generated. Most probable class by returning the highest product of two probabilities: prior probability of the class P(c) and likelihood ofthe doc P(d|c))\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\nSolution for unkown words is to ignore them--also ignore stop words\n\n## Module 12 Lecture Notes\nPrevious focus on models for optimal decision: now we focus on how to acquire a model from data/experience\nLearning params, structs, hidden concepts\nEx for text example: pam/ham binary classification for text input\nSomeone has to label the features of spam, including caps, dollar signs\nEx for digit recognition (digital imaging):\nGiven some images labeled with digits, we want to predict future labeling on images\nEx for other classification tasks: automatic grading, medical diagnoses, fraud detection\nWhat structure for BN and how to learn params for model-based learning?\nNaive Bayes\nNaive bayes for digits:\nAll feats are independent of the label\nSimple digit recognition version:\nFor each feature, the label causes that feature to be active or inactive\nOne feature var for each grid position\nInput maps to feature vector\nCan be binary valued\nEvery feature is conditionally independent of every other feature given the class label\nWe can easily find the probability of a feature given a particular label\nGeneral naive Bayes model: joint probability of a vector of features given a class label is the probability of a label times the product of all the probabilities of a particular feature given that label\nNumber of params is linear in number of features\nOnly have to specify how each feature depends on the class\nModel simplistic but works anyways\nGeneral naive bayes requires:\nInference method: need P(Y) and P(Fi|Y) tables\nEstimates of local conditional probabilities table\nNaive Bayes for text:\nWhat is the probability of piazza in a spam email?\nProbability of word at position i (vs not being the ith word in the dictionary)\nBag of words bayes:\nFeatures are conditionally independent given email\nModel is insensitive to word ordering/reordering\nGiven labeled instances, we have a training set, held out set, test set\nTraining: how to estimate params\nHeld out: how to estimate hyperparms of model\nTest: determine how well system is doing\nCan never peek at the test set!!\nEval: accuracy is the fraction of instances predicted correctly\nOverfitting and generalization: we want a classifier which does well on test data\nOverfitting: fitting data closely, not generalizing well\nOverfitting: probs(2) given “3.” example\nFits 2 better than 3 because of the period\nGeneralization and overfitting:\nRelative frequency params will overfit training data\nJust bc we don’t see 3 (example) during training doesn't mean it doesn’t happen at test time\nNeed to smooth/regularize estimates\nEx: red + blue jelly bean jar\nFor each outcome x, look at the empirical rate of that value too\nEstimate that maximizes likelihood of the data\nWhat is the likelihood of seeing our training data \nLaplace smoothing:\nReserves estimates for never seen before events\nP_ML(x) = <2/3, 1/3>\nP_LAP(X) = <3/5, 2/5>\nPretend we see every outcome once more than you actually did\nNever assigns a zero probability to anything\nWe can extend this by saying we saw every outcome an extra k times\nK = hyperparm (external)\nK is the strength of the prior\nK = 0 means that ML\nP_LAP,0(X) = same as ML\nP_LAP,1(X) = same as LAP\nP_LAP,100(X) = <102/203, 101/203>\nEstimation: linear interpolation\t\nGet empirical P(X) from data\nMakes sure the estimate of P(X|Y) isn’t too different from the empirical P(X)\nPLIN(x|y) = alphaP(x|y) + (1 - alpha)P(x)\nTuning on held-out data\nUnknowns: params (probabilities of P(X|Y), P(Y)), hyperparams (e.g. type of smoothing)\nLearn params from training data\nLearn hyperparams on different data (held-out data)\nTrain and test on the held-out data\nChoose best value and final test on test data\nBaseline\nSimplest thing to get results on a particular task\nLower bound on task difficulty\nWeak baseline: most frequent label classifier\nGives all test instances whatever label was most common in the training set\nStrong baseline: previous work -- often used in real research\nConfidence (of a model)\nProbabilistic classifier\nRepresents how sure classifier is of the classification\nNo guarantee that it’s correct\nEx: probability of mail being spam\nPerceptrons\nError driven model that takes training data, randomly inits params, and for every item in training data, tweaks params to make them a better fit\nInitially inspired by a neuron\nContains:\nSet of inputs\nSet of weights\nWeighted sum: summation of product of inputs and associated weights\nActivation function: if sum is greater than threshold, there will be an output\nPerceptrons for decision making:\nDifferent factors (inputs) contribute to a decision \nCan be described as dot product of input vector and weight vector\nLearning weights from examples:\nInputs as features--feature values are fixed, but weight vectors can change to get a different classifier\nLearning: binary perceptron\nStart with weights = 0\nFor each training instance, classify with current weights and if correct, no change\nOtherwise, adjust the weight vector by adding/subtracting\nSubtract if y* is -1\nW = w + y* dot f\nMulticlass decision rule\nEach class has own weight vector \nTakes score of a particular input and pick the weight vector with maximum activation\nAka prediction highest score wins\nStart with all weights and pick up training experience one by one\nPredict w/current weights and if correct, there’s not change\nElse, lower score of wrong answer, raise score of right answer\n Properties\nSeparability\nConvergence \nMistake bound\ndelta^2 = margin\nProblems with perceptrons:\nNoise: if data isn’t separable, weights might thrash (averaging weight vectors over time can help)\nMediocre generalization: finds a barely separating solution\nOvertraining: a kind of overfitting in which test/held-out accuracy rises for awhile, then falls\n\n\n## Module 12 Definitions\n* **Induction** - specific set of observations to general rule\n* **Classification** - learning problem when output is a finite set of values\n* **Regression** - when it's a number\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 = \"\"\"Sigmoid = classifier to make binary decision about class of a new input observation. Logistic regression solves task by learning from a training set a vector weights and a bis tem.\n",
        "Bias term = intercept is added to eh weighted inputs. The dot product gives us a legal probability--apply sigmoid.\"\"\"\n",
        "slp_chapter5_2 = \"\"\"To learnin logistic regresson, we require metric for how close label is to the true old label--distance between system output and gold output = loss funciton/cost function; second thing\n",
        "needed is optimazation algo ffor iteratively updating weights to minimze loss ufnction. Standard algo is graident descent.\"\"\"\n",
        "slp_chapter5_3 = \"\"\"Conditional max likelihood estimation: choose params that maximize log probability o the true y labels in the training data given observations x--> loss function is negative log likelihood loss, or\n",
        "cross-entropy loss.\"\"\"\n",
        "slp_chapter5_4 = \"\"\"Gradient descent finds min of a function by figuring out which direction the functions slope is rising most steepply and moving in the opp direction. \n",
        "Loss function is a convex for logistic regression. Graident descent algo finds graident of loss function at the current point andn moving in the opposite direction. Magnitude of amount to move in gradient descent is val of slope \n",
        "weighted by a learning rate n.\"\"\"\n",
        "slp_chapter5_5 = \"\"\"Regularization counters overfitting by penalizing large weights. \"\"\"\n",
        "slp_chapter5_6 = \"\"\"Multinomial logistic regression/softmax regression/maxent classifier: target y is a var that ranges over more than two classes; want to know proability of y being in each class. Then classifier uses generalization of \n",
        "the sigmoid called softmax to compute probability p(y=c|x)\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"Unit of neural network take sa weighted sum of its inputs w/additional bias terms--> set of corresponding weights and a bias b so weighted sum z can be \n",
        "b + summation of weighted x00vector and dot product.\"\"\"\n",
        "slp_chapter7_2 = \"\"\"XOR is not linearly separable--> solution is neural networks.\"\"\"\n",
        "slp_chapter7_3 = \"\"\"Feedforward network is a multilayer network in which units are connected w/no cycles--outputs from units in each layer are passed to units in the next higher layer and no outputs are passed back to lower layer. \n",
        "Three kinds of nodes: input untis, hiddne units, output uits. Input layer x = vector of simple scalar values; core is hidden layer h ofhidden units h1 and each layer is fully connected, meaning each unit in each layer \n",
        "takes input the outputs etc. \"\"\"\n",
        "slp_chapter7_4 = \"\"\"Classification: feedforward networks for NLP. Helps predict upcoming words from prior word context. Use forward inference/decoding for neural LMs.\n",
        "Algo for this: 1) select three embeddings from E matrix 2) multiply by W and pass through reLu to hiddn layer h 3) multiply by U 4) apply softmax.\"\"\"\n",
        "slp_chapter7_5 = \"\"\"Training neural nets require loss ufnction, find pararms that minimize loss function (gradient descent) and gradient descent requires knowing gradient of loss function--partial out loss over all intermediate layers by using\n",
        "error backpropagation/backward differentiation.\"\"\"\n",
        "slp_chapter7_6 = \"\"\"Neural language models use neural network as probabilistic classifier to compute prob of next work given previous n words\"\"\"\n",
        "slp_chapter7_7 = \"\"\"NLM use pretrained embeddings or learn embddgins from scratch in process of language modeling.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"Logistic Regression\n",
        "Classifier components:  Machine learning classifiers require a training corpus of M observations input/output pairs (x^i, y^i)\n",
        "Feature representation of input--vector of features\n",
        "Classification function: computes estimated class y via p(y|x)\n",
        "Objective function for learning, usually involving minimizing error on training examples (how good/bad is our classifier)\n",
        "Algo for optimizing objective function\n",
        "Sentiment classifier: take input, encode in some feature representation, and classifer output y can be 1 (positive sentiment) or 0 (negative sentiment)\n",
        "Want to estimate P(y=1|x)\n",
        "Logistic regression solves task by learning a vector of weights and a bias term\n",
        "Get feature element and multiply by weight to get dot product + bias term\n",
        "Sigmoid function:\n",
        "Probability for 1 i shown below (probability for 0 is 1 - the below)\n",
        "Decision boundary: when to output 0 or 1?\n",
        "0.5 can be the decision boundary if P(y=1 | x) is more than .5, we say yes; else no\n",
        "Extracting features:\n",
        "Can count number of positive connotation + negative connotation words\n",
        "Negation words, pronouns\n",
        "Assign wieghts to each var\n",
        "Computing Z = get product of values and weight of each var\n",
        "Learning in logistic regression:\n",
        "Get weights of model by learning params (weights + bias) via learning using:\n",
        "objective/loss function that tells us distance between system output and gold output. Cross-entropy loss used\n",
        "Algo for optimizng objective function--use stochastic gradient descent to minimize loss function\n",
        "Loss Function\n",
        "Determines how close a gold standard label item is to an output for a classifer\n",
        "Loss tells how much our prediction differs from the truth (mean square error)\n",
        "Loss function for probabilistic classification:\n",
        "Prefers class labels of the training example to be more likely\n",
        "Conditional mximum likelihood estimation--choose params w, b that maximize the log probabilities of the true labels in the training data\n",
        "Reseulting loss function is the negative log likelihood loss/cross entropy loss\n",
        "For one observation x, maximize probability of the correct label \n",
        "Change this to log spacex\n",
        "Result is cross entropy loss\n",
        "Minimzing negative log probability--loss to be smaller if model’s estimate is close to correct and loss to be bigger if it’s more conufsed\n",
        "Stochastic Gradient Descent:\n",
        "Theta is set of params in our model: weight vector and bias terms\n",
        "Minimizes cross-entropy loss across every example (ideally)\n",
        "Gradient descent is a method that finds a min of a function by figuring out in which direction the function’s slope is rising the most steeply, and moving in the oppposite direction\n",
        "Global v local minimums:\n",
        "For logistic regression, loss function is conveniently convex\n",
        "Convex function has one minmum so no local minima to get stuck in\n",
        "Gradient descent starting from any point is guaranteed to find a min\n",
        "Weight at each timestep is going to be the weight at the previous time and step minus the learning rate\n",
        "For each weight in vector, has own slope\n",
        "What is derivative with respect to our classifier in our current set of params\n",
        "Sum the number of elements in our params\n",
        "Gradient: cross entropy loss of weights of our prediction can be \n",
        "Mini batch training: stochastic graind gdescent choose a random example\n",
        "Alternate is batch training, which computes the graident over entire dataset--> better eestimates but takes a long time to compute\n",
        "Commonly used compromise is mini-batch training, and train on a small batch and loss is accumulated\n",
        "Regularization:\n",
        "Overfitting can be a problem with many models\n",
        "If feature only occurs in one class, attend with high weight\n",
        "Regularization is penalizing large weights\n",
        "SoftwMax: takes input vector and outputs a vector of values normalized into probabitlies\n",
        "Neural Network\n",
        "Perceptron: inputs go through activation function, and we generate a single improv\n",
        "Single neuron is actually a whole network in layers--output, hidden, hidden, input, for example\n",
        "Output of one layer--> intput into next layer\n",
        "If weights set correctly, can approxmiate a huge range of possible functions\n",
        "Incoming arrows: inputs to neurons, and from outside too\n",
        "perceptron--<logistic regression\n",
        "Feed-forward neural network\n",
        "Training neural nets: want to learn best params for neural net to make its predictions y as close as possible\n",
        "Need: loss function, optimization algorithm, wat of computing graident the log brooch\n",
        "Cross entry Loss-should be same in logistic.regression\n",
        "To compute gradient: logistic regression as network w/one wieght layer and isgmoid output\n",
        "Found slope and took step in a downward protection\n",
        "Computation graphs: general procedue like backward differentiation\n",
        "Depends on notion on your computation graphs\n",
        "Backward differentiation: importance of computation graph comes from ackward pass and need to know weight update.\t\n",
        "How to compute derivative of our output function L w/respect to the input\n",
        "Backwards differenciation using chain rule from calculus\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "bd62bdeb-1333-4243-a624-41605e997986"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\nSigmoid = classifier to make binary decision about class of a new input observation. Logistic regression solves task by learning from a training set a vector weights and a bis tem.\nBias term = intercept is added to eh weighted inputs. The dot product gives us a legal probability--apply sigmoid.\n\n## SLP Chapter 5.2 Learning in Logistic Regression\nTo learnin logistic regresson, we require metric for how close label is to the true old label--distance between system output and gold output = loss funciton/cost function; second thing\nneeded is optimazation algo ffor iteratively updating weights to minimze loss ufnction. Standard algo is graident descent.\n\n## SLP Chapter 5.3 The cross-entropy loss function\nConditional max likelihood estimation: choose params that maximize log probability o the true y labels in the training data given observations x--> loss function is negative log likelihood loss, or\ncross-entropy loss.\n\n## SLP Chapter 5.4 Gradient Descent\nGradient descent finds min of a function by figuring out which direction the functions slope is rising most steepply and moving in the opp direction. \nLoss function is a convex for logistic regression. Graident descent algo finds graident of loss function at the current point andn moving in the opposite direction. Magnitude of amount to move in gradient descent is val of slope \nweighted by a learning rate n.\n\n## SLP Chapter 5.5 Regularization\nRegularization counters overfitting by penalizing large weights. \n\n## SLP Chapter 5.6 Multinomial logistic regression\nMultinomial logistic regression/softmax regression/maxent classifier: target y is a var that ranges over more than two classes; want to know proability of y being in each class. Then classifier uses generalization of \nthe sigmoid called softmax to compute probability p(y=c|x)\n\n## SLP Chapter 7.1 Units\nUnit of neural network take sa weighted sum of its inputs w/additional bias terms--> set of corresponding weights and a bias b so weighted sum z can be \nb + summation of weighted x00vector and dot product.\n\n## SLP Chapter 7.2 The XOR problem\nXOR is not linearly separable--> solution is neural networks.\n\n## SLP Chapter 7.3 Feedforward Neural Networks\nFeedforward network is a multilayer network in which units are connected w/no cycles--outputs from units in each layer are passed to units in the next higher layer and no outputs are passed back to lower layer. \nThree kinds of nodes: input untis, hiddne units, output uits. Input layer x = vector of simple scalar values; core is hidden layer h ofhidden units h1 and each layer is fully connected, meaning each unit in each layer \ntakes input the outputs etc. \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\nClassification: feedforward networks for NLP. Helps predict upcoming words from prior word context. Use forward inference/decoding for neural LMs.\nAlgo for this: 1) select three embeddings from E matrix 2) multiply by W and pass through reLu to hiddn layer h 3) multiply by U 4) apply softmax.\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\nTraining neural nets require loss ufnction, find pararms that minimize loss function (gradient descent) and gradient descent requires knowing gradient of loss function--partial out loss over all intermediate layers by using\nerror backpropagation/backward differentiation.\n\n## SLP Chapter 7.6 Training Neural Nets\nNeural language models use neural network as probabilistic classifier to compute prob of next work given previous n words\n\n## SLP Chapter 7.7 Training the neural language model\nNLM use pretrained embeddings or learn embddgins from scratch in process of language modeling.\n\n## Module 13 Lecture Notes\nLogistic Regression\nClassifier components:  Machine learning classifiers require a training corpus of M observations input/output pairs (x^i, y^i)\nFeature representation of input--vector of features\nClassification function: computes estimated class y via p(y|x)\nObjective function for learning, usually involving minimizing error on training examples (how good/bad is our classifier)\nAlgo for optimizing objective function\nSentiment classifier: take input, encode in some feature representation, and classifer output y can be 1 (positive sentiment) or 0 (negative sentiment)\nWant to estimate P(y=1|x)\nLogistic regression solves task by learning a vector of weights and a bias term\nGet feature element and multiply by weight to get dot product + bias term\nSigmoid function:\nProbability for 1 i shown below (probability for 0 is 1 - the below)\nDecision boundary: when to output 0 or 1?\n0.5 can be the decision boundary if P(y=1 | x) is more than .5, we say yes; else no\nExtracting features:\nCan count number of positive connotation + negative connotation words\nNegation words, pronouns\nAssign wieghts to each var\nComputing Z = get product of values and weight of each var\nLearning in logistic regression:\nGet weights of model by learning params (weights + bias) via learning using:\nobjective/loss function that tells us distance between system output and gold output. Cross-entropy loss used\nAlgo for optimizng objective function--use stochastic gradient descent to minimize loss function\nLoss Function\nDetermines how close a gold standard label item is to an output for a classifer\nLoss tells how much our prediction differs from the truth (mean square error)\nLoss function for probabilistic classification:\nPrefers class labels of the training example to be more likely\nConditional mximum likelihood estimation--choose params w, b that maximize the log probabilities of the true labels in the training data\nReseulting loss function is the negative log likelihood loss/cross entropy loss\nFor one observation x, maximize probability of the correct label \nChange this to log spacex\nResult is cross entropy loss\nMinimzing negative log probability--loss to be smaller if model’s estimate is close to correct and loss to be bigger if it’s more conufsed\nStochastic Gradient Descent:\nTheta is set of params in our model: weight vector and bias terms\nMinimizes cross-entropy loss across every example (ideally)\nGradient descent is a method that finds a min of a function by figuring out in which direction the function’s slope is rising the most steeply, and moving in the oppposite direction\nGlobal v local minimums:\nFor logistic regression, loss function is conveniently convex\nConvex function has one minmum so no local minima to get stuck in\nGradient descent starting from any point is guaranteed to find a min\nWeight at each timestep is going to be the weight at the previous time and step minus the learning rate\nFor each weight in vector, has own slope\nWhat is derivative with respect to our classifier in our current set of params\nSum the number of elements in our params\nGradient: cross entropy loss of weights of our prediction can be \nMini batch training: stochastic graind gdescent choose a random example\nAlternate is batch training, which computes the graident over entire dataset--> better eestimates but takes a long time to compute\nCommonly used compromise is mini-batch training, and train on a small batch and loss is accumulated\nRegularization:\nOverfitting can be a problem with many models\nIf feature only occurs in one class, attend with high weight\nRegularization is penalizing large weights\nSoftwMax: takes input vector and outputs a vector of values normalized into probabitlies\nNeural Network\nPerceptron: inputs go through activation function, and we generate a single improv\nSingle neuron is actually a whole network in layers--output, hidden, hidden, input, for example\nOutput of one layer--> intput into next layer\nIf weights set correctly, can approxmiate a huge range of possible functions\nIncoming arrows: inputs to neurons, and from outside too\nperceptron--<logistic regression\nFeed-forward neural network\nTraining neural nets: want to learn best params for neural net to make its predictions y as close as possible\nNeed: loss function, optimization algorithm, wat of computing graident the log brooch\nCross entry Loss-should be same in logistic.regression\nTo compute gradient: logistic regression as network w/one wieght layer and isgmoid output\nFound slope and took step in a downward protection\nComputation graphs: general procedue like backward differentiation\nDepends on notion on your computation graphs\nBackward differentiation: importance of computation graph comes from ackward pass and need to know weight update.\t\nHow to compute derivative of our output function L w/respect to the input\nBackwards differenciation using chain rule from calculus\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 = \"\"\"\"\"\"\n",
        "slp_chapter9_2 = \"\"\"\"\"\"\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 = \"\"\"Lexical semantics: linguistic study of word meaning. Leammas and senses: meanings of a word and aspects of a meaning. Lemmas can be \n",
        "polysemous. Synonmy = words with the same meaning--propositional meaning satsifies truth conditoins. Priinciple of contrast: difference in linguistc form is assoficated with difference in meaning.\n",
        "Word similarity: similarity is categorization. Word relatedness = association and belong to same semantic field. Semantic frames and roles: denote perspectives or paritcipants in particular type of event. Connotation\n",
        "means sentiment.\"\"\"\n",
        "slp_chapter6_2 = \"\"\"Vector semantics: standrad way to rep word meaning in nLP and deifne the maning of word by distriution in lanugage. VEctors for representing words are called embeddings. In tf-idf model, meaning of a word is defined\n",
        "by a simple function .. Method results in long, sparse, mostly zero vectors. word2vec model for short dense vectors w/useful semantic properties. Cosine = way to use embedding to compute semantic similarity.\"\"\"\n",
        "slp_chapter6_3 = \"\"\"Term-dcoument matrix, each row rep word in vocab and is part of vector space model of info retrieval. Vector spac e= collection of vectors by dimension. Matrix useful for info retrieval.\"\"\"\n",
        "slp_chapter6_4 = \"\"\"normazlied dot prodcut = same as cosine of angle between two vectors.\"\"\"\n",
        "slp_chapter6_8 = \"\"\"tl-idf weighting isthe product of two terms wtih term catching one of these two intutions: term frequency or document fequency\"\"\"\n",
        "slp_chapter6_10 = \"\"\"semantics of embedding: analogy/relational similarity; \"\"\"\n",
        "slp_chapter6_11 = \"\"\"allocational harm--bad biases. We want to debias to get rid of representational harm. \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"Entailment in formal semantics--easily/mathematically understand and easy for computer to understand\n",
        "Knowledge must come from somewhere else though: people have to do this to get taxonomic structure\n",
        "Tokens are partitioned into senses--> forms lexical semantics\n",
        "Wordnet\n",
        "Vector space models:\n",
        "Words are represented as points in n-dimensional vector spaces and similar words end up in close proximity (same vector space)\n",
        "Data-driven\n",
        "Distributional hypothesis: as corpus (text/verbiage) grows, so does the probability that two similar words appear in the same environment\n",
        "Document similarity: \n",
        "Use vector space models and normalization to help find similar words/related words (using count)\n",
        "Can also use cosine distance\n",
        "Alternatives to count: transform vectors using TF-IDF and PPMI\n",
        "Term frequency*  inverse document frequency\n",
        "Co-occurrence: long and sparse vs learn vectors that are short and dense\n",
        "Language modeling: learn function that returns joint probability\n",
        "Difficulties:\n",
        "Curse of dimensionality (too much data)--> use chain rule\n",
        "Probability table: but this requires smoothing and back-off and doesn’t actually generalize\n",
        "Solution: neural language models: can establish similarity based on vocab-->vector representation; express joint probability function of a word sequence in terms of word vectors; learn params of function and word vectors simultaneously;\n",
        "Can generalize contexts given similar contexts\n",
        "Neural LMs\n",
        "Input = k-gram of words w_1:k*\n",
        "Output = probability distribution over next word\n",
        "Skip-gram algos\t\n",
        "Treat target word + neighboring context word as positive exes\n",
        "Randomly sample other words in lexicon to get negative samples\n",
        "Use logistic regression to train a classifier to distinguish two cases\n",
        "Use weights as embeddings\n",
        "Computing p(+|t,c):\n",
        "Dot product--model similarity\n",
        "Words are likely to appear near similar words\n",
        "For context words, assume independence--dot product, or get log of both to reduce the right side to a summation\n",
        "Training:\n",
        "Random words as negative examples\n",
        "Could pick according to unigram frequency--choose according to probability distribution\n",
        "Alpha param--noise word chosen according to unigram frequency\n",
        "Alpha = .75 words works well bc rare noise word have a slightly higher probability\n",
        "How to learn skip-gram embeddings:\n",
        "Start w/ random 300d vectors as initial embeddings and use logistic regression\n",
        "Take corpus and take pairs of words that co occur as positive examples\n",
        "Take pairs of words that don’t co occur as negative examples\n",
        "Train classifier to distinguish this by slowly adjusting embeddings to improve classifier performance\n",
        "Throw away classifier code, keep embeddings\n",
        "Properties of embeddings:\n",
        "Similarity depends on window size C\n",
        "Hogwarts +-2: locations magical like Hogwarts, also fictional\n",
        "Similar in type\n",
        "Hogwarts +-5: dumbledore, malfoy\n",
        "Topically related\n",
        "Solving analogies with embeddings\n",
        "Use vector arithmetic: a:a* as b:b*, b - a  + a*\n",
        "Train embeddings on old books to study changes in word meaning: diachronic word embeddings for studying language change\n",
        "Embeddings + bias:\n",
        "Embeddings reveal society biases\n",
        "Need to be evaluated--ethics: use debiasing algorithms\n",
        "Need some measure of cultural bias--interesting to evaluate this as well to study historical bias\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "092c0d2d-295e-4096-b65d-7d2402d5eb6d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\nLexical semantics: linguistic study of word meaning. Leammas and senses: meanings of a word and aspects of a meaning. Lemmas can be \npolysemous. Synonmy = words with the same meaning--propositional meaning satsifies truth conditoins. Priinciple of contrast: difference in linguistc form is assoficated with difference in meaning.\nWord similarity: similarity is categorization. Word relatedness = association and belong to same semantic field. Semantic frames and roles: denote perspectives or paritcipants in particular type of event. Connotation\nmeans sentiment.\n\n## SLP Chapter 6.2 Vector Semantics\nVector semantics: standrad way to rep word meaning in nLP and deifne the maning of word by distriution in lanugage. VEctors for representing words are called embeddings. In tf-idf model, meaning of a word is defined\nby a simple function .. Method results in long, sparse, mostly zero vectors. word2vec model for short dense vectors w/useful semantic properties. Cosine = way to use embedding to compute semantic similarity.\n\n## SLP Chapter 6.3 Words and Vectors\nTerm-dcoument matrix, each row rep word in vocab and is part of vector space model of info retrieval. Vector spac e= collection of vectors by dimension. Matrix useful for info retrieval.\n\n## SLP Chapter 6.4 Cosine for measuring similarity\nnormazlied dot prodcut = same as cosine of angle between two vectors.\n\n## SLP Chapter 6.8 Word2vec\ntl-idf weighting isthe product of two terms wtih term catching one of these two intutions: term frequency or document fequency\n\n## SLP Chapter 6.10 Semantic properties of embeddings\nsemantics of embedding: analogy/relational similarity; \n\n## SLP Chapter 6.11 Bias and Embeddings\nallocational harm--bad biases. We want to debias to get rid of representational harm. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\nLogistic Regression\nClassifier components:  Machine learning classifiers require a training corpus of M observations input/output pairs (x^i, y^i)\nFeature representation of input--vector of features\nClassification function: computes estimated class y via p(y|x)\nObjective function for learning, usually involving minimizing error on training examples (how good/bad is our classifier)\nAlgo for optimizing objective function\nSentiment classifier: take input, encode in some feature representation, and classifer output y can be 1 (positive sentiment) or 0 (negative sentiment)\nWant to estimate P(y=1|x)\nLogistic regression solves task by learning a vector of weights and a bias term\nGet feature element and multiply by weight to get dot product + bias term\nSigmoid function:\nProbability for 1 i shown below (probability for 0 is 1 - the below)\nDecision boundary: when to output 0 or 1?\n0.5 can be the decision boundary if P(y=1 | x) is more than .5, we say yes; else no\nExtracting features:\nCan count number of positive connotation + negative connotation words\nNegation words, pronouns\nAssign wieghts to each var\nComputing Z = get product of values and weight of each var\nLearning in logistic regression:\nGet weights of model by learning params (weights + bias) via learning using:\nobjective/loss function that tells us distance between system output and gold output. Cross-entropy loss used\nAlgo for optimizng objective function--use stochastic gradient descent to minimize loss function\nLoss Function\nDetermines how close a gold standard label item is to an output for a classifer\nLoss tells how much our prediction differs from the truth (mean square error)\nLoss function for probabilistic classification:\nPrefers class labels of the training example to be more likely\nConditional mximum likelihood estimation--choose params w, b that maximize the log probabilities of the true labels in the training data\nReseulting loss function is the negative log likelihood loss/cross entropy loss\nFor one observation x, maximize probability of the correct label \nChange this to log spacex\nResult is cross entropy loss\nMinimzing negative log probability--loss to be smaller if model’s estimate is close to correct and loss to be bigger if it’s more conufsed\nStochastic Gradient Descent:\nTheta is set of params in our model: weight vector and bias terms\nMinimizes cross-entropy loss across every example (ideally)\nGradient descent is a method that finds a min of a function by figuring out in which direction the function’s slope is rising the most steeply, and moving in the oppposite direction\nGlobal v local minimums:\nFor logistic regression, loss function is conveniently convex\nConvex function has one minmum so no local minima to get stuck in\nGradient descent starting from any point is guaranteed to find a min\nWeight at each timestep is going to be the weight at the previous time and step minus the learning rate\nFor each weight in vector, has own slope\nWhat is derivative with respect to our classifier in our current set of params\nSum the number of elements in our params\nGradient: cross entropy loss of weights of our prediction can be \nMini batch training: stochastic graind gdescent choose a random example\nAlternate is batch training, which computes the graident over entire dataset--> better eestimates but takes a long time to compute\nCommonly used compromise is mini-batch training, and train on a small batch and loss is accumulated\nRegularization:\nOverfitting can be a problem with many models\nIf feature only occurs in one class, attend with high weight\nRegularization is penalizing large weights\nSoftwMax: takes input vector and outputs a vector of values normalized into probabitlies\nNeural Network\nPerceptron: inputs go through activation function, and we generate a single improv\nSingle neuron is actually a whole network in layers--output, hidden, hidden, input, for example\nOutput of one layer--> intput into next layer\nIf weights set correctly, can approxmiate a huge range of possible functions\nIncoming arrows: inputs to neurons, and from outside too\nperceptron--<logistic regression\nFeed-forward neural network\nTraining neural nets: want to learn best params for neural net to make its predictions y as close as possible\nNeed: loss function, optimization algorithm, wat of computing graident the log brooch\nCross entry Loss-should be same in logistic.regression\nTo compute gradient: logistic regression as network w/one wieght layer and isgmoid output\nFound slope and took step in a downward protection\nComputation graphs: general procedue like backward differentiation\nDepends on notion on your computation graphs\nBackward differentiation: importance of computation graph comes from ackward pass and need to know weight update.\t\nHow to compute derivative of our output function L w/respect to the input\nBackwards differenciation using chain rule from calculus\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": "4ab79629-422c-4472-afa8-8d65146c2666"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nAgent assignts P(s) to each uncertain state. P(s'|s,a) is transition model. MEU formalizes the right thing an agent should do, but\nnot how to do it: need perception, learning, knowledge representation, inference. Performance measure gives score for history--sequence of states.\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\nConstraints on rational preferences: A > B = agent prefers A over B. A ~ B = agent is indifferent. A >- agent prefers A over B or is indifferent\nbetween them. A and B are sets of outcomes for each action as a lottery where the action is a ticket. L w/outcomes S1...Sn w/probabilities p1...pn is L = [p1, S1, ...pn, Sn].\nSix constraints that preference relations should obey: orderability (preference), transitivity, continuity (in the middle), substitutability (A and B and more complex lotteries where B\nis subbing A in one of them), monotonicity (lottery w/higher probability for A if A is preferred), decomposability (compound lotteries to simple) = axioms of utility theory. \n\n## AIMA Chapter 16.3 Utility Functions\nDecision theory is a normmative theory--describes how rational agent should act. Descriptive theory describes how agents actually act. Certainty effect-->people are\nattracted to certainty bc to reduce computation burden; distrust legitimacy of stated probabilities; accounting for emotinoal and financial state\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nMarkovian transitions are ones whose probability of reaching s' from s depeneds only on s and not history of earlier states. If decision problem is sequential, specify utility\nfunction by sequence of states and actions--the environment history. Reward = R(s, a, s') for s transition from s to s'. MDP: sequential decision problem for fully observable, stochastic env\nwith Markovian transition model and additive rewards (solvable using DP). Finite horizons mean fixed time N and game is over (nonstationary); infinite means the optimal action depends\nnly on current state and optimal policy is stationary. Lower discount rate values closer rewards. U(s) = expected reward for next transition plus discounted utility of the next state. Action-utility function \nor Q-function Q(s,a) is the expected utility of taking a givne action in a given state. Dynamic decision networks (DDN) are factored reps that have exponential complexity advantage over atomic reps and can\nmodel substantial real-world problems: state St is composed of 4 state vars: Xt w/2d location on grid + orientation; Xt rate of change of X; charging when robot is plugged in; battery.\n\n## AIMA Chapter 17.2 Algorithms for MDPs\nValue iteration, policy iteration, linear programming offer same solutions to MDP. Value iteration is iterative, and starts with initial vals for utilities, calculate RH side of equation, \nplug into LH side, updates U for every s from utility of neighbors until equilibrium. Contractions has one fixed point; if 2, wouldn't get closer. When function applied to arg, value must get closer\nto fixed point so repeated applicaton of a contraction always reaches the fixed point in the limit. Policy iteration: algo alternates between policy eval and policy improvment. Linear programming (LP) \ngood for formulating constraine doptimization problems; considers U(s) of each s and notes uilities for optimal policy are the highest utilites attainable consistent with Bellman. RTDP: good for moderate\ndomains like grid worlds.\n\n## Module 8 Lecture Notes\nMDP: nondeterministic search problems that are applicable in a fully observable task environment where we have to make a series of actions whose outcomes are nondeterministic\nDue to nondeterminism, single sequence of actions can’t always be the solution--one way of solving: expectimax: value + policy iteration w/Additive rewards + probabilistic transition function. Intro to MDP: Navigating an asteroid field where we have a fully observable grid world\nand we pick an action at each time step--game terminates when it reaches a goal state and environment is stochastic: when action is picked, its result is uncertain. 80% of up is up; 20% of up moves to right or left Stochastic transition model as a probability:\np(s’ | s, a): possible result state, current state, and action that gets to resulting state. The above reads as the probability of s’ given that we are in state sand we selected action a\nWe ignore sequence of steps so far to end up in this state--Markovian transitions because the probability of arriving in s’ only depends on s and not the history of earlier states. Rewards can be positive or negative, bounded by some max value; Environmental history scores have a total utility = sum of instantaneous rewards\nMDP formulation: Markov Decision Process: Sequential decision problem, Fully observable environment, Stochastic transition model, Additive rewards. Expectimax nodes: outcomes are uncertain. In expectimax search we calculate their expected utilities:\nProbabilities defined over arcs: average of utilities of the outcomes weighted by probabilities: MDP formal definition: set of states, set of actions, Transition function: T(s, a, s’), Reward function: R(s, a, s’) or sometimes just R(s) or R(s’), Initial state s_0, Optionally, one or more terminal states, Solution to MDP = policy\nPolicies and rewards: If we implement the same policy multiple times, this may lead to a different sequence of states and actions (environment history), and thus a different score under the reward function, so need to compute expected utility of all the possible paths generated by a policy\nDepending on reward amount, there could be a more optimal policy. Sequence of rewards: performance of an agent in an MDP is the sum of the rewards for the transitions it takes\nUtility function on an environment history: U_h([s0, a0, s1, a1,..., sn]). If the reward is positive, we can bounce around forever and avoid exits for infinite rewards!\nWe prefer rewards now versus later (bc the environment is stochastic and we may not get rewards later) But what if we want greater rewards in the future?\nDiscounting: values of rewards decay exponentially--every time we descend a level, we multiple in the discount once--Sooner rewards probably have higher utility than later rewards and helps algorithm coverage\nExponentiated gamma --> bound on value of future rewards: example 0.5: U([1, 2, 3]): 0.5^0*1 + 0.5^1*2 + 0.5^2*3 = 1 + 0.5*2 + 0.25*3 so that U([1, 2, 3]) < U([3, 2, 1])\nMDP Search Tree\nMDP state projects an expectimax-like search tree\nS --> a leads to more s’, a’...\n(s,a) state action pair is a q-state\n(s, a, s’) is a transition ==> T(s, a, s’) = P(s’ | s, a) R(s, a, s’)\nOptimal quantities: \nValue (utility) of a state s:\nV*(s) = expected utility starting in s and acting optimally\nValue (utility) of a q-state (s,a):\nQ*(s, a) = expected utility starting out having taken action a from state s and thereafter acting optimally\nThe optimal policy:\npi*(s) = optimal action from state s\nValues of states:\nFundamental operation: compute the expectimax value of a state\nExpected utility under optimal action\nAverage sum of discounted rewards\nRecursive definition of value:\nBellman = Q* is sum of T()[R(s, a, s’) + yV*(s’)]\nRacing search tree:\nRecursion can have high branching factors--we don’t need to do that much expectimax\nProblem: states are repeated so to solve that, we only compute needed quantities once\nProblem: tree goes on forever\nIdea: do depth-limited computation, but with increasing depths until change is small\nDeep parts of the tree don’t matter if y < 1\nValue iteration: \nStarting with V0(s) = 0: no time steps left means an expected reward sum of zero\nGiven vector of V_k(s) state values, do one ply of expectimax from each state\nRepeat until convergence\nComplexity of each iteration: O(A * S^2)\nTheorem: will converge to unique optimal values\nBasic idea: approximations get refined towards optimal values\nPolicy may converge long before values do\nV_{k+1}(s) = max_a Q*(s,a)\n        Then update values: V*(s) = V_{k+1}(s)\nQ*(s,a) = Σ_s' T(s,a,s') [R(s,a,s') + γ V*(s')]\nPolicy evaluation: \nUtilities for a fixed policy:\nCompute utility of a state s under a fixed (generally non-optimal) policy\nDefine the utility of a state s, under a fixed policy pi\nV^pi(s) = expected total discounted rewards starting in s and following pi\nCalculating V’s for a fixed policy pi:\nTurn recursive bellman equations into updates\nEfficiency: O(S^2) per iteration\nLinear system without the maxes \nPolicy iteration:\t\nProblem with value iteration: asymptotic and max at each state rarely changes\nApproach for optimal values:\nPolicy evaluation: calculate utilities for some fixed policy (not optimal utilities) until convergence\nPolicy improvement: update policy using one-step look-ahead with resulting converged but not optimal utilities as future values\nRepeat until policy converges\nPolicy iteration is optimal and converges faster under some conditions\nStep 1 (policy evaluation): for fixed current policy pi, find values with policy evaluation:\nIterate until values converge\nStep 2 (policy improvement): for fixed values, get a better policy using policy extraction \nOne step look ahead\nValue iteration vs policy iteration:\t\nValue iteration: \nEvery iteration updates both values and policy\nDoesn’t track policy, but takes max over actions implicitly recomputes it\nPolicy iteration:\nDo several passes that update utilities w/fixed policy (each pass is fast bc we consider only one action, not all of them)\nAfter policy is evaluated, a new policy is chosen\nNew policy will be better, or we’re done\nTo compute optimal values: value iteration or policy terationi\nCompute values for a particular policy: policy evaluation\nTurn values to policy: policy extraction (one-step lookahead)\nMaximum expected utility:\nPrinciple of MEU: rational agent should choose the action that maximizes its expected utility, given its knowledge\nFor worst-case minimax reasoning, terminal function scale doesn’t matter\nBetter states to have higher evaluations--> insensitivity to monotonic transformations (average case reasoning)\nFor average-case expectimax reasoning, we need magnitudes to be meaningful\nUtilities are functions from outcomes (states of the world) to real numbers that describe an agent’s performance\nUtilities summarize the agent's goals\nTheorem: any rational preferences can be summarized as a utility function\nWe hard-wire utilities and let behaviors emerge\nPreferences:\nAgent must have preferences among:\nPrizes (A, B, etc)\nLotteries: situations with uncertain prizes\nL= [p, A; (1-p), B] \nNotation:\nPreference: A > B\nIndifference: A ~ B\nFulfills axiom of transitivity\n\n\n\n## Module 8 Definitions\n* **Utility function** - U(s) assigns single number indicating desirability of state\n* **Expected utility** - average utility value of outcomes weighted by probability that outcome occurs\n* **Meu** - rational agent should choose aaction that maximize's agent's EU\n* **Existence of utility function** - agent's preferences obey axioms of utility and U(A) > U(B) iff A > B; U(A) = U(B) iff A ~ B.\n* **Expected utility of a lottery** - utility of lottery is sum of probability of each outocme x utility of that outcome\n* **Value function** - ordinal utlity function/preference ranking on states w/o need for nums\n* **Preference elicitation** - presents choices to human and uses observed preferences to pin utility function\n* **Normalized utilites** - 0,1 scale\n* **Monotonicity** - where more is better\n* **Certainty equivalent** - value in lieu of a lottery\n* **Insurance premium** - differenc ebetween EMV of lottery and certainty equivalent\n* **Risk neutral** - linear curve\n* **Optimizer's curse** - estimated expected tuility of best choice = too high\n* **Framing effect** - wording of decision problem impacting agent's choice\n* **Anchoring effect** - idea of something being relatively cheap\n* **Policy** - solution that specifies what agent does for any state it can reach (optimal = highest expected utility)\n* **Proper policy** - solution that is guaranteed to reach a terminal state\n* **Contraction** - function of one arg when applied to two diff inputs, produces 22 output vals that are close together than original inputs\n* **Asynchronous policy iteration** - given certian conditions, async policy iteration is guaranteed to converge to an optimal policy\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nExploitation vs exploration decision. Bandit problem: each arm M is a Markov reward process w/one possible action a (has states, TM, reward). Overall bandit problem \nis MDP--state space is given by Cartesian product, actions a. Gittens index: simple optimal policy for bandit: pull arm whighest Gittins index and update Gittins indices. Bernoulli bandit\nhas each arm M produce reward of 0/1 w/fixed but unknown probability\n\n## AIMA Chapter 22.1 Learning from Rewards\nWin/loss rewards are sparse for chess and racing, while tennis and cricket are the opposite. Intermediate rewards help the agent\nlearn. In model-based RL the agent uses a transition model of the environment to help interpret the reward signals and make decisions about how to act. The model may be initially unknown, \nin which case the agent learns the model from observations. Model-based reinforcement learning systems often learn a utility function in terms of the sum of rewards from state onward.\nIn model-free RL, the agent neither knows nor learns a transition model for the environment--it learns either action-utility learning (Q-learning/do something in state s based on highest Q-value) \nor policy search (policy that maps from states to actions). Passive RL--policy is fixed and learn U(s) and is blind. Active RL--agent must figure out what to do--must explore.\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nPassive reinforcement learning: policy is fixed and learn U(s) starting in state s--similar to policy evaluation, but we don't know reward or transition functions. Agent executes\nset of trials using policy pi. U(s) determined by the reward and the expected utility of the successor states. Ignores connections between states. Modified policy iteration: simplified value iteration\nprocess to update utility estimates after each change to learned model. A prioritized sweeping heuristic makes adjustments to states whose likely successors who have had huge changes in utility. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nActive RL allows agents to choose the action they take--agent learns complete transition model w/outcome probabilities for all actions. Agent is greedy and will make whatever it thinks is\nthe best move. Will make tradeoffs between exploitation and exploration. Temporal difference q-learning avoids learning models--instead, it learns an action-utility function Q(s, a) instead of a utility function.\nTD Q-learning agent does not use a transition model for learning or action selection--it's off-policy learning. SARSA is on-policy. \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nReward shaping and pseudorewrds to speed up training--potential downfall to maximize on those and not goal rewards. Hierarchical reinforcement learning breaks up long action seqeunces into \nsmaller pieces until they are short enough to make learning easy (soccer and keepaway). Partial programs outline hierarchical structure for agent's behavior, which we use in learning--agent can choose any action from \nspecified set. HRL based on concept of joint state space where state (s, m) for physical and machine states. Sovles Markovian decision problem w/choice states of joint\nstate space; actions according to the partial program; reward function = expected sum of rewards for all physical transitions occurring between the choice states; transition model. \n\n## Module 9 Lecture Notes\nImportant ideas in reinforcement learning: exploration: try unknown actions to get information; xploitation: eventually, using what you know\nregret: even if you learn intelligently, you make mistakes;sampling: bc of chance, you must try things iteratively;difficulty: learning can be harder than solving a known MDP\nIntro to reinforcement learning II:\nBasic idea:\nAgent who is always acting w/set of available actions\nReceives feedback in the form of rewards\nUtility defined by reward function\nMust act so as to maximize expected rewards\nAll learning based on observed samples of outcomes\nStill governed by MDP:\nProcess contains:\nSet of states s in S\nSet of actions per state A\nModel T(s, a, s’)\nReward function R(s, a, s’)\nStill looking for a policy pi\nTwist: we don’t know T or R\nMust try actions to figure these out\nThis is online learning (vs MDP being offline learning)\nWe can’t compute things in our head and we don’t know much in advance\nModel-based learning:\nLearn an approximate model based on experiences\nSolve for values as if the learned model was correct\nStep 1: learn empirical MDP model\nCount outcomes s’ for each s, a\nNormalize to get an estimate of the transition model\nDiscover each reward function for each (s, a, s’)\nStep 2: solve the learned MDP\nCan use value iteration, for example, to get the best policy\nPassive Reinforcement Learning\nModel-free learning\nOnce an action is taken, we compare our expected results with the actual ones\nPassive reinforcement learning: letting someone else choose the policy for us and we evaluate the reward\nSimplified task: policy evaluation\nInput: a fixed policy\nGoal is to learn the state values given unknown transitions and rewards\nIn this case, the learner is along for the ride and they don’t get to choose their actions\nDirect evaluation\nGoal: compute values for each state under pi policy\nIdeal: average together observed sample values\nAct accordingly to pi policy\nRecord sum of discounted rewards for each state\nAverage samples \nPros and cons:\nPros: easy to understand, no knowledge of T, R required, eventually computes the correct average values using only sample transitions\nCons: wastes information about state connections, each state must be learned separately--> takes a long time to learn\nCannot use policy evaluation bc we need T and R to do it\nImprove estimate of V by providing by computing averages\nTake samples of outcomes s’ by doing the action and average\nTemporal difference learning\nBig difference: learn from every experience -- update V(s) every time we experience a transition (s, a, s’, r)\nLikely outcomes s’ will contribute updates more often\nTemporal difference learning of values\nPolicy fixed, still doing evaluation\nMove values toward value of whatever successor occurs: running average\nSample of V(s): sample = R(s, pi(s), s’ + yV^pi(s’)\nUpdate to V(s): (1-alpha)V^pi(s) + (alpha)sample OR V^pi(s) + alpha(sample - V^pi(s))\nTemporal difference learning bc we are comparing current estimates against a value we’re actually sampling\nExponential moving average\nMore recent samples are more important, as 1 - alpha term exponentially decays\nDecreasing learning rate (alpha) can give converging averages\nForgets about the past (distant past values were wrong anyway, so this is good)\nProblems with TD value learning\nTD value learning is model-free way to do policy evaluation, mimikcing bellman updates w/running sample averages\nIf we want to turn values into a new policy, we’re sunk bc we need to learn Q-values directly, not values themselves in order to have action selection be model-freeas well\nActive reinforcement Learning (Q-learning)\nFull reinforcement learning: optimal polices (like value iteration)\nDon’t know T or S, but we choose the actions now\nGoal: learn the optimal policy/values\nIn this case: the learner makes the choices\nExploration vs exploitation\nNOT offline planning, as we take actions in the world and find out what happens\nDetour: Q-value iteration\nValue iteration: find successive depth-limited values up to k + 1 values for all states given Vk:\nWe are going to use Q-values instead, so that the best policy is directly observable from those Q-values\nThus, given Qk, we calculate the depth k + 1 q-values for all q-states\nMove expectimax to the Q-value of the Qk+1 function\nQ-learning: sample-based Q-value iteration\nMust take a lot of samples in order to gain certainty about the transition function and reward function\nLearn Q(s, a) values as you go\nReceive a sample (s, a, s’, r)\nConsider old estimate Q(s, a)\nConsider your new sample estimate = R(s, a, s’) + ymaxQ(s’, a’)\nIncorporate the new estimate into a running average: Q(s, a) <-- (1-alpha)*Q(s, a) + alpha[sample]\nAs alpha gets closer to 1, we put more weight on the sample, and as alpha gets closer to 0, we put more weight on our previous estimates\nWe are able to update values as we go and our estimates for a particular Q-state improve\nEven though we don’t know the correct Q-values intially, we converge to the optimal policy\nQ-learning properties:\nConverges to optimal policy even when acting suboptimally--> off-policy learning\nCaveats: \nHave to explore enough\nHave to eventually make the learning rate small enough, but not decrease it too quickly\nIn the limit, it doesn’t matter how you select actions\nCan tweak learning rate to trust previous history more than recent history\nExploration vs exploitation: \nExploration: have to try new things + make some mistakes\nForcing exploration:\nSimplest: random actions (e-greedy)\nEvery time step, flip a coin\nw/small probability e, act randomly\nw/large probability 1 - e, act on current policy\nProblems with random actions? \nKeeps trhashing once learning is done\nSolution: lower e over time, or exploration functions\nWhen to explore? (exploration function addresses this)\nRandom actions: explore a fixed amount or\nExplore ares whose badness is not established yet, eventually stop exploring-->xplore areas of uncertainty, be optimistic \nExploration function:\nTakes value estimate u and visit count n and returns an optimistic utility f(u, n) = u + k/n\nModified q-update: plugin exploration function instead of normal maxQ(s’, a’) function\nRegret:\nEvent if learn the optimal policy, you still make mistakes along the way\nMeasures total mistake cost: difference between your expected rewards, including youthful suboptimality, and optimal (expected) rewards\nMinimizing regret goes beyond learning to be optimal--requires optimally learning to be optimal\nEx: random exploration and exploration functions both end up optimal, but random exploration has higher regret\nApproximate Q-learning:\nGeneralizing across states:\nBasic q-learning keps a table of all q-values\nIn realistic scenarios, we can’t learn about every single state\nToo many states to visit in training + hold the q-tables in memory\nNeed to generalize:\nLearn about small number of training states from experience\nGeneralize experience to new, similar situations\nFundamental idea in ML\nFlashback: eval functions\nScore non-terminals in depth-limited search\nIdeal function: returns actual minimax value of position\nIn practice: typically weighted linear sum of features\nEx: f1(s) = num white queens - num black queens\nLinear value functions\nCan write q function for any state using weights + feature representation\nAdvantage: experience summed up in a few powerful nums\nDisadvantage: states may share features but be different in value\nApproximate q-learning\nTransition = (s, a, r, s’)\nDifference = [r + ymaxQ(s’, a’)] - Q(s, a)\nWhat we thought we would get - what we actually get\nExact Q’s: Q(s, a) <-- Q(s, a) + alpha[difference]\nApproximate Q’s: wi<-- wi + alpha[difference] fi(s, a)\nUpdate weight in linear function if feature value is active\nIntuitively:\nAdjust weights of active features\nE.g. if something bad happens, blame features that were on and disprefer all states w/that state’s features\nFormal justification: online least squares\n\n\n## Module 9 Definitions\n* **Reinforcement learning** - agent interacts w/world and receives periodic rewards\n* **Direct utility estimation (reward to-go)** - U(s) = expected total reward from that state onward; each trial provides sample of this quantity for each state visited to maintain running avg\n* **Adaptive dynamic programming** - uses constraints among each U(s) by learning the transition model that connects them and solving the corresponding MDP using DP\n* **Pseudoexperience** - created by simulating current transition model\n* **Glie** - “greedy in the limit of infinite exploration\n* **Additive decomposition** - sum of rewards over time\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nActing under uncertainty: need to keep track of belief state--represents setof all possible worlds. Drawbacks are that agent\nmust consider every possible explanation fro sensor observations; correct contingent plan can grow too large and considers unlikely contingencies\nas welll; no plan guaranteed to achieve goal but agent must act--need way to compare merits of plans that are not guaranteed. Qualification problem: weak conclusions\nwhen can be simplified. Right thing to do--rational decision--depends on relative importance of various goals and likelihood and degree to which they will achieved. To use\nonly logic  hard when diagnosing: laziness, theoretical ignorance, practical ignorance. Agent knowledge can only provide degree of belief. Theory of probability\nprovides a way of summarizing the uncertainty that comes from our laziness and ignorance--solves qualification problem. Agent must have preferences amongst outcom--use utility theory to reason \nquantitatively. Decision theory = prob theory + utility theory.\n\n## AIMA Chapter 12.2 Basic Probability Notation\nSample space: set of all possible worlds--they are mutually exclusive and exhaustive. Cannot both be the case and one possible world must be the case. Fully specified\nprobability model associates a numerical probability P(w) w/each possible world. In prob theory, sets are events, and in logic, set of world correspond to a proposition in a formal language.\nFactored representation: possible world rep by a set of variable/value pairs. Structured representation is more expression. Random vars are vars in probability theory--functio that maps from domain\nof possible world to some range (possible values it can take on).\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nInference using full join distributions: probabilistic inference = computation of posterior probabilities for query propositionis given observer evidence.\n\n## AIMA Chapter 12.4 Independence\nINndependence: marginal vs absolute.\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\nBayes = P(b|a) = P(a|b)P(b)/P(a); P(effect | cause) = causal vs P(cause | effect) diagnostic (more fragile than causal).\n\n## AIMA Chapter 12.6 Naive Bayes Models\nNaive Bayes = used in cases where effect variables are not strictly indpeendent. \n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\nspeech recognition--example of noisy, ambiguous input that requires probabiliteies to distinguish. Also used in spell correct and grammar verifiction. Probabilities\nare important augmentative and alternative communication systems. Language models are models that assign probabilties to sequences of words. An n-gram is a sequence of words. Relative frequency is the ratio of the n-gram probability\nto the observed frequency of a particular sequence by the observed frequency of a prefix.\n\n## SLP Chapter 3.2 Evaluating Language Models\nEval LMs through extrinsic evaluation--know if a particular improvement in a component is going to help the task at hand--embed in applicatino and measure application \nimprovement. Instrinsic evaluation is one that measures the quality of a model independent of any application: need training set/corpus, test set. Models fit such test sets if model assigns a higher probability \nto the test set--it more accurately predicts the test set. Given 2 probabilistic models, better model has a tighter fit to tset data. Training on test set introduces bias tha makes all prob look too hig and causes inccuracies in\nperplexity (inverse probability of the test set, normalized by number of words).\n\n## SLP Chapter 3.3 Sampling sentences from a language model\nsampling sentences from a lanugage model: choose random points according to their likelihood. \n\n## SLP Chapter 3.4 Generalization and Zeros\nGeneralization and zeros: use training corpus when building n-gram models in a similar genre as to what we're doing. Need it in an appropriate dialect/variety \nrelated to our LM. Still can encounter sparsity in a closed vocabulary bc corpus is limited. Zeros: things that don't occur in training set but are in test set. Unknown words/OOV words are words we have never seen before. \nOOV rate is percentage of OOV words that appear in test set--open vocab system is one where we model these potential unknown words in the test set by adding a pseudo-word called UNK. Can train probabilites of the UNK by turning problem back\ninto closed vocab one and choosing a fixed vocab in advance: 1) choose vocab 2) convert training set any word not in set to UNK 3) estimate probabilities for UNK; can instead replace words in training data by UNK based \non frequency.\n\n## SLP Chapter 3.5 Smoothing\nSmoothing/discounting is shaving off a bit of probability mass for more freuqent events. Laplace smoothing: add one to all n-gram counts\nbefore normalizing them into probabiltiies--practical for text classificationn. Add k-smoothing is adding a fractional count k--we choose k by optimizing\non a devset. Backoff + interpolation uses the trigram if the evidence is sufficient--otherwise use bigram, else unigram. Go to lower-order n-gram iif there is 0 evidence for higher-order n-gram. \nInterpolation mixes probability estimates from all n-gram estimators, weighing and combining 3-2-1gram counts\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nstupid backoff: doesnt discount higher-order prbabilities--just backoff to a lower order ng-ram if higher-order n-gram has a zero count. Doesn't produce a prob distribution.\n\n## Module 10 Lecture Notes\nReview of Probabilities:\nGeneral situation:\nTwo components: observed variables (evidence) and unobserved variables (states)\nUnderlying that, probabilities are attributed to these variables (model)\nProbabilistic reasoning gives us a framework for managing our beliefs and knowledge\nProbabilities are about possible worlds--quantifies how likely a world is\nPossible worlds = sample space and are mutually exclusive and exhaustive\nFully specified probability model associates a probability P(w) w/each possible world w\nRandom variables: important in probability model\nSome aspect of world for which we can have uncertainty\nDenote random vars w/capital letters\nAxioms of probability:\nProbability of any world is between 0 and 1 for every world w (inclusive\nTotally probability of the set of all possible worlds is 1\nDistributions\nUnobserved random vars have distributions\nDistribution: table of probabilities of values\nProbability (lower case value) is a single number\nJoint probability distributsion:\nOver sets of random variables x_1, ..., x_n\nSpecifies real number for each assignment, or outcome\np(X1 = x1, ..., Xn = xn)\nSize of joint distribution if n variables w/domain sizes d? D to the power of n\nFor all but smallest distributions, impractical to write out--should be a very large table\nCan make this more manageable by making assumptions about independence to reduce size of tables to a bunch of smaller tables\nProbabilistic model: joint distribution over a set of random variables\nContains: random vars with domains, assignments are called outcomes, joint distributions (whether outcomes are likely)\nDomains are set of values that a variable can take out\nSum of assignments sum to one\nOnly certain variables directly interact w/each other--independence is common\nEvents: event is a set E of outcomes\n\nCan sum these values together (ORs and ANDs)\nEvents are usually partial assignments (like P(T=hot) vs P(T=hot, S=sunny)\nMarginal distributions\nSubtables that eliminate variables that we don’t care about atm\nMarginalization: summing out by combining collapsed rows by adding\nConditional probabilities: simple relation between joint and conditional\nTells us what we didn’t get to measure \nGive joint probability distribution, we need to get more info about one of the variables and its outcome\nConditional distribution: probability distributions over some vars given fixed values of others \nExtracted from joint distribution\nProbabilistic Inference and Rules\nCompute desired probability from other known probabilities (eg conditional from joint)\nGenerally compute conditional probabilities, which represent the agent’s beliefs given the evidence\nProbabilities change w/new evidence: new evidence causes beliefs to update \nA method: inference by enumeration:\nSplit variables into three: evidence variables (things we have observed), query variables (outcomes we want to reason about), hidden variables (vars we are not observing/actively reasoning about)\n3 steps:\nCan write probability distribution for query variables after separating all variables\nTake big joint probability and select entries consistent with evidence\nSum out H to get joint of query and evidence\nNormalize by summing over all Q, which will give us the Z term/denominator\nA method: the product rule\nGiven subtables/conditional probability--> construct big joint probability table\nReverse of inference by enumeration\nThe chain rule\nProduct rule to more than two vars--joint distribution as increment product of conditional distributions\nBayes’ rule: two diff ways to factor a joint distribution over two variables\nLets us build one conditional from its reverse\nFoundation of many systems--often one conditoinal is trickier to derive than the other\nProbabilistic Language Models\nProbabilistic model: take each word positions as discrete, random var where the possible outcomes is the set of all vocab in the English dictionary\nGiven a few observations, estimate probability distribution over all assignments of words in the English dictionary\nOne goal: assign probability to a sentence\nAutocomplete for texting\nMachine translation: input sentence in one languagae and translate to other\t\nBayes: probability of english given foreign and probability of english\nSpell check\nSpeech recognition\nGoals: compute probability fo a sentence or sequence of words\nRelated task: probability of an upcoming word (autcomplete)--> language model (LM)\nLanguage model: P(W) or P(wn|w1, w2...wn-1)\nEx: computing probability of a sentence/sequence of words\nW/sentence of n words in length, each of n words are going to correspond to a random var, so what is the probability that the sentence exists in the english language?\nComputing P(W): use chain rule (sort of transitive in a way)--> need probability esimate for each component of the probability\nMaximum likelihood estimation: counting up probabilities for conditional / probability for more general part\nNever have enough data to estimate whole sentence\nSimplifying assumption: Markov assumption\nLimit history and only let previous k number of environment history/observations to make more accurate estimations\nAmount of history taken into account defines the model\nPredictably, unigram models are nonsensical--> as we increase to n-grams, text becomes useful\n\n\n## Module 10 Definitions\n* **Ontological commitment** - world is composed of facts that do not hold in any particular case\n* **Epistemological commitements** - logical agent believes each sentence to be true/false/no opinion, whereas prob agent might have numerical degree belief\n* **Prob density function** - probability that rnaod var takes on some x as parameterized function of x\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\nBayesian networks can represent depenedencies among variables + any full joint prob distribution--directed graph in which\neach node is annotated w/quantitative prob info: 1) each node corresponds to a random var, discrete or continuous 2)directed links/arrows connect pairs of nodes and the graph\nis a DAG 3) each node has associated probabiltiy info that quantifies effect of parents on the node using finite num of params. Local probability info attached to each node is in the form \nof a conditional probability table (discrete)--each row contains conditional prob of each node value for a conditioning case. Probs summarize a potentially infinite set of circumstances\nin which something happens==a small agent can cope w/large world. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nBayesian netowrk is correpct rep of domain if each node is conditionally independent of its other predeecssors in the in the node ordering, given its parents. Methodology:\nnodes = set of variables required to model the domain; links = for i in range n choose minimal set of parents, insert link from parent to Xi for each parent, CPTs write down DPT for P(Xi|Parents(Xi)). \nCompactness of Bayesian networks is an example of general property of locally structured/sparse systems--grows linearly, not exponentially. Each variable is conditionally independent of its\nnon-descendants, given its parents; variable is conditionally independent if all other nodes in the network, given parents, children, and children's parents--give Markov blanket (allows for local\nand distributed stochastic sampling processes). check for d-seapration by 1) consdiering ancestral subgraph XYZ and ancestors 2) add links between any unlinked pair of nodes that share a common child to get\nmoral graph 3) replace all directed links by undirected links 4) if Z blocks all paths between X and Y in resulting graph, Z d-separates X and Y such that X is conditionally indepnedent of Y given Z. Else, original\nBayes net does not require conditional independence. Bayes net can include hidden vars that are essential for structuring network\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\ntask for any probabilistic inference system is to compute psoterior proabbility distribution for set of query vars given an observed event (assignment of values to a set of evidece vars.\nA query can be answered using Bayes net by computing sums of products of conditional probabilities  from the network. Variable elimination evaluates expressions in right to left/bottom up order and \nintermediate results are stored w/summations over each variable done for portions of expression that depend on the variable. Time + space complexity fo exact inference in polytrees is linear in the size of the network.\nFor multiply connected netowkrs (insurance), variable elimination can have exponential complexity since it includes inference in propositoinal logic as a special case--thus NP hard. Clustering algos like join tree algo can reduce\ntime of Bayes net to O(n).\n\n## Module 11 Lecture Notes\nReview of Independence\nFor two random vars x and y are independent if joint probability of x and y is equal to the marginal probabilities of x and y\nConditional probability: x and y are independent given Z--ex: alarm, fire, smoke\nAbsolute independence is rare--doesn’t help us make inferences about other variables\nConditional independence is our most basic and robust form of knowledge about uncertain envrionments\nBayes Net Assumptions\nAssumptions needed to define Bayes net given graph: Probability of xi | only conditional on its parents\nBeyond the chain rule--> Bayes net conditional independence assumptinos\nAdditional conditional independences\nCan be read off the graph\nImportant for modeling: understand assumptions made when choosing a Bayes net graph\nTool for us to model the world\nD-separation (descendants): outline\nAlgo to determine independence between variables\nCausal chain:\nLow pressure--> rain--> traffic such that P(x, y, z) = P(x)P(y|x)P(z|y)\nNo guarantee that X is independent of Z\nCan guarantee X is independent of Z given Y\nCommon cause:\n \nX not independent of Z\n\nCommon effect: \n\nReachability and Paths:\nGiven bayes net graph, are two variables in BN independent? (given evidenc)\nSolution: analyze the graph\nAny complex example can be broken into repetitions of the three canonical cases\nReachability:\nRecipe: shade evidence nodes, look for paths in the resulting graph\nAttempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent--> doesn’t work\nPath is active if each triple is active:\nCausal chain A-->B-->C where B is unobserved\nCommon cause A<--B-->C where B is unobserved\nCommon effect\nAll it takes to block a path is a single inactive segment\nD-separation algorithm:\nQuery: all undirected paths from i to j and check if all triples are inactive--this would be independent, otherwise it’ll not be independent\ninactive so independence is guaranteed\nactive path so no guarantee to be independent\nactive and not guaranteed independence\nInference\nCalculating some userful quantity from a joint probability distribution\nGiven query Q and evidence variables observed, what is the probability of the assignments?\nInference by enumeration\nGeneral case: we want probability of query variable given all observed vairables\nSelect all entries consistent with evidence-->sum out H to get joint of query and evidence---> normalize\nInference by enumeration in Bayes’ Net\nGiven unlimited time, inference in BNs is easy\nReminder of inference by enumeration by example:\nBut takes too long: destroyed our Bayes simplified summation\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\nImprovement in learning depends on component to be improved, prior knowledgethe agent has, and data + feedback on that data.\ncomponents of agents are direct mapping from condition on curr state to actions; means to infer relevant properties ofthe world from percept sequence; \ninfo about way the world evolves and about the results of possible actions agent can take; utility info indicating desirability of actions;\ngoals that describe most desirable states; problem generator, critic, learning el that enable the system to improve. Three types of feedback: supervised learnin, agent observes\ninput-output pairs and learns a function that maps from input to output--inputs could be camera images, each accompanied by output/label; unsupervised learning is when agent\nlearns patterns in input w/o explicit feedback (clustering as an example--detecting maybe useful clusters of input examples); reinforcement learning is when agent \nlearns from series of reinforcements--rewards and punishments.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nSupervised learning is given a training set of N example input-output pairs where each pair was generated by a function f(x), discover functoin h that approximates true function f; h is \nhyptohesis about hte world drawn from hypothesis space. h can be called a model of the data drawn from model class H and output y = ground truth (true answer asking model to predict).Choose hypothesis space by\nperforming exporatory data analysis and choose good hypthesis by hoping for a consistent hypothesis--h such taht each xi in training set has h(xi) = yi. Look for best-fit function for which each h(x) is close to y. h generalizes well if it predicts\noutput of test set. Bias is tendency of a predictive hypothesis to deviate from expected value when average voer diff training sets. hypothesis underfitting when it fails to find a pattern in the data; overfitting \niis when it pays too much attention to the particular data set it's trained on.  Bias-variance tradeoff is a choice between more complex, low-bias hypotheses that fit training data well and simpler, lower-variance hypotheses that may generalize better.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nDecision tree = rep of a function that maps a vector of attribute values to a single output value--decision. REaches decision by performing a sequence of tets from root until a leaf is reached. Simplistic values and outputs are true or \nfalse (boolean classification, pos/neg). Four cases when considring recursive subproblems 1) if remaining examples are all pos/neg, done 2) some post + neg, choose best attribute to split them 3) no examples left means\nno example has been observed for this combination of attibute values and we return the most common output value from the set of examples that were used in constructing parent node 4) no attributes left but some pos + neg examples mean examples \nhave same description but different classification; error/noise in data/domain is nondeterminstic/can't observe an attr that would distinguish examples. Decision tree pruning combats overfitting. \n\n## AIMA Chapter 5.5 Stochastic Games\nStationarity assumption: given example E that has same prior probability distribution and is indpenedent of previous exampes, examples that\nsatisfy this are independent + identically distributed. Optimal fit is hypothesis that minimizes error rate. Need three data sets: training set to train, validation set to eval models and choose best, test set to do final unbiased eval of best model.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nComoputational learning theory: any hypothesis is seriously will will be found out with hgh probability after a small num of examples. Hypothesis that is consistent w/larget set of training eamples \nis unlikley to be wrong--probably approx correct (PAC). PAC learning applys to a new hypothesis space-decision lists.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nlinear functions of continuous-valued inputs--> linear regression.  Find values of weights to minimize empirical loss to fit a line in data. Many forms of learning involve adjusting weights to minimize loss--> use weight space.\nDecision boundary is line that separates two classes-linear decision boundary = linear separator and data that admit a spearator are called linearly separable.\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\nMultinomial naive Bayes classifier makes naive assumption about how features interact. TExt doc as bag of words; Bayesian inference breaks down conditional probability into other probabilities. Naive Bayes is a generative model--makes\nimplicit assumption about how a doc is generated. Most probable class by returning the highest product of two probabilities: prior probability of the class P(c) and likelihood ofthe doc P(d|c))\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\nSolution for unkown words is to ignore them--also ignore stop words\n\n## Module 12 Lecture Notes\nPrevious focus on models for optimal decision: now we focus on how to acquire a model from data/experience\nLearning params, structs, hidden concepts\nEx for text example: pam/ham binary classification for text input\nSomeone has to label the features of spam, including caps, dollar signs\nEx for digit recognition (digital imaging):\nGiven some images labeled with digits, we want to predict future labeling on images\nEx for other classification tasks: automatic grading, medical diagnoses, fraud detection\nWhat structure for BN and how to learn params for model-based learning?\nNaive Bayes\nNaive bayes for digits:\nAll feats are independent of the label\nSimple digit recognition version:\nFor each feature, the label causes that feature to be active or inactive\nOne feature var for each grid position\nInput maps to feature vector\nCan be binary valued\nEvery feature is conditionally independent of every other feature given the class label\nWe can easily find the probability of a feature given a particular label\nGeneral naive Bayes model: joint probability of a vector of features given a class label is the probability of a label times the product of all the probabilities of a particular feature given that label\nNumber of params is linear in number of features\nOnly have to specify how each feature depends on the class\nModel simplistic but works anyways\nGeneral naive bayes requires:\nInference method: need P(Y) and P(Fi|Y) tables\nEstimates of local conditional probabilities table\nNaive Bayes for text:\nWhat is the probability of piazza in a spam email?\nProbability of word at position i (vs not being the ith word in the dictionary)\nBag of words bayes:\nFeatures are conditionally independent given email\nModel is insensitive to word ordering/reordering\nGiven labeled instances, we have a training set, held out set, test set\nTraining: how to estimate params\nHeld out: how to estimate hyperparms of model\nTest: determine how well system is doing\nCan never peek at the test set!!\nEval: accuracy is the fraction of instances predicted correctly\nOverfitting and generalization: we want a classifier which does well on test data\nOverfitting: fitting data closely, not generalizing well\nOverfitting: probs(2) given “3.” example\nFits 2 better than 3 because of the period\nGeneralization and overfitting:\nRelative frequency params will overfit training data\nJust bc we don’t see 3 (example) during training doesn't mean it doesn’t happen at test time\nNeed to smooth/regularize estimates\nEx: red + blue jelly bean jar\nFor each outcome x, look at the empirical rate of that value too\nEstimate that maximizes likelihood of the data\nWhat is the likelihood of seeing our training data \nLaplace smoothing:\nReserves estimates for never seen before events\nP_ML(x) = <2/3, 1/3>\nP_LAP(X) = <3/5, 2/5>\nPretend we see every outcome once more than you actually did\nNever assigns a zero probability to anything\nWe can extend this by saying we saw every outcome an extra k times\nK = hyperparm (external)\nK is the strength of the prior\nK = 0 means that ML\nP_LAP,0(X) = same as ML\nP_LAP,1(X) = same as LAP\nP_LAP,100(X) = <102/203, 101/203>\nEstimation: linear interpolation\t\nGet empirical P(X) from data\nMakes sure the estimate of P(X|Y) isn’t too different from the empirical P(X)\nPLIN(x|y) = alphaP(x|y) + (1 - alpha)P(x)\nTuning on held-out data\nUnknowns: params (probabilities of P(X|Y), P(Y)), hyperparams (e.g. type of smoothing)\nLearn params from training data\nLearn hyperparams on different data (held-out data)\nTrain and test on the held-out data\nChoose best value and final test on test data\nBaseline\nSimplest thing to get results on a particular task\nLower bound on task difficulty\nWeak baseline: most frequent label classifier\nGives all test instances whatever label was most common in the training set\nStrong baseline: previous work -- often used in real research\nConfidence (of a model)\nProbabilistic classifier\nRepresents how sure classifier is of the classification\nNo guarantee that it’s correct\nEx: probability of mail being spam\nPerceptrons\nError driven model that takes training data, randomly inits params, and for every item in training data, tweaks params to make them a better fit\nInitially inspired by a neuron\nContains:\nSet of inputs\nSet of weights\nWeighted sum: summation of product of inputs and associated weights\nActivation function: if sum is greater than threshold, there will be an output\nPerceptrons for decision making:\nDifferent factors (inputs) contribute to a decision \nCan be described as dot product of input vector and weight vector\nLearning weights from examples:\nInputs as features--feature values are fixed, but weight vectors can change to get a different classifier\nLearning: binary perceptron\nStart with weights = 0\nFor each training instance, classify with current weights and if correct, no change\nOtherwise, adjust the weight vector by adding/subtracting\nSubtract if y* is -1\nW = w + y* dot f\nMulticlass decision rule\nEach class has own weight vector \nTakes score of a particular input and pick the weight vector with maximum activation\nAka prediction highest score wins\nStart with all weights and pick up training experience one by one\nPredict w/current weights and if correct, there’s not change\nElse, lower score of wrong answer, raise score of right answer\n Properties\nSeparability\nConvergence \nMistake bound\ndelta^2 = margin\nProblems with perceptrons:\nNoise: if data isn’t separable, weights might thrash (averaging weight vectors over time can help)\nMediocre generalization: finds a barely separating solution\nOvertraining: a kind of overfitting in which test/held-out accuracy rises for awhile, then falls\n\n\n## Module 12 Definitions\n* **Induction** - specific set of observations to general rule\n* **Classification** - learning problem when output is a finite set of values\n* **Regression** - when it's a number\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\nSigmoid = classifier to make binary decision about class of a new input observation. Logistic regression solves task by learning from a training set a vector weights and a bis tem.\nBias term = intercept is added to eh weighted inputs. The dot product gives us a legal probability--apply sigmoid.\n\n## SLP Chapter 5.2 Learning in Logistic Regression\nTo learnin logistic regresson, we require metric for how close label is to the true old label--distance between system output and gold output = loss funciton/cost function; second thing\nneeded is optimazation algo ffor iteratively updating weights to minimze loss ufnction. Standard algo is graident descent.\n\n## SLP Chapter 5.3 The cross-entropy loss function\nConditional max likelihood estimation: choose params that maximize log probability o the true y labels in the training data given observations x--> loss function is negative log likelihood loss, or\ncross-entropy loss.\n\n## SLP Chapter 5.4 Gradient Descent\nGradient descent finds min of a function by figuring out which direction the functions slope is rising most steepply and moving in the opp direction. \nLoss function is a convex for logistic regression. Graident descent algo finds graident of loss function at the current point andn moving in the opposite direction. Magnitude of amount to move in gradient descent is val of slope \nweighted by a learning rate n.\n\n## SLP Chapter 5.5 Regularization\nRegularization counters overfitting by penalizing large weights. \n\n## SLP Chapter 5.6 Multinomial logistic regression\nMultinomial logistic regression/softmax regression/maxent classifier: target y is a var that ranges over more than two classes; want to know proability of y being in each class. Then classifier uses generalization of \nthe sigmoid called softmax to compute probability p(y=c|x)\n\n## SLP Chapter 7.1 Units\nUnit of neural network take sa weighted sum of its inputs w/additional bias terms--> set of corresponding weights and a bias b so weighted sum z can be \nb + summation of weighted x00vector and dot product.\n\n## SLP Chapter 7.2 The XOR problem\nXOR is not linearly separable--> solution is neural networks.\n\n## SLP Chapter 7.3 Feedforward Neural Networks\nFeedforward network is a multilayer network in which units are connected w/no cycles--outputs from units in each layer are passed to units in the next higher layer and no outputs are passed back to lower layer. \nThree kinds of nodes: input untis, hiddne units, output uits. Input layer x = vector of simple scalar values; core is hidden layer h ofhidden units h1 and each layer is fully connected, meaning each unit in each layer \ntakes input the outputs etc. \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\nClassification: feedforward networks for NLP. Helps predict upcoming words from prior word context. Use forward inference/decoding for neural LMs.\nAlgo for this: 1) select three embeddings from E matrix 2) multiply by W and pass through reLu to hiddn layer h 3) multiply by U 4) apply softmax.\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\nTraining neural nets require loss ufnction, find pararms that minimize loss function (gradient descent) and gradient descent requires knowing gradient of loss function--partial out loss over all intermediate layers by using\nerror backpropagation/backward differentiation.\n\n## SLP Chapter 7.6 Training Neural Nets\nNeural language models use neural network as probabilistic classifier to compute prob of next work given previous n words\n\n## SLP Chapter 7.7 Training the neural language model\nNLM use pretrained embeddings or learn embddgins from scratch in process of language modeling.\n\n## Module 13 Lecture Notes\nLogistic Regression\nClassifier components:  Machine learning classifiers require a training corpus of M observations input/output pairs (x^i, y^i)\nFeature representation of input--vector of features\nClassification function: computes estimated class y via p(y|x)\nObjective function for learning, usually involving minimizing error on training examples (how good/bad is our classifier)\nAlgo for optimizing objective function\nSentiment classifier: take input, encode in some feature representation, and classifer output y can be 1 (positive sentiment) or 0 (negative sentiment)\nWant to estimate P(y=1|x)\nLogistic regression solves task by learning a vector of weights and a bias term\nGet feature element and multiply by weight to get dot product + bias term\nSigmoid function:\nProbability for 1 i shown below (probability for 0 is 1 - the below)\nDecision boundary: when to output 0 or 1?\n0.5 can be the decision boundary if P(y=1 | x) is more than .5, we say yes; else no\nExtracting features:\nCan count number of positive connotation + negative connotation words\nNegation words, pronouns\nAssign wieghts to each var\nComputing Z = get product of values and weight of each var\nLearning in logistic regression:\nGet weights of model by learning params (weights + bias) via learning using:\nobjective/loss function that tells us distance between system output and gold output. Cross-entropy loss used\nAlgo for optimizng objective function--use stochastic gradient descent to minimize loss function\nLoss Function\nDetermines how close a gold standard label item is to an output for a classifer\nLoss tells how much our prediction differs from the truth (mean square error)\nLoss function for probabilistic classification:\nPrefers class labels of the training example to be more likely\nConditional mximum likelihood estimation--choose params w, b that maximize the log probabilities of the true labels in the training data\nReseulting loss function is the negative log likelihood loss/cross entropy loss\nFor one observation x, maximize probability of the correct label \nChange this to log spacex\nResult is cross entropy loss\nMinimzing negative log probability--loss to be smaller if model’s estimate is close to correct and loss to be bigger if it’s more conufsed\nStochastic Gradient Descent:\nTheta is set of params in our model: weight vector and bias terms\nMinimizes cross-entropy loss across every example (ideally)\nGradient descent is a method that finds a min of a function by figuring out in which direction the function’s slope is rising the most steeply, and moving in the oppposite direction\nGlobal v local minimums:\nFor logistic regression, loss function is conveniently convex\nConvex function has one minmum so no local minima to get stuck in\nGradient descent starting from any point is guaranteed to find a min\nWeight at each timestep is going to be the weight at the previous time and step minus the learning rate\nFor each weight in vector, has own slope\nWhat is derivative with respect to our classifier in our current set of params\nSum the number of elements in our params\nGradient: cross entropy loss of weights of our prediction can be \nMini batch training: stochastic graind gdescent choose a random example\nAlternate is batch training, which computes the graident over entire dataset--> better eestimates but takes a long time to compute\nCommonly used compromise is mini-batch training, and train on a small batch and loss is accumulated\nRegularization:\nOverfitting can be a problem with many models\nIf feature only occurs in one class, attend with high weight\nRegularization is penalizing large weights\nSoftwMax: takes input vector and outputs a vector of values normalized into probabitlies\nNeural Network\nPerceptron: inputs go through activation function, and we generate a single improv\nSingle neuron is actually a whole network in layers--output, hidden, hidden, input, for example\nOutput of one layer--> intput into next layer\nIf weights set correctly, can approxmiate a huge range of possible functions\nIncoming arrows: inputs to neurons, and from outside too\nperceptron--<logistic regression\nFeed-forward neural network\nTraining neural nets: want to learn best params for neural net to make its predictions y as close as possible\nNeed: loss function, optimization algorithm, wat of computing graident the log brooch\nCross entry Loss-should be same in logistic.regression\nTo compute gradient: logistic regression as network w/one wieght layer and isgmoid output\nFound slope and took step in a downward protection\nComputation graphs: general procedue like backward differentiation\nDepends on notion on your computation graphs\nBackward differentiation: importance of computation graph comes from ackward pass and need to know weight update.\t\nHow to compute derivative of our output function L w/respect to the input\nBackwards differenciation using chain rule from calculus\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\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\nLexical semantics: linguistic study of word meaning. Leammas and senses: meanings of a word and aspects of a meaning. Lemmas can be \npolysemous. Synonmy = words with the same meaning--propositional meaning satsifies truth conditoins. Priinciple of contrast: difference in linguistc form is assoficated with difference in meaning.\nWord similarity: similarity is categorization. Word relatedness = association and belong to same semantic field. Semantic frames and roles: denote perspectives or paritcipants in particular type of event. Connotation\nmeans sentiment.\n\n## SLP Chapter 6.2 Vector Semantics\nVector semantics: standrad way to rep word meaning in nLP and deifne the maning of word by distriution in lanugage. VEctors for representing words are called embeddings. In tf-idf model, meaning of a word is defined\nby a simple function .. Method results in long, sparse, mostly zero vectors. word2vec model for short dense vectors w/useful semantic properties. Cosine = way to use embedding to compute semantic similarity.\n\n## SLP Chapter 6.3 Words and Vectors\nTerm-dcoument matrix, each row rep word in vocab and is part of vector space model of info retrieval. Vector spac e= collection of vectors by dimension. Matrix useful for info retrieval.\n\n## SLP Chapter 6.4 Cosine for measuring similarity\nnormazlied dot prodcut = same as cosine of angle between two vectors.\n\n## SLP Chapter 6.8 Word2vec\ntl-idf weighting isthe product of two terms wtih term catching one of these two intutions: term frequency or document fequency\n\n## SLP Chapter 6.10 Semantic properties of embeddings\nsemantics of embedding: analogy/relational similarity; \n\n## SLP Chapter 6.11 Bias and Embeddings\nallocational harm--bad biases. We want to debias to get rid of representational harm. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\nLogistic Regression\nClassifier components:  Machine learning classifiers require a training corpus of M observations input/output pairs (x^i, y^i)\nFeature representation of input--vector of features\nClassification function: computes estimated class y via p(y|x)\nObjective function for learning, usually involving minimizing error on training examples (how good/bad is our classifier)\nAlgo for optimizing objective function\nSentiment classifier: take input, encode in some feature representation, and classifer output y can be 1 (positive sentiment) or 0 (negative sentiment)\nWant to estimate P(y=1|x)\nLogistic regression solves task by learning a vector of weights and a bias term\nGet feature element and multiply by weight to get dot product + bias term\nSigmoid function:\nProbability for 1 i shown below (probability for 0 is 1 - the below)\nDecision boundary: when to output 0 or 1?\n0.5 can be the decision boundary if P(y=1 | x) is more than .5, we say yes; else no\nExtracting features:\nCan count number of positive connotation + negative connotation words\nNegation words, pronouns\nAssign wieghts to each var\nComputing Z = get product of values and weight of each var\nLearning in logistic regression:\nGet weights of model by learning params (weights + bias) via learning using:\nobjective/loss function that tells us distance between system output and gold output. Cross-entropy loss used\nAlgo for optimizng objective function--use stochastic gradient descent to minimize loss function\nLoss Function\nDetermines how close a gold standard label item is to an output for a classifer\nLoss tells how much our prediction differs from the truth (mean square error)\nLoss function for probabilistic classification:\nPrefers class labels of the training example to be more likely\nConditional mximum likelihood estimation--choose params w, b that maximize the log probabilities of the true labels in the training data\nReseulting loss function is the negative log likelihood loss/cross entropy loss\nFor one observation x, maximize probability of the correct label \nChange this to log spacex\nResult is cross entropy loss\nMinimzing negative log probability--loss to be smaller if model’s estimate is close to correct and loss to be bigger if it’s more conufsed\nStochastic Gradient Descent:\nTheta is set of params in our model: weight vector and bias terms\nMinimizes cross-entropy loss across every example (ideally)\nGradient descent is a method that finds a min of a function by figuring out in which direction the function’s slope is rising the most steeply, and moving in the oppposite direction\nGlobal v local minimums:\nFor logistic regression, loss function is conveniently convex\nConvex function has one minmum so no local minima to get stuck in\nGradient descent starting from any point is guaranteed to find a min\nWeight at each timestep is going to be the weight at the previous time and step minus the learning rate\nFor each weight in vector, has own slope\nWhat is derivative with respect to our classifier in our current set of params\nSum the number of elements in our params\nGradient: cross entropy loss of weights of our prediction can be \nMini batch training: stochastic graind gdescent choose a random example\nAlternate is batch training, which computes the graident over entire dataset--> better eestimates but takes a long time to compute\nCommonly used compromise is mini-batch training, and train on a small batch and loss is accumulated\nRegularization:\nOverfitting can be a problem with many models\nIf feature only occurs in one class, attend with high weight\nRegularization is penalizing large weights\nSoftwMax: takes input vector and outputs a vector of values normalized into probabitlies\nNeural Network\nPerceptron: inputs go through activation function, and we generate a single improv\nSingle neuron is actually a whole network in layers--output, hidden, hidden, input, for example\nOutput of one layer--> intput into next layer\nIf weights set correctly, can approxmiate a huge range of possible functions\nIncoming arrows: inputs to neurons, and from outside too\nperceptron--<logistic regression\nFeed-forward neural network\nTraining neural nets: want to learn best params for neural net to make its predictions y as close as possible\nNeed: loss function, optimization algorithm, wat of computing graident the log brooch\nCross entry Loss-should be same in logistic.regression\nTo compute gradient: logistic regression as network w/one wieght layer and isgmoid output\nFound slope and took step in a downward protection\nComputation graphs: general procedue like backward differentiation\nDepends on notion on your computation graphs\nBackward differentiation: importance of computation graph comes from ackward pass and need to know weight update.\t\nHow to compute derivative of our output function L w/respect to the input\nBackwards differenciation using chain rule from calculus\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}