{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "650ddb99-4b7b-4b8e-ab38-cfeb3f826097"
      },
      "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": 73,
      "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/",
          "height": 0
        },
        "outputId": "d5a5bf93-7cae-4df7-f916-ad7342f789c0"
      },
      "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": 74,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 75,
      "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 preferences captured by a utility function.\\n\n",
        "MEU principle formalizes that agent should do that right thing, but doesn't operationalize it\\n\n",
        "If an agent acts in order to maximize utility function, agent will get the highest possible score\\n\n",
        " \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Making sure that utility function follows properties\\n\n",
        "Lottery -- set of outcomes for each action\\n\n",
        "agent only needs to rank the states, not have a value for each one -- this is called value function or ordinal utility function\\n\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" preference elicitation is looking at human behavior and trying to guess a utility function\\n\n",
        "normalized utilities are between 0 and 1\\n\n",
        "we can assess the utility of a prize S by asking agent to choose between S and a standard lottery\\n\n",
        "value of a statistical life are around 10 million\\n\n",
        "micromort is 1/1000000 chance of death\\n\n",
        "Quality adjusted life year (QALY) is also a unit of utility\\n\n",
        "Agent prefers more money to less, all other things being equal --> monotonic preference\\n\n",
        "the value an agent will accept in lieu of a lottery is the certainty equivalent\\n\n",
        "difference between expected monetary value and certainty of a lottery is the insurance premium\\n\n",
        "agent that has a linear curve is risk-neutral\\n\n",
        "order statistic is the distribution of a  ranked element of a sample\\n\n",
        "unbiased -- expected value of error is 0\\n\n",
        "Tendency for estimated expected utility of best choice to be too high = optimizer’s curse\\n\n",
        "Decision theory is normative -- describes how a rational agent should act, but descriptive theory describes what happens\\n\n",
        "certainty effect -- people like gains that are certain\\n\n",
        "anchoring effect, ambiguity aversion, framing effect\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Assume environment is fully observable\\n\n",
        "a solution that specifies what the agent should do for any state that the agent might reach is a policy\\n\n",
        "optimal policy is highest expected utility\\n\n",
        "finite horizon -- fixed time, infinite horizon -- no fixed time\\n\n",
        "policy which depends on time is nonstationary\\n\n",
        "policy which reaches end state is proper policy\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" Showing that value iteration converges --> contraction\\n\n",
        "policy evaluation -- given a policy, calculate utility of each state if the policy was executed\\n\n",
        "policy improvement -- create a new MEU policy based on one-step-lookahead\\n\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "**INTRO TO MDP**\\n\n",
        "MDP are nondeterministic search problems\\n\n",
        "Fully observable environment\\n\n",
        "Pick an ACTION at each time step, terminates when you reach a goal state\\n\n",
        "If the environment were deterministic, then the solution for this would be easy\\n\n",
        "But, we treat this environment as STOCHASTIC, meaning when you pick an action, the result is undetermined\\n\n",
        "Define a transition model that is probabilistic\\n\n",
        "instead of having successor of a current state which is deterministic, you need to introduce probabilities\\n\n",
        "The transition function is written as T(s,a,s') or explicitly as a probability p(s' | s,a)\\n\n",
        "Transitions are Markovian, the probability of arriving in s' depends on s and not history of earlier states\\n\n",
        "We also need to define a REWARD FUNCTION\\n\n",
        "Can be positive or negative but are bounded by a max value\\n\n",
        "We get a reward INSTANTANEOUSLY -- meaning agent receives a reward at each time step bsaed on transition from s to s' via a\\n\n",
        "Defined by reward function R(s,a,s')\\n\n",
        "Rewards are additive\\n\n",
        "The way that we define reward affects behavior of agent as it explores environments\\n\n",
        "\n",
        "\n",
        "**MDP FOrmulation part 1**\\n\n",
        "Sequential decision problem\\n\n",
        "Fully observable environment\\n\n",
        "stochastic transition model\\n\n",
        "additive rewards\\n\n",
        "*NON DETERMINISTIC* search problems, can solve it using things like expectimax\\n\n",
        "Need to define a few things:\\n\n",
        "Set of states, Set of actions, transitino function T(s,a,s') with probabilities -- this is called the model, a reward function R(s,a,s'), an initial state, and optionally terminal states\\n\n",
        "Solution an MDP is different than solutions to other search problems\\n\n",
        "Other search problems were a deterministic set of actions\\n\n",
        "We don't have deterministic here, we need to use policies. Policy is a function that says given that I am at a current state, what action should I take?\\n\n",
        "Policy is a function that looks like Pi(s) = a for state s\\n\n",
        "pi* denotes the optimal policy\\n\n",
        "Need to compute the EXPECTED UTILITY of all possible paths generated by a policy bc one policy could have different outcomes if executed multiple times\\n\n",
        "You could have infinite rewards with infinite length games or sometimes even positive rewards\\n\n",
        "Utilities of sequences: what preferences shuold an agent have over reward sequences?\\n\n",
        "Maximize reward, rewards that happen earlier rather than later b/c its a stochastic environment\\n\n",
        "\n",
        "\n",
        "$$MDP Formulation part 2**\\n\n",
        "We add a new factor to rewards called discounting term\\n\n",
        "How long you're willing to postpone rewards currently in order to get rewards in the future\\n\n",
        "One solution: values of rewards decay exponentially\\n\n",
        "If a value is worth 1 now, then gamma in next step, and gamma ^2 2 steps later\\n\n",
        "Each time we descend a level in expectimax tree, we multiply discount once\n",
        "Why discount? Sooner rewards have higher rewards than later utility, and helps algorithms converge\\n\n",
        "A cool thing about discounting is that if you assume that agent has stationary preferences, if you take the two reward sequences and add one value to both of them, it will still prefer the same one\\n\n",
        "If you assume this, then there are only 2 ways to define utilities: additive utilities and discounted utilities (additive utility is just discounted utility where gamma = 1)\\n\n",
        "How to deal with infinite utilities:\\n\n",
        "Finite horizon similar to depth limited search\\n\n",
        "Terminate episodes after a fixed T steps\\n\n",
        "Give nonstationary policies (pi depends on time limit)\\n\n",
        "Another solution is to set gamma between 0 and 1\\n\n",
        "We can also have an absorbing state guaranteeing that for every policy, a terminal state will eventually be reached\\n\n",
        "\n",
        "**MDP examples**\\n\n",
        "Can visualize problems as a search tree where you get rewards at every level\\n\n",
        "Each MDP STATE projects an expectimax-like tree\\n\n",
        "Given a q state, what is the probability that you end up in s'?\\n\n",
        "We want to compute the value/utility of a state s. V*(s) = expected utility starting in s and acting optimally\\n\n",
        "Value(utility) of a q-state(s,a): Q*(s,a) = expected utility starting out having taken action a from state s and acting optimally\\n\n",
        "Optimal policy is Pi*(s) = optimal action from state s\\n\n",
        "Values of states: compute expectimax value of a state, recursive definition of value\\n\n",
        "V*(s) = Max over all a of Q*(s,a)\\n\n",
        "Q*(s,a) = sum over all s' (T(s,a,s') * (reward for ending up in s' + value of being in s' * gamma))\\n\n",
        "V*(s) = max over all a of the sum over all s' (T(s,a,s') * (reward for ending up in s' + value of being in s' * gamma))\\n\n",
        "THIS IS RECURSIVE\\n\n",
        "Doing expectimax is way too much work\\n\n",
        "States can end up being repeated, and we should only compute needed quantities once -- dynamic programming\\n\n",
        "Tree goes on forever: can do a depth limited search to fix this.\\n\n",
        "\n",
        "**Value Iteration Algorithm**\\n\n",
        "Start with vector of each of steps and have counter saying how much time remaining you have in the game\\n\n",
        "Start with V0(s) = 0, no time steps left means an expected reward sum of 0\n",
        "Given a vector Vk of values, compute Vk+1 using the same formula s above\\n\n",
        "repeat until converge, complexity of each iteration is O(S^2 * A)\\n\n",
        "This theorem will converge to unique optimal values because approximations get refined towards optimal values\\n\n",
        "V0 is at the bottom of the tree, then V1 is one layer up, V2 is one layer up from that, etc\\n\n",
        "How do we know that vectors converge?\\n\n",
        "Case 1: if tree has max depth of M, then VM holds the untruncated value\\n\n",
        "Case 2: if discount factor is less than 1, then each layer has exponential decay and values go down, so values eventually converge\\n\n",
        "\n",
        "**Policy Evaluation**\\n\n",
        "evaluate policies to compare two policies and decide which is better\\n\n",
        "For a policy, what are its values?\\n\n",
        "Need to define utility of a state s under fixed policy Pi, recursively\\n\n",
        "Given a set of values, can we figure out policy extraction/what policy we should take?\\n\n",
        "\n",
        "**Policy Iteration**\\n\n",
        "Combines evaluating policy with improving policy based on its values\\n\n",
        "Problems with value iteration: repeats Bellman updates and its slow, and max at each state rarely changes\\n\n",
        "value of state tend to go up until convergence, but convergence of policy happens before convergence of values\\n\n",
        "Alternative approach for optimal values. 1) policy evaltuation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\\n\n",
        "2) policy improvement: update policy using one-step look ahead with resulting converged, but not optimal utilities as future values\\n\n",
        "REPEAT\\n\n",
        "optimal, converges much faster under some conditions\\n\n",
        "Step 1 (Policy Evaluation): for fixed current policy pi, find values with policy evaluation, iterate until values converge\\n\n",
        "Step 2 (Policy improvement): for fixed values, get a better policy using policy extraction -- one step look ahead\\n\n",
        "Value iteration vs policy iteration: both want to find optimal values and from there apply policy extraction to get optimal policy\\n\n",
        "Policy iteration iterates over explicit policies and value iteration does it implicitly\\n\n",
        "In policy iteration: do serveral passes that update utilities with fixed policy, after policy is evaluated a new policy is chosen, or if no better one exists then we're done\\n\n",
        "Both are DP algorithms\\n\n",
        "Summary of MDP algorithm:\\n\n",
        "compute optimal values, use value iteration or policy iteration\\n\n",
        "compute values for a particular policy, use policy evaluation\\n\n",
        "turn your values into a policy, use policy extraction (one-step lookahead)\\n\n",
        "These all look the same because they basically are -- variations of Bellman updates\\n\n",
        "All use one-step lookahead expectimax fragments\\n\n",
        "Differ only in whether we plug in a fixed policy or max over actions\\n\n",
        "\n",
        "**Maximum Expected Utility**/n\n",
        "Different utilities imply different actions. Depending on reward, discount term, etc, the behavior changes\\n\n",
        "Chapter 16 of textbook for utilities\\n\n",
        "In expectimax and MDP, average over utility, but before that we had minimax, etc\\n\n",
        "Minimax we worry about minimizing our losses in the worst case, but worst case is not always going to happen\\n\n",
        "Better way is to quantify likelihood of each outcome and do that\\n\n",
        "Principle of maximum expected utility (MEU): a rational agent should choose the action that maximizes its expected utility given knowledge about the world\\n\n",
        "Where do utilities come from? How do we know such utilities exist? How do we know that averaging even makes sense?\\n\n",
        "We just want better states to have higher evaluations -- we call this insensitivity to monotonic transformations\\n\n",
        "Utilities -- functions from outcomes to real numbers that describe an agents preferences\\n\n",
        "Where do they come from? In a game, may be simple +1/-1, but they should summarize the agent's goals\\n\n",
        "Theorem that any \"rational\" preferences can be summarized as a utility function\\n\n",
        "We hard-wire utilities and let behaviors emerge -- not behaviors\\n\n",
        "We prescribe utility, and behaviors happen themselves\\n\n",
        "Robot has to not only pick between utilities but uncertain outcomes\\n\n",
        "Robot has preferences, has preferences between prizes/rewards, and lotteries which are situations with unceratin prizes\\n\n",
        "L = [p, A; (1-p), B]\\n\n",
        "Notation: A>B is preference, indifference is A~B\\n\n",
        "We can define rationality based on preference lists\\n\n",
        "Add constraints on preferences before we call them rational\\n\n",
        "Lots of axioms about rational preferences and behaviors\\n\n",
        "Axiom of transitivity: if I prefer A to B and B to C, then I prefer A to C\\n\n",
        "An agent with intransitive preferences could be tricked into giving away money\\n\n",
        "5 axioms of rationality:\\n\n",
        "1) either you prefer A to B, B to A, or they're the same\\n\n",
        "2) transitivity\\n\n",
        "3) continuity: If we like A better than C, and B is in the middle, then there is some value of p such that if A happened with p and C happened with 1-p, I'd prefer that to B equally\\n\n",
        "4) Subtitutability: if I don't prefer A or B, then in some lottery between A and C, I will have equal preference with a lottery between B and C\\n\n",
        "5) Monotonicity: If I prefer A over B, then if I had to pick between a lottery between A and B with A having prob p, and a lottery between A and B with A having prob q, I would pick whichever one is greater.\\n\n",
        "Theorem: rational preferences imply behavior describable as maximization of expected utility\\n\n",
        "MEU Principle: Theorem that given any preferences that satisfy these axioms, there exists a real valued function U that obeys your preferences\\n\n",
        "I.e. values assigned by U preserve preferences of both prizes and lotteries\\n\n",
        "If we choose an action that maximizes expected utility, then we are following the MEU principle\\n\n",
        "Note: an agent can be entirely rational/consistent with MEU without ever representing or manipulating utilities and probabilities\\n\n",
        "Normalized utility, translate utilities to a scale between 0 and 1\\n\n",
        "Micromort: one-millionth chance of death, useful for paying to reduce product risk\\n\n",
        "QALYs: quality-adjusted life years, useful for medical decisions involving substantial risk\\n\n",
        "Behavior is invariant under positive linear transformation\\n\n",
        "Utilities map states to real numbers, which numbers?\\n\n",
        "Compare a prize A to standard lottery L_p between best possible prize u+ with probability p and worst possible catastrophe u- with 1-p. \n",
        "Adjust lottery probability p until indifferece: A ~ L_p\\n\n",
        "Resulting p is a utility in [0,1]\\n\n",
        "Money does NOT behave as a utility function because it doesn't behave similarly when you're stuck in a lottery\\n\n",
        "Expected monetary value of a lottery = p * dollar value X + (1-p) * Y\\n\n",
        "Typically people believe the lottery worth some value of money is worth less than just having the pocket money itself\\n\n",
        "Poeple are risk averse, but when deep in debt, people are risk-prone\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 76,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 4588
        },
        "outputId": "b9bab73c-36b5-40eb-d5dc-d7dbb026c3ab"
      },
      "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": 77,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent preferences captured by a utility function.\n\nMEU principle formalizes that agent should do that right thing, but doesn't operationalize it\n\nIf an agent acts in order to maximize utility function, agent will get the highest possible score\n\n  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Making sure that utility function follows properties\n\nLottery -- set of outcomes for each action\n\nagent only needs to rank the states, not have a value for each one -- this is called value function or ordinal utility function\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n preference elicitation is looking at human behavior and trying to guess a utility function\n\nnormalized utilities are between 0 and 1\n\nwe can assess the utility of a prize S by asking agent to choose between S and a standard lottery\n\nvalue of a statistical life are around 10 million\n\nmicromort is 1/1000000 chance of death\n\nQuality adjusted life year (QALY) is also a unit of utility\n\nAgent prefers more money to less, all other things being equal --> monotonic preference\n\nthe value an agent will accept in lieu of a lottery is the certainty equivalent\n\ndifference between expected monetary value and certainty of a lottery is the insurance premium\n\nagent that has a linear curve is risk-neutral\n\norder statistic is the distribution of a  ranked element of a sample\n\nunbiased -- expected value of error is 0\n\nTendency for estimated expected utility of best choice to be too high = optimizer’s curse\n\nDecision theory is normative -- describes how a rational agent should act, but descriptive theory describes what happens\n\ncertainty effect -- people like gains that are certain\n\nanchoring effect, ambiguity aversion, framing effect\n\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Assume environment is fully observable\n\na solution that specifies what the agent should do for any state that the agent might reach is a policy\n\noptimal policy is highest expected utility\n\nfinite horizon -- fixed time, infinite horizon -- no fixed time\n\npolicy which depends on time is nonstationary\n\npolicy which reaches end state is proper policy\n\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Showing that value iteration converges --> contraction\n\npolicy evaluation -- given a policy, calculate utility of each state if the policy was executed\n\npolicy improvement -- create a new MEU policy based on one-step-lookahead\n\n \n\n## Module 8 Lecture Notes\n \n**INTRO TO MDP**\n\nMDP are nondeterministic search problems\n\nFully observable environment\n\nPick an ACTION at each time step, terminates when you reach a goal state\n\nIf the environment were deterministic, then the solution for this would be easy\n\nBut, we treat this environment as STOCHASTIC, meaning when you pick an action, the result is undetermined\n\nDefine a transition model that is probabilistic\n\ninstead of having successor of a current state which is deterministic, you need to introduce probabilities\n\nThe transition function is written as T(s,a,s') or explicitly as a probability p(s' | s,a)\n\nTransitions are Markovian, the probability of arriving in s' depends on s and not history of earlier states\n\nWe also need to define a REWARD FUNCTION\n\nCan be positive or negative but are bounded by a max value\n\nWe get a reward INSTANTANEOUSLY -- meaning agent receives a reward at each time step bsaed on transition from s to s' via a\n\nDefined by reward function R(s,a,s')\n\nRewards are additive\n\nThe way that we define reward affects behavior of agent as it explores environments\n\n\n\n**MDP FOrmulation part 1**\n\nSequential decision problem\n\nFully observable environment\n\nstochastic transition model\n\nadditive rewards\n\n*NON DETERMINISTIC* search problems, can solve it using things like expectimax\n\nNeed to define a few things:\n\nSet of states, Set of actions, transitino function T(s,a,s') with probabilities -- this is called the model, a reward function R(s,a,s'), an initial state, and optionally terminal states\n\nSolution an MDP is different than solutions to other search problems\n\nOther search problems were a deterministic set of actions\n\nWe don't have deterministic here, we need to use policies. Policy is a function that says given that I am at a current state, what action should I take?\n\nPolicy is a function that looks like Pi(s) = a for state s\n\npi* denotes the optimal policy\n\nNeed to compute the EXPECTED UTILITY of all possible paths generated by a policy bc one policy could have different outcomes if executed multiple times\n\nYou could have infinite rewards with infinite length games or sometimes even positive rewards\n\nUtilities of sequences: what preferences shuold an agent have over reward sequences?\n\nMaximize reward, rewards that happen earlier rather than later b/c its a stochastic environment\n\n\n\n$$MDP Formulation part 2**\n\nWe add a new factor to rewards called discounting term\n\nHow long you're willing to postpone rewards currently in order to get rewards in the future\n\nOne solution: values of rewards decay exponentially\n\nIf a value is worth 1 now, then gamma in next step, and gamma ^2 2 steps later\n\nEach time we descend a level in expectimax tree, we multiply discount once\nWhy discount? Sooner rewards have higher rewards than later utility, and helps algorithms converge\n\nA cool thing about discounting is that if you assume that agent has stationary preferences, if you take the two reward sequences and add one value to both of them, it will still prefer the same one\n\nIf you assume this, then there are only 2 ways to define utilities: additive utilities and discounted utilities (additive utility is just discounted utility where gamma = 1)\n\nHow to deal with infinite utilities:\n\nFinite horizon similar to depth limited search\n\nTerminate episodes after a fixed T steps\n\nGive nonstationary policies (pi depends on time limit)\n\nAnother solution is to set gamma between 0 and 1\n\nWe can also have an absorbing state guaranteeing that for every policy, a terminal state will eventually be reached\n\n\n**MDP examples**\n\nCan visualize problems as a search tree where you get rewards at every level\n\nEach MDP STATE projects an expectimax-like tree\n\nGiven a q state, what is the probability that you end up in s'?\n\nWe want to compute the value/utility of a state s. V*(s) = expected utility starting in s and acting optimally\n\nValue(utility) of a q-state(s,a): Q*(s,a) = expected utility starting out having taken action a from state s and acting optimally\n\nOptimal policy is Pi*(s) = optimal action from state s\n\nValues of states: compute expectimax value of a state, recursive definition of value\n\nV*(s) = Max over all a of Q*(s,a)\n\nQ*(s,a) = sum over all s' (T(s,a,s') * (reward for ending up in s' + value of being in s' * gamma))\n\nV*(s) = max over all a of the sum over all s' (T(s,a,s') * (reward for ending up in s' + value of being in s' * gamma))\n\nTHIS IS RECURSIVE\n\nDoing expectimax is way too much work\n\nStates can end up being repeated, and we should only compute needed quantities once -- dynamic programming\n\nTree goes on forever: can do a depth limited search to fix this.\n\n\n**Value Iteration Algorithm**\n\nStart with vector of each of steps and have counter saying how much time remaining you have in the game\n\nStart with V0(s) = 0, no time steps left means an expected reward sum of 0\nGiven a vector Vk of values, compute Vk+1 using the same formula s above\n\nrepeat until converge, complexity of each iteration is O(S^2 * A)\n\nThis theorem will converge to unique optimal values because approximations get refined towards optimal values\n\nV0 is at the bottom of the tree, then V1 is one layer up, V2 is one layer up from that, etc\n\nHow do we know that vectors converge?\n\nCase 1: if tree has max depth of M, then VM holds the untruncated value\n\nCase 2: if discount factor is less than 1, then each layer has exponential decay and values go down, so values eventually converge\n\n\n**Policy Evaluation**\n\nevaluate policies to compare two policies and decide which is better\n\nFor a policy, what are its values?\n\nNeed to define utility of a state s under fixed policy Pi, recursively\n\nGiven a set of values, can we figure out policy extraction/what policy we should take?\n\n\n**Policy Iteration**\n\nCombines evaluating policy with improving policy based on its values\n\nProblems with value iteration: repeats Bellman updates and its slow, and max at each state rarely changes\n\nvalue of state tend to go up until convergence, but convergence of policy happens before convergence of values\n\nAlternative approach for optimal values. 1) policy evaltuation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n\n2) policy improvement: update policy using one-step look ahead with resulting converged, but not optimal utilities as future values\n\nREPEAT\n\noptimal, converges much faster under some conditions\n\nStep 1 (Policy Evaluation): for fixed current policy pi, find values with policy evaluation, iterate until values converge\n\nStep 2 (Policy improvement): for fixed values, get a better policy using policy extraction -- one step look ahead\n\nValue iteration vs policy iteration: both want to find optimal values and from there apply policy extraction to get optimal policy\n\nPolicy iteration iterates over explicit policies and value iteration does it implicitly\n\nIn policy iteration: do serveral passes that update utilities with fixed policy, after policy is evaluated a new policy is chosen, or if no better one exists then we're done\n\nBoth are DP algorithms\n\nSummary of MDP algorithm:\n\ncompute optimal values, use value iteration or policy iteration\n\ncompute values for a particular policy, use policy evaluation\n\nturn your values into a policy, use policy extraction (one-step lookahead)\n\nThese all look the same because they basically are -- variations of Bellman updates\n\nAll use one-step lookahead expectimax fragments\n\nDiffer only in whether we plug in a fixed policy or max over actions\n\n\n**Maximum Expected Utility**/n\nDifferent utilities imply different actions. Depending on reward, discount term, etc, the behavior changes\n\nChapter 16 of textbook for utilities\n\nIn expectimax and MDP, average over utility, but before that we had minimax, etc\n\nMinimax we worry about minimizing our losses in the worst case, but worst case is not always going to happen\n\nBetter way is to quantify likelihood of each outcome and do that\n\nPrinciple of maximum expected utility (MEU): a rational agent should choose the action that maximizes its expected utility given knowledge about the world\n\nWhere do utilities come from? How do we know such utilities exist? How do we know that averaging even makes sense?\n\nWe just want better states to have higher evaluations -- we call this insensitivity to monotonic transformations\n\nUtilities -- functions from outcomes to real numbers that describe an agents preferences\n\nWhere do they come from? In a game, may be simple +1/-1, but they should summarize the agent's goals\n\nTheorem that any \"rational\" preferences can be summarized as a utility function\n\nWe hard-wire utilities and let behaviors emerge -- not behaviors\n\nWe prescribe utility, and behaviors happen themselves\n\nRobot has to not only pick between utilities but uncertain outcomes\n\nRobot has preferences, has preferences between prizes/rewards, and lotteries which are situations with unceratin prizes\n\nL = [p, A; (1-p), B]\n\nNotation: A>B is preference, indifference is A~B\n\nWe can define rationality based on preference lists\n\nAdd constraints on preferences before we call them rational\n\nLots of axioms about rational preferences and behaviors\n\nAxiom of transitivity: if I prefer A to B and B to C, then I prefer A to C\n\nAn agent with intransitive preferences could be tricked into giving away money\n\n5 axioms of rationality:\n\n1) either you prefer A to B, B to A, or they're the same\n\n2) transitivity\n\n3) continuity: If we like A better than C, and B is in the middle, then there is some value of p such that if A happened with p and C happened with 1-p, I'd prefer that to B equally\n\n4) Subtitutability: if I don't prefer A or B, then in some lottery between A and C, I will have equal preference with a lottery between B and C\n\n5) Monotonicity: If I prefer A over B, then if I had to pick between a lottery between A and B with A having prob p, and a lottery between A and B with A having prob q, I would pick whichever one is greater.\n\nTheorem: rational preferences imply behavior describable as maximization of expected utility\n\nMEU Principle: Theorem that given any preferences that satisfy these axioms, there exists a real valued function U that obeys your preferences\n\nI.e. values assigned by U preserve preferences of both prizes and lotteries\n\nIf we choose an action that maximizes expected utility, then we are following the MEU principle\n\nNote: an agent can be entirely rational/consistent with MEU without ever representing or manipulating utilities and probabilities\n\nNormalized utility, translate utilities to a scale between 0 and 1\n\nMicromort: one-millionth chance of death, useful for paying to reduce product risk\n\nQALYs: quality-adjusted life years, useful for medical decisions involving substantial risk\n\nBehavior is invariant under positive linear transformation\n\nUtilities map states to real numbers, which numbers?\n\nCompare a prize A to standard lottery L_p between best possible prize u+ with probability p and worst possible catastrophe u- with 1-p. \nAdjust lottery probability p until indifferece: A ~ L_p\n\nResulting p is a utility in [0,1]\n\nMoney does NOT behave as a utility function because it doesn't behave similarly when you're stuck in a lottery\n\nExpected monetary value of a lottery = p * dollar value X + (1-p) * Y\n\nTypically people believe the lottery worth some value of money is worth less than just having the pocket money itself\n\nPoeple are risk averse, but when deep in debt, people are risk-prone\n\n\n \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "\n",
        "**Intro**\\n\n",
        "In MDP, agent is given reward and transition functions, in reinforcement learning, agent learns these functions by interacting with world\\n\n",
        "goal of agent is to maximize expected rewards over time using observations\\n\n",
        "Tradeoff between exploration and exploitation\\n\n",
        "Exploration -- agent must try new actions including ones where reward may be worse than if it tried a different action\\n\n",
        "Exploitation -- agent must use knowledge that it learned in order to choose best action\\n\n",
        "Model based learning -- transitino function represented using an explicit probabilistic model\\n\n",
        "Tempral difference learning -- agent updates beliefs about world after every action using exponential moving\\n\n",
        "Regret -- measures the total rewards we get over a particular exploration strat, compare that with expected rewards if agent followed optimal policy the whole time\\n\n",
        "\n",
        "**Reinforcement learning part 1**\\n\n",
        "Still in uncertain environments --> need to develop policies\\n\n",
        "An additional layer of complication\\n\n",
        "In MDP, we knew the probability distributions, and we could see the rewards\\n\n",
        "We don't have these given to us anymore\\n\n",
        "Double bandit problem, one machine gives u 1 but other gives u either 2 or 0\\n\n",
        "Can model this as a MDP -- use value iteration and determine best policy, or other MDP algo\\n\n",
        "Now, what if we don't know the probability distribution?\\n\n",
        "How do we know when it's a worse strategy to play red than to play blue slot machine?\\n\n",
        "Need to find at what point we can decide whether red is a better or worse policy\\n\n",
        "For MDP, we could PLAN, but for this, we don't plan, we learn -- reinforcement learning\\n\n",
        "There was an MDp, but you couldn't solve it with just computation\\n\n",
        "Need to actually act to figure it out\\n\n",
        "Process is more difficult than MDPs we had before\\n\n",
        "\n",
        "**Reinforcement learning part 2**\\n\n",
        "Basic idea:\\n\n",
        "Have an agent that is always acting, agent has actions available to it, it will choose an action and environment will resolve the action and after you act on environment you see what happens -- what state and what reward\\n\n",
        "Agent's utility is defined by the reward function\\n\n",
        "Want to learn how to maximize expected rewards\\n\n",
        "All learning is based on observed samples of outcomes\\n\n",
        "Still assume a markov decision process: set of states, set of actions, model T(s,a,s') and a reward function R(s,a,s')\\n\n",
        "New twist is that we don't know T or R, so we need to try out actions and learn\\n\n",
        "Offline planning -- MDP, Online planning -- Reinforcement learning\\n\n",
        "Model-Based learning: learn an approximate model based on experiences, and then solve for values as if the learned model is correct\\n\n",
        "Take a bunch of sample and estimate by normalizing\\n\n",
        "Step 1: Learn empirical Model, count outcomes s' for each s, a. Then normalize to give an estimate of T_hat(s,a,s'), discover each R_hat(s,a,s') when we experience (s,a,s')\\n\n",
        "Step 2: example, use value iteration as before\\n\n",
        "\n",
        "**Passive reinforcement learning**\\n\n",
        "model-free learning: not going to construct an explicit model, instead take an action and every time, take a result compared to what we thought was going to happen\\n\n",
        "Whenever something deviates from expected, we adjust models\\n\n",
        "We track JUST values of interest themselves, not transition or reward\\n\n",
        "We let someone else choose policy for us, we try it out, and see what happens\\n\n",
        "Simplified task: policy evaluation\\n\n",
        "Input: a fixed policy pi(s), don't know transition or reward, goal is to learn state values\\n\n",
        "In this case, learner is along for the ride, no choice about actions to take, just execute policy and learn from experience\\n\n",
        "This is NOT offline planning, you take actions in the world\\n\n",
        "Direct evaluation -- goal is to compute values for each state under pi\\n\n",
        "Idea is to average together observed sample values, act according to pi\\n\n",
        "Every time you visit a state, write down what the sum of discounted rewards turned out to be, adn average those samples\\n\n",
        "This is direct evaluation\\n\n",
        "Direct evaluation is easy to understand, doesn't require knowledge of T or R, and eventually will compute the correct average values using just sample transitions\\n\n",
        "Bad things, though, is that it wastes information about structure/state connections, each state must be learned separately, so it takes a long time to learn\\n\n",
        "Why not use policy evaluation? simplified bellman updates calculate V for a fixed policy\\n\n",
        "Each round, replace V with a one-step-look-ahead layer over V\\n\n",
        "This approach fully exploited the connections between the states, unfortunately we need T and R to do it\\n\n",
        "Could we do policy evaluation without knowing T and R?\\n\n",
        "Sample based policy evaluation is the answer\\n\n",
        "Take a bunch of samples of how often we end up at s' and then average\\n\n",
        "Not going to work though because we can't rewind time to get sample after sample from state s'n\n",
        "\n",
        "**Temporal Difference Learning**\\n\n",
        "Instead of updating values for the value of being in pi after n steps, let's update every time\\n\n",
        "Update V(s) each time we experience a transition (s,a,s',r)\\n\n",
        "Likely outcomes s' will contribute updates more often -- weighted more heavily\\n\n",
        "temporal difference learning of values: policy still fixed, still doing evaluation\\n\n",
        "Move values toward value of whatever successor occurs: running average\\n\n",
        "Alpha is a variable we choose that sets how much we allow current samples to influence our overall estimates, etc\\n\n",
        "Difference beteween what we observe and what is expected is weighted by alpha\\n\n",
        "More recent samples end up being more important -- ends up being an exponential moving average\\n\n",
        "Forgets about the past\\n\n",
        "Decreasing learning rate (alpha) can give converging values\\n\n",
        "TD value learning is model free, mimicking bellman updates with running sample averages\n",
        "Problems with TD value learning -- if we want to turn values into new policy, we need to get Q values too, so we need to learn the Q values directly, not values themselves\\n\n",
        "\n",
        "**Active reinforcement learning (Q-learning)**\\n\n",
        "We want to know what are the optimal policies and the values of states\\n\n",
        "We are going to figure out what actions to take/what the policy is in active reinforcement learning\\n\n",
        "Q-value iteration -- find successive depth limited values\\n\n",
        "Determining best policy from a state, its easier if instead of best value of state, get best value of Q-state\\n\n",
        "Start with Q_0(s,a) = 0, given Q_k calculate depth k+1 q-values for all q-states\\n\n",
        "Q-learning: instead of Q-value iteration, do it based on samples we observe\\n\n",
        "Learn Q(s,a) values as you go. Every action you take gets a sample (s,a,s',r), then consider your old estimate Q(s,a), consider your new sample estimate, incorporate the new estimate in a running average\\n\n",
        "Similar to temporal difference learning, just for Q-states and Q-values\\n\n",
        "Eventually we will converge to the optimal policy, even though we may be acting suboptimally\\n\n",
        "This is called !) off policy learning\\n\n",
        "learn best policy even if current policy isn't the best\\n\n",
        "Caveats: you need to explore enough, you have to eventually make learning rate small enough, but not decrease it too quickly, in the limit, doesn't matter how you select actions\\n\n",
        "\n",
        "**Exploration vs. Exploitation**\\n\n",
        "Q-learning requires exploring to learn optimal policy\\n\n",
        "In exploration, try out new things and make mistakes, need to decide how and when to do it\\n\n",
        "How to explore? Simplest is just randomly pick actions\\n\n",
        "Or, epsilon-greedy, with small probability epsilon, act randomly, and with large probability 1 - epsilon, act on current policy\\n\n",
        "Problems with random actions? -- you do exploree space but keep thrashing around once learning is done. A solutino is to lower epsilon over time or have exploration functions\\n\n",
        "Exploration functions: when should we explore and what should we explore when we decide to explore vs. exploit?\\n\n",
        "Want to explore areas whose badness is not (yet) established, eventually stop exploring\\n\n",
        "Takes a value estimate/utility u and a visit count n, and returns an optimistic utility f(u,n) = u + k/n\\n\n",
        "Want to give a bonus if we haven't visited a state often, bonus is k\\n\n",
        "A regular q-update without exploration function doesn't use exploraiton function, but modified Q update uses the exploration function instead of just whatever values we have currently\\n\n",
        "This propagates the bonus back to states that lead to unknown states as well\\n\n",
        "You can quantify goodness of epsilon-greedy or exploration functions using regret\\n\n",
        "Regret measures how many mistakes we made over time -- difference between expected rewards and optimal rewards\\n\n",
        "Minimixing regret goes beyond learning to be optimal -- it requires optimally learning to be optimal\\n\n",
        "example: random exploration and exploration function both end up optimal, but random exploration has higher regret\\n\n",
        "\n",
        "**Approximate Q-learning**\\n\n",
        "In some problems, there are so many states that you can't possibly visit all of them\\n\n",
        "Generalizing across states -- basic Q-learning keeps a table of all q-values\\n\n",
        "In realistic situations, you can't learn about every single state, too many states to visit and too many states to keep in memory\\n\n",
        "Intead, we generalize -- learn about some small number of training states, and generalize that experience to new states that look similar. Fundamental idea in machine learning\\n\n",
        "Linear value function -- using a feature representation, we can write a q function or value function for any state using a few weights\\n\n",
        "V(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)\\n\n",
        "Q(s,a) = w1f1(s,a) + w2f2(s,a) + ... + wnfn(s,a) <- approximate q-learning \\n\n",
        "Advantage: our experience is summed up in a few powerful numbers\\n\n",
        "Disadvantage: states may share features but actually be very different in value\\n\n",
        "Q-learning with linear Q-functions:\\n\n",
        "Transition = (s,a,r,s'), difference: [r + gamma * max over all a (Q(s',a'))] - Q(s,a)\\n\n",
        "Difference is essentially an error term that tells us the difference between what we thought we would get and what we seem to get based on sample and one step lookahead\\n\n",
        "then, set Q(s,a) <- Q(s,a) + alpha * difference\\n\n",
        "In approximate Q-learning, we ant to update the weights.\\n\n",
        "So, to update weights, we can do w_i <- w_i + alpha * difference * f_i(s,a)\n",
        "Intuitive interpretation:\\n\n",
        "Each of the weights is like a little slider and we can adjust weights on active features\\n\n",
        "If something unexpectedly bad happens, we blame features that are active when something happens\\n\n",
        "Formal justification: online least squares\\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"exploration\" : \"you have to try unknown actions to get information\",\n",
        "\"exploitation\": \"eventually, you have to use what you know\",\n",
        "\"regret\": \"even if you learn intelligently, you make mistakes\",\n",
        "\"sampling\": \"because of chance, you have to try things repeatedly\",\n",
        "\"difficulty\": \"learning can be much harder than solving a known MDP\"\n",
        "}"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3503
        },
        "cellView": "form",
        "outputId": "183c5dc1-c88c-4907-9f67-909f3fc544ec"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n \n\n**Intro**\n\nIn MDP, agent is given reward and transition functions, in reinforcement learning, agent learns these functions by interacting with world\n\ngoal of agent is to maximize expected rewards over time using observations\n\nTradeoff between exploration and exploitation\n\nExploration -- agent must try new actions including ones where reward may be worse than if it tried a different action\n\nExploitation -- agent must use knowledge that it learned in order to choose best action\n\nModel based learning -- transitino function represented using an explicit probabilistic model\n\nTempral difference learning -- agent updates beliefs about world after every action using exponential moving\n\nRegret -- measures the total rewards we get over a particular exploration strat, compare that with expected rewards if agent followed optimal policy the whole time\n\n\n**Reinforcement learning part 1**\n\nStill in uncertain environments --> need to develop policies\n\nAn additional layer of complication\n\nIn MDP, we knew the probability distributions, and we could see the rewards\n\nWe don't have these given to us anymore\n\nDouble bandit problem, one machine gives u 1 but other gives u either 2 or 0\n\nCan model this as a MDP -- use value iteration and determine best policy, or other MDP algo\n\nNow, what if we don't know the probability distribution?\n\nHow do we know when it's a worse strategy to play red than to play blue slot machine?\n\nNeed to find at what point we can decide whether red is a better or worse policy\n\nFor MDP, we could PLAN, but for this, we don't plan, we learn -- reinforcement learning\n\nThere was an MDp, but you couldn't solve it with just computation\n\nNeed to actually act to figure it out\n\nProcess is more difficult than MDPs we had before\n\n\n**Reinforcement learning part 2**\n\nBasic idea:\n\nHave an agent that is always acting, agent has actions available to it, it will choose an action and environment will resolve the action and after you act on environment you see what happens -- what state and what reward\n\nAgent's utility is defined by the reward function\n\nWant to learn how to maximize expected rewards\n\nAll learning is based on observed samples of outcomes\n\nStill assume a markov decision process: set of states, set of actions, model T(s,a,s') and a reward function R(s,a,s')\n\nNew twist is that we don't know T or R, so we need to try out actions and learn\n\nOffline planning -- MDP, Online planning -- Reinforcement learning\n\nModel-Based learning: learn an approximate model based on experiences, and then solve for values as if the learned model is correct\n\nTake a bunch of sample and estimate by normalizing\n\nStep 1: Learn empirical Model, count outcomes s' for each s, a. Then normalize to give an estimate of T_hat(s,a,s'), discover each R_hat(s,a,s') when we experience (s,a,s')\n\nStep 2: example, use value iteration as before\n\n\n**Passive reinforcement learning**\n\nmodel-free learning: not going to construct an explicit model, instead take an action and every time, take a result compared to what we thought was going to happen\n\nWhenever something deviates from expected, we adjust models\n\nWe track JUST values of interest themselves, not transition or reward\n\nWe let someone else choose policy for us, we try it out, and see what happens\n\nSimplified task: policy evaluation\n\nInput: a fixed policy pi(s), don't know transition or reward, goal is to learn state values\n\nIn this case, learner is along for the ride, no choice about actions to take, just execute policy and learn from experience\n\nThis is NOT offline planning, you take actions in the world\n\nDirect evaluation -- goal is to compute values for each state under pi\n\nIdea is to average together observed sample values, act according to pi\n\nEvery time you visit a state, write down what the sum of discounted rewards turned out to be, adn average those samples\n\nThis is direct evaluation\n\nDirect evaluation is easy to understand, doesn't require knowledge of T or R, and eventually will compute the correct average values using just sample transitions\n\nBad things, though, is that it wastes information about structure/state connections, each state must be learned separately, so it takes a long time to learn\n\nWhy not use policy evaluation? simplified bellman updates calculate V for a fixed policy\n\nEach round, replace V with a one-step-look-ahead layer over V\n\nThis approach fully exploited the connections between the states, unfortunately we need T and R to do it\n\nCould we do policy evaluation without knowing T and R?\n\nSample based policy evaluation is the answer\n\nTake a bunch of samples of how often we end up at s' and then average\n\nNot going to work though because we can't rewind time to get sample after sample from state s'n\n\n**Temporal Difference Learning**\n\nInstead of updating values for the value of being in pi after n steps, let's update every time\n\nUpdate V(s) each time we experience a transition (s,a,s',r)\n\nLikely outcomes s' will contribute updates more often -- weighted more heavily\n\ntemporal difference learning of values: policy still fixed, still doing evaluation\n\nMove values toward value of whatever successor occurs: running average\n\nAlpha is a variable we choose that sets how much we allow current samples to influence our overall estimates, etc\n\nDifference beteween what we observe and what is expected is weighted by alpha\n\nMore recent samples end up being more important -- ends up being an exponential moving average\n\nForgets about the past\n\nDecreasing learning rate (alpha) can give converging values\n\nTD value learning is model free, mimicking bellman updates with running sample averages\nProblems with TD value learning -- if we want to turn values into new policy, we need to get Q values too, so we need to learn the Q values directly, not values themselves\n\n\n**Active reinforcement learning (Q-learning)**\n\nWe want to know what are the optimal policies and the values of states\n\nWe are going to figure out what actions to take/what the policy is in active reinforcement learning\n\nQ-value iteration -- find successive depth limited values\n\nDetermining best policy from a state, its easier if instead of best value of state, get best value of Q-state\n\nStart with Q_0(s,a) = 0, given Q_k calculate depth k+1 q-values for all q-states\n\nQ-learning: instead of Q-value iteration, do it based on samples we observe\n\nLearn Q(s,a) values as you go. Every action you take gets a sample (s,a,s',r), then consider your old estimate Q(s,a), consider your new sample estimate, incorporate the new estimate in a running average\n\nSimilar to temporal difference learning, just for Q-states and Q-values\n\nEventually we will converge to the optimal policy, even though we may be acting suboptimally\n\nThis is called !) off policy learning\n\nlearn best policy even if current policy isn't the best\n\nCaveats: you need to explore enough, you have to eventually make learning rate small enough, but not decrease it too quickly, in the limit, doesn't matter how you select actions\n\n\n**Exploration vs. Exploitation**\n\nQ-learning requires exploring to learn optimal policy\n\nIn exploration, try out new things and make mistakes, need to decide how and when to do it\n\nHow to explore? Simplest is just randomly pick actions\n\nOr, epsilon-greedy, with small probability epsilon, act randomly, and with large probability 1 - epsilon, act on current policy\n\nProblems with random actions? -- you do exploree space but keep thrashing around once learning is done. A solutino is to lower epsilon over time or have exploration functions\n\nExploration functions: when should we explore and what should we explore when we decide to explore vs. exploit?\n\nWant to explore areas whose badness is not (yet) established, eventually stop exploring\n\nTakes a value estimate/utility u and a visit count n, and returns an optimistic utility f(u,n) = u + k/n\n\nWant to give a bonus if we haven't visited a state often, bonus is k\n\nA regular q-update without exploration function doesn't use exploraiton function, but modified Q update uses the exploration function instead of just whatever values we have currently\n\nThis propagates the bonus back to states that lead to unknown states as well\n\nYou can quantify goodness of epsilon-greedy or exploration functions using regret\n\nRegret measures how many mistakes we made over time -- difference between expected rewards and optimal rewards\n\nMinimixing regret goes beyond learning to be optimal -- it requires optimally learning to be optimal\n\nexample: random exploration and exploration function both end up optimal, but random exploration has higher regret\n\n\n**Approximate Q-learning**\n\nIn some problems, there are so many states that you can't possibly visit all of them\n\nGeneralizing across states -- basic Q-learning keeps a table of all q-values\n\nIn realistic situations, you can't learn about every single state, too many states to visit and too many states to keep in memory\n\nIntead, we generalize -- learn about some small number of training states, and generalize that experience to new states that look similar. Fundamental idea in machine learning\n\nLinear value function -- using a feature representation, we can write a q function or value function for any state using a few weights\n\nV(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)\n\nQ(s,a) = w1f1(s,a) + w2f2(s,a) + ... + wnfn(s,a) <- approximate q-learning \n\nAdvantage: our experience is summed up in a few powerful numbers\n\nDisadvantage: states may share features but actually be very different in value\n\nQ-learning with linear Q-functions:\n\nTransition = (s,a,r,s'), difference: [r + gamma * max over all a (Q(s',a'))] - Q(s,a)\n\nDifference is essentially an error term that tells us the difference between what we thought we would get and what we seem to get based on sample and one step lookahead\n\nthen, set Q(s,a) <- Q(s,a) + alpha * difference\n\nIn approximate Q-learning, we ant to update the weights.\n\nSo, to update weights, we can do w_i <- w_i + alpha * difference * f_i(s,a)\nIntuitive interpretation:\n\nEach of the weights is like a little slider and we can adjust weights on active features\n\nIf something unexpectedly bad happens, we blame features that are active when something happens\n\nFormal justification: online least squares\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 9 Definitions\n* **Exploration** - you have to try unknown actions to get information\n* **Exploitation** - eventually, you have to use what you know\n* **Regret** - even if you learn intelligently, you make mistakes\n* **Sampling** - because of chance, you have to try things repeatedly\n* **Difficulty** - learning can be much harder than solving a known MDP\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "\n",
        "Uncertainty -- observed variables(evidence), unobserved variables(states), and model. Probabilistic reasoning gives us a framework for managing our beliefs and knowledge\\n\n",
        "Probabilities are about possible worlds, and instead of ruling out possibilities, probabilities quantify how likely a possible world is\\n\n",
        "Possible words are sample space, and they are mutually exclusive and exhaustive,\\n\n",
        "Probability model associates a probability P(w) with each possible world w.\\n\n",
        "Random variable is some aspect about world which may have uncertainty\\n\n",
        "Probabilities are always between 0 and 1, and the sum of all of them equals 1\\n\n",
        "Unobserved RVs have distributions, and a distribution is a table of probabilities of values. \\n\n",
        "P(hot) = P(T = hot),\\n\n",
        "Joint Distribution -- over a set of RVs, specifies a real number for each assignment or outcome\\n\n",
        "P(X_1 = x_1, X_2 = x_2 ... X_n = x_n) = P(x_1, x_2, ..., x_n)\\n\n",
        "Must obeys the axioms of probability above where its a >=0 probability and the sum over all (x1,x2,...xn) is 1\\n\n",
        "Probabilistic Models -- joint distribution over a set of RVs\\n\n",
        "They have: random variables with domainds, assignments called outcomes, joint distributions say whether assignments are likely, normalized where sum is 1, and ideally only certain variables interact\\n\n",
        "An event is a set E of outcomes -- froma. joint distribution we can calculate the probability of any event: hot and sunny, hot, hot or sunny, etc\\n\n",
        "Typically we care about partial assignments like P(T = hot)\\n\n",
        "Marginal Distributions are subtables which eliminate variables -- they combine collapsed rows by adding to do marginalization (summing out)\\n\n",
        "Conditional distributions are probability distributions over some variables given fixed values of others\\n\n",
        "Probabilistic Inference -- compute a desired probability from other known probabilities (conditional from joint)\\n\n",
        "Generally compute conditional probabilities which represent agent's beliefs given evidence. Probabilities can also chance with new evidence\\n\n",
        "Inference by Enumeration: General case has evidence variables E_1, E_2, ... E_k = e_1, e_2, ... e_k. Also has query variable(s) Q, and hidden variables H_1,... H_r\\n\n",
        "We want to compute P(Q | e_1...e_k)\\n\n",
        "Step 1: select entries consistent with evidence\\n\n",
        "Step 2: P(Q,e_1...e_k) = sum over all (h1...h_r) of P(Q, h1...h_r, e1...e_k). -- sum out H to get joint of query and evidence\\n\n",
        "Step 3: normalize by dividing by Z where Z is the sum over all q of(P(Q,e1...ek))\\n\n",
        "Product rule: P(y) * P(x|y) = P(x,y)\\n\n",
        "Chain rule: P(x1,x2,x3) = P(x1) * P(x2 | x1) * P(x3 | x1, x2)\\n\n",
        "Bayes rule: P(x|y) = P(y|x)/P(y) * P(x)\n",
        "\n",
        "**Probabilistic Language Models**\\n\n",
        "Goal is to assign probability to a sequence -- autocomplete for texting, machine translation, spelling correction, speech recognition\\n\n",
        "Related task to this is computing the probability of an upcoming word -- a model that computes either of these is called a language model or LM\\n\n",
        "P(W) = P(w1,w2,w3,w4,w5) -- this is probability of a sentence of sequence of words, P(w5|w1, w2, w3, w4) is probability of an upcoming word\\n\n",
        "A model that computes either of these is a language model\\n\n",
        "The grammar is better but language model is standard\\n\n",
        "Join probability of words in a sentence involves chain rule of conditional probabilities\\n\n",
        "How to estimate these probabilities? Could we just count and divide --> Maximum Likelihood estimation (MLE)?\\n\n",
        "This doesn't work because with long phrases you oftentimes won't see those phrases much so you'll need huge inefficient datasets to make some queries work\\n\n",
        "In MLE, P(won | the underdog team) = COUNT(the underdog team won)/ COUNT(the underdog team)\\n\n",
        "Markov simplifying assumption\\n\n",
        "Only depend on current state and not long history of states that you've gone through\\n\n",
        "In this case, it only depends on the previous k words, and not the whole context\\n\n",
        "P(w1w2w3...wn) = Product over all i up until n of (P(wi | w_{i-k} ... w_{i-1})\\n\n",
        "The type of gram determines how much history we should use: unigram-no history, bigram-1 word history, trigram-2 word history, 4-gram = 3 words history\\n\n",
        "Simplest case is unigram model were each word is just considered on its own, and for n gram model we conditions on the previous n-1 words\\n\n",
        "MLE estimates for bigram models: P(w_i | w_{i-1}) = count(w_{i-1}, w_i)/count(w_{i-1})\\n\n",
        "But MLE might give probability of 0 if its never seen the word before\\n\n",
        "We can normalize training data by replacing any word not in L with <unk>\\n\n",
        "Avoid 0s with smoothing\\n\n",
        "We do everything in log space, we can avoid underflow and adding is faster than multiplying\\n\n",
        "Google n-gram release\\n\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 80,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2235
        },
        "cellView": "form",
        "outputId": "f910745b-f1b4-44e4-a0b7-37ef30c3b6e8"
      },
      "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": 81,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \n\nUncertainty -- observed variables(evidence), unobserved variables(states), and model. Probabilistic reasoning gives us a framework for managing our beliefs and knowledge\n\nProbabilities are about possible worlds, and instead of ruling out possibilities, probabilities quantify how likely a possible world is\n\nPossible words are sample space, and they are mutually exclusive and exhaustive,\n\nProbability model associates a probability P(w) with each possible world w.\n\nRandom variable is some aspect about world which may have uncertainty\n\nProbabilities are always between 0 and 1, and the sum of all of them equals 1\n\nUnobserved RVs have distributions, and a distribution is a table of probabilities of values. \n\nP(hot) = P(T = hot),\n\nJoint Distribution -- over a set of RVs, specifies a real number for each assignment or outcome\n\nP(X_1 = x_1, X_2 = x_2 ... X_n = x_n) = P(x_1, x_2, ..., x_n)\n\nMust obeys the axioms of probability above where its a >=0 probability and the sum over all (x1,x2,...xn) is 1\n\nProbabilistic Models -- joint distribution over a set of RVs\n\nThey have: random variables with domainds, assignments called outcomes, joint distributions say whether assignments are likely, normalized where sum is 1, and ideally only certain variables interact\n\nAn event is a set E of outcomes -- froma. joint distribution we can calculate the probability of any event: hot and sunny, hot, hot or sunny, etc\n\nTypically we care about partial assignments like P(T = hot)\n\nMarginal Distributions are subtables which eliminate variables -- they combine collapsed rows by adding to do marginalization (summing out)\n\nConditional distributions are probability distributions over some variables given fixed values of others\n\nProbabilistic Inference -- compute a desired probability from other known probabilities (conditional from joint)\n\nGenerally compute conditional probabilities which represent agent's beliefs given evidence. Probabilities can also chance with new evidence\n\nInference by Enumeration: General case has evidence variables E_1, E_2, ... E_k = e_1, e_2, ... e_k. Also has query variable(s) Q, and hidden variables H_1,... H_r\n\nWe want to compute P(Q | e_1...e_k)\n\nStep 1: select entries consistent with evidence\n\nStep 2: P(Q,e_1...e_k) = sum over all (h1...h_r) of P(Q, h1...h_r, e1...e_k). -- sum out H to get joint of query and evidence\n\nStep 3: normalize by dividing by Z where Z is the sum over all q of(P(Q,e1...ek))\n\nProduct rule: P(y) * P(x|y) = P(x,y)\n\nChain rule: P(x1,x2,x3) = P(x1) * P(x2 | x1) * P(x3 | x1, x2)\n\nBayes rule: P(x|y) = P(y|x)/P(y) * P(x)\n\n**Probabilistic Language Models**\n\nGoal is to assign probability to a sequence -- autocomplete for texting, machine translation, spelling correction, speech recognition\n\nRelated task to this is computing the probability of an upcoming word -- a model that computes either of these is called a language model or LM\n\nP(W) = P(w1,w2,w3,w4,w5) -- this is probability of a sentence of sequence of words, P(w5|w1, w2, w3, w4) is probability of an upcoming word\n\nA model that computes either of these is a language model\n\nThe grammar is better but language model is standard\n\nJoin probability of words in a sentence involves chain rule of conditional probabilities\n\nHow to estimate these probabilities? Could we just count and divide --> Maximum Likelihood estimation (MLE)?\n\nThis doesn't work because with long phrases you oftentimes won't see those phrases much so you'll need huge inefficient datasets to make some queries work\n\nIn MLE, P(won | the underdog team) = COUNT(the underdog team won)/ COUNT(the underdog team)\n\nMarkov simplifying assumption\n\nOnly depend on current state and not long history of states that you've gone through\n\nIn this case, it only depends on the previous k words, and not the whole context\n\nP(w1w2w3...wn) = Product over all i up until n of (P(wi | w_{i-k} ... w_{i-1})\n\nThe type of gram determines how much history we should use: unigram-no history, bigram-1 word history, trigram-2 word history, 4-gram = 3 words history\n\nSimplest case is unigram model were each word is just considered on its own, and for n gram model we conditions on the previous n-1 words\n\nMLE estimates for bigram models: P(w_i | w_{i-1}) = count(w_{i-1}, w_i)/count(w_{i-1})\n\nBut MLE might give probability of 0 if its never seen the word before\n\nWe can normalize training data by replacing any word not in L with <unk>\n\nAvoid 0s with smoothing\n\nWe do everything in log space, we can avoid underflow and adding is faster than multiplying\n\nGoogle n-gram release\n\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "**Bayes' Nets**\\n\n",
        "Models are always simplifications and may not account for all interactions between variables\\n\n",
        "With probabilistic models, we need to reason about unknown variables, given evidence -- explanation v. prediction\\n\n",
        "Independence is a simplifying modeling assumption: empirical joint distributions are at best \"close\" to independent\\n\n",
        "*Conditional Independence* -- X is conditionally independent of Y given Z iff P(x,y|z) = P(x|z) * P(y|z) AKA P(x|z,y) = P(x|z) for all x,y,z\\n\n",
        "Chain rule would say P(Traffic, Rain, Umbrella) = P(Rain) * P(Traffic|Rain) * P(Umbrella | Rain, Traffic), but if we assume conditional independence between Traffic and Umbrella, P(Traffic, Rain, Umbrella) = P(Rain)*P(Traffic|Rain)*P(Umbrella|Rain)\\n\n",
        "Big picture of Bayes' Nets: Two problems with using full joint distribution tables as our probabilistic models -- 1) Way too big to represent explicitly, and 2) hard to estimate anything empirical about more than a few variables at a time\\n\n",
        "!) Bayes' nets are a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities) -- they are more properly called graphical models, describing how local variables interact and chain together to give global indirect interactions\\n\n",
        "Nodes are variables with domains and arcs are interactions\\n\n",
        "Semantics: set of nodes, one per variable X; DAG; conditional distribution for each node -- a collection of distributions over X, one for each combo of parents' values: P(X | a1...an), CPT: conditional probability table\\n\n",
        "A Bayes net = Topology(graph) + Local conditional probabilities\\n\n",
        "Probabilities in BNs: Bayes' nets implicitly encode joint distributions as a product of local conditional distributions\\n\n",
        "P(x1,x2,...xn) = Product of i going from 1 to n of (P(x_i | parents(X_i)))\\n\n",
        "We can guarantee that doing this results in a proper joint distribution because of the chain rule and then once we ASSUME conditional independence\\n\n",
        "Not every BN can represent every joint distribution -- the topology enforces certain conditional independencies\\n\n",
        "Causality: when Bayes' nets reflect the true causal pattern, it's often simpler, easier to think about, and easier to elicit from experts\\n\n",
        "BNs need not actually be causal -- sometimes no causal net exists over the domain espeically if variables are missing, you end up with arrows that reflect correlation, not causation\\n\n",
        "What do arrows really mean? Topology may happen to encode causal structure, but the Topology really encodes conditional independence: P(x_i | x1...xn) = P(x_i | parents(Xi))\\n\n",
        "Size of a BN: how big is a joint distribution with N variables -> 2^N\\n\n",
        "An N-node net if nodes have up to k parents is O(N * 2^{k+1})\\n\n",
        "Both give you the power to calculate P(X1, X2, ... , Xn) but BN has huge savings, and it is easier to elicit local CPTs and faster to answer queries\\n\n",
        "Assumptions of BN: often additional conditional independence assumptions that can be read off the graph\\m\n",
        "To model better, we need to understand the assumptions made when choosing a Bayes net graph\\n\n",
        "\n",
        "**D-separation**\\n\n",
        "Causal chain: the following configuration is a causal chain -- P(x,y,z) = P(x) * P(y | x) * P(z | y)\\n\n",
        "X is not guaranteed independent of Z here\\n\n",
        "However, it is guaranteed that X is independent of Z given Y because of the equation below:\\n\n",
        "P(z | x,y) = P(x,y,z)/P(x,y) = P(x) * P(y|x) * P(z | y) / P(x) / P(y|x) = P(z|y)\\n\n",
        "!) Evidence along the chain \"blocks\" the influence\\n\n",
        "Common cause: the following configuration is a common cause -- P(x,y,z) = P(y) * P(x|y) * P(z|y)\\n\n",
        "Guaranteed X is independent of Z? NO -- one example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed. P(+x | +y) = 1, P(-x | -y) = 1, P(+z | +y) = 1, P(-z|-y) = 1\\n\n",
        "However, for a common cause, we are guaranteed that X and Z are independent GIVEN Y -- !) observing the cause blocks influence between effects\\n\n",
        "Common effect -- v structure: P(x,y,z) = P(x) P(y) P(z | x,y)\\n\n",
        "X and Y are independent but X and Y are not independent given Z -- this is backwards from other cases. !) Observing an effect activates influence between possible causes\\n\n",
        "General Case: general question is that in a given BN, are two variables independent given evidence? -- solution is to analyze the graph and any complex example can be broken down into repetition of 3 canonical cases\\n\n",
        "Reachability: recipe is to shade evidence nodes and look for paths in the resulting graph. attempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent. almost works, but not quite becacuse it breaks with the v-structure becuase it doesn't count as a link in a path unless active\\n\n",
        "Now considering active/inactive paths -- Are X and Y conditionally independent given evidence variables {Z}?\\n\n",
        "Yes, if X and Y are \"d-separated\" by Z. Consider all undirected paths from X to Y, if there are no active paths, then independence\\n\n",
        "A path is active if each triple is active: Causal chain A->B->C where B is unobserved, Common cause A<-B->C where B is unobserved, Common effect (V-structure) A-> B <- C where B or one of its descendents is observed\\n\n",
        "All it takes to block a path is a single inactive segnment\\n\n",
        "D-separation: if we want to see if Xi and Xj are conditionally independent given X_k1 ... X_kn, we check all undirected paths between Xi and Xj. If one or more is active, then independence is not guaranteed, but if all paths are inactive, then independence is guaranteed.\\n\n",
        "Structure implications: Given a BN structure, can run d-separation algorithm to build a complete list of conditional independences that are necessarily true of the form Xi conditionally independent with Xj given Xk1, ... , Xkn\\b\n",
        "This list determines the set of probability distributions that can be represented\\n\n",
        "BN representation summary -- BN compactly encode joint distributions. Guaranteed independencies of distributions can be deduced from BN graph structure. D-separation gives precise conditional independence guarantees from graph alone. A BN joint distribution may have further (conditional) independence that is not detectable until you inspect its specific distribution\\n\n",
        "Inference: calculating some joint useful quantity from a joint probability distribution. Example, posterior probability = P(Q|E1 = e1...Ek = ek) and Most likely explanation = argmax over all q of P(Q = q | E1 = e1 ... )\\n\n",
        "Inference by enumeration in BN is similar to inference by enumeration normally\\n\n",
        "Select entries consistent with evidence, get joint of query and evidencce, and normalize\\n\n",
        "Given unlimited time, inference in BNs is easy\\n\n",
        "Inference by Enumeration vs. Variable elimination: inference by enumeration is slow because you join up the whole joint distribution before you sum out the hidden values\\n\n",
        "Variable elimination: interleaving joining and marginalizing, still NP-hard but usually much faster than inference by enumeration\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1838
        },
        "cellView": "form",
        "outputId": "a03257e4-e031-4148-a269-7c830b8bef56"
      },
      "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": 83,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \n**Bayes' Nets**\n\nModels are always simplifications and may not account for all interactions between variables\n\nWith probabilistic models, we need to reason about unknown variables, given evidence -- explanation v. prediction\n\nIndependence is a simplifying modeling assumption: empirical joint distributions are at best \"close\" to independent\n\n*Conditional Independence* -- X is conditionally independent of Y given Z iff P(x,y|z) = P(x|z) * P(y|z) AKA P(x|z,y) = P(x|z) for all x,y,z\n\nChain rule would say P(Traffic, Rain, Umbrella) = P(Rain) * P(Traffic|Rain) * P(Umbrella | Rain, Traffic), but if we assume conditional independence between Traffic and Umbrella, P(Traffic, Rain, Umbrella) = P(Rain)*P(Traffic|Rain)*P(Umbrella|Rain)\n\nBig picture of Bayes' Nets: Two problems with using full joint distribution tables as our probabilistic models -- 1) Way too big to represent explicitly, and 2) hard to estimate anything empirical about more than a few variables at a time\n\n!) Bayes' nets are a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities) -- they are more properly called graphical models, describing how local variables interact and chain together to give global indirect interactions\n\nNodes are variables with domains and arcs are interactions\n\nSemantics: set of nodes, one per variable X; DAG; conditional distribution for each node -- a collection of distributions over X, one for each combo of parents' values: P(X | a1...an), CPT: conditional probability table\n\nA Bayes net = Topology(graph) + Local conditional probabilities\n\nProbabilities in BNs: Bayes' nets implicitly encode joint distributions as a product of local conditional distributions\n\nP(x1,x2,...xn) = Product of i going from 1 to n of (P(x_i | parents(X_i)))\n\nWe can guarantee that doing this results in a proper joint distribution because of the chain rule and then once we ASSUME conditional independence\n\nNot every BN can represent every joint distribution -- the topology enforces certain conditional independencies\n\nCausality: when Bayes' nets reflect the true causal pattern, it's often simpler, easier to think about, and easier to elicit from experts\n\nBNs need not actually be causal -- sometimes no causal net exists over the domain espeically if variables are missing, you end up with arrows that reflect correlation, not causation\n\nWhat do arrows really mean? Topology may happen to encode causal structure, but the Topology really encodes conditional independence: P(x_i | x1...xn) = P(x_i | parents(Xi))\n\nSize of a BN: how big is a joint distribution with N variables -> 2^N\n\nAn N-node net if nodes have up to k parents is O(N * 2^{k+1})\n\nBoth give you the power to calculate P(X1, X2, ... , Xn) but BN has huge savings, and it is easier to elicit local CPTs and faster to answer queries\n\nAssumptions of BN: often additional conditional independence assumptions that can be read off the graph\\m\nTo model better, we need to understand the assumptions made when choosing a Bayes net graph\n\n\n**D-separation**\n\nCausal chain: the following configuration is a causal chain -- P(x,y,z) = P(x) * P(y | x) * P(z | y)\n\nX is not guaranteed independent of Z here\n\nHowever, it is guaranteed that X is independent of Z given Y because of the equation below:\n\nP(z | x,y) = P(x,y,z)/P(x,y) = P(x) * P(y|x) * P(z | y) / P(x) / P(y|x) = P(z|y)\n\n!) Evidence along the chain \"blocks\" the influence\n\nCommon cause: the following configuration is a common cause -- P(x,y,z) = P(y) * P(x|y) * P(z|y)\n\nGuaranteed X is independent of Z? NO -- one example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed. P(+x | +y) = 1, P(-x | -y) = 1, P(+z | +y) = 1, P(-z|-y) = 1\n\nHowever, for a common cause, we are guaranteed that X and Z are independent GIVEN Y -- !) observing the cause blocks influence between effects\n\nCommon effect -- v structure: P(x,y,z) = P(x) P(y) P(z | x,y)\n\nX and Y are independent but X and Y are not independent given Z -- this is backwards from other cases. !) Observing an effect activates influence between possible causes\n\nGeneral Case: general question is that in a given BN, are two variables independent given evidence? -- solution is to analyze the graph and any complex example can be broken down into repetition of 3 canonical cases\n\nReachability: recipe is to shade evidence nodes and look for paths in the resulting graph. attempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent. almost works, but not quite becacuse it breaks with the v-structure becuase it doesn't count as a link in a path unless active\n\nNow considering active/inactive paths -- Are X and Y conditionally independent given evidence variables {Z}?\n\nYes, if X and Y are \"d-separated\" by Z. Consider all undirected paths from X to Y, if there are no active paths, then independence\n\nA path is active if each triple is active: Causal chain A->B->C where B is unobserved, Common cause A<-B->C where B is unobserved, Common effect (V-structure) A-> B <- C where B or one of its descendents is observed\n\nAll it takes to block a path is a single inactive segnment\n\nD-separation: if we want to see if Xi and Xj are conditionally independent given X_k1 ... X_kn, we check all undirected paths between Xi and Xj. If one or more is active, then independence is not guaranteed, but if all paths are inactive, then independence is guaranteed.\n\nStructure implications: Given a BN structure, can run d-separation algorithm to build a complete list of conditional independences that are necessarily true of the form Xi conditionally independent with Xj given Xk1, ... , Xkn\b\nThis list determines the set of probability distributions that can be represented\n\nBN representation summary -- BN compactly encode joint distributions. Guaranteed independencies of distributions can be deduced from BN graph structure. D-separation gives precise conditional independence guarantees from graph alone. A BN joint distribution may have further (conditional) independence that is not detectable until you inspect its specific distribution\n\nInference: calculating some joint useful quantity from a joint probability distribution. Example, posterior probability = P(Q|E1 = e1...Ek = ek) and Most likely explanation = argmax over all q of P(Q = q | E1 = e1 ... )\n\nInference by enumeration in BN is similar to inference by enumeration normally\n\nSelect entries consistent with evidence, get joint of query and evidencce, and normalize\n\nGiven unlimited time, inference in BNs is easy\n\nInference by Enumeration vs. Variable elimination: inference by enumeration is slow because you join up the whole joint distribution before you sum out the hidden values\n\nVariable elimination: interleaving joining and marginalizing, still NP-hard but usually much faster than inference by enumeration\n\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "**Classification Tasks**\\n\n",
        "Instead of joint probability table, decompose into smaller tables --> Bayesian Networks\\n\n",
        "How do we get the probability values? Up until now, it'sbeen how use a model to make optimal decisions\\n\n",
        "Machine learning tells us how to acquire a model from data/experience. Learning parameters (probabilities), structure (eg BN graphs), hidden concepts (eg clustering)\\n\n",
        "Model based classification with naive bayes and perceptrons\\n\n",
        "Model based = uses a probability based model\\n\n",
        "Classification: input of our system is a feature vector, depending on what our output is, we either do classification or regression. For ML, we will have a set of data with labels, and then learn a function which takes a new entry and predicts/classifies\\n\n",
        "Transform to vector representation where each vector corresponds to a feature\\n\n",
        "Digit recognition and spam email classification problems are classification\\n\n",
        "Take raw input of pixels and have vectors for digit classification, also number of loops, etc\\n\n",
        "Given inputs x, predict labels y\\n\n",
        "Model-based classification\\n\n",
        "build a model where both the label and features are random variables, each input is a RV, instantiate all observed features and the query the model.\\n\n",
        "What kind of relationship between RVs should there be, what's the structure? How do we collect probabilities?\\n\n",
        "\n",
        "**Naive Bayes**\\n\n",
        "Naive: assume all the features that we use to represent inputs are independent of each other and only dependent on the label\\n\n",
        "How do we construct a BN for naive bayes? Class variable Y has no parents, and for each feature, we have a probability of that feature given the parents, and the only parent is Y (the class variable)\\n\n",
        "Naive bayes says probability given features is proportional to prior value of label and the product of each of the conditional probabilities\\n\n",
        "GENERAL NAIVE BAYES MODEL: P(Y, F1 ... Fn) = P(Y) * product over all i (P(F_i | Y))\\n\n",
        "|Y| times |F|^n values\\n\n",
        "We only have to specify how each feature depends on the class\\n\n",
        "Total number of parameters is linear in number of features\\n\n",
        "Model is very simplistic but often works anyway even though we make super strong simplifying assumptions\\n\n",
        "We can estimate parameters in a pretty effective way\\n\n",
        "Inference for Naive Bayes: Goal: compute posterior distribution over label variable Y\\n\n",
        "Step 1: get joint probability of label and evidence for each label. Get P(y1,f1...fn), P(y2,f1...fn), ... P(yk,f1...fn)\\n\n",
        "Step 2: sum to get probability of evidence P(f1...fn)\\n\n",
        "Step 3: Normalize by dividing step 1 and step 2 --> P(Y | f1...fn)\\n\n",
        "What do we need in order to use Naive Bayes? Inference method (we just saw this) -- start with probabilities P(Y) and P(F_i | Y) tables, then use standard inference to compute P(Y|f1...fn\\n\n",
        "The other thing we need is the estimates of local conditional probability tables -- P(Y), and P(F_i | Y), these are parameters we will denote by theta\\n\n",
        "Until now, we assumed these appeared by magic, but they come from training data counts\\n\n",
        "\n",
        "**Basic concepts for ML**\\n\n",
        "Training and testing, at training we have labels but for testing we don't\\n\n",
        "Partition training data into training data, test data, and held out data, where if we have hyperparameters, we will optimize those on held out set\\n\n",
        "Use training set for parameters, learn hyperparameters for held out data, and run it on test data and have evaluation function\\n\n",
        "Don't want overfitting, for example if we take a product and one of the things is 0 for no reason, the whole thing will be 0. \\n\n",
        "Relative frewuency parameters will overfit the training data, just because we didn't see something in training data doesn't mean we won't see it at all\\n\n",
        "Want to avoid giving things you've never seen before zero probability, so you smooth or regularize the data\\n\n",
        "Parameter estimation: estimating the distribution of a random variable -- one way is to ask an expert / human, another way is to do it empirically / using training data\\n\n",
        "Use MLE estimation for training data -- compute which theta is best by computing which one maximizes the likelihood of that data\\n\n",
        "L(x, theta) = product over all i of P_theta(x_i)\\n\n",
        "Parameter settings of our model are going to be pick the parameter settings that maximize likelihood of data given those parameter settings, which is the argmax over all theta of the product over all i of P_theta(x_i)\\n\n",
        "Unseen events: avoid zero probabilities, and use smoothing like LaPlace smoothing -- pretend like you saw everything one more time than you actually did\\n\n",
        "Hyperparameter -- instead of adding 1, we can add LaPlace with some value k, and k is the strength of the prior\\n\n",
        "P_LAP,k(x|y) = (c(x,y) + k) / (c(y) + k|X|)\\n\n",
        "another technique to avoid 0 probabilities is interpolation\\n\n",
        "When we estimate conditional, use observed MLE, and then back out to a prior for some amount of it\\n\n",
        "Have a second hyperparameter -- k of how much to smooth, and alpha of how much to weight the conditional vs. the prior\\n\n",
        "What if alpha is 0, no weight to conditional, all to prior, and if alpha is 1, its reversed\\n\n",
        "If we have hyperparameters like k and alpha, how do we tune model?\\n\n",
        "How to pick best value of parameters and hyperparameters\\n\n",
        "Learn parameters from training data, hyperparameters from held out data because we will lose nice features if we do the hyperparameters also on the training data\\n\n",
        "Choose best value and do a final test on the test data\\n\n",
        "We can also improve models by thinking of other features\\n\n",
        "First step: get a baseline. Pick a simple baseline and then help determine how hard the task is, which helps know what a good accuracy is\\n\n",
        "Weak baseline: most frequent label classifier\\n\n",
        "For real research, usually use previous work as a baseline\\n\n",
        "\n",
        "**Perceptron**\\n\n",
        "Naive Bayes is model based classifier\\n\n",
        "Perceptrons developed in 1950s loosely inspired by the neuron\\n\n",
        "Dendrites are input to neuron, transmits output to other neurons\\n\n",
        "!) Accept a bunch of inputs, combine into an activation function, transmit\\n\n",
        "Perceptron takes weighted sum of all inputs and decides whether or not to transmit the output\\n\n",
        "Can think about perceptron or the sigmoid neuron as a device that makes decisions by weighing up evidence\\n\n",
        "Can vary weights and thresholds\\n\n",
        "Notation changes -- change 1 is writing as a dotproduct of input vector and weight vector, change 2 is move threshold to other side of the equality and call that term the bias\\n\n",
        "Think of bias as a measure of how easy it is to get the perceptron to output 1 / how easy it is to fire \\n\n",
        "What are manipulations to learn a good parameterization?\\n\n",
        "We try to learn the weight factor. Think of inputs as features representing something we want to classify. The feature avlues for inputs are fixed, but we can choose different weight vectors. Depending on the weight vector that we pick, we will get a different classifier\\n\n",
        "Bias allows us to move decision boundary around\\n\n",
        "Weight updates -- based on error driven learning. Start with weight vector where all are set to 0. Then for each training instance, classify with current weights, if correct keep the weights, if not, update weights so that they are closer\\n\n",
        "we can use this for binary or multiclass, for multiclass its have a weight vector for each class\\n\n",
        "Calculate activation score of all classes, and prediction with highest score wins\\n\n",
        "To learn the weights, nudge the weights whenever it's incorrect\\n\n",
        "\n",
        "**Improvements on Perceptrons and SVM**\\n\n",
        "If data is linearly separable, then we're guaranteed to converge on a set of parameters\\n\n",
        "If it's not, then we can come up with a bound on number of mistakes that algorithm will end up with -- for a binary classifier, we can bound it by k / (margin)^2\\n\n",
        "Margin is distance between positive and negative classes\\n\n",
        "Problems w perceptron -- weights might thrash if data isn't seperable, can average weights over time to help\\n\n",
        "Another proble. is even if you can separate, you might have a \"barely\" separating solution\\n\n",
        "Last one is that you can overtrain and training accuracy can go up but then go down\\n\n",
        "TO fix the perceptron, we can use some algos\\n\n",
        "MIRA = margin infused relaxed algorithm, instead of updating weights by a big amount every time, update by just enough to fix current mistake and more\\n\n",
        "Scale the incorrect guess by tau when you update weight vector\\n\n",
        "Get maximum step size\\n\n",
        "Support vector machine (SVM)\\n\n",
        "Draw 2 support vectors and maximize the margin between them. Only support vectors matter, help you find the boundary between 2 classes\\n\n",
        "NOnlinear separators, data that is linearly separable works out great for linear decision rules, but what are we going to do if the dataset is just too hard\\n\n",
        "Can shift data into a higher dimension, kernel trick is to transform input into different dimensions, squaring or figuring out distance from origin etc\\n\n",
        "\n",
        "**Summary**\\n\n",
        "Naive Bayes: builds a model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data (counting)\\n\n",
        "Perceptrons/MIRA: makes less assumptions about data, mistake-driven learning, multiple passes through data (prediction), often more accurate\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 84,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3544
        },
        "cellView": "form",
        "outputId": "a67be104-bc2a-4cf3-c41f-cf30eecaabfa"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 85,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n**Classification Tasks**\n\nInstead of joint probability table, decompose into smaller tables --> Bayesian Networks\n\nHow do we get the probability values? Up until now, it'sbeen how use a model to make optimal decisions\n\nMachine learning tells us how to acquire a model from data/experience. Learning parameters (probabilities), structure (eg BN graphs), hidden concepts (eg clustering)\n\nModel based classification with naive bayes and perceptrons\n\nModel based = uses a probability based model\n\nClassification: input of our system is a feature vector, depending on what our output is, we either do classification or regression. For ML, we will have a set of data with labels, and then learn a function which takes a new entry and predicts/classifies\n\nTransform to vector representation where each vector corresponds to a feature\n\nDigit recognition and spam email classification problems are classification\n\nTake raw input of pixels and have vectors for digit classification, also number of loops, etc\n\nGiven inputs x, predict labels y\n\nModel-based classification\n\nbuild a model where both the label and features are random variables, each input is a RV, instantiate all observed features and the query the model.\n\nWhat kind of relationship between RVs should there be, what's the structure? How do we collect probabilities?\n\n\n**Naive Bayes**\n\nNaive: assume all the features that we use to represent inputs are independent of each other and only dependent on the label\n\nHow do we construct a BN for naive bayes? Class variable Y has no parents, and for each feature, we have a probability of that feature given the parents, and the only parent is Y (the class variable)\n\nNaive bayes says probability given features is proportional to prior value of label and the product of each of the conditional probabilities\n\nGENERAL NAIVE BAYES MODEL: P(Y, F1 ... Fn) = P(Y) * product over all i (P(F_i | Y))\n\n|Y| times |F|^n values\n\nWe only have to specify how each feature depends on the class\n\nTotal number of parameters is linear in number of features\n\nModel is very simplistic but often works anyway even though we make super strong simplifying assumptions\n\nWe can estimate parameters in a pretty effective way\n\nInference for Naive Bayes: Goal: compute posterior distribution over label variable Y\n\nStep 1: get joint probability of label and evidence for each label. Get P(y1,f1...fn), P(y2,f1...fn), ... P(yk,f1...fn)\n\nStep 2: sum to get probability of evidence P(f1...fn)\n\nStep 3: Normalize by dividing step 1 and step 2 --> P(Y | f1...fn)\n\nWhat do we need in order to use Naive Bayes? Inference method (we just saw this) -- start with probabilities P(Y) and P(F_i | Y) tables, then use standard inference to compute P(Y|f1...fn\n\nThe other thing we need is the estimates of local conditional probability tables -- P(Y), and P(F_i | Y), these are parameters we will denote by theta\n\nUntil now, we assumed these appeared by magic, but they come from training data counts\n\n\n**Basic concepts for ML**\n\nTraining and testing, at training we have labels but for testing we don't\n\nPartition training data into training data, test data, and held out data, where if we have hyperparameters, we will optimize those on held out set\n\nUse training set for parameters, learn hyperparameters for held out data, and run it on test data and have evaluation function\n\nDon't want overfitting, for example if we take a product and one of the things is 0 for no reason, the whole thing will be 0. \n\nRelative frewuency parameters will overfit the training data, just because we didn't see something in training data doesn't mean we won't see it at all\n\nWant to avoid giving things you've never seen before zero probability, so you smooth or regularize the data\n\nParameter estimation: estimating the distribution of a random variable -- one way is to ask an expert / human, another way is to do it empirically / using training data\n\nUse MLE estimation for training data -- compute which theta is best by computing which one maximizes the likelihood of that data\n\nL(x, theta) = product over all i of P_theta(x_i)\n\nParameter settings of our model are going to be pick the parameter settings that maximize likelihood of data given those parameter settings, which is the argmax over all theta of the product over all i of P_theta(x_i)\n\nUnseen events: avoid zero probabilities, and use smoothing like LaPlace smoothing -- pretend like you saw everything one more time than you actually did\n\nHyperparameter -- instead of adding 1, we can add LaPlace with some value k, and k is the strength of the prior\n\nP_LAP,k(x|y) = (c(x,y) + k) / (c(y) + k|X|)\n\nanother technique to avoid 0 probabilities is interpolation\n\nWhen we estimate conditional, use observed MLE, and then back out to a prior for some amount of it\n\nHave a second hyperparameter -- k of how much to smooth, and alpha of how much to weight the conditional vs. the prior\n\nWhat if alpha is 0, no weight to conditional, all to prior, and if alpha is 1, its reversed\n\nIf we have hyperparameters like k and alpha, how do we tune model?\n\nHow to pick best value of parameters and hyperparameters\n\nLearn parameters from training data, hyperparameters from held out data because we will lose nice features if we do the hyperparameters also on the training data\n\nChoose best value and do a final test on the test data\n\nWe can also improve models by thinking of other features\n\nFirst step: get a baseline. Pick a simple baseline and then help determine how hard the task is, which helps know what a good accuracy is\n\nWeak baseline: most frequent label classifier\n\nFor real research, usually use previous work as a baseline\n\n\n**Perceptron**\n\nNaive Bayes is model based classifier\n\nPerceptrons developed in 1950s loosely inspired by the neuron\n\nDendrites are input to neuron, transmits output to other neurons\n\n!) Accept a bunch of inputs, combine into an activation function, transmit\n\nPerceptron takes weighted sum of all inputs and decides whether or not to transmit the output\n\nCan think about perceptron or the sigmoid neuron as a device that makes decisions by weighing up evidence\n\nCan vary weights and thresholds\n\nNotation changes -- change 1 is writing as a dotproduct of input vector and weight vector, change 2 is move threshold to other side of the equality and call that term the bias\n\nThink of bias as a measure of how easy it is to get the perceptron to output 1 / how easy it is to fire \n\nWhat are manipulations to learn a good parameterization?\n\nWe try to learn the weight factor. Think of inputs as features representing something we want to classify. The feature avlues for inputs are fixed, but we can choose different weight vectors. Depending on the weight vector that we pick, we will get a different classifier\n\nBias allows us to move decision boundary around\n\nWeight updates -- based on error driven learning. Start with weight vector where all are set to 0. Then for each training instance, classify with current weights, if correct keep the weights, if not, update weights so that they are closer\n\nwe can use this for binary or multiclass, for multiclass its have a weight vector for each class\n\nCalculate activation score of all classes, and prediction with highest score wins\n\nTo learn the weights, nudge the weights whenever it's incorrect\n\n\n**Improvements on Perceptrons and SVM**\n\nIf data is linearly separable, then we're guaranteed to converge on a set of parameters\n\nIf it's not, then we can come up with a bound on number of mistakes that algorithm will end up with -- for a binary classifier, we can bound it by k / (margin)^2\n\nMargin is distance between positive and negative classes\n\nProblems w perceptron -- weights might thrash if data isn't seperable, can average weights over time to help\n\nAnother proble. is even if you can separate, you might have a \"barely\" separating solution\n\nLast one is that you can overtrain and training accuracy can go up but then go down\n\nTO fix the perceptron, we can use some algos\n\nMIRA = margin infused relaxed algorithm, instead of updating weights by a big amount every time, update by just enough to fix current mistake and more\n\nScale the incorrect guess by tau when you update weight vector\n\nGet maximum step size\n\nSupport vector machine (SVM)\n\nDraw 2 support vectors and maximize the margin between them. Only support vectors matter, help you find the boundary between 2 classes\n\nNOnlinear separators, data that is linearly separable works out great for linear decision rules, but what are we going to do if the dataset is just too hard\n\nCan shift data into a higher dimension, kernel trick is to transform input into different dimensions, squaring or figuring out distance from origin etc\n\n\n**Summary**\n\nNaive Bayes: builds a model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data (counting)\n\nPerceptrons/MIRA: makes less assumptions about data, mistake-driven learning, multiple passes through data (prediction), often more accurate\n\n\n\n\n\n\n\n \n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "\n",
        "**Logistic Regression**\\n\n",
        "Type of classifier similar to perceptron\\n\n",
        "Supervised ML problem with: feature representation, classification function, objective function, and optimizing the objective function\\n\n",
        "Feature engineering is trying to build features that will correctly represent the situation\\n\n",
        "Before, if we wanted to build a faster model, we would try to pick the best features, but nowadays we want to change structure of NN itself\\n\n",
        "Objective function is referred to as a loss function and we want to minimize error on training examples\\n\n",
        "Sentiment classifier: encode review into a way that classifier can use -- variant of perceptron\\n\n",
        "Go through each of the elements and multiply by weight and add bias, equivalent to dot product\\n\n",
        "Squish value using the sigmoid function, and if the sigmoid is > 1/2, predict 1 and if not, predict 0\\n\n",
        "1/2 ends up being the decision boundary here, but we can change it\\n\n",
        "Now we need to extract features to represent each training item\\n\n",
        "For a piece of text, some features are -- positive lexicon words, negative lexicon words, whether or not no appears, first and second person pronouns, whether exclamation appears, log of the word count\\n\n",
        "Then we want to associate weights with each of the features\\n\n",
        "How do we get the weight values? Different than in perceptron\\n\n",
        "1) get an objective or loss function that tells us the distance between the system output and gold output, we use cross entropy loss. 2) an algorithm for optimizing the objective function, we will use stochastic gradient descent to minimize the loss function\\n\n",
        "\n",
        "**Loss functions**\\n\n",
        "Lots of families of loss functions\\n\n",
        "goal is to determine how close the gold standard is to what we predict\\n\n",
        "One example is Mean squared error, take difference between prediction and truth and square it\\n\n",
        "But this is hard to optimize, and it is non convex when applied to probabilistic classification\\n\n",
        "Loss functions for probabilistic classification -- we use a loss function that prefers the correct class labels of the training example to be more likely.\\n\n",
        "Conditional MLE: choose parameters w, b to maximize the log probabilities of the true labels in the training data\\n\n",
        "The rresulting loss function is the negative log likelihodd loss, or cross entropy loss\\n\n",
        "Want to maximize probability of true label Y given X. Maximize P(y | x) = y_hat ^ y * (1 - y_hat)^(1-y)\\n\n",
        "This works because y is either 1 or 0\\n\n",
        "When it's a positive case, we want y_hat to be as large as possible, when it is a negative case, we want 1 - y_hat to be as large as possible\\n\n",
        "Change this to log space -- still maximizing, this tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we'll flip the signs\\n\n",
        "Result is cross entropy loss\\n\n",
        "We want to minimize loss on all training examples\\n\n",
        "\n",
        "**Stochastic Gradient Descent**\\n\n",
        "Want to find parameters, theta, that will minimize the CE loss over all examples\\n\n",
        "Gradient descent is a method that finds a minimum of a function by figuring out in which direction, in the space of the parameters theta) the function's slope is rising the most steeeply, and moving in the opposite direction.\\n\n",
        "You're in a canyon, you want to get down to a river quickest, want to go in the direction that will help you go down the furthest\\n\n",
        "For logistic regression, this loss function is conveniently convex\\n\n",
        "Convex function has 1 minimum, so a gradient descent will find that minimum\\n\n",
        "How much should we update the parameter by? Weight at each time step is going to be previous time step weight - learning rate -- slope is derivative of loss function with respect to weight\\n\n",
        "This is convex optimization -- one minimum, but there can be other ones\\n\n",
        "If step size is too big, you might step over minimum and step back and never hit it -- over time, you might want to descrease the step size\\n\n",
        "Now, we want to see how this extends to many dimensions where we have weight, loss function, and bias term\\n\n",
        "Each feature is going to be a dimension, and we want to see how a small change over any of these dimensions impacts the loss function\\n\n",
        "We want to take the partial derivative with respect to weight_i of the loss function for each of the weights, and this gives us a new vector, and the new set of parameters at time step t+1 is the parameters at timestep t - learning rate * this derivative vector\\n\n",
        "Mini batch training -- stochastic gradient descent chooses a single random example at a time and updates its weights on that example -- alternative is batch training which computes gradient over entire dataset, which gives better estimate of what direction to. move\\n\n",
        "Good compromise is mini batch training\\n\n",
        "Regularization: overfitting is a problem, we want to penalize large weights -- a regularization term is added to the loss function, lasso regression uses L1 regularization, Ridge uses L2\\n\n",
        "Softmax -- function which takes in an input vector and outputs a vector of values normalized into probabilities\\n\n",
        "\n",
        "**Neural Networks**\\n\n",
        "Percceptrons were developed in the 1950s and 1960s, loosely inspired by the neuron\\n\n",
        "Neural networks -- the building block of a neural network is a single computational input which takes in a set of real valued numbers as input and performs a computation\\n\n",
        "Input vector goes into the neuron and then the output gets produced\\n\n",
        "Neural networks have input layers, and then some hidden layers and then output layer\\n\n",
        "Perceptron -> logistic regression -- Like the pereptron, logistic regression uses a vector of ewights and bias term, but instead of outputting z directly, logistic regression TRANSFORMS it with the sigmoid function\\n\n",
        "Problem with perceptron is that a small change in the weights or bias of any single pereptron in the network can cause the output to flip from 0 to 1 --> solution is sigmoid neuron\\n\n",
        "Smoothness is crucial: smoothness of sigmoid function means that small changed in the weights and the bias will produce a small change in the output from the neuron\\n\n",
        "This makes it easy to choose small changes in weights and biases to achieve any desired small change in the output\\n\n",
        "Activation function: instead of just outputting z = wx + b, neuron units apply non-linear function f to z, and the result is the activation value for the unit\\n\n",
        "Sigmoid, tanh, and relu are all examples of activation functions\\n\n",
        "Feed forward NN -- simplest kind of NN, multilayer network where all units are fully connected and there are no cycles\\n\n",
        "No outputs are ever passed to lower layers in FF NN\\n\n",
        "Equations for a FF network: single hidden unit has parameters w and b, and we represent parameters for an entire layer by combining the weight vector w_i and bias b_i for each unit i into a single weight matrix W and a single bias vector b for the whole layer\\n\n",
        "better to use a single matrix W for the weights of the entire layer bc the hidden layer computation can be done efficiently with simple matrix operations -- 3 steps: 1) multiply the weight matrix by input vector, 2) add bias vector, 3) apply activation function\\n\n",
        "Output of hidden layer is the vector h, which is h = sigmoid(Wx + b)\\n\n",
        "Then, once we get to the output layer, which itself has a weight vector U, we can compute z = U * h where h is the input vector to the output layer, and say y = softmax(z) to normalize the output and turn it into a probability distribution\\n\n",
        "Training Neural Nets -- to get the best parameters, we need a loss function: cross entropy loss, an optimization algorithm: gradient descent, and a way of computing the gradient of the loss function: error propagation\\n\n",
        "Cross entropy loss -- if the neural network is a binary classifier, with a sigmoid at the final layer, the loss function is the same as we saw in logistic regression:\\n\n",
        "L_CE(y_hat, y) = -log p(y|x) = -[y log(y_hat) + (1-y)log(1-y_hat)]\\n\n",
        "For multinomial classification, it's the sum over all classes of y_i log(y_i_hat), and negate that all at the end\\n\n",
        "If there is only one correct answer, where the truth is y_i = 1, it simplifies to -log(y_i_hat)\\n\n",
        "To compute gradient in logistic regression, its (sigmoig(wx + b) - y)x_j, but those derivatives only give correct updates for last layer\\n\n",
        "For deeper networks, you need to look back through all earlier layers in network which can be done using error backpropagation algorithm\\n\n",
        "Computation graphs -- although backpropagation was made for neural nets, it is related to a general procedure called backward differentiation, which depends on the notion of computation graphs, which represents process of computing mathematical expression using separate operations which are nodes in a graph\\n\n",
        "Backward differentiation -- the importance of computation grpah comes from backward pass, used to compute derivatives we need. Backwards differentiatino uses the chain rule from calculus\\n\n",
        "LEARN HOW TO DO BACKWARDS PASS AND COMPUTATION GRAPH FOR NN\\n\n",
        "Summary: like with logistic regression, we learn the best parameters for the neural net to make predictions y_hat as close to possible as the gold standard labels in our training data y\\n\n",
        "We use 1) cross entropy loss function, 2) gradient descent to perform optimization, and 3) error back propagation to compute gradient of loss function\\n\n",
        "Since NN combine perceptron like neural units, we have many more parameters in the models (weights and biases). This allows us to trian systems to perform even more sophisticated tasks\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 86,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3154
        },
        "cellView": "form",
        "outputId": "e21ce9c2-1bf2-43b9-aac8-1d9270e54939"
      },
      "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": 87,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n**Logistic Regression**\n\nType of classifier similar to perceptron\n\nSupervised ML problem with: feature representation, classification function, objective function, and optimizing the objective function\n\nFeature engineering is trying to build features that will correctly represent the situation\n\nBefore, if we wanted to build a faster model, we would try to pick the best features, but nowadays we want to change structure of NN itself\n\nObjective function is referred to as a loss function and we want to minimize error on training examples\n\nSentiment classifier: encode review into a way that classifier can use -- variant of perceptron\n\nGo through each of the elements and multiply by weight and add bias, equivalent to dot product\n\nSquish value using the sigmoid function, and if the sigmoid is > 1/2, predict 1 and if not, predict 0\n\n1/2 ends up being the decision boundary here, but we can change it\n\nNow we need to extract features to represent each training item\n\nFor a piece of text, some features are -- positive lexicon words, negative lexicon words, whether or not no appears, first and second person pronouns, whether exclamation appears, log of the word count\n\nThen we want to associate weights with each of the features\n\nHow do we get the weight values? Different than in perceptron\n\n1) get an objective or loss function that tells us the distance between the system output and gold output, we use cross entropy loss. 2) an algorithm for optimizing the objective function, we will use stochastic gradient descent to minimize the loss function\n\n\n**Loss functions**\n\nLots of families of loss functions\n\ngoal is to determine how close the gold standard is to what we predict\n\nOne example is Mean squared error, take difference between prediction and truth and square it\n\nBut this is hard to optimize, and it is non convex when applied to probabilistic classification\n\nLoss functions for probabilistic classification -- we use a loss function that prefers the correct class labels of the training example to be more likely.\n\nConditional MLE: choose parameters w, b to maximize the log probabilities of the true labels in the training data\n\nThe rresulting loss function is the negative log likelihodd loss, or cross entropy loss\n\nWant to maximize probability of true label Y given X. Maximize P(y | x) = y_hat ^ y * (1 - y_hat)^(1-y)\n\nThis works because y is either 1 or 0\n\nWhen it's a positive case, we want y_hat to be as large as possible, when it is a negative case, we want 1 - y_hat to be as large as possible\n\nChange this to log space -- still maximizing, this tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we'll flip the signs\n\nResult is cross entropy loss\n\nWe want to minimize loss on all training examples\n\n\n**Stochastic Gradient Descent**\n\nWant to find parameters, theta, that will minimize the CE loss over all examples\n\nGradient descent is a method that finds a minimum of a function by figuring out in which direction, in the space of the parameters theta) the function's slope is rising the most steeeply, and moving in the opposite direction.\n\nYou're in a canyon, you want to get down to a river quickest, want to go in the direction that will help you go down the furthest\n\nFor logistic regression, this loss function is conveniently convex\n\nConvex function has 1 minimum, so a gradient descent will find that minimum\n\nHow much should we update the parameter by? Weight at each time step is going to be previous time step weight - learning rate -- slope is derivative of loss function with respect to weight\n\nThis is convex optimization -- one minimum, but there can be other ones\n\nIf step size is too big, you might step over minimum and step back and never hit it -- over time, you might want to descrease the step size\n\nNow, we want to see how this extends to many dimensions where we have weight, loss function, and bias term\n\nEach feature is going to be a dimension, and we want to see how a small change over any of these dimensions impacts the loss function\n\nWe want to take the partial derivative with respect to weight_i of the loss function for each of the weights, and this gives us a new vector, and the new set of parameters at time step t+1 is the parameters at timestep t - learning rate * this derivative vector\n\nMini batch training -- stochastic gradient descent chooses a single random example at a time and updates its weights on that example -- alternative is batch training which computes gradient over entire dataset, which gives better estimate of what direction to. move\n\nGood compromise is mini batch training\n\nRegularization: overfitting is a problem, we want to penalize large weights -- a regularization term is added to the loss function, lasso regression uses L1 regularization, Ridge uses L2\n\nSoftmax -- function which takes in an input vector and outputs a vector of values normalized into probabilities\n\n\n**Neural Networks**\n\nPercceptrons were developed in the 1950s and 1960s, loosely inspired by the neuron\n\nNeural networks -- the building block of a neural network is a single computational input which takes in a set of real valued numbers as input and performs a computation\n\nInput vector goes into the neuron and then the output gets produced\n\nNeural networks have input layers, and then some hidden layers and then output layer\n\nPerceptron -> logistic regression -- Like the pereptron, logistic regression uses a vector of ewights and bias term, but instead of outputting z directly, logistic regression TRANSFORMS it with the sigmoid function\n\nProblem with perceptron is that a small change in the weights or bias of any single pereptron in the network can cause the output to flip from 0 to 1 --> solution is sigmoid neuron\n\nSmoothness is crucial: smoothness of sigmoid function means that small changed in the weights and the bias will produce a small change in the output from the neuron\n\nThis makes it easy to choose small changes in weights and biases to achieve any desired small change in the output\n\nActivation function: instead of just outputting z = wx + b, neuron units apply non-linear function f to z, and the result is the activation value for the unit\n\nSigmoid, tanh, and relu are all examples of activation functions\n\nFeed forward NN -- simplest kind of NN, multilayer network where all units are fully connected and there are no cycles\n\nNo outputs are ever passed to lower layers in FF NN\n\nEquations for a FF network: single hidden unit has parameters w and b, and we represent parameters for an entire layer by combining the weight vector w_i and bias b_i for each unit i into a single weight matrix W and a single bias vector b for the whole layer\n\nbetter to use a single matrix W for the weights of the entire layer bc the hidden layer computation can be done efficiently with simple matrix operations -- 3 steps: 1) multiply the weight matrix by input vector, 2) add bias vector, 3) apply activation function\n\nOutput of hidden layer is the vector h, which is h = sigmoid(Wx + b)\n\nThen, once we get to the output layer, which itself has a weight vector U, we can compute z = U * h where h is the input vector to the output layer, and say y = softmax(z) to normalize the output and turn it into a probability distribution\n\nTraining Neural Nets -- to get the best parameters, we need a loss function: cross entropy loss, an optimization algorithm: gradient descent, and a way of computing the gradient of the loss function: error propagation\n\nCross entropy loss -- if the neural network is a binary classifier, with a sigmoid at the final layer, the loss function is the same as we saw in logistic regression:\n\nL_CE(y_hat, y) = -log p(y|x) = -[y log(y_hat) + (1-y)log(1-y_hat)]\n\nFor multinomial classification, it's the sum over all classes of y_i log(y_i_hat), and negate that all at the end\n\nIf there is only one correct answer, where the truth is y_i = 1, it simplifies to -log(y_i_hat)\n\nTo compute gradient in logistic regression, its (sigmoig(wx + b) - y)x_j, but those derivatives only give correct updates for last layer\n\nFor deeper networks, you need to look back through all earlier layers in network which can be done using error backpropagation algorithm\n\nComputation graphs -- although backpropagation was made for neural nets, it is related to a general procedure called backward differentiation, which depends on the notion of computation graphs, which represents process of computing mathematical expression using separate operations which are nodes in a graph\n\nBackward differentiation -- the importance of computation grpah comes from backward pass, used to compute derivatives we need. Backwards differentiatino uses the chain rule from calculus\n\nLEARN HOW TO DO BACKWARDS PASS AND COMPUTATION GRAPH FOR NN\n\nSummary: like with logistic regression, we learn the best parameters for the neural net to make predictions y_hat as close to possible as the gold standard labels in our training data y\n\nWe use 1) cross entropy loss function, 2) gradient descent to perform optimization, and 3) error back propagation to compute gradient of loss function\n\nSince NN combine perceptron like neural units, we have many more parameters in the models (weights and biases). This allows us to trian systems to perform even more sophisticated tasks\n\n\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" \n",
        "**Neural Language Models**\\n\n",
        "langauge model is estimating probability of some sequence of words, and we will see what's probability of next word given the k words before it\\n\n",
        "Sparsity is a problem -- if we don't have something in our training then overall probability is 0\\n\n",
        "We could smooth using LaPlacian smoothing\\n\n",
        "Neural language models -- have advantages over n-gram LMs. 1) don't need smoothing, 2) can handle longer histories, 3) can generalize over contexts of similar words, 4) tend to have higher accuracy than n-grams\\n\n",
        "Neural LMs proposed almost 20 years ago in 2003 by Bengio\\n\n",
        "1) Associate each word in the vocab w/ vector representation, creating a notion of similarity between words\\n\n",
        "2) express join prob as a function of a word sequence in terms of word vectors for words in that sequence\\n\n",
        "3) simultaneously learn the word vectors and params of function\\n\n",
        "The word vectors are low-dimensional dense vectors, prob function is expressed as the product of conditional probs of next word given prev word using multi-layer FF neural network\\n\n",
        "Input: sequence of k words, output: probability distribution over all words in vocab, each word is associated with an embedding vector\\n\n",
        "Input vector x just concatenates v(w) for each of the k words\\n\n",
        "input x is fed into NN with 1 or more hidden layers\\n\n",
        "Output layer has number of words equal to the size of the vocab, which is very large\\n\n",
        "One-hot vector, binary vector and only one element in that vector will be turned on\\n\n",
        "Training examples are simply word k-grams from corpus, the identities of the first k+1 words are used as features, and last word is the target label, model is trained using CE loss\\n\n",
        "Probability tables -- we construct tables to look up probability of seeing a word given a history. The tables only store observed sequences. What happens when we have unseen sequences?\\n\n",
        "Unseen sequences -- we could 1) back-off, 2) smoothing and interpolation. Ultimately we are stitching together short sequences of observed words\\n\n",
        "Model will learn to generalize. We can assign probabilities that are similar to things we have seen before\\n\n",
        "Will assign representations to words that make them more than multinomial distribution -- vector space model\\n\n",
        "Neural probabilistic model LM -- 1) use a vector space model where words are vectors with real values, giving us a way to compute word similarity\\n\n",
        "2) define a function that returns a joint probability of words in a sequence based on a sequence of these vectors\\n\n",
        "3) simultaneusly learn the word representations and the probability function from the data\\n\n",
        "Seeing one of the cat/dog sentences allows them to increase the probability for that sentence AND its combinatorial number of neighbor sentences in vector space\\n\n",
        "Allows us to put similar words together\\n\n",
        "ELMo, GPT, BERT, GPT-2 are current state of the art neural LMs\\n\n",
        "\n",
        "**Lexical Semantic Models**\\n\n",
        "How do we represent meaning of words in models?\\n\n",
        "Word meaning -- N-gram LMs we represented words as a s tring of letters or as an index of vocab list\\n\n",
        "But we want a meaning representation to encode 1) synonyms, 2) antonyms, 3)connotations - positive or negative, 4) semantic roles -- buy sell and pay are all parts of same underlying purchase event, 5) support for entailment\\n\n",
        "Entailment in formal semantics -- dog is a subset of animals. SO if you say All animals have an ulnar artery, you should be able to say all dogs have an ulnar artery\\n\n",
        "Mathematically well understood, powerful machinery for handling logical operations, but an issue is logic must come from somewhere else\\n\n",
        "Hypernym is more general than current word, Hyponym is more specific\\n\n",
        "\n",
        "**Vector Space model**\\n\n",
        "Instead of a word net, we can use vector space model -- can't get the same operations as we would on a word net, but we can do others\\n\n",
        "Will let us do it at a large scale and can do operations such as automatically extracting knowledge from a giant corpus\\n\n",
        "points close to each other in vector space represent something similar semantically\\n\n",
        "Lots of NLP applications are dependent on recognizing that words are similar to each other\\n\n",
        "fast is similar to rapid, tall is similar to height\\n\n",
        "Way to compute these word vectors is following Distributional Hypothesis of language\\n\n",
        "if we consider 2 words like optometrist and eye doctor, these will share lots of sentence environments, but 2 unrelated words might not share as many sentence environments\\n\n",
        "So, it's a measure of relative frequency of sentence environments.\\n\n",
        "Intutiton behind vector space representation is that if 2 words are similar, they will occur in similar sentence contexts\\n\n",
        "History of vector space models -- each document in a collection is represented as a point in space, a user's query is a pseudo-document and is represented as a point in the same space as documents, perform IR by retriving documents whose vectors are close together\\n\n",
        "Can construct a term-document matrix -- every column is a document, every row is a word, and a cell is how much that word exists in that document\\n\n",
        "Pretty sparse matrix, can compare how similar 2 documents are by looking at column vectors\\n\n",
        "What does comparing 2 row vectors do? Tells us how similar 2 words are -- first instance of representing meaning for a word as a vector\\n\n",
        "Words that occur in similar sets of documents are often similar\\n\n",
        "Once we get vector representation of words and documents, we can evaluate similarity\\n\n",
        "Can plot vectors on a graph and see how close they are in Euclidean distance\\n\n",
        "We can normalize the vectors based on their vector length (L2 normalization)\\n\n",
        "Or, you can measure cosine distnace between two vectors and not euclidean distance\\n\n",
        "Other types of word representaion we can do is term-term aka term-context matrix -- every row and column are the words themselves\\n\n",
        "Cell indicates how often word 1 appears in a context window surrounding word 2\\n\n",
        "Context window {w-2, w-1, TARGET WORD, w+1, w+2}\\n\n",
        "We can tell sentences have long distance dependency by looking at certain properties of language -- i.e. subject verb agreement\\n\n",
        "We have developed dependency parsing which can decipher these syntactical relationships\\n\n",
        "We can use syntax to define a word's context\\n\n",
        "The meaning of entitites and grammatical relations among them is related to the restriction of combos of these entities relative to other entities\\n\n",
        "This gives us another way of populating term-context matrix\\n\n",
        "Sometimes, we don't want to take raw counts and instead transform the raw counts somehow\\n\n",
        "Raw counts are really skewed to the frequent words, so we should look at transformed counts -- one that is common is TF-IDF\\n\n",
        "TF-IDF = term frequency * inverse document frequency = how often a word occurred in a document * 1 over the number of documents that it occurred in\\n\n",
        "\n",
        "**Word-Embedding**\\n\n",
        "We can also transform how we go about meaning of words in a different way\\n\n",
        "So far, we have looked at co-occurrence matrices which are sparse and dense\\n\n",
        "Alternative is to learn vectors that are short and dense\\n\n",
        "Train a classifier to get a dense vector\\n\n",
        "1) treat target word and neighboring context word as positive examples\\n\n",
        "2) randomly sample other words in the lexicon to get negative samples\\n\n",
        "3) use logistic regresion to train a classifier to distinguish\\n\n",
        "4) use weihgts as embeddings for dense vector representations\\n\n",
        "This is what based Word2Vec which is made by google\\n\n",
        "It is fast and easy to train, and has pretrained embeddings\\n\n",
        "We want predictions of words we know to be high, and ramdom words to be low\\n\n",
        "Embeddings capture relational meanings -- can solve word analogy problems using vector representation\\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 88,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3021
        },
        "outputId": "41c78471-2dad-401f-bf7d-a519f5f46e4b"
      },
      "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": 89,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n**Logistic Regression**\n\nType of classifier similar to perceptron\n\nSupervised ML problem with: feature representation, classification function, objective function, and optimizing the objective function\n\nFeature engineering is trying to build features that will correctly represent the situation\n\nBefore, if we wanted to build a faster model, we would try to pick the best features, but nowadays we want to change structure of NN itself\n\nObjective function is referred to as a loss function and we want to minimize error on training examples\n\nSentiment classifier: encode review into a way that classifier can use -- variant of perceptron\n\nGo through each of the elements and multiply by weight and add bias, equivalent to dot product\n\nSquish value using the sigmoid function, and if the sigmoid is > 1/2, predict 1 and if not, predict 0\n\n1/2 ends up being the decision boundary here, but we can change it\n\nNow we need to extract features to represent each training item\n\nFor a piece of text, some features are -- positive lexicon words, negative lexicon words, whether or not no appears, first and second person pronouns, whether exclamation appears, log of the word count\n\nThen we want to associate weights with each of the features\n\nHow do we get the weight values? Different than in perceptron\n\n1) get an objective or loss function that tells us the distance between the system output and gold output, we use cross entropy loss. 2) an algorithm for optimizing the objective function, we will use stochastic gradient descent to minimize the loss function\n\n\n**Loss functions**\n\nLots of families of loss functions\n\ngoal is to determine how close the gold standard is to what we predict\n\nOne example is Mean squared error, take difference between prediction and truth and square it\n\nBut this is hard to optimize, and it is non convex when applied to probabilistic classification\n\nLoss functions for probabilistic classification -- we use a loss function that prefers the correct class labels of the training example to be more likely.\n\nConditional MLE: choose parameters w, b to maximize the log probabilities of the true labels in the training data\n\nThe rresulting loss function is the negative log likelihodd loss, or cross entropy loss\n\nWant to maximize probability of true label Y given X. Maximize P(y | x) = y_hat ^ y * (1 - y_hat)^(1-y)\n\nThis works because y is either 1 or 0\n\nWhen it's a positive case, we want y_hat to be as large as possible, when it is a negative case, we want 1 - y_hat to be as large as possible\n\nChange this to log space -- still maximizing, this tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we'll flip the signs\n\nResult is cross entropy loss\n\nWe want to minimize loss on all training examples\n\n\n**Stochastic Gradient Descent**\n\nWant to find parameters, theta, that will minimize the CE loss over all examples\n\nGradient descent is a method that finds a minimum of a function by figuring out in which direction, in the space of the parameters theta) the function's slope is rising the most steeeply, and moving in the opposite direction.\n\nYou're in a canyon, you want to get down to a river quickest, want to go in the direction that will help you go down the furthest\n\nFor logistic regression, this loss function is conveniently convex\n\nConvex function has 1 minimum, so a gradient descent will find that minimum\n\nHow much should we update the parameter by? Weight at each time step is going to be previous time step weight - learning rate -- slope is derivative of loss function with respect to weight\n\nThis is convex optimization -- one minimum, but there can be other ones\n\nIf step size is too big, you might step over minimum and step back and never hit it -- over time, you might want to descrease the step size\n\nNow, we want to see how this extends to many dimensions where we have weight, loss function, and bias term\n\nEach feature is going to be a dimension, and we want to see how a small change over any of these dimensions impacts the loss function\n\nWe want to take the partial derivative with respect to weight_i of the loss function for each of the weights, and this gives us a new vector, and the new set of parameters at time step t+1 is the parameters at timestep t - learning rate * this derivative vector\n\nMini batch training -- stochastic gradient descent chooses a single random example at a time and updates its weights on that example -- alternative is batch training which computes gradient over entire dataset, which gives better estimate of what direction to. move\n\nGood compromise is mini batch training\n\nRegularization: overfitting is a problem, we want to penalize large weights -- a regularization term is added to the loss function, lasso regression uses L1 regularization, Ridge uses L2\n\nSoftmax -- function which takes in an input vector and outputs a vector of values normalized into probabilities\n\n\n**Neural Networks**\n\nPercceptrons were developed in the 1950s and 1960s, loosely inspired by the neuron\n\nNeural networks -- the building block of a neural network is a single computational input which takes in a set of real valued numbers as input and performs a computation\n\nInput vector goes into the neuron and then the output gets produced\n\nNeural networks have input layers, and then some hidden layers and then output layer\n\nPerceptron -> logistic regression -- Like the pereptron, logistic regression uses a vector of ewights and bias term, but instead of outputting z directly, logistic regression TRANSFORMS it with the sigmoid function\n\nProblem with perceptron is that a small change in the weights or bias of any single pereptron in the network can cause the output to flip from 0 to 1 --> solution is sigmoid neuron\n\nSmoothness is crucial: smoothness of sigmoid function means that small changed in the weights and the bias will produce a small change in the output from the neuron\n\nThis makes it easy to choose small changes in weights and biases to achieve any desired small change in the output\n\nActivation function: instead of just outputting z = wx + b, neuron units apply non-linear function f to z, and the result is the activation value for the unit\n\nSigmoid, tanh, and relu are all examples of activation functions\n\nFeed forward NN -- simplest kind of NN, multilayer network where all units are fully connected and there are no cycles\n\nNo outputs are ever passed to lower layers in FF NN\n\nEquations for a FF network: single hidden unit has parameters w and b, and we represent parameters for an entire layer by combining the weight vector w_i and bias b_i for each unit i into a single weight matrix W and a single bias vector b for the whole layer\n\nbetter to use a single matrix W for the weights of the entire layer bc the hidden layer computation can be done efficiently with simple matrix operations -- 3 steps: 1) multiply the weight matrix by input vector, 2) add bias vector, 3) apply activation function\n\nOutput of hidden layer is the vector h, which is h = sigmoid(Wx + b)\n\nThen, once we get to the output layer, which itself has a weight vector U, we can compute z = U * h where h is the input vector to the output layer, and say y = softmax(z) to normalize the output and turn it into a probability distribution\n\nTraining Neural Nets -- to get the best parameters, we need a loss function: cross entropy loss, an optimization algorithm: gradient descent, and a way of computing the gradient of the loss function: error propagation\n\nCross entropy loss -- if the neural network is a binary classifier, with a sigmoid at the final layer, the loss function is the same as we saw in logistic regression:\n\nL_CE(y_hat, y) = -log p(y|x) = -[y log(y_hat) + (1-y)log(1-y_hat)]\n\nFor multinomial classification, it's the sum over all classes of y_i log(y_i_hat), and negate that all at the end\n\nIf there is only one correct answer, where the truth is y_i = 1, it simplifies to -log(y_i_hat)\n\nTo compute gradient in logistic regression, its (sigmoig(wx + b) - y)x_j, but those derivatives only give correct updates for last layer\n\nFor deeper networks, you need to look back through all earlier layers in network which can be done using error backpropagation algorithm\n\nComputation graphs -- although backpropagation was made for neural nets, it is related to a general procedure called backward differentiation, which depends on the notion of computation graphs, which represents process of computing mathematical expression using separate operations which are nodes in a graph\n\nBackward differentiation -- the importance of computation grpah comes from backward pass, used to compute derivatives we need. Backwards differentiatino uses the chain rule from calculus\n\nLEARN HOW TO DO BACKWARDS PASS AND COMPUTATION GRAPH FOR NN\n\nSummary: like with logistic regression, we learn the best parameters for the neural net to make predictions y_hat as close to possible as the gold standard labels in our training data y\n\nWe use 1) cross entropy loss function, 2) gradient descent to perform optimization, and 3) error back propagation to compute gradient of loss function\n\nSince NN combine perceptron like neural units, we have many more parameters in the models (weights and biases). This allows us to trian systems to perform even more sophisticated tasks\n\n\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 21745
        },
        "id": "T3cm1WV542_a",
        "outputId": "a3a85c4e-2499-472b-b5c2-b0f7f7c3d534"
      },
      "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": 90,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent preferences captured by a utility function.\n\nMEU principle formalizes that agent should do that right thing, but doesn't operationalize it\n\nIf an agent acts in order to maximize utility function, agent will get the highest possible score\n\n  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Making sure that utility function follows properties\n\nLottery -- set of outcomes for each action\n\nagent only needs to rank the states, not have a value for each one -- this is called value function or ordinal utility function\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n preference elicitation is looking at human behavior and trying to guess a utility function\n\nnormalized utilities are between 0 and 1\n\nwe can assess the utility of a prize S by asking agent to choose between S and a standard lottery\n\nvalue of a statistical life are around 10 million\n\nmicromort is 1/1000000 chance of death\n\nQuality adjusted life year (QALY) is also a unit of utility\n\nAgent prefers more money to less, all other things being equal --> monotonic preference\n\nthe value an agent will accept in lieu of a lottery is the certainty equivalent\n\ndifference between expected monetary value and certainty of a lottery is the insurance premium\n\nagent that has a linear curve is risk-neutral\n\norder statistic is the distribution of a  ranked element of a sample\n\nunbiased -- expected value of error is 0\n\nTendency for estimated expected utility of best choice to be too high = optimizer’s curse\n\nDecision theory is normative -- describes how a rational agent should act, but descriptive theory describes what happens\n\ncertainty effect -- people like gains that are certain\n\nanchoring effect, ambiguity aversion, framing effect\n\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Assume environment is fully observable\n\na solution that specifies what the agent should do for any state that the agent might reach is a policy\n\noptimal policy is highest expected utility\n\nfinite horizon -- fixed time, infinite horizon -- no fixed time\n\npolicy which depends on time is nonstationary\n\npolicy which reaches end state is proper policy\n\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Showing that value iteration converges --> contraction\n\npolicy evaluation -- given a policy, calculate utility of each state if the policy was executed\n\npolicy improvement -- create a new MEU policy based on one-step-lookahead\n\n \n\n## Module 8 Lecture Notes\n \n**INTRO TO MDP**\n\nMDP are nondeterministic search problems\n\nFully observable environment\n\nPick an ACTION at each time step, terminates when you reach a goal state\n\nIf the environment were deterministic, then the solution for this would be easy\n\nBut, we treat this environment as STOCHASTIC, meaning when you pick an action, the result is undetermined\n\nDefine a transition model that is probabilistic\n\ninstead of having successor of a current state which is deterministic, you need to introduce probabilities\n\nThe transition function is written as T(s,a,s') or explicitly as a probability p(s' | s,a)\n\nTransitions are Markovian, the probability of arriving in s' depends on s and not history of earlier states\n\nWe also need to define a REWARD FUNCTION\n\nCan be positive or negative but are bounded by a max value\n\nWe get a reward INSTANTANEOUSLY -- meaning agent receives a reward at each time step bsaed on transition from s to s' via a\n\nDefined by reward function R(s,a,s')\n\nRewards are additive\n\nThe way that we define reward affects behavior of agent as it explores environments\n\n\n\n**MDP FOrmulation part 1**\n\nSequential decision problem\n\nFully observable environment\n\nstochastic transition model\n\nadditive rewards\n\n*NON DETERMINISTIC* search problems, can solve it using things like expectimax\n\nNeed to define a few things:\n\nSet of states, Set of actions, transitino function T(s,a,s') with probabilities -- this is called the model, a reward function R(s,a,s'), an initial state, and optionally terminal states\n\nSolution an MDP is different than solutions to other search problems\n\nOther search problems were a deterministic set of actions\n\nWe don't have deterministic here, we need to use policies. Policy is a function that says given that I am at a current state, what action should I take?\n\nPolicy is a function that looks like Pi(s) = a for state s\n\npi* denotes the optimal policy\n\nNeed to compute the EXPECTED UTILITY of all possible paths generated by a policy bc one policy could have different outcomes if executed multiple times\n\nYou could have infinite rewards with infinite length games or sometimes even positive rewards\n\nUtilities of sequences: what preferences shuold an agent have over reward sequences?\n\nMaximize reward, rewards that happen earlier rather than later b/c its a stochastic environment\n\n\n\n$$MDP Formulation part 2**\n\nWe add a new factor to rewards called discounting term\n\nHow long you're willing to postpone rewards currently in order to get rewards in the future\n\nOne solution: values of rewards decay exponentially\n\nIf a value is worth 1 now, then gamma in next step, and gamma ^2 2 steps later\n\nEach time we descend a level in expectimax tree, we multiply discount once\nWhy discount? Sooner rewards have higher rewards than later utility, and helps algorithms converge\n\nA cool thing about discounting is that if you assume that agent has stationary preferences, if you take the two reward sequences and add one value to both of them, it will still prefer the same one\n\nIf you assume this, then there are only 2 ways to define utilities: additive utilities and discounted utilities (additive utility is just discounted utility where gamma = 1)\n\nHow to deal with infinite utilities:\n\nFinite horizon similar to depth limited search\n\nTerminate episodes after a fixed T steps\n\nGive nonstationary policies (pi depends on time limit)\n\nAnother solution is to set gamma between 0 and 1\n\nWe can also have an absorbing state guaranteeing that for every policy, a terminal state will eventually be reached\n\n\n**MDP examples**\n\nCan visualize problems as a search tree where you get rewards at every level\n\nEach MDP STATE projects an expectimax-like tree\n\nGiven a q state, what is the probability that you end up in s'?\n\nWe want to compute the value/utility of a state s. V*(s) = expected utility starting in s and acting optimally\n\nValue(utility) of a q-state(s,a): Q*(s,a) = expected utility starting out having taken action a from state s and acting optimally\n\nOptimal policy is Pi*(s) = optimal action from state s\n\nValues of states: compute expectimax value of a state, recursive definition of value\n\nV*(s) = Max over all a of Q*(s,a)\n\nQ*(s,a) = sum over all s' (T(s,a,s') * (reward for ending up in s' + value of being in s' * gamma))\n\nV*(s) = max over all a of the sum over all s' (T(s,a,s') * (reward for ending up in s' + value of being in s' * gamma))\n\nTHIS IS RECURSIVE\n\nDoing expectimax is way too much work\n\nStates can end up being repeated, and we should only compute needed quantities once -- dynamic programming\n\nTree goes on forever: can do a depth limited search to fix this.\n\n\n**Value Iteration Algorithm**\n\nStart with vector of each of steps and have counter saying how much time remaining you have in the game\n\nStart with V0(s) = 0, no time steps left means an expected reward sum of 0\nGiven a vector Vk of values, compute Vk+1 using the same formula s above\n\nrepeat until converge, complexity of each iteration is O(S^2 * A)\n\nThis theorem will converge to unique optimal values because approximations get refined towards optimal values\n\nV0 is at the bottom of the tree, then V1 is one layer up, V2 is one layer up from that, etc\n\nHow do we know that vectors converge?\n\nCase 1: if tree has max depth of M, then VM holds the untruncated value\n\nCase 2: if discount factor is less than 1, then each layer has exponential decay and values go down, so values eventually converge\n\n\n**Policy Evaluation**\n\nevaluate policies to compare two policies and decide which is better\n\nFor a policy, what are its values?\n\nNeed to define utility of a state s under fixed policy Pi, recursively\n\nGiven a set of values, can we figure out policy extraction/what policy we should take?\n\n\n**Policy Iteration**\n\nCombines evaluating policy with improving policy based on its values\n\nProblems with value iteration: repeats Bellman updates and its slow, and max at each state rarely changes\n\nvalue of state tend to go up until convergence, but convergence of policy happens before convergence of values\n\nAlternative approach for optimal values. 1) policy evaltuation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n\n2) policy improvement: update policy using one-step look ahead with resulting converged, but not optimal utilities as future values\n\nREPEAT\n\noptimal, converges much faster under some conditions\n\nStep 1 (Policy Evaluation): for fixed current policy pi, find values with policy evaluation, iterate until values converge\n\nStep 2 (Policy improvement): for fixed values, get a better policy using policy extraction -- one step look ahead\n\nValue iteration vs policy iteration: both want to find optimal values and from there apply policy extraction to get optimal policy\n\nPolicy iteration iterates over explicit policies and value iteration does it implicitly\n\nIn policy iteration: do serveral passes that update utilities with fixed policy, after policy is evaluated a new policy is chosen, or if no better one exists then we're done\n\nBoth are DP algorithms\n\nSummary of MDP algorithm:\n\ncompute optimal values, use value iteration or policy iteration\n\ncompute values for a particular policy, use policy evaluation\n\nturn your values into a policy, use policy extraction (one-step lookahead)\n\nThese all look the same because they basically are -- variations of Bellman updates\n\nAll use one-step lookahead expectimax fragments\n\nDiffer only in whether we plug in a fixed policy or max over actions\n\n\n**Maximum Expected Utility**/n\nDifferent utilities imply different actions. Depending on reward, discount term, etc, the behavior changes\n\nChapter 16 of textbook for utilities\n\nIn expectimax and MDP, average over utility, but before that we had minimax, etc\n\nMinimax we worry about minimizing our losses in the worst case, but worst case is not always going to happen\n\nBetter way is to quantify likelihood of each outcome and do that\n\nPrinciple of maximum expected utility (MEU): a rational agent should choose the action that maximizes its expected utility given knowledge about the world\n\nWhere do utilities come from? How do we know such utilities exist? How do we know that averaging even makes sense?\n\nWe just want better states to have higher evaluations -- we call this insensitivity to monotonic transformations\n\nUtilities -- functions from outcomes to real numbers that describe an agents preferences\n\nWhere do they come from? In a game, may be simple +1/-1, but they should summarize the agent's goals\n\nTheorem that any \"rational\" preferences can be summarized as a utility function\n\nWe hard-wire utilities and let behaviors emerge -- not behaviors\n\nWe prescribe utility, and behaviors happen themselves\n\nRobot has to not only pick between utilities but uncertain outcomes\n\nRobot has preferences, has preferences between prizes/rewards, and lotteries which are situations with unceratin prizes\n\nL = [p, A; (1-p), B]\n\nNotation: A>B is preference, indifference is A~B\n\nWe can define rationality based on preference lists\n\nAdd constraints on preferences before we call them rational\n\nLots of axioms about rational preferences and behaviors\n\nAxiom of transitivity: if I prefer A to B and B to C, then I prefer A to C\n\nAn agent with intransitive preferences could be tricked into giving away money\n\n5 axioms of rationality:\n\n1) either you prefer A to B, B to A, or they're the same\n\n2) transitivity\n\n3) continuity: If we like A better than C, and B is in the middle, then there is some value of p such that if A happened with p and C happened with 1-p, I'd prefer that to B equally\n\n4) Subtitutability: if I don't prefer A or B, then in some lottery between A and C, I will have equal preference with a lottery between B and C\n\n5) Monotonicity: If I prefer A over B, then if I had to pick between a lottery between A and B with A having prob p, and a lottery between A and B with A having prob q, I would pick whichever one is greater.\n\nTheorem: rational preferences imply behavior describable as maximization of expected utility\n\nMEU Principle: Theorem that given any preferences that satisfy these axioms, there exists a real valued function U that obeys your preferences\n\nI.e. values assigned by U preserve preferences of both prizes and lotteries\n\nIf we choose an action that maximizes expected utility, then we are following the MEU principle\n\nNote: an agent can be entirely rational/consistent with MEU without ever representing or manipulating utilities and probabilities\n\nNormalized utility, translate utilities to a scale between 0 and 1\n\nMicromort: one-millionth chance of death, useful for paying to reduce product risk\n\nQALYs: quality-adjusted life years, useful for medical decisions involving substantial risk\n\nBehavior is invariant under positive linear transformation\n\nUtilities map states to real numbers, which numbers?\n\nCompare a prize A to standard lottery L_p between best possible prize u+ with probability p and worst possible catastrophe u- with 1-p. \nAdjust lottery probability p until indifferece: A ~ L_p\n\nResulting p is a utility in [0,1]\n\nMoney does NOT behave as a utility function because it doesn't behave similarly when you're stuck in a lottery\n\nExpected monetary value of a lottery = p * dollar value X + (1-p) * Y\n\nTypically people believe the lottery worth some value of money is worth less than just having the pocket money itself\n\nPoeple are risk averse, but when deep in debt, people are risk-prone\n\n\n \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n \n\n**Intro**\n\nIn MDP, agent is given reward and transition functions, in reinforcement learning, agent learns these functions by interacting with world\n\ngoal of agent is to maximize expected rewards over time using observations\n\nTradeoff between exploration and exploitation\n\nExploration -- agent must try new actions including ones where reward may be worse than if it tried a different action\n\nExploitation -- agent must use knowledge that it learned in order to choose best action\n\nModel based learning -- transitino function represented using an explicit probabilistic model\n\nTempral difference learning -- agent updates beliefs about world after every action using exponential moving\n\nRegret -- measures the total rewards we get over a particular exploration strat, compare that with expected rewards if agent followed optimal policy the whole time\n\n\n**Reinforcement learning part 1**\n\nStill in uncertain environments --> need to develop policies\n\nAn additional layer of complication\n\nIn MDP, we knew the probability distributions, and we could see the rewards\n\nWe don't have these given to us anymore\n\nDouble bandit problem, one machine gives u 1 but other gives u either 2 or 0\n\nCan model this as a MDP -- use value iteration and determine best policy, or other MDP algo\n\nNow, what if we don't know the probability distribution?\n\nHow do we know when it's a worse strategy to play red than to play blue slot machine?\n\nNeed to find at what point we can decide whether red is a better or worse policy\n\nFor MDP, we could PLAN, but for this, we don't plan, we learn -- reinforcement learning\n\nThere was an MDp, but you couldn't solve it with just computation\n\nNeed to actually act to figure it out\n\nProcess is more difficult than MDPs we had before\n\n\n**Reinforcement learning part 2**\n\nBasic idea:\n\nHave an agent that is always acting, agent has actions available to it, it will choose an action and environment will resolve the action and after you act on environment you see what happens -- what state and what reward\n\nAgent's utility is defined by the reward function\n\nWant to learn how to maximize expected rewards\n\nAll learning is based on observed samples of outcomes\n\nStill assume a markov decision process: set of states, set of actions, model T(s,a,s') and a reward function R(s,a,s')\n\nNew twist is that we don't know T or R, so we need to try out actions and learn\n\nOffline planning -- MDP, Online planning -- Reinforcement learning\n\nModel-Based learning: learn an approximate model based on experiences, and then solve for values as if the learned model is correct\n\nTake a bunch of sample and estimate by normalizing\n\nStep 1: Learn empirical Model, count outcomes s' for each s, a. Then normalize to give an estimate of T_hat(s,a,s'), discover each R_hat(s,a,s') when we experience (s,a,s')\n\nStep 2: example, use value iteration as before\n\n\n**Passive reinforcement learning**\n\nmodel-free learning: not going to construct an explicit model, instead take an action and every time, take a result compared to what we thought was going to happen\n\nWhenever something deviates from expected, we adjust models\n\nWe track JUST values of interest themselves, not transition or reward\n\nWe let someone else choose policy for us, we try it out, and see what happens\n\nSimplified task: policy evaluation\n\nInput: a fixed policy pi(s), don't know transition or reward, goal is to learn state values\n\nIn this case, learner is along for the ride, no choice about actions to take, just execute policy and learn from experience\n\nThis is NOT offline planning, you take actions in the world\n\nDirect evaluation -- goal is to compute values for each state under pi\n\nIdea is to average together observed sample values, act according to pi\n\nEvery time you visit a state, write down what the sum of discounted rewards turned out to be, adn average those samples\n\nThis is direct evaluation\n\nDirect evaluation is easy to understand, doesn't require knowledge of T or R, and eventually will compute the correct average values using just sample transitions\n\nBad things, though, is that it wastes information about structure/state connections, each state must be learned separately, so it takes a long time to learn\n\nWhy not use policy evaluation? simplified bellman updates calculate V for a fixed policy\n\nEach round, replace V with a one-step-look-ahead layer over V\n\nThis approach fully exploited the connections between the states, unfortunately we need T and R to do it\n\nCould we do policy evaluation without knowing T and R?\n\nSample based policy evaluation is the answer\n\nTake a bunch of samples of how often we end up at s' and then average\n\nNot going to work though because we can't rewind time to get sample after sample from state s'n\n\n**Temporal Difference Learning**\n\nInstead of updating values for the value of being in pi after n steps, let's update every time\n\nUpdate V(s) each time we experience a transition (s,a,s',r)\n\nLikely outcomes s' will contribute updates more often -- weighted more heavily\n\ntemporal difference learning of values: policy still fixed, still doing evaluation\n\nMove values toward value of whatever successor occurs: running average\n\nAlpha is a variable we choose that sets how much we allow current samples to influence our overall estimates, etc\n\nDifference beteween what we observe and what is expected is weighted by alpha\n\nMore recent samples end up being more important -- ends up being an exponential moving average\n\nForgets about the past\n\nDecreasing learning rate (alpha) can give converging values\n\nTD value learning is model free, mimicking bellman updates with running sample averages\nProblems with TD value learning -- if we want to turn values into new policy, we need to get Q values too, so we need to learn the Q values directly, not values themselves\n\n\n**Active reinforcement learning (Q-learning)**\n\nWe want to know what are the optimal policies and the values of states\n\nWe are going to figure out what actions to take/what the policy is in active reinforcement learning\n\nQ-value iteration -- find successive depth limited values\n\nDetermining best policy from a state, its easier if instead of best value of state, get best value of Q-state\n\nStart with Q_0(s,a) = 0, given Q_k calculate depth k+1 q-values for all q-states\n\nQ-learning: instead of Q-value iteration, do it based on samples we observe\n\nLearn Q(s,a) values as you go. Every action you take gets a sample (s,a,s',r), then consider your old estimate Q(s,a), consider your new sample estimate, incorporate the new estimate in a running average\n\nSimilar to temporal difference learning, just for Q-states and Q-values\n\nEventually we will converge to the optimal policy, even though we may be acting suboptimally\n\nThis is called !) off policy learning\n\nlearn best policy even if current policy isn't the best\n\nCaveats: you need to explore enough, you have to eventually make learning rate small enough, but not decrease it too quickly, in the limit, doesn't matter how you select actions\n\n\n**Exploration vs. Exploitation**\n\nQ-learning requires exploring to learn optimal policy\n\nIn exploration, try out new things and make mistakes, need to decide how and when to do it\n\nHow to explore? Simplest is just randomly pick actions\n\nOr, epsilon-greedy, with small probability epsilon, act randomly, and with large probability 1 - epsilon, act on current policy\n\nProblems with random actions? -- you do exploree space but keep thrashing around once learning is done. A solutino is to lower epsilon over time or have exploration functions\n\nExploration functions: when should we explore and what should we explore when we decide to explore vs. exploit?\n\nWant to explore areas whose badness is not (yet) established, eventually stop exploring\n\nTakes a value estimate/utility u and a visit count n, and returns an optimistic utility f(u,n) = u + k/n\n\nWant to give a bonus if we haven't visited a state often, bonus is k\n\nA regular q-update without exploration function doesn't use exploraiton function, but modified Q update uses the exploration function instead of just whatever values we have currently\n\nThis propagates the bonus back to states that lead to unknown states as well\n\nYou can quantify goodness of epsilon-greedy or exploration functions using regret\n\nRegret measures how many mistakes we made over time -- difference between expected rewards and optimal rewards\n\nMinimixing regret goes beyond learning to be optimal -- it requires optimally learning to be optimal\n\nexample: random exploration and exploration function both end up optimal, but random exploration has higher regret\n\n\n**Approximate Q-learning**\n\nIn some problems, there are so many states that you can't possibly visit all of them\n\nGeneralizing across states -- basic Q-learning keeps a table of all q-values\n\nIn realistic situations, you can't learn about every single state, too many states to visit and too many states to keep in memory\n\nIntead, we generalize -- learn about some small number of training states, and generalize that experience to new states that look similar. Fundamental idea in machine learning\n\nLinear value function -- using a feature representation, we can write a q function or value function for any state using a few weights\n\nV(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)\n\nQ(s,a) = w1f1(s,a) + w2f2(s,a) + ... + wnfn(s,a) <- approximate q-learning \n\nAdvantage: our experience is summed up in a few powerful numbers\n\nDisadvantage: states may share features but actually be very different in value\n\nQ-learning with linear Q-functions:\n\nTransition = (s,a,r,s'), difference: [r + gamma * max over all a (Q(s',a'))] - Q(s,a)\n\nDifference is essentially an error term that tells us the difference between what we thought we would get and what we seem to get based on sample and one step lookahead\n\nthen, set Q(s,a) <- Q(s,a) + alpha * difference\n\nIn approximate Q-learning, we ant to update the weights.\n\nSo, to update weights, we can do w_i <- w_i + alpha * difference * f_i(s,a)\nIntuitive interpretation:\n\nEach of the weights is like a little slider and we can adjust weights on active features\n\nIf something unexpectedly bad happens, we blame features that are active when something happens\n\nFormal justification: online least squares\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 9 Definitions\n* **Exploration** - you have to try unknown actions to get information\n* **Exploitation** - eventually, you have to use what you know\n* **Regret** - even if you learn intelligently, you make mistakes\n* **Sampling** - because of chance, you have to try things repeatedly\n* **Difficulty** - learning can be much harder than solving a known MDP\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \n\nUncertainty -- observed variables(evidence), unobserved variables(states), and model. Probabilistic reasoning gives us a framework for managing our beliefs and knowledge\n\nProbabilities are about possible worlds, and instead of ruling out possibilities, probabilities quantify how likely a possible world is\n\nPossible words are sample space, and they are mutually exclusive and exhaustive,\n\nProbability model associates a probability P(w) with each possible world w.\n\nRandom variable is some aspect about world which may have uncertainty\n\nProbabilities are always between 0 and 1, and the sum of all of them equals 1\n\nUnobserved RVs have distributions, and a distribution is a table of probabilities of values. \n\nP(hot) = P(T = hot),\n\nJoint Distribution -- over a set of RVs, specifies a real number for each assignment or outcome\n\nP(X_1 = x_1, X_2 = x_2 ... X_n = x_n) = P(x_1, x_2, ..., x_n)\n\nMust obeys the axioms of probability above where its a >=0 probability and the sum over all (x1,x2,...xn) is 1\n\nProbabilistic Models -- joint distribution over a set of RVs\n\nThey have: random variables with domainds, assignments called outcomes, joint distributions say whether assignments are likely, normalized where sum is 1, and ideally only certain variables interact\n\nAn event is a set E of outcomes -- froma. joint distribution we can calculate the probability of any event: hot and sunny, hot, hot or sunny, etc\n\nTypically we care about partial assignments like P(T = hot)\n\nMarginal Distributions are subtables which eliminate variables -- they combine collapsed rows by adding to do marginalization (summing out)\n\nConditional distributions are probability distributions over some variables given fixed values of others\n\nProbabilistic Inference -- compute a desired probability from other known probabilities (conditional from joint)\n\nGenerally compute conditional probabilities which represent agent's beliefs given evidence. Probabilities can also chance with new evidence\n\nInference by Enumeration: General case has evidence variables E_1, E_2, ... E_k = e_1, e_2, ... e_k. Also has query variable(s) Q, and hidden variables H_1,... H_r\n\nWe want to compute P(Q | e_1...e_k)\n\nStep 1: select entries consistent with evidence\n\nStep 2: P(Q,e_1...e_k) = sum over all (h1...h_r) of P(Q, h1...h_r, e1...e_k). -- sum out H to get joint of query and evidence\n\nStep 3: normalize by dividing by Z where Z is the sum over all q of(P(Q,e1...ek))\n\nProduct rule: P(y) * P(x|y) = P(x,y)\n\nChain rule: P(x1,x2,x3) = P(x1) * P(x2 | x1) * P(x3 | x1, x2)\n\nBayes rule: P(x|y) = P(y|x)/P(y) * P(x)\n\n**Probabilistic Language Models**\n\nGoal is to assign probability to a sequence -- autocomplete for texting, machine translation, spelling correction, speech recognition\n\nRelated task to this is computing the probability of an upcoming word -- a model that computes either of these is called a language model or LM\n\nP(W) = P(w1,w2,w3,w4,w5) -- this is probability of a sentence of sequence of words, P(w5|w1, w2, w3, w4) is probability of an upcoming word\n\nA model that computes either of these is a language model\n\nThe grammar is better but language model is standard\n\nJoin probability of words in a sentence involves chain rule of conditional probabilities\n\nHow to estimate these probabilities? Could we just count and divide --> Maximum Likelihood estimation (MLE)?\n\nThis doesn't work because with long phrases you oftentimes won't see those phrases much so you'll need huge inefficient datasets to make some queries work\n\nIn MLE, P(won | the underdog team) = COUNT(the underdog team won)/ COUNT(the underdog team)\n\nMarkov simplifying assumption\n\nOnly depend on current state and not long history of states that you've gone through\n\nIn this case, it only depends on the previous k words, and not the whole context\n\nP(w1w2w3...wn) = Product over all i up until n of (P(wi | w_{i-k} ... w_{i-1})\n\nThe type of gram determines how much history we should use: unigram-no history, bigram-1 word history, trigram-2 word history, 4-gram = 3 words history\n\nSimplest case is unigram model were each word is just considered on its own, and for n gram model we conditions on the previous n-1 words\n\nMLE estimates for bigram models: P(w_i | w_{i-1}) = count(w_{i-1}, w_i)/count(w_{i-1})\n\nBut MLE might give probability of 0 if its never seen the word before\n\nWe can normalize training data by replacing any word not in L with <unk>\n\nAvoid 0s with smoothing\n\nWe do everything in log space, we can avoid underflow and adding is faster than multiplying\n\nGoogle n-gram release\n\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \n**Bayes' Nets**\n\nModels are always simplifications and may not account for all interactions between variables\n\nWith probabilistic models, we need to reason about unknown variables, given evidence -- explanation v. prediction\n\nIndependence is a simplifying modeling assumption: empirical joint distributions are at best \"close\" to independent\n\n*Conditional Independence* -- X is conditionally independent of Y given Z iff P(x,y|z) = P(x|z) * P(y|z) AKA P(x|z,y) = P(x|z) for all x,y,z\n\nChain rule would say P(Traffic, Rain, Umbrella) = P(Rain) * P(Traffic|Rain) * P(Umbrella | Rain, Traffic), but if we assume conditional independence between Traffic and Umbrella, P(Traffic, Rain, Umbrella) = P(Rain)*P(Traffic|Rain)*P(Umbrella|Rain)\n\nBig picture of Bayes' Nets: Two problems with using full joint distribution tables as our probabilistic models -- 1) Way too big to represent explicitly, and 2) hard to estimate anything empirical about more than a few variables at a time\n\n!) Bayes' nets are a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities) -- they are more properly called graphical models, describing how local variables interact and chain together to give global indirect interactions\n\nNodes are variables with domains and arcs are interactions\n\nSemantics: set of nodes, one per variable X; DAG; conditional distribution for each node -- a collection of distributions over X, one for each combo of parents' values: P(X | a1...an), CPT: conditional probability table\n\nA Bayes net = Topology(graph) + Local conditional probabilities\n\nProbabilities in BNs: Bayes' nets implicitly encode joint distributions as a product of local conditional distributions\n\nP(x1,x2,...xn) = Product of i going from 1 to n of (P(x_i | parents(X_i)))\n\nWe can guarantee that doing this results in a proper joint distribution because of the chain rule and then once we ASSUME conditional independence\n\nNot every BN can represent every joint distribution -- the topology enforces certain conditional independencies\n\nCausality: when Bayes' nets reflect the true causal pattern, it's often simpler, easier to think about, and easier to elicit from experts\n\nBNs need not actually be causal -- sometimes no causal net exists over the domain espeically if variables are missing, you end up with arrows that reflect correlation, not causation\n\nWhat do arrows really mean? Topology may happen to encode causal structure, but the Topology really encodes conditional independence: P(x_i | x1...xn) = P(x_i | parents(Xi))\n\nSize of a BN: how big is a joint distribution with N variables -> 2^N\n\nAn N-node net if nodes have up to k parents is O(N * 2^{k+1})\n\nBoth give you the power to calculate P(X1, X2, ... , Xn) but BN has huge savings, and it is easier to elicit local CPTs and faster to answer queries\n\nAssumptions of BN: often additional conditional independence assumptions that can be read off the graph\\m\nTo model better, we need to understand the assumptions made when choosing a Bayes net graph\n\n\n**D-separation**\n\nCausal chain: the following configuration is a causal chain -- P(x,y,z) = P(x) * P(y | x) * P(z | y)\n\nX is not guaranteed independent of Z here\n\nHowever, it is guaranteed that X is independent of Z given Y because of the equation below:\n\nP(z | x,y) = P(x,y,z)/P(x,y) = P(x) * P(y|x) * P(z | y) / P(x) / P(y|x) = P(z|y)\n\n!) Evidence along the chain \"blocks\" the influence\n\nCommon cause: the following configuration is a common cause -- P(x,y,z) = P(y) * P(x|y) * P(z|y)\n\nGuaranteed X is independent of Z? NO -- one example set of CPTs for which X is not independent of Z is sufficient to show this independence is not guaranteed. P(+x | +y) = 1, P(-x | -y) = 1, P(+z | +y) = 1, P(-z|-y) = 1\n\nHowever, for a common cause, we are guaranteed that X and Z are independent GIVEN Y -- !) observing the cause blocks influence between effects\n\nCommon effect -- v structure: P(x,y,z) = P(x) P(y) P(z | x,y)\n\nX and Y are independent but X and Y are not independent given Z -- this is backwards from other cases. !) Observing an effect activates influence between possible causes\n\nGeneral Case: general question is that in a given BN, are two variables independent given evidence? -- solution is to analyze the graph and any complex example can be broken down into repetition of 3 canonical cases\n\nReachability: recipe is to shade evidence nodes and look for paths in the resulting graph. attempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent. almost works, but not quite becacuse it breaks with the v-structure becuase it doesn't count as a link in a path unless active\n\nNow considering active/inactive paths -- Are X and Y conditionally independent given evidence variables {Z}?\n\nYes, if X and Y are \"d-separated\" by Z. Consider all undirected paths from X to Y, if there are no active paths, then independence\n\nA path is active if each triple is active: Causal chain A->B->C where B is unobserved, Common cause A<-B->C where B is unobserved, Common effect (V-structure) A-> B <- C where B or one of its descendents is observed\n\nAll it takes to block a path is a single inactive segnment\n\nD-separation: if we want to see if Xi and Xj are conditionally independent given X_k1 ... X_kn, we check all undirected paths between Xi and Xj. If one or more is active, then independence is not guaranteed, but if all paths are inactive, then independence is guaranteed.\n\nStructure implications: Given a BN structure, can run d-separation algorithm to build a complete list of conditional independences that are necessarily true of the form Xi conditionally independent with Xj given Xk1, ... , Xkn\b\nThis list determines the set of probability distributions that can be represented\n\nBN representation summary -- BN compactly encode joint distributions. Guaranteed independencies of distributions can be deduced from BN graph structure. D-separation gives precise conditional independence guarantees from graph alone. A BN joint distribution may have further (conditional) independence that is not detectable until you inspect its specific distribution\n\nInference: calculating some joint useful quantity from a joint probability distribution. Example, posterior probability = P(Q|E1 = e1...Ek = ek) and Most likely explanation = argmax over all q of P(Q = q | E1 = e1 ... )\n\nInference by enumeration in BN is similar to inference by enumeration normally\n\nSelect entries consistent with evidence, get joint of query and evidencce, and normalize\n\nGiven unlimited time, inference in BNs is easy\n\nInference by Enumeration vs. Variable elimination: inference by enumeration is slow because you join up the whole joint distribution before you sum out the hidden values\n\nVariable elimination: interleaving joining and marginalizing, still NP-hard but usually much faster than inference by enumeration\n\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n**Classification Tasks**\n\nInstead of joint probability table, decompose into smaller tables --> Bayesian Networks\n\nHow do we get the probability values? Up until now, it'sbeen how use a model to make optimal decisions\n\nMachine learning tells us how to acquire a model from data/experience. Learning parameters (probabilities), structure (eg BN graphs), hidden concepts (eg clustering)\n\nModel based classification with naive bayes and perceptrons\n\nModel based = uses a probability based model\n\nClassification: input of our system is a feature vector, depending on what our output is, we either do classification or regression. For ML, we will have a set of data with labels, and then learn a function which takes a new entry and predicts/classifies\n\nTransform to vector representation where each vector corresponds to a feature\n\nDigit recognition and spam email classification problems are classification\n\nTake raw input of pixels and have vectors for digit classification, also number of loops, etc\n\nGiven inputs x, predict labels y\n\nModel-based classification\n\nbuild a model where both the label and features are random variables, each input is a RV, instantiate all observed features and the query the model.\n\nWhat kind of relationship between RVs should there be, what's the structure? How do we collect probabilities?\n\n\n**Naive Bayes**\n\nNaive: assume all the features that we use to represent inputs are independent of each other and only dependent on the label\n\nHow do we construct a BN for naive bayes? Class variable Y has no parents, and for each feature, we have a probability of that feature given the parents, and the only parent is Y (the class variable)\n\nNaive bayes says probability given features is proportional to prior value of label and the product of each of the conditional probabilities\n\nGENERAL NAIVE BAYES MODEL: P(Y, F1 ... Fn) = P(Y) * product over all i (P(F_i | Y))\n\n|Y| times |F|^n values\n\nWe only have to specify how each feature depends on the class\n\nTotal number of parameters is linear in number of features\n\nModel is very simplistic but often works anyway even though we make super strong simplifying assumptions\n\nWe can estimate parameters in a pretty effective way\n\nInference for Naive Bayes: Goal: compute posterior distribution over label variable Y\n\nStep 1: get joint probability of label and evidence for each label. Get P(y1,f1...fn), P(y2,f1...fn), ... P(yk,f1...fn)\n\nStep 2: sum to get probability of evidence P(f1...fn)\n\nStep 3: Normalize by dividing step 1 and step 2 --> P(Y | f1...fn)\n\nWhat do we need in order to use Naive Bayes? Inference method (we just saw this) -- start with probabilities P(Y) and P(F_i | Y) tables, then use standard inference to compute P(Y|f1...fn\n\nThe other thing we need is the estimates of local conditional probability tables -- P(Y), and P(F_i | Y), these are parameters we will denote by theta\n\nUntil now, we assumed these appeared by magic, but they come from training data counts\n\n\n**Basic concepts for ML**\n\nTraining and testing, at training we have labels but for testing we don't\n\nPartition training data into training data, test data, and held out data, where if we have hyperparameters, we will optimize those on held out set\n\nUse training set for parameters, learn hyperparameters for held out data, and run it on test data and have evaluation function\n\nDon't want overfitting, for example if we take a product and one of the things is 0 for no reason, the whole thing will be 0. \n\nRelative frewuency parameters will overfit the training data, just because we didn't see something in training data doesn't mean we won't see it at all\n\nWant to avoid giving things you've never seen before zero probability, so you smooth or regularize the data\n\nParameter estimation: estimating the distribution of a random variable -- one way is to ask an expert / human, another way is to do it empirically / using training data\n\nUse MLE estimation for training data -- compute which theta is best by computing which one maximizes the likelihood of that data\n\nL(x, theta) = product over all i of P_theta(x_i)\n\nParameter settings of our model are going to be pick the parameter settings that maximize likelihood of data given those parameter settings, which is the argmax over all theta of the product over all i of P_theta(x_i)\n\nUnseen events: avoid zero probabilities, and use smoothing like LaPlace smoothing -- pretend like you saw everything one more time than you actually did\n\nHyperparameter -- instead of adding 1, we can add LaPlace with some value k, and k is the strength of the prior\n\nP_LAP,k(x|y) = (c(x,y) + k) / (c(y) + k|X|)\n\nanother technique to avoid 0 probabilities is interpolation\n\nWhen we estimate conditional, use observed MLE, and then back out to a prior for some amount of it\n\nHave a second hyperparameter -- k of how much to smooth, and alpha of how much to weight the conditional vs. the prior\n\nWhat if alpha is 0, no weight to conditional, all to prior, and if alpha is 1, its reversed\n\nIf we have hyperparameters like k and alpha, how do we tune model?\n\nHow to pick best value of parameters and hyperparameters\n\nLearn parameters from training data, hyperparameters from held out data because we will lose nice features if we do the hyperparameters also on the training data\n\nChoose best value and do a final test on the test data\n\nWe can also improve models by thinking of other features\n\nFirst step: get a baseline. Pick a simple baseline and then help determine how hard the task is, which helps know what a good accuracy is\n\nWeak baseline: most frequent label classifier\n\nFor real research, usually use previous work as a baseline\n\n\n**Perceptron**\n\nNaive Bayes is model based classifier\n\nPerceptrons developed in 1950s loosely inspired by the neuron\n\nDendrites are input to neuron, transmits output to other neurons\n\n!) Accept a bunch of inputs, combine into an activation function, transmit\n\nPerceptron takes weighted sum of all inputs and decides whether or not to transmit the output\n\nCan think about perceptron or the sigmoid neuron as a device that makes decisions by weighing up evidence\n\nCan vary weights and thresholds\n\nNotation changes -- change 1 is writing as a dotproduct of input vector and weight vector, change 2 is move threshold to other side of the equality and call that term the bias\n\nThink of bias as a measure of how easy it is to get the perceptron to output 1 / how easy it is to fire \n\nWhat are manipulations to learn a good parameterization?\n\nWe try to learn the weight factor. Think of inputs as features representing something we want to classify. The feature avlues for inputs are fixed, but we can choose different weight vectors. Depending on the weight vector that we pick, we will get a different classifier\n\nBias allows us to move decision boundary around\n\nWeight updates -- based on error driven learning. Start with weight vector where all are set to 0. Then for each training instance, classify with current weights, if correct keep the weights, if not, update weights so that they are closer\n\nwe can use this for binary or multiclass, for multiclass its have a weight vector for each class\n\nCalculate activation score of all classes, and prediction with highest score wins\n\nTo learn the weights, nudge the weights whenever it's incorrect\n\n\n**Improvements on Perceptrons and SVM**\n\nIf data is linearly separable, then we're guaranteed to converge on a set of parameters\n\nIf it's not, then we can come up with a bound on number of mistakes that algorithm will end up with -- for a binary classifier, we can bound it by k / (margin)^2\n\nMargin is distance between positive and negative classes\n\nProblems w perceptron -- weights might thrash if data isn't seperable, can average weights over time to help\n\nAnother proble. is even if you can separate, you might have a \"barely\" separating solution\n\nLast one is that you can overtrain and training accuracy can go up but then go down\n\nTO fix the perceptron, we can use some algos\n\nMIRA = margin infused relaxed algorithm, instead of updating weights by a big amount every time, update by just enough to fix current mistake and more\n\nScale the incorrect guess by tau when you update weight vector\n\nGet maximum step size\n\nSupport vector machine (SVM)\n\nDraw 2 support vectors and maximize the margin between them. Only support vectors matter, help you find the boundary between 2 classes\n\nNOnlinear separators, data that is linearly separable works out great for linear decision rules, but what are we going to do if the dataset is just too hard\n\nCan shift data into a higher dimension, kernel trick is to transform input into different dimensions, squaring or figuring out distance from origin etc\n\n\n**Summary**\n\nNaive Bayes: builds a model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data (counting)\n\nPerceptrons/MIRA: makes less assumptions about data, mistake-driven learning, multiple passes through data (prediction), often more accurate\n\n\n\n\n\n\n\n \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n**Logistic Regression**\n\nType of classifier similar to perceptron\n\nSupervised ML problem with: feature representation, classification function, objective function, and optimizing the objective function\n\nFeature engineering is trying to build features that will correctly represent the situation\n\nBefore, if we wanted to build a faster model, we would try to pick the best features, but nowadays we want to change structure of NN itself\n\nObjective function is referred to as a loss function and we want to minimize error on training examples\n\nSentiment classifier: encode review into a way that classifier can use -- variant of perceptron\n\nGo through each of the elements and multiply by weight and add bias, equivalent to dot product\n\nSquish value using the sigmoid function, and if the sigmoid is > 1/2, predict 1 and if not, predict 0\n\n1/2 ends up being the decision boundary here, but we can change it\n\nNow we need to extract features to represent each training item\n\nFor a piece of text, some features are -- positive lexicon words, negative lexicon words, whether or not no appears, first and second person pronouns, whether exclamation appears, log of the word count\n\nThen we want to associate weights with each of the features\n\nHow do we get the weight values? Different than in perceptron\n\n1) get an objective or loss function that tells us the distance between the system output and gold output, we use cross entropy loss. 2) an algorithm for optimizing the objective function, we will use stochastic gradient descent to minimize the loss function\n\n\n**Loss functions**\n\nLots of families of loss functions\n\ngoal is to determine how close the gold standard is to what we predict\n\nOne example is Mean squared error, take difference between prediction and truth and square it\n\nBut this is hard to optimize, and it is non convex when applied to probabilistic classification\n\nLoss functions for probabilistic classification -- we use a loss function that prefers the correct class labels of the training example to be more likely.\n\nConditional MLE: choose parameters w, b to maximize the log probabilities of the true labels in the training data\n\nThe rresulting loss function is the negative log likelihodd loss, or cross entropy loss\n\nWant to maximize probability of true label Y given X. Maximize P(y | x) = y_hat ^ y * (1 - y_hat)^(1-y)\n\nThis works because y is either 1 or 0\n\nWhen it's a positive case, we want y_hat to be as large as possible, when it is a negative case, we want 1 - y_hat to be as large as possible\n\nChange this to log space -- still maximizing, this tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we'll flip the signs\n\nResult is cross entropy loss\n\nWe want to minimize loss on all training examples\n\n\n**Stochastic Gradient Descent**\n\nWant to find parameters, theta, that will minimize the CE loss over all examples\n\nGradient descent is a method that finds a minimum of a function by figuring out in which direction, in the space of the parameters theta) the function's slope is rising the most steeeply, and moving in the opposite direction.\n\nYou're in a canyon, you want to get down to a river quickest, want to go in the direction that will help you go down the furthest\n\nFor logistic regression, this loss function is conveniently convex\n\nConvex function has 1 minimum, so a gradient descent will find that minimum\n\nHow much should we update the parameter by? Weight at each time step is going to be previous time step weight - learning rate -- slope is derivative of loss function with respect to weight\n\nThis is convex optimization -- one minimum, but there can be other ones\n\nIf step size is too big, you might step over minimum and step back and never hit it -- over time, you might want to descrease the step size\n\nNow, we want to see how this extends to many dimensions where we have weight, loss function, and bias term\n\nEach feature is going to be a dimension, and we want to see how a small change over any of these dimensions impacts the loss function\n\nWe want to take the partial derivative with respect to weight_i of the loss function for each of the weights, and this gives us a new vector, and the new set of parameters at time step t+1 is the parameters at timestep t - learning rate * this derivative vector\n\nMini batch training -- stochastic gradient descent chooses a single random example at a time and updates its weights on that example -- alternative is batch training which computes gradient over entire dataset, which gives better estimate of what direction to. move\n\nGood compromise is mini batch training\n\nRegularization: overfitting is a problem, we want to penalize large weights -- a regularization term is added to the loss function, lasso regression uses L1 regularization, Ridge uses L2\n\nSoftmax -- function which takes in an input vector and outputs a vector of values normalized into probabilities\n\n\n**Neural Networks**\n\nPercceptrons were developed in the 1950s and 1960s, loosely inspired by the neuron\n\nNeural networks -- the building block of a neural network is a single computational input which takes in a set of real valued numbers as input and performs a computation\n\nInput vector goes into the neuron and then the output gets produced\n\nNeural networks have input layers, and then some hidden layers and then output layer\n\nPerceptron -> logistic regression -- Like the pereptron, logistic regression uses a vector of ewights and bias term, but instead of outputting z directly, logistic regression TRANSFORMS it with the sigmoid function\n\nProblem with perceptron is that a small change in the weights or bias of any single pereptron in the network can cause the output to flip from 0 to 1 --> solution is sigmoid neuron\n\nSmoothness is crucial: smoothness of sigmoid function means that small changed in the weights and the bias will produce a small change in the output from the neuron\n\nThis makes it easy to choose small changes in weights and biases to achieve any desired small change in the output\n\nActivation function: instead of just outputting z = wx + b, neuron units apply non-linear function f to z, and the result is the activation value for the unit\n\nSigmoid, tanh, and relu are all examples of activation functions\n\nFeed forward NN -- simplest kind of NN, multilayer network where all units are fully connected and there are no cycles\n\nNo outputs are ever passed to lower layers in FF NN\n\nEquations for a FF network: single hidden unit has parameters w and b, and we represent parameters for an entire layer by combining the weight vector w_i and bias b_i for each unit i into a single weight matrix W and a single bias vector b for the whole layer\n\nbetter to use a single matrix W for the weights of the entire layer bc the hidden layer computation can be done efficiently with simple matrix operations -- 3 steps: 1) multiply the weight matrix by input vector, 2) add bias vector, 3) apply activation function\n\nOutput of hidden layer is the vector h, which is h = sigmoid(Wx + b)\n\nThen, once we get to the output layer, which itself has a weight vector U, we can compute z = U * h where h is the input vector to the output layer, and say y = softmax(z) to normalize the output and turn it into a probability distribution\n\nTraining Neural Nets -- to get the best parameters, we need a loss function: cross entropy loss, an optimization algorithm: gradient descent, and a way of computing the gradient of the loss function: error propagation\n\nCross entropy loss -- if the neural network is a binary classifier, with a sigmoid at the final layer, the loss function is the same as we saw in logistic regression:\n\nL_CE(y_hat, y) = -log p(y|x) = -[y log(y_hat) + (1-y)log(1-y_hat)]\n\nFor multinomial classification, it's the sum over all classes of y_i log(y_i_hat), and negate that all at the end\n\nIf there is only one correct answer, where the truth is y_i = 1, it simplifies to -log(y_i_hat)\n\nTo compute gradient in logistic regression, its (sigmoig(wx + b) - y)x_j, but those derivatives only give correct updates for last layer\n\nFor deeper networks, you need to look back through all earlier layers in network which can be done using error backpropagation algorithm\n\nComputation graphs -- although backpropagation was made for neural nets, it is related to a general procedure called backward differentiation, which depends on the notion of computation graphs, which represents process of computing mathematical expression using separate operations which are nodes in a graph\n\nBackward differentiation -- the importance of computation grpah comes from backward pass, used to compute derivatives we need. Backwards differentiatino uses the chain rule from calculus\n\nLEARN HOW TO DO BACKWARDS PASS AND COMPUTATION GRAPH FOR NN\n\nSummary: like with logistic regression, we learn the best parameters for the neural net to make predictions y_hat as close to possible as the gold standard labels in our training data y\n\nWe use 1) cross entropy loss function, 2) gradient descent to perform optimization, and 3) error back propagation to compute gradient of loss function\n\nSince NN combine perceptron like neural units, we have many more parameters in the models (weights and biases). This allows us to trian systems to perform even more sophisticated tasks\n\n\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n**Logistic Regression**\n\nType of classifier similar to perceptron\n\nSupervised ML problem with: feature representation, classification function, objective function, and optimizing the objective function\n\nFeature engineering is trying to build features that will correctly represent the situation\n\nBefore, if we wanted to build a faster model, we would try to pick the best features, but nowadays we want to change structure of NN itself\n\nObjective function is referred to as a loss function and we want to minimize error on training examples\n\nSentiment classifier: encode review into a way that classifier can use -- variant of perceptron\n\nGo through each of the elements and multiply by weight and add bias, equivalent to dot product\n\nSquish value using the sigmoid function, and if the sigmoid is > 1/2, predict 1 and if not, predict 0\n\n1/2 ends up being the decision boundary here, but we can change it\n\nNow we need to extract features to represent each training item\n\nFor a piece of text, some features are -- positive lexicon words, negative lexicon words, whether or not no appears, first and second person pronouns, whether exclamation appears, log of the word count\n\nThen we want to associate weights with each of the features\n\nHow do we get the weight values? Different than in perceptron\n\n1) get an objective or loss function that tells us the distance between the system output and gold output, we use cross entropy loss. 2) an algorithm for optimizing the objective function, we will use stochastic gradient descent to minimize the loss function\n\n\n**Loss functions**\n\nLots of families of loss functions\n\ngoal is to determine how close the gold standard is to what we predict\n\nOne example is Mean squared error, take difference between prediction and truth and square it\n\nBut this is hard to optimize, and it is non convex when applied to probabilistic classification\n\nLoss functions for probabilistic classification -- we use a loss function that prefers the correct class labels of the training example to be more likely.\n\nConditional MLE: choose parameters w, b to maximize the log probabilities of the true labels in the training data\n\nThe rresulting loss function is the negative log likelihodd loss, or cross entropy loss\n\nWant to maximize probability of true label Y given X. Maximize P(y | x) = y_hat ^ y * (1 - y_hat)^(1-y)\n\nThis works because y is either 1 or 0\n\nWhen it's a positive case, we want y_hat to be as large as possible, when it is a negative case, we want 1 - y_hat to be as large as possible\n\nChange this to log space -- still maximizing, this tells us what log likelihood should be maximized. But for loss functions, we want to minimize things, so we'll flip the signs\n\nResult is cross entropy loss\n\nWe want to minimize loss on all training examples\n\n\n**Stochastic Gradient Descent**\n\nWant to find parameters, theta, that will minimize the CE loss over all examples\n\nGradient descent is a method that finds a minimum of a function by figuring out in which direction, in the space of the parameters theta) the function's slope is rising the most steeeply, and moving in the opposite direction.\n\nYou're in a canyon, you want to get down to a river quickest, want to go in the direction that will help you go down the furthest\n\nFor logistic regression, this loss function is conveniently convex\n\nConvex function has 1 minimum, so a gradient descent will find that minimum\n\nHow much should we update the parameter by? Weight at each time step is going to be previous time step weight - learning rate -- slope is derivative of loss function with respect to weight\n\nThis is convex optimization -- one minimum, but there can be other ones\n\nIf step size is too big, you might step over minimum and step back and never hit it -- over time, you might want to descrease the step size\n\nNow, we want to see how this extends to many dimensions where we have weight, loss function, and bias term\n\nEach feature is going to be a dimension, and we want to see how a small change over any of these dimensions impacts the loss function\n\nWe want to take the partial derivative with respect to weight_i of the loss function for each of the weights, and this gives us a new vector, and the new set of parameters at time step t+1 is the parameters at timestep t - learning rate * this derivative vector\n\nMini batch training -- stochastic gradient descent chooses a single random example at a time and updates its weights on that example -- alternative is batch training which computes gradient over entire dataset, which gives better estimate of what direction to. move\n\nGood compromise is mini batch training\n\nRegularization: overfitting is a problem, we want to penalize large weights -- a regularization term is added to the loss function, lasso regression uses L1 regularization, Ridge uses L2\n\nSoftmax -- function which takes in an input vector and outputs a vector of values normalized into probabilities\n\n\n**Neural Networks**\n\nPercceptrons were developed in the 1950s and 1960s, loosely inspired by the neuron\n\nNeural networks -- the building block of a neural network is a single computational input which takes in a set of real valued numbers as input and performs a computation\n\nInput vector goes into the neuron and then the output gets produced\n\nNeural networks have input layers, and then some hidden layers and then output layer\n\nPerceptron -> logistic regression -- Like the pereptron, logistic regression uses a vector of ewights and bias term, but instead of outputting z directly, logistic regression TRANSFORMS it with the sigmoid function\n\nProblem with perceptron is that a small change in the weights or bias of any single pereptron in the network can cause the output to flip from 0 to 1 --> solution is sigmoid neuron\n\nSmoothness is crucial: smoothness of sigmoid function means that small changed in the weights and the bias will produce a small change in the output from the neuron\n\nThis makes it easy to choose small changes in weights and biases to achieve any desired small change in the output\n\nActivation function: instead of just outputting z = wx + b, neuron units apply non-linear function f to z, and the result is the activation value for the unit\n\nSigmoid, tanh, and relu are all examples of activation functions\n\nFeed forward NN -- simplest kind of NN, multilayer network where all units are fully connected and there are no cycles\n\nNo outputs are ever passed to lower layers in FF NN\n\nEquations for a FF network: single hidden unit has parameters w and b, and we represent parameters for an entire layer by combining the weight vector w_i and bias b_i for each unit i into a single weight matrix W and a single bias vector b for the whole layer\n\nbetter to use a single matrix W for the weights of the entire layer bc the hidden layer computation can be done efficiently with simple matrix operations -- 3 steps: 1) multiply the weight matrix by input vector, 2) add bias vector, 3) apply activation function\n\nOutput of hidden layer is the vector h, which is h = sigmoid(Wx + b)\n\nThen, once we get to the output layer, which itself has a weight vector U, we can compute z = U * h where h is the input vector to the output layer, and say y = softmax(z) to normalize the output and turn it into a probability distribution\n\nTraining Neural Nets -- to get the best parameters, we need a loss function: cross entropy loss, an optimization algorithm: gradient descent, and a way of computing the gradient of the loss function: error propagation\n\nCross entropy loss -- if the neural network is a binary classifier, with a sigmoid at the final layer, the loss function is the same as we saw in logistic regression:\n\nL_CE(y_hat, y) = -log p(y|x) = -[y log(y_hat) + (1-y)log(1-y_hat)]\n\nFor multinomial classification, it's the sum over all classes of y_i log(y_i_hat), and negate that all at the end\n\nIf there is only one correct answer, where the truth is y_i = 1, it simplifies to -log(y_i_hat)\n\nTo compute gradient in logistic regression, its (sigmoig(wx + b) - y)x_j, but those derivatives only give correct updates for last layer\n\nFor deeper networks, you need to look back through all earlier layers in network which can be done using error backpropagation algorithm\n\nComputation graphs -- although backpropagation was made for neural nets, it is related to a general procedure called backward differentiation, which depends on the notion of computation graphs, which represents process of computing mathematical expression using separate operations which are nodes in a graph\n\nBackward differentiation -- the importance of computation grpah comes from backward pass, used to compute derivatives we need. Backwards differentiatino uses the chain rule from calculus\n\nLEARN HOW TO DO BACKWARDS PASS AND COMPUTATION GRAPH FOR NN\n\nSummary: like with logistic regression, we learn the best parameters for the neural net to make predictions y_hat as close to possible as the gold standard labels in our training data y\n\nWe use 1) cross entropy loss function, 2) gradient descent to perform optimization, and 3) error back propagation to compute gradient of loss function\n\nSince NN combine perceptron like neural units, we have many more parameters in the models (weights and biases). This allows us to trian systems to perform even more sophisticated tasks\n\n\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}