{
  "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/"
        },
        "outputId": "91ad4745-99a2-4293-c531-8e62a3871bf6"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "77b8500a-b4bb-423d-8b2c-11ae5dee2bc0"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Transition model for an agent written as P(s'|s, a), meaning the probability that action 'a' in state 's' reaches state s' \\\n",
        "Decision theory deals with choosing among actions based on the desirability of their immediate outcomes. The MEU principle formalizes that an agent \\\n",
        "should do the right thing, but doesn't operationalize the advice. If agent acts to maximize a correct utility function, then agent will achieve highest \\\n",
        "possible average performance score. Utility function applies to very next state, so it can be used to guide actions step by step.\n",
        "\"\"\"  + sample_equation\n",
        "\n",
        "\n",
        "chapter16_2 =  \"\"\" The constraints for this section are covered in definitions. These are used to address the issue that utility theory needs to \\\n",
        "understand how preferences between complex lotteries are related to preverences between the underlying states of those lotteries. Rational preferences \\\n",
        "lead to utility. A utility function is proven to exist for an agent, but is not necessarily unique. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter16_3 =  \"\"\" No absolute scale for utilities, but useful to get some scale for a problem. Established by fixing utilities of any two outcomes. \\\n",
        "Given max/min utility, can assess utility of any prize S by having agent choose between S and standard lottery, adjusting p until agent is indifferent between \\\n",
        "S and the standard lottery. A micromort can be used to put a value on life itself. Utility is not proportional to monetary value. \n",
        "\n",
        "Rational way to choose best action, a*, is to maximize expected utility. Real outcomes will usually be much worse than esteimated, even if estimate is unbiased. \\\n",
        "Leads to optimizers curse (defined). Difference between normative and descriptive theory illustrated in humans choosing money with probablities (Allais paradox). \\\n",
        "Many effects lead humans to choose non-rational choices, like the certainty effect, framing effect, ambiguity aversion, and anchoring effect.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" In a sequential decision problem, utility functoin depends on the environment history rather than a single state. For every transition from s \\\n",
        "to s' via a, agent is given a reward bounded by +-Rmax. MDPs consist of set of states with initial state, set of actions for each state, transition model, and \\\n",
        "reward function. Solutions typically use dynamic programming. Solutions are called policy. If R is very negative, will take shortest path out if even leaving \\\n",
        "into a bad state. If R slightly negative, optimal policy takes no risks at all. If R > 0, life good, avoids both exits. \n",
        "\n",
        "Policies for infinite horizenor simpler, as optimal policy is stationary. If discount factor gamma is close to 0, rewards in distant future seen as insignificant, \\\n",
        "whereas if close to 1, agent will wait for long term rewards. If discount = 1, then its just a purely additive model. Assume that agent's preferences between \\\n",
        "state sequences are stationary. I.e. if you prefer one future to another starting tomorrow, then you should still prefer that future if it were starting today. In \\\n",
        "infinite sequence, can compare using average reward per time step. If using discounted utilities with infinite horizons, optimal policy is independent of starting state. \\\n",
        "\n",
        "The utility of a state is the expected reward for the next transition plus the discounted utility of the next state if agent chooses optimal action. Solutions to Bellman \\\n",
        "equation are unique. Interesting: In Tetris, if every policy is optimal, board will still eventually fill.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter17_2 =  \"\"\" Value iteration, policy iteration, and linear programming all give exact solutions offline. Monte Carlo planning gives online approximate solutions. \\\n",
        "Bellman equation basis for value iteration algorithm to solve MDP. Gives unique solutoins that correspond to optimal policy. Can think of value iteration as propagating \\\n",
        "information through the state space by local updates. The Bellman update is a contraction by a factor of gamma on space of utility vectors. Can calculate when it converges. \\\n",
        "Agent really actually cares about how well it will do if it acts according to utility function.\n",
        "\n",
        "Policy Iteration: iterates the following two steps - 1. Policy evaluation, given a policy pi_i, calculate U_i = U_pi_i, the utility of each state if pi_i were to be executed. \\\n",
        "2. Policy improvement, calculate a new MEU policy pi_i+1 using one-step look-ahead based on U_i. Policy iteration terminates when step 2 makes no more changes to the utilities. \\\n",
        "For small state spaces, policy evaluation using exact solution methods is the generally most efficient. Large state spaces can use an approximation version. Don't necessarily \\\n",
        "have to update all values at once, can choose a subset, allowing for much more efficient algorithms. \n",
        "\n",
        "Linear Programming: Consider as variables in LP the utilities U(s) of each state s. LP solvers seldom as efficient as dynamic programming for MDP\n",
        "\n",
        "Real-time dynamic programming useful in moderate-sized domains such as grid worlds. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Convergence: how do we know Vk vectors going to converge? Case 1: If tree has maximum depth M, then V_m holds the actual untruncated values. \\\n",
        "\n",
        "Case 2: If the discount is less than 1: \n",
        "\n",
        "- Sketch: for any state V_k and V_(k+1) can be viewed as depth k+1 expectimax results in nearly identical search trees\n",
        "\n",
        "- The difference is that on the bottom layer, V_(k+1) has actual rewards while V_k has zeros\n",
        "\n",
        "- That last layer is at best all R_MAX\n",
        "\n",
        "- It is at worst R_MIN\n",
        "\n",
        "- Everything discounted by gamma^k that far out\n",
        "\n",
        "- V_k and V_(k+1) are at most gamma^k max|R| different\n",
        "\n",
        "- as k increases, the values converge\n",
        "\n",
        "______\n",
        "\n",
        "Actions are easier to select from Q-values than values. \n",
        "\n",
        "Problems with Value Iteration: 1. It's slow O(S^2 * A) per iteration. 2. The \"max at each state rarely changes. 3. The policy often converges long before the values. \n",
        "\n",
        "Policy iteration converges much faster under some conditions\n",
        "\n",
        "Summary: Value Iteration: - Every iteration updates both values and (implicitely) the policy. We don't track the policy, but taking the max over actions implicitely \\\n",
        "recomputes it. Policy Iteration: - Do several passes that update utilities with fixed policy (each pass fast because we consider only one action, not all). - After the policy \\\n",
        "is evalutated, a new policy is chosen (slow like a value iteration pass). New policy will be better (or we're done). Policy iteration converges in fewer iterations but has \\\n",
        "higher time cost per iteration O(S^3).\n",
        "\n",
        "Both are Dynamic programs for solving MDPs\n",
        "\n",
        "A proper policy does NOT always exist for an MDP\n",
        "\n",
        "Utility function estimate does not have to be completely accurate to get an optimal policy\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\" : \"assigns single number to express desirability of a state\",\n",
        "\"Expected Utility\" : \"The average utility value of outcomes, weighted by probability that that outcome occurs\",\n",
        "\"maximum expected utility (MEU)\" : \"A rational agent should choose the action that maximizes the agent's expected utility\",\n",
        "\"lottery\" : \"The set of outcomes for each action; can think of each action as a ticket\",\n",
        "\"Orderability\": \"Exactly one of (A≻B),(B≻A), or (A~B) holds\",\n",
        "\"Transitivity\" : \"(A≻B)∧(B≻A)⇒(A≻C)\",\n",
        "\"Continuity\" : \"A≻B≻C⇒∃p[p,A;1-p,C]~B. If B between A,C preference, then prob p s.t. agent indifferent between B guarenteed and lottery that yields A\",\n",
        "\"Substitutability\": \"A\\~B⇒[p,A;1-p,C]\\~[p,B;1-p,C]. Agent indifferent b.t. A/B, then indifferent b.t. when B substituted for A\",\n",
        "\"Monotonicity\": \"A≻B⇒(p>q⇔[p,A;1-p,B]≻[q,A;1-q,B]). If prefers A over B, then must prefer lottery with higher prob for A\",\n",
        "\"Decomposability\": \"[p,A;1-p,[q,B;1-q,C]]~[p,A;(1-p)q,B;(1-p)(1-q),C]. Compound probabilities can be reduced to simpler ones (no fun in gambling)\",\n",
        "\"Value function/Ordinal Utility Function\" : \"agent needs only a preference ranking on the states, therefore the numbers don't matter\",\n",
        "\"Preference elicitation\" : \"presenting choices to the human and observing to get utility function\",\n",
        "\"Standard lottery\" : \"[p, u_max; (1-p), u_min]\",\n",
        "\"micromort\" : \"currency measuring the value of human life, one in a million chance of death\",\n",
        "\"QALY\" : \"Quality-adjusted life year, such as living 2 years in bad health vs. 1 year in good health\",\n",
        "\"monotonic preference\" : \"If money, agent prefers more money to less. Does not mean money behaves as utility function\",\n",
        "\"risk-averse\" : \"Prefer sur thing with payoff that is less than the expected monetary value involved in a gamble\",\n",
        "\"Certainty equivalent\" : \"value an agent accepts in place of lottery\",\n",
        "\"insurance premium\" : \"The difference between EMV of lottery and its certainty equivalent\",\n",
        "\"risk-neutral\" : \"linear curve for agent\",\n",
        "\"Optimizers curse\" : \"tendency for estimated expected utility of best coice to be too high\",\n",
        "\"Normative theory\" : \"Describes how rational agent should act (as in decision theory)\",\n",
        "\"Descriptive Theory\" : \"Describes how actual agents really do act (like humans)\",\n",
        "\"Certainty effect\" : \"People will make 'illogical' choices because they are much more attracted to certain gains.\",\n",
        "\"Ambiguity aversion\" : \"People dislike ambiguity\",\n",
        "\"Framing effect\" : \"How a question is asked influences the answer\",\n",
        "\"Anchoring effect\" : \"200 dollar wine presented first, 50 looks like a good deal now\",\n",
        "\"Markovian\" : \"probability of reaching s' froms depends only on s, not history\",\n",
        "\"Markovian Decision Process\" : \"Sequential decision problem for fuly observable, stochastic environment with Markovian transition model and additive rewards\",\n",
        "\"Policy\" : \"A solution that specifies what agent should do for any state the agent could reach\",\n",
        "\"Finite horizen\" : \"fixed time N that game must end by\",\n",
        "\"Nonstationary\" : \"a policy that depends on time\",\n",
        "\"Additive discount rewards\" : \"Sicount factor gamma applied to reward history when adding\",\n",
        "\"Proper policy\" : \"A policy that is guaranteed to reach a termical state\",\n",
        "\"Bellman equation\" : \"U(s) = max_a[sum_over_s']P(s'|s,a)[R(s,a,s') + gamma*U(s')]\",\n",
        "\"Q-function/Action-utility function\" : \"U(s) = max_a[Q(s,a)]. Expected utility of taking a given action in a given state\",\n",
        "\"Shaping theorem\" : \"Following translation leaves optimal policy unchanged: R'(s,a,s') = R(s,a,s') + gamma*Theta(s') - Theta(s)\",\n",
        "\"Potential\" : \"Theta(s). Gradient is gamma*Theta(s') - Theta(s)\",\n",
        "\"Dynamic decision networks\" : \"factored representations of terminology in Chapter 2\",\n",
        "\"Value iteration\" : \"Uses Bellman equation to update the utility value for state S at i'th iteration, applied to all states simultaneously\",\n",
        "\"Contraction\" : \"Function of one argument, when applied to 2 inputs, produces 2 outputs closer together. Basis for value iteration convergence\",\n",
        "\"Max norm\" : \"Measures length of vector by absolute value of biggest component. ||U|| = max_s|U(s)|\",\n",
        "\"Policy loss\" : \"most the agent can lose by executing pi_i instead of optimal policy pi_star. pi_i optimal before U_i converged\",\n",
        "\"Modified policy iteration\" : \"Made simpler to use on large spaces to give approximation of best policy\",\n",
        "\"Asynchronous policy iteration\" : \"Can update utility or policy for any subset of states\",\n",
        "\"Linear programming\" : \"Consider as variables in the LP the utilities U(s) of each state s\",\n",
        "\"Real-time dynamic programming\" : \"Explored states constitute a sub-MDP of main MDP, which can be solved using a previous algorithm\",\n",
        "\"N-armed bandit\" : \"bandit (slot machine) with n levers. Each lever has fixed and unknown prob dist. of winning\",\n",
        "\"Exploitation\" : \"keep using current lever that's been giving best output. Opposite of 'exploration'\",\n",
        "\"Bandit problem\" : \"Each arm M_i is Markov reward process. Overall bandit problem is an MDP.\",\n",
        "\"Markov reward process\" : \"an MDP with only one possible action\",\n",
        "\"Gittens index\" : \"Provides for simple policy, pull arm with highest Gittens index, then update Gittens indices\",\n",
        "\"Restart MDP\" : \"Replace the choice to get infinite sequence of gamma-rewards with choice to back and restart M from initial state\",\n",
        "\"Bernoulli bandit\" : \"Simple. Each arem M_i produces reward of 0 or 1 with unknown probablity\",\n",
        "\"Thompson sampling\" : \"Choose arm randomly according to the probability that it is the most optimal\",\n",
        "\"Selection problems\" : \"Similar to bandit, but different mathematically. No index function exists\",\n",
        "\"Bandit superprocess (BSP)\" : \"each arm is a full Markov decision process, rather than Markov reward with only one action. Like multitasking\",\n",
        "\"Opportunity cost\" : \"Useful to solve BSPs. How much utility is given up per time step by not using another arm\",\n",
        "\"Dominating policy\" : \"An optimal policy can be applied, converting an arm into a Markov reward process\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f54edcde-53e2-4953-a470-3752b0e3055d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Transition model for an agent written as P(s'|s, a), meaning the probability that action 'a' in state 's' reaches state s' Decision theory deals with choosing among actions based on the desirability of their immediate outcomes. The MEU principle formalizes that an agent should do the right thing, but doesn't operationalize the advice. If agent acts to maximize a correct utility function, then agent will achieve highest possible average performance score. Utility function applies to very next state, so it can be used to guide actions step by step.\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 The constraints for this section are covered in definitions. These are used to address the issue that utility theory needs to understand how preferences between complex lotteries are related to preverences between the underlying states of those lotteries. Rational preferences lead to utility. A utility function is proven to exist for an agent, but is not necessarily unique. \n\n\n## AIMA Chapter 16.3 Utility Functions\n No absolute scale for utilities, but useful to get some scale for a problem. Established by fixing utilities of any two outcomes. Given max/min utility, can assess utility of any prize S by having agent choose between S and standard lottery, adjusting p until agent is indifferent between S and the standard lottery. A micromort can be used to put a value on life itself. Utility is not proportional to monetary value. \n\nRational way to choose best action, a*, is to maximize expected utility. Real outcomes will usually be much worse than esteimated, even if estimate is unbiased. Leads to optimizers curse (defined). Difference between normative and descriptive theory illustrated in humans choosing money with probablities (Allais paradox). Many effects lead humans to choose non-rational choices, like the certainty effect, framing effect, ambiguity aversion, and anchoring effect.\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n In a sequential decision problem, utility functoin depends on the environment history rather than a single state. For every transition from s to s' via a, agent is given a reward bounded by +-Rmax. MDPs consist of set of states with initial state, set of actions for each state, transition model, and reward function. Solutions typically use dynamic programming. Solutions are called policy. If R is very negative, will take shortest path out if even leaving into a bad state. If R slightly negative, optimal policy takes no risks at all. If R > 0, life good, avoids both exits. \n\nPolicies for infinite horizenor simpler, as optimal policy is stationary. If discount factor gamma is close to 0, rewards in distant future seen as insignificant, whereas if close to 1, agent will wait for long term rewards. If discount = 1, then its just a purely additive model. Assume that agent's preferences between state sequences are stationary. I.e. if you prefer one future to another starting tomorrow, then you should still prefer that future if it were starting today. In infinite sequence, can compare using average reward per time step. If using discounted utilities with infinite horizons, optimal policy is independent of starting state. \nThe utility of a state is the expected reward for the next transition plus the discounted utility of the next state if agent chooses optimal action. Solutions to Bellman equation are unique. Interesting: In Tetris, if every policy is optimal, board will still eventually fill.\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value iteration, policy iteration, and linear programming all give exact solutions offline. Monte Carlo planning gives online approximate solutions. Bellman equation basis for value iteration algorithm to solve MDP. Gives unique solutoins that correspond to optimal policy. Can think of value iteration as propagating information through the state space by local updates. The Bellman update is a contraction by a factor of gamma on space of utility vectors. Can calculate when it converges. Agent really actually cares about how well it will do if it acts according to utility function.\n\nPolicy Iteration: iterates the following two steps - 1. Policy evaluation, given a policy pi_i, calculate U_i = U_pi_i, the utility of each state if pi_i were to be executed. 2. Policy improvement, calculate a new MEU policy pi_i+1 using one-step look-ahead based on U_i. Policy iteration terminates when step 2 makes no more changes to the utilities. For small state spaces, policy evaluation using exact solution methods is the generally most efficient. Large state spaces can use an approximation version. Don't necessarily have to update all values at once, can choose a subset, allowing for much more efficient algorithms. \n\nLinear Programming: Consider as variables in LP the utilities U(s) of each state s. LP solvers seldom as efficient as dynamic programming for MDP\n\nReal-time dynamic programming useful in moderate-sized domains such as grid worlds. \n\n\n## Module 8 Lecture Notes\n Convergence: how do we know Vk vectors going to converge? Case 1: If tree has maximum depth M, then V_m holds the actual untruncated values. \nCase 2: If the discount is less than 1: \n\n- Sketch: for any state V_k and V_(k+1) can be viewed as depth k+1 expectimax results in nearly identical search trees\n\n- The difference is that on the bottom layer, V_(k+1) has actual rewards while V_k has zeros\n\n- That last layer is at best all R_MAX\n\n- It is at worst R_MIN\n\n- Everything discounted by gamma^k that far out\n\n- V_k and V_(k+1) are at most gamma^k max|R| different\n\n- as k increases, the values converge\n\n______\n\nActions are easier to select from Q-values than values. \n\nProblems with Value Iteration: 1. It's slow O(S^2 * A) per iteration. 2. The \"max at each state rarely changes. 3. The policy often converges long before the values. \n\nPolicy iteration converges much faster under some conditions\n\nSummary: Value Iteration: - Every iteration updates both values and (implicitely) the policy. We don't track the policy, but taking the max over actions implicitely recomputes it. Policy Iteration: - Do several passes that update utilities with fixed policy (each pass fast because we consider only one action, not all). - After the policy is evalutated, a new policy is chosen (slow like a value iteration pass). New policy will be better (or we're done). Policy iteration converges in fewer iterations but has higher time cost per iteration O(S^3).\n\nBoth are Dynamic programs for solving MDPs\n\nA proper policy does NOT always exist for an MDP\n\nUtility function estimate does not have to be completely accurate to get an optimal policy\n\n\n## Module 8 Definitions\n* **Utility function** - assigns single number to express desirability of a state\n* **Expected utility** - The average utility value of outcomes, weighted by probability that that outcome occurs\n* **Maximum expected utility (meu)** - A rational agent should choose the action that maximizes the agent's expected utility\n* **Lottery** - The set of outcomes for each action; can think of each action as a ticket\n* **Orderability** - Exactly one of (A≻B),(B≻A), or (A~B) holds\n* **Transitivity** - (A≻B)∧(B≻A)⇒(A≻C)\n* **Continuity** - A≻B≻C⇒∃p[p,A;1-p,C]~B. If B between A,C preference, then prob p s.t. agent indifferent between B guarenteed and lottery that yields A\n* **Substitutability** - A\\~B⇒[p,A;1-p,C]\\~[p,B;1-p,C]. Agent indifferent b.t. A/B, then indifferent b.t. when B substituted for A\n* **Monotonicity** - A≻B⇒(p>q⇔[p,A;1-p,B]≻[q,A;1-q,B]). If prefers A over B, then must prefer lottery with higher prob for A\n* **Decomposability** - [p,A;1-p,[q,B;1-q,C]]~[p,A;(1-p)q,B;(1-p)(1-q),C]. Compound probabilities can be reduced to simpler ones (no fun in gambling)\n* **Value function/ordinal utility function** - agent needs only a preference ranking on the states, therefore the numbers don't matter\n* **Preference elicitation** - presenting choices to the human and observing to get utility function\n* **Standard lottery** - [p, u_max; (1-p), u_min]\n* **Micromort** - currency measuring the value of human life, one in a million chance of death\n* **Qaly** - Quality-adjusted life year, such as living 2 years in bad health vs. 1 year in good health\n* **Monotonic preference** - If money, agent prefers more money to less. Does not mean money behaves as utility function\n* **Risk-averse** - Prefer sur thing with payoff that is less than the expected monetary value involved in a gamble\n* **Certainty equivalent** - value an agent accepts in place of lottery\n* **Insurance premium** - The difference between EMV of lottery and its certainty equivalent\n* **Risk-neutral** - linear curve for agent\n* **Optimizers curse** - tendency for estimated expected utility of best coice to be too high\n* **Normative theory** - Describes how rational agent should act (as in decision theory)\n* **Descriptive theory** - Describes how actual agents really do act (like humans)\n* **Certainty effect** - People will make 'illogical' choices because they are much more attracted to certain gains.\n* **Ambiguity aversion** - People dislike ambiguity\n* **Framing effect** - How a question is asked influences the answer\n* **Anchoring effect** - 200 dollar wine presented first, 50 looks like a good deal now\n* **Markovian** - probability of reaching s' froms depends only on s, not history\n* **Markovian decision process** - Sequential decision problem for fuly observable, stochastic environment with Markovian transition model and additive rewards\n* **Policy** - A solution that specifies what agent should do for any state the agent could reach\n* **Finite horizen** - fixed time N that game must end by\n* **Nonstationary** - a policy that depends on time\n* **Additive discount rewards** - Sicount factor gamma applied to reward history when adding\n* **Proper policy** - A policy that is guaranteed to reach a termical state\n* **Bellman equation** - U(s) = max_a[sum_over_s']P(s'|s,a)[R(s,a,s') + gamma*U(s')]\n* **Q-function/action-utility function** - U(s) = max_a[Q(s,a)]. Expected utility of taking a given action in a given state\n* **Shaping theorem** - Following translation leaves optimal policy unchanged: R'(s,a,s') = R(s,a,s') + gamma*Theta(s') - Theta(s)\n* **Potential** - Theta(s). Gradient is gamma*Theta(s') - Theta(s)\n* **Dynamic decision networks** - factored representations of terminology in Chapter 2\n* **Value iteration** - Uses Bellman equation to update the utility value for state S at i'th iteration, applied to all states simultaneously\n* **Contraction** - Function of one argument, when applied to 2 inputs, produces 2 outputs closer together. Basis for value iteration convergence\n* **Max norm** - Measures length of vector by absolute value of biggest component. ||U|| = max_s|U(s)|\n* **Policy loss** - most the agent can lose by executing pi_i instead of optimal policy pi_star. pi_i optimal before U_i converged\n* **Modified policy iteration** - Made simpler to use on large spaces to give approximation of best policy\n* **Asynchronous policy iteration** - Can update utility or policy for any subset of states\n* **Linear programming** - Consider as variables in the LP the utilities U(s) of each state s\n* **Real-time dynamic programming** - Explored states constitute a sub-MDP of main MDP, which can be solved using a previous algorithm\n* **N-armed bandit** - bandit (slot machine) with n levers. Each lever has fixed and unknown prob dist. of winning\n* **Exploitation** - keep using current lever that's been giving best output. Opposite of 'exploration'\n* **Bandit problem** - Each arm M_i is Markov reward process. Overall bandit problem is an MDP.\n* **Markov reward process** - an MDP with only one possible action\n* **Gittens index** - Provides for simple policy, pull arm with highest Gittens index, then update Gittens indices\n* **Restart mdp** - Replace the choice to get infinite sequence of gamma-rewards with choice to back and restart M from initial state\n* **Bernoulli bandit** - Simple. Each arem M_i produces reward of 0 or 1 with unknown probablity\n* **Thompson sampling** - Choose arm randomly according to the probability that it is the most optimal\n* **Selection problems** - Similar to bandit, but different mathematically. No index function exists\n* **Bandit superprocess (bsp)** - each arm is a full Markov decision process, rather than Markov reward with only one action. Like multitasking\n* **Opportunity cost** - Useful to solve BSPs. How much utility is given up per time step by not using another arm\n* **Dominating policy** - An optimal policy can be applied, converting an arm into a Markov reward process\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Bandit problem good formal model for many real life problems. Key aspects are that arms are independent. Gittens index can be calcluated to provide a \\\n",
        "simple optimal policy: pull lever with highest Gittens index, then update gittens indeces. O(n) for initial indices, O(1) for each decision after. When calculating Gittens \\\n",
        "index, its essentially at tipping point of choosing arm M and choosing fixed arm M_lambda (i.e. value of choosing M is same as value of choosing infinite sequence of lambda-rewards) \\\n",
        "In Bernoulli bandit problem, arms with higher payoff probablities preferred, but an exploration bonus exists for arms only tried a few times so far. \n",
        "\n",
        "Many \"nearly as good\" solutions exist. First class uses upper confidence bound. Choose arm with highest upper bound of confidence. Another method Thompson chooses arm randomly \\\n",
        "based on probablity that that arm is the optimal once. Regret grows as O(logN). \n",
        "\n",
        "Task of choosing best option under similar conditions called Selection Problem. Similar to bandit but different mathematically: i.e., no index function exists for \\\n",
        "selection problems. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Goal in reinforcement learning is same as goal in Markoc Decision Processes, to maximize the expected sum of rewards. Difference is agent is not \\\n",
        "given an MDP to solve, it is in the MDP. Two types of reinforcement learning. \n",
        "\n",
        "1. Model-based. Uses a transition model to intreprety and make decisions. Model may be unkown or known. Generally learn a utility function U(s). \n",
        "\n",
        "2. Model-free reinforcement learning: two varieties: 2a) Action-utility learning - Q-learning, where Q denotes sum of rewards from state s onward if 'a' taken. \\\n",
        "2b) Policy search - agent learns policy pi(s) that maps directly from states to actions. \n",
        "\n",
        "Can use passive reinforcement learning or active reinforcement learning (both defined below). \n",
        "\"\"\" \n",
        "\n",
        "\n",
        "chapter22_2 =  \"\"\" Difference between policty evaluation and passive learning is that in passive learning, the agent doesn't know the transition model P(s'|s,a), nor \\\n",
        "the reward function R(s,a,s'). Passive learning agent must complete trials, then calculates direct utility estimation, where each trial provides a sample o this quantity \\\n",
        "for each state visited. In infinitely many trials, sample average will converge to true expectation for each state. Reduces to standard supervised learning problem \\\n",
        "where each example is a (state, reward-to-go) pair. This however ignores that the utility of a state is determined by the reward and the expected utility of the \\\n",
        "successor states. Direct learning misses opportunity for learning by ignoring connection between states. Converges very slowly because of this. \n",
        "\n",
        "Adaptive dynamic programming learns transition models connecting states and solves Marov decision processes using dynamic programming. Plugs in the learned transition model. \\\n",
        "Can also adopt approach of modified policy iteration to update utility estimates after each change in learned model. ADP agent limited only by its ability to laern the \\\n",
        "transition model. \n",
        "\n",
        "Temporal difference (TD) learning: Adjusts utility estimates toward the ideal equilibriumj that holds locally when the utility estimates are correct using a learning rate parameter. \\\n",
        "TD does not need a transition model to perform its updates! Environment itself supplies cnnection between neighboring states in form of observed transitions. Key difference \\\n",
        "between ADP and TD: TD adjusts a state to agree with observed successor, while ADP adjusts state to agree with all successors that might occur, weighted by their probs. Also, \\\n",
        "while TD makes adjustment per observed transition, ADP makes as many as it needs to restore consistency between utility estimates U and transition model P. TD basically first \\\n",
        "approximation of ADP. Approximate ADP can learn roughly as fast as full ADP using strategies such as prioritized sweeping heuristics. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter22_3 =  \"\"\" Ative learning agent must decide what actions to take. Can be greedy, where it learns a path quickly and sticks to it, foregoing exploration, but rarely \\\n",
        "is an optimal solution. Non-optimal because the learned environment is not the same as the true environment. Can use GLIE scheme to eventually get the true environment. \\\n",
        "With f(u,n), actions that lead toward unexplored regions are weighted more highly, rather than just actions themselves that are unfamiliar. \n",
        "\n",
        "Three mathematical approaches that favor choosing a policy that works resasonably well for a whole of models reasonably accurate - Bayesian reinforcement learning, robust \\\n",
        "control theory, and (maybe?) Temporal-difference Q-learning. Bayesian essentially becomes an exploratin POMDP. Robust control theory basically has a set of possible models \\\n",
        "and solves for the bets outcome in the worst-case scenario. Issue is that it can become overly conservative. The Q-learning method avoids need of a model by learning \\\n",
        "action-utility function Q(s,a) rather than usility fucntion U(s). IMPORTANT: A TD Q-learning agent does not need a transtion model, P(s'|s,a) either for learning or for \\\n",
        "action selection. Difference between Q-learning and SARSA is that Q-learning backs up the Q-value from the best action in s', SARSA waits until action is ataken and backs up \\\n",
        "Q-value for that action. Q-learning is off-policy, SARSA is on-policy. Q-learning more flexible than SARSA. SARSA more appropriate if overall policy is even partly \\\n",
        "controlled by other agents or programs, where it's better to learn a Q-function for what will actually happen.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter22_4 =  \"\"\" Convergence too slow on many real world problems. Must use function approximation, such as weighted linear features, to approximate. Most importantly, \\\n",
        "allows agents to generalize from states it has visited to those it hasn't. Changing parameters theta_i after seen a transition changes U_theta for every other state! Features \\\n",
        "can be arbitrary nonlinear combinations of the state variables. Catastrophic forgetting is a common problem, but can be solved by experience replay (defined below). \n",
        "\n",
        "Deep RL rarely applied in commercial settings compared to other applications of deep learning. \n",
        "\n",
        "Can use pseudorewards in sparse reward problems, but has issue that the agent my learn to maximize the pseudorewards rather than the actual rewards. Can use \\\n",
        "hierarchical reinforcement learning to break long action sequences into smaller chunks that are easier to learn. Hierarchcal learning begins with a partial program that \\\n",
        "outlines the hierarchical structure for the agent's behaviour. This provides the general know-how of a program, i.e. structural organization for complex behaviours, then learning \\\n",
        "process just works out details. Utilizes a joint state space. Machine state = current internal state of agent program. Choice state = program counter for 'm' is at choice \\\n",
        "point in agent program. Hierarchical structure provides natural additive decomposition of the overall utility function.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter22_5 =  \"\"\" Simplest strategy, change policy as long as its improving then stop. NOTE: If policy is represented by Q-functions, then policy search results in a process \\\n",
        "that learns Q functions, but this is NOT the same as Q-learning. Policy search: Optimize theta to optimize performance. Q-learning: Optimize theta to find Q close to optimal Q. \\\n",
        "Problem with policy learning is that a policy is a discontiuous function of the parameters when actions are discrete. Makes gradient based search difficult. Thus, most policy \\\n",
        "search methods use stochastic policy, the probability of selecting action a in state s. Use a policy value and policy gradient to incrementelly find optimal policy. \n",
        "\n",
        "Blackjack example: Use correlated sampling (giving both programs the same set of hands to test with). to eliminate measurement error due to the difference in cards received. \\\n",
        "The number of random sequences required to ensure that the value of every policy is well estimated depends only on complexity of the policy space, and not complexity of \\\n",
        "the underlying domain.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "\n",
        "Passive reinforcement learning: Just execute policy and learn from experience. This is NOT offline planning!\n",
        "\n",
        "Direct evaluation problems: 1. waste information about state connections, each state must be learned separately, takes a long time to learn\n",
        "\n",
        "Q-learning converges to optimal policy, even if you're acting suboptimally\n",
        "\n",
        "Regret: Measure of total mistake cost. Difference between expected rewards and optimal rewards\n",
        "\n",
        "Direct utility estimation ONLY uses sample transitions\n",
        "\n",
        "ADP and TD both adjust utility of state locally to agree with utility of at least one successor state \n",
        "\n",
        "Q-learning with linear function approximation will NOT always converge to the optimal policy\n",
        "\n",
        "A deterministic policy is a mapping from states to actions\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"N-armed bandit\" : \"bandit (slot machine) with n levers. Each lever has fixed and unknown prob dist. of winning\",\n",
        "\"Exploitation\" : \"keep using current lever that's been giving best output. Opposite of 'exploration'\",\n",
        "\"Bandit problem\" : \"Each arm M_i is Markov reward process. Overall bandit problem is an MDP.\",\n",
        "\"Markov reward process\" : \"an MDP with only one possible action\",\n",
        "\"Gittens index\" : \"Provides for simple policy, pull arm with highest Gittens index, then update Gittens indices\",\n",
        "\"Restart MDP\" : \"Replace the choice to get infinite sequence of gamma-rewards with choice to back and restart M from initial state\",\n",
        "\"Bernoulli bandit\" : \"Simple. Each arem M_i produces reward of 0 or 1 with unknown probablity\",\n",
        "\"Thompson sampling\" : \"Choose arm randomly according to the probability that it is the most optimal\",\n",
        "\"Selection problems\" : \"Similar to bandit, but different mathematically. No index function exists\",\n",
        "\"Bandit superprocess (BSP)\" : \"each arm is a full Markov decision process, rather than Markov reward with only one action. Like multitasking\",\n",
        "\"Opportunity cost\" : \"Useful to solve BSPs. How much utility is given up per time step by not using another arm\",\n",
        "\"Dominating policy\" : \"An optimal policy can be applied, converting an arm into a Markov reward process\",\n",
        "\"Reinforcement learning\" : \"agent interacts with rold and recieves rewards based on its performance\",\n",
        "\"Sparse rewards\" : \"majority of states don't give the agent a reward signal at all\",\n",
        "\"Model-based reinforcement learning\" : \"Uses a transition model to interpret reward signals and make decisions\",\n",
        "\"Model-free reinforcement learning\" : \"Agent doesn't know transition model. Learns through more direct representation\",\n",
        "\"Action-utility learning\" : \"Q-learning. Q denotes sum of rewards from state s onward if 'a' taken\",\n",
        "\"Policy search\" : \"agent learns policy pi(s) that maps directly from states to actions\",\n",
        "\"Passive reinforcement learning\" : \"agent's policy is fixed and task is to learn utilities of states or state-action pairs\",\n",
        "\"Active reinforcement learning\" : \"Agent must figure out what to do\",\n",
        "\"Direct utility estimation\" : \"Utility of state defined as expected total reward from that state onward (expected reward-to-go). Trial=sample\",\n",
        "\"Adaptive dynamic programming\" : \"Learns transition models connecting states and solves Marov decision processes using dynamic programming\",\n",
        "\"Tempral-difference equation\" : \"U_pi(s) <- U_pi(s) _ alpha [R(s,pi(s),s') + gammaxU_pi(s') - U_pi(s)]\",\n",
        "\"Prioritized sweeping heuristic\" : \"used to generate more efficient ADP by adjust states whose likely successors have had large adjusment in utility\",\n",
        "\"Active learning agent\" : \"Agent gets to decide what actions to take\",\n",
        "\"Greedy agent\" : \"Learns a sort-of-optimal policy really fast and sticks to it, foregoing future exploration\",\n",
        "\"GLIE\" : \"Greedy in the limit of infinite exploration. Try each action in each state over and over until probabilty optimal action missed is essentialy 0\",\n",
        "\"Exploration function\" : \"f(u,n) determines how greed is traded off against curiosity. Increasing in u, decreasing in n\",\n",
        "\"Absorbing state\" : \"when agent has no actions that have any effect and no rewards\",\n",
        "\"Bayesian reinforcement learning\" : \"Assume prior probability P(h) over hypothese h about the true model. Posterior-prob obtained by Baye's rule\",\n",
        "\"Robust control thoery\" : \"Set of models, solve for best-case scenario for worst-case model. Can be too conservative\",\n",
        "\"SARSA\" : \"(state,action,reward,state,action). Similar to Q-learning update, but SARSA updates with Q-value of the action a' that is actualy taken\",\n",
        "\"Function approximation\" : \"Process of constructnig a compact approximation of true utility function / Q-function\",\n",
        "\"Widro-Hoff rule / Delta rule\" : \"an error function and computing its gradient with respect to the parameters\",\n",
        "\"catastrophic forgetting\" : \"Car example. Drives in center too long, forgets the edges are dangerous\",\n",
        "\"experience replay\" : \"Relive early crashes often so it doesn't forget\",\n",
        "\"Reward shaping\" : \"helps solve credit assignment by providing an agent with pseudorewards, strat known as reward shaping\",\n",
        "\"Hierarchical reinforcement learning\" : \"Break long action sequences into smaller chunks until they are easy to learn\",\n",
        "\"Joint state space\" : \"Each state (s,m) is composed of physical state and machine state\",\n",
        "\"Additive decomposition\" : \"Can decompose problem, learn smaller utilitys, and add together back to entire problem\",\n",
        "\"Policy search\" : \"Keep changing policy as long as performance improves, then stop. Simplest strategy\",\n",
        "\"Stochastic policy\" : \"probablility of selecting action 'a' in state 's', used in policy search\",\n",
        "\"Coreelated sampling\" : \"Give both programs the same set of hands\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a713b519-99d5-4625-b8d6-ed8cfbf4cfb5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Bandit problem good formal model for many real life problems. Key aspects are that arms are independent. Gittens index can be calcluated to provide a simple optimal policy: pull lever with highest Gittens index, then update gittens indeces. O(n) for initial indices, O(1) for each decision after. When calculating Gittens index, its essentially at tipping point of choosing arm M and choosing fixed arm M_lambda (i.e. value of choosing M is same as value of choosing infinite sequence of lambda-rewards) In Bernoulli bandit problem, arms with higher payoff probablities preferred, but an exploration bonus exists for arms only tried a few times so far. \n\nMany \"nearly as good\" solutions exist. First class uses upper confidence bound. Choose arm with highest upper bound of confidence. Another method Thompson chooses arm randomly based on probablity that that arm is the optimal once. Regret grows as O(logN). \n\nTask of choosing best option under similar conditions called Selection Problem. Similar to bandit but different mathematically: i.e., no index function exists for selection problems. \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n Goal in reinforcement learning is same as goal in Markoc Decision Processes, to maximize the expected sum of rewards. Difference is agent is not given an MDP to solve, it is in the MDP. Two types of reinforcement learning. \n\n1. Model-based. Uses a transition model to intreprety and make decisions. Model may be unkown or known. Generally learn a utility function U(s). \n\n2. Model-free reinforcement learning: two varieties: 2a) Action-utility learning - Q-learning, where Q denotes sum of rewards from state s onward if 'a' taken. 2b) Policy search - agent learns policy pi(s) that maps directly from states to actions. \n\nCan use passive reinforcement learning or active reinforcement learning (both defined below). \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Difference between policty evaluation and passive learning is that in passive learning, the agent doesn't know the transition model P(s'|s,a), nor the reward function R(s,a,s'). Passive learning agent must complete trials, then calculates direct utility estimation, where each trial provides a sample o this quantity for each state visited. In infinitely many trials, sample average will converge to true expectation for each state. Reduces to standard supervised learning problem where each example is a (state, reward-to-go) pair. This however ignores that the utility of a state is determined by the reward and the expected utility of the successor states. Direct learning misses opportunity for learning by ignoring connection between states. Converges very slowly because of this. \n\nAdaptive dynamic programming learns transition models connecting states and solves Marov decision processes using dynamic programming. Plugs in the learned transition model. Can also adopt approach of modified policy iteration to update utility estimates after each change in learned model. ADP agent limited only by its ability to laern the transition model. \n\nTemporal difference (TD) learning: Adjusts utility estimates toward the ideal equilibriumj that holds locally when the utility estimates are correct using a learning rate parameter. TD does not need a transition model to perform its updates! Environment itself supplies cnnection between neighboring states in form of observed transitions. Key difference between ADP and TD: TD adjusts a state to agree with observed successor, while ADP adjusts state to agree with all successors that might occur, weighted by their probs. Also, while TD makes adjustment per observed transition, ADP makes as many as it needs to restore consistency between utility estimates U and transition model P. TD basically first approximation of ADP. Approximate ADP can learn roughly as fast as full ADP using strategies such as prioritized sweeping heuristics. \n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Ative learning agent must decide what actions to take. Can be greedy, where it learns a path quickly and sticks to it, foregoing exploration, but rarely is an optimal solution. Non-optimal because the learned environment is not the same as the true environment. Can use GLIE scheme to eventually get the true environment. With f(u,n), actions that lead toward unexplored regions are weighted more highly, rather than just actions themselves that are unfamiliar. \n\nThree mathematical approaches that favor choosing a policy that works resasonably well for a whole of models reasonably accurate - Bayesian reinforcement learning, robust control theory, and (maybe?) Temporal-difference Q-learning. Bayesian essentially becomes an exploratin POMDP. Robust control theory basically has a set of possible models and solves for the bets outcome in the worst-case scenario. Issue is that it can become overly conservative. The Q-learning method avoids need of a model by learning action-utility function Q(s,a) rather than usility fucntion U(s). IMPORTANT: A TD Q-learning agent does not need a transtion model, P(s'|s,a) either for learning or for action selection. Difference between Q-learning and SARSA is that Q-learning backs up the Q-value from the best action in s', SARSA waits until action is ataken and backs up Q-value for that action. Q-learning is off-policy, SARSA is on-policy. Q-learning more flexible than SARSA. SARSA more appropriate if overall policy is even partly controlled by other agents or programs, where it's better to learn a Q-function for what will actually happen.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Convergence too slow on many real world problems. Must use function approximation, such as weighted linear features, to approximate. Most importantly, allows agents to generalize from states it has visited to those it hasn't. Changing parameters theta_i after seen a transition changes U_theta for every other state! Features can be arbitrary nonlinear combinations of the state variables. Catastrophic forgetting is a common problem, but can be solved by experience replay (defined below). \n\nDeep RL rarely applied in commercial settings compared to other applications of deep learning. \n\nCan use pseudorewards in sparse reward problems, but has issue that the agent my learn to maximize the pseudorewards rather than the actual rewards. Can use hierarchical reinforcement learning to break long action sequences into smaller chunks that are easier to learn. Hierarchcal learning begins with a partial program that outlines the hierarchical structure for the agent's behaviour. This provides the general know-how of a program, i.e. structural organization for complex behaviours, then learning process just works out details. Utilizes a joint state space. Machine state = current internal state of agent program. Choice state = program counter for 'm' is at choice point in agent program. Hierarchical structure provides natural additive decomposition of the overall utility function.\n\n\n## Module 9 Lecture Notes\n\n\nPassive reinforcement learning: Just execute policy and learn from experience. This is NOT offline planning!\n\nDirect evaluation problems: 1. waste information about state connections, each state must be learned separately, takes a long time to learn\n\nQ-learning converges to optimal policy, even if you're acting suboptimally\n\nRegret: Measure of total mistake cost. Difference between expected rewards and optimal rewards\n\nDirect utility estimation ONLY uses sample transitions\n\nADP and TD both adjust utility of state locally to agree with utility of at least one successor state \n\nQ-learning with linear function approximation will NOT always converge to the optimal policy\n\nA deterministic policy is a mapping from states to actions\n\n\n## Module 9 Definitions\n* **N-armed bandit** - bandit (slot machine) with n levers. Each lever has fixed and unknown prob dist. of winning\n* **Exploitation** - keep using current lever that's been giving best output. Opposite of 'exploration'\n* **Bandit problem** - Each arm M_i is Markov reward process. Overall bandit problem is an MDP.\n* **Markov reward process** - an MDP with only one possible action\n* **Gittens index** - Provides for simple policy, pull arm with highest Gittens index, then update Gittens indices\n* **Restart mdp** - Replace the choice to get infinite sequence of gamma-rewards with choice to back and restart M from initial state\n* **Bernoulli bandit** - Simple. Each arem M_i produces reward of 0 or 1 with unknown probablity\n* **Thompson sampling** - Choose arm randomly according to the probability that it is the most optimal\n* **Selection problems** - Similar to bandit, but different mathematically. No index function exists\n* **Bandit superprocess (bsp)** - each arm is a full Markov decision process, rather than Markov reward with only one action. Like multitasking\n* **Opportunity cost** - Useful to solve BSPs. How much utility is given up per time step by not using another arm\n* **Dominating policy** - An optimal policy can be applied, converting an arm into a Markov reward process\n* **Reinforcement learning** - agent interacts with rold and recieves rewards based on its performance\n* **Sparse rewards** - majority of states don't give the agent a reward signal at all\n* **Model-based reinforcement learning** - Uses a transition model to interpret reward signals and make decisions\n* **Model-free reinforcement learning** - Agent doesn't know transition model. Learns through more direct representation\n* **Action-utility learning** - Q-learning. Q denotes sum of rewards from state s onward if 'a' taken\n* **Policy search** - Keep changing policy as long as performance improves, then stop. Simplest strategy\n* **Passive reinforcement learning** - agent's policy is fixed and task is to learn utilities of states or state-action pairs\n* **Active reinforcement learning** - Agent must figure out what to do\n* **Direct utility estimation** - Utility of state defined as expected total reward from that state onward (expected reward-to-go). Trial=sample\n* **Adaptive dynamic programming** - Learns transition models connecting states and solves Marov decision processes using dynamic programming\n* **Tempral-difference equation** - U_pi(s) <- U_pi(s) _ alpha [R(s,pi(s),s') + gammaxU_pi(s') - U_pi(s)]\n* **Prioritized sweeping heuristic** - used to generate more efficient ADP by adjust states whose likely successors have had large adjusment in utility\n* **Active learning agent** - Agent gets to decide what actions to take\n* **Greedy agent** - Learns a sort-of-optimal policy really fast and sticks to it, foregoing future exploration\n* **Glie** - Greedy in the limit of infinite exploration. Try each action in each state over and over until probabilty optimal action missed is essentialy 0\n* **Exploration function** - f(u,n) determines how greed is traded off against curiosity. Increasing in u, decreasing in n\n* **Absorbing state** - when agent has no actions that have any effect and no rewards\n* **Bayesian reinforcement learning** - Assume prior probability P(h) over hypothese h about the true model. Posterior-prob obtained by Baye's rule\n* **Robust control thoery** - Set of models, solve for best-case scenario for worst-case model. Can be too conservative\n* **Sarsa** - (state,action,reward,state,action). Similar to Q-learning update, but SARSA updates with Q-value of the action a' that is actualy taken\n* **Function approximation** - Process of constructnig a compact approximation of true utility function / Q-function\n* **Widro-hoff rule / delta rule** - an error function and computing its gradient with respect to the parameters\n* **Catastrophic forgetting** - Car example. Drives in center too long, forgets the edges are dangerous\n* **Experience replay** - Relive early crashes often so it doesn't forget\n* **Reward shaping** - helps solve credit assignment by providing an agent with pseudorewards, strat known as reward shaping\n* **Hierarchical reinforcement learning** - Break long action sequences into smaller chunks until they are easy to learn\n* **Joint state space** - Each state (s,m) is composed of physical state and machine state\n* **Additive decomposition** - Can decompose problem, learn smaller utilitys, and add together back to entire problem\n* **Stochastic policy** - probablility of selecting action 'a' in state 's', used in policy search\n* **Coreelated sampling** - Give both programs the same set of hands\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 = \"\"\" Old way of using belief states and having a plan for everything only works on simple problems. The \\\n",
        "rational decision depends on both the relative importance of various goals and the likelihood that, and degree, they will \\\n",
        "be achieved. Real world diagnosis problems almost always have uncertainty. Can't use logic to cope with domains like this \\\n",
        "(example: diagnosing tooth ache). Fails due to Laziness, Theoretical ignorance, and Practical ignorance, defined below. \\\n",
        "Theory of prob. summarizes the uncertainty the comes from humans laziness and ignorance, solving qualification problem. \\\n",
        "Decision theory = probablility theory + utility theory. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter12_2 = \"\"\" Set of all worlds called sample space; mutually exclusive and exhaustive. Probablility model associates each possible \\\n",
        "with a numerical probability. Events satisfy an assertion. For each proposition, the corresponding worlds in which the proposition holds. \\\n",
        "Unconditional vs. Conditional probability examples given. A possible world is defined to be an assignment of values to all of the \\\n",
        "random variables under consideration. De Finetti's theorem implies that no rational agent can have beliefs that violate the axioms of probability. \\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter12_3 = \"\"\" Section describes how to calculate probabilities and marginal probabilities given full joint distributions. Already understand very well. \\\n",
        "Conditional probability given as P(cavity | toothache) = P(cavity AND toothache) / P(toothache). Can use normalization as shortcut or if don't know some values. \\\n",
        "Full joint distrubution in tabular form seldom a practical tool. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter12_4 = \"\"\" Can decompose large distrubution tables, especially using independence between variables. Independence assertions usually based on knowledge of \\\n",
        "the domain. Very nice when able to use independence, but generally doesn't work for most real world problems.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter12_5 = \"\"\" Bayes rule (defined below) underlies most modern AI systems. Can also be written as P(cause|effect) = P(effect | cause)P(cause) / P(effect). \\\n",
        "P(effect|cause) is the causal direction, and P(cause|effect) is the diagnostic direction. Diagnostic knowledge usually more fragile than causal knowledge. KEY \\\n",
        "POINT: For n symptoms that are all conditionally independent given Cavity, the size of the representation grows as O(n) instead of O(2^n). Therefore, conditional \\\n",
        "independence assertions allows probabilistic systems to scale up; also they are more commonly available than absolute independence assertions. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter12_6 = \"\"\" Naive Bayes model is P(cause, Effect_1, Effect_2, .... , Effect_n) = P(Cause)(product_over_i)P(Effect_i)|Cause). Considered Naive because its usually \\\n",
        "simplifying things, when in reality the effect varaibles are not strictly independent. However, even in this case it works very well. Run time is linear in the number of \\\n",
        "observed effects and doesn't depend on the number of unobserved effects. Decent at language classification, even though each word specifically isn't independent \\\n",
        "('First quarter' example). Widely used for language determination, document retrieval, spam filtering, and other classifications. More sophisticated models should be used in \\\n",
        "fields like medicine. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter12_7 = \"\"\" Uncertainty can arise in the Wumpus world. Good example of how to use the previously discussed theorems to improve choosing a square in to move to \\\n",
        "in the Wumpus world.\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 = \"\"\" Intro: Predicting words important for applications like speech recognition, spelling correction, and grammatical error correction. \\\n",
        "Also useful for AAC (Augmentative and alternative communication) systems (used by people who are unable to speak). n-grams much simpler than state \\\n",
        "of the art, but demonstrate fundamental concepts.\n",
        "\n",
        "Ch3_1: P(w/h) = probability of a word w given a history h. Method of estimating probs directly from word counts fine, but even web not \\\n",
        "big enough to have a large enough corpus; senteces are creative. Chain rule gives probability of a word given the previous words (covered in AIMA). \\\n",
        "Bigram model for P(the|Walden Pond's water is so transparant that) is approximated as P(the|that). n-gram model looks at n - 1 words into the past. \\\n",
        "Calculating probability of \"I want English food\" given a corpus given. Use log probabilities to avoid too small of numbers, since everything is \\\n",
        "less than or equal to 1.\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Best way to evaulate performance of a language model is extrinsic evaluation (Defined below). Generally very expensive, so can \\\n",
        "be better to use intrinsic evaluation (test set and training set). Whichever model assigns a higher probability to the test set is the better \\\n",
        "model. Generally divide into 80% training, 10% development, and 10% test. Don't actually use raw probabilities, but perplexity (defined below). \\\n",
        "Minimizing perplexity is good. Perplexity can also be described as the weighted average branching factor of a language. The higher the 'n' of the \\\n",
        "n-gram model, the lower the perplexity. Note: Perplexity of two language models only comparable if they use identical vocabularies. Decreasing \\\n",
        "perplexity in instristic environment doesn't always decrease it in extrinsic test, so good to check extrinsicly too to make sure. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "SLP_chapter3_3 = \"\"\" Sampling from a language model is to generate some sentences, choosing each sentence according to its likelihood defined by \\\n",
        "the model. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "SLP_chapter3_4 = \"\"\" n-grams do a better and better job of modeling the training corpus as we increase the value of N. Statistical models are mostly \\\n",
        "useless if training and test sets are as different as Shakespeare and the WSJ. Must use similar genre at least for training and test sets. Also \\\n",
        "issue of sparcity, any corpus could be missing perfectly logical sentences, thus giving the model a 0% chance of thinking they could exist. A \\\n",
        "sentence that never occurs in the training set but does in the test set is called a 'zero'. OOV rate = percentage of out-of-vocabulary words that \\\n",
        "appear in the test set. Two ways to fix. 1. Convert unknown words to just <UNK> and treat them as all one word. 2. Build vocabulary implicitely, \\\n",
        "and just call things with very low word-count as <UNK>. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "SLP_chapter3_5 = \"\"\" Smoothing defined below. Many ways to do this, Laplace, add-k, stupid backoff, and Kneser-Ney (Section 3_6). \n",
        "\n",
        "Laplace smoothing: Add 1 to all the n-gram counts before normalizing to probabilities. All 0's go to 1's with this. Not very robust, but good \\\n",
        "concept fundumentally. \n",
        "\n",
        "Add-k smoothing: Add even less than 1 to the 0-counts. Can be chosen by optimizing on a devset. Still doesn't work very well for many applications\n",
        "\n",
        "Backoff and Interpolation: Backoff method is purposely using less context if model hasn't seen (use a bigram instead of a trigram). Interpolation is \\\n",
        "mixing all the probability estimates from many n-gram estimators (bigram, trigram, etc.). \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "SLP_chapter3_7 = \"\"\" Can prune language models, such as only use words with a count threshold > 40 like Googles does. Stupid back-off is sufficient \\\n",
        "in many cases, where there's no discounting of higher-order probabilities, you just backoff to a lower-order n-gram if there's a 0-count. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "\n",
        "Bigram model only considers i{w-1}\n",
        "\n",
        "In trigram model, the probabilities of all words w given w{i-1} and w{i-2} add up to 1\n",
        "\n",
        "Effect of Markov assumption in n-gram models is it makes it possible to estimate the probabilities from data\n",
        "\n",
        "Chain rule: P(x_1,x_2,x_3,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)...P(x_n|x1,...,x_(n-1))\n",
        "\n",
        "Maximum Likelihood Estimate: P(w_i|w_(i-1)) = count(w_(i-1), w_i) / count(w_(i-1))\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Belief state\" : \"old way: represent all possible states, and have plan for everything\",\n",
        "\"Qualification problem\" : \"Having infinitely many contigency plans (I.e. what if meteor hits the car)\",\n",
        "\"Laziness\" : \"Too much work to think of all exceptions\",\n",
        "\"Theoretical ignorance\" : \"No complete theory for a domain\",\n",
        "\"Practical ignorance\" : \"Would need to many test to run, even if knew of all the rules\",\n",
        "\"Ontological commitments\" : \"World is composed of facts that do or do not hold\",\n",
        "\"Epistemological commitments\" : \"Logical agent believes true/false/no opinion, but probablistic agent believes between 0 and 1\",\n",
        "\"Decision theory\" : \"An agent is rational iff it chooses action that yields highest expected utility, averaged over all outcomes\",\n",
        "\"Sample space\" : \"Set of all possible worlds; mutuallyl exclusive and exhaustive\",\n",
        "\"Probability model\" : \"Associates numerical probability with each possible world\",\n",
        "\"Event\" : \"Sets that satisfy an assertion\",\n",
        "\"Unconditional/prior probabilities\" : \"Degrees of belief in proposition in absence of any other information\",\n",
        "\"Conditional probability\" : \"Evidence already. Prob of rolling eleven total given first die is a 5\",\n",
        "\"Factored representation\" : \"possible world represented by set of variable/value pairs\",\n",
        "\"Random variable\" : \"Variables in probability theory. Function that maps from domain of possible worlds to some range\",\n",
        "\"Probability function\" : \"Probability that a random variable takes on some value x as a parameterized function of x\",\n",
        "\"Joint probability distribution\" : \"Distributions on multiple variables\",\n",
        "\"Inclusion-exclusion principle\" : \"P(a OR b) = P(a) + P(b) - P(a AND b)\",\n",
        "\"Probabilistic inference\" : \"computatin of posterior probabilities for query propositions given evidence\",\n",
        "\"Marginilization/summing out\" : \"sums up the probabilities for each possible value of the other variables\",\n",
        "\"Independence\" : \"P(a|b) = P(a), P(b|a) = p(a), P(a,b) = P(a)P(b)\",\n",
        "\"Bayes' Rule\" : \"P(b|a) = P(a|b)P(b) / P(a)\",\n",
        "\"Conditional independence\" : \"P(toothache AND catch | Cavity) = P(toothache | Cavity)P(catch | Cavity)\",\n",
        "\"Separation\" : \"Cavity separates toothace and catch because its a direct cause of both\",\n",
        "\"Language models\" : \"Models that assign probabilities to sequences of words\",\n",
        "\"Bigram model\" : \"P(w_n|w_(1:n-1)) =~ P(w_n) | w_(n-1)\",\n",
        "\"Markov assumption\" : \"Probability that a word depends only on the previous word\",\n",
        "\"Relative frequency\" : \"ratio of observed frequency of a particular sequency to the observed frequency of a prefix\",\n",
        "\"Extrinsic evaluation\" : \"Embed language model in an application and measure how much the application improves\",\n",
        "\"test set\" : \"The 'held out' data that will be used to test after model used on training set\",\n",
        "\"Development set (devset)\" : \"A test set that is trained on a lot, giving need for a fresh new test set\",\n",
        "\"Perplexity\" : \"The inverse probability of the test set, normalized by number of words. Also, 2^(power of cross-entropy)\",\n",
        "\"Sampling\" : \"Choosing random points from a distribution according to their likelihood\",\n",
        "\"Zeros\" : \"Sentences that occur in the training set but not in the test set\",\n",
        "\"Closed vocabulary\" : \"test set can only contain words from lexicon (no unknowns)\",\n",
        "\"Smoothing/discounting\" : \"Shave off some probability mass from frequent events and give to events we've never seen but know exist\",\n",
        "\"Held-out corpus\" : \"additional training corpus used to set hyperparameters\",\n",
        "\"Katz backoff\" : \"Rely on discounted prob P* if seen this n-gram, otherwise back off to the shorter history (N-1)gram\",\n",
        "\"Stupid back-off\": \"No discount of higher order n-gram, just back off to a lower order n-gram if count is 0\",\n",
        "\"Entropy\" : \"A measure of information\",\n",
        "\"Cross-entropy\" : \"The upper bound on the entropy\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "52b40699-cb3a-41ea-c5b4-f49c458079da"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Old way of using belief states and having a plan for everything only works on simple problems. The rational decision depends on both the relative importance of various goals and the likelihood that, and degree, they will be achieved. Real world diagnosis problems almost always have uncertainty. Can't use logic to cope with domains like this (example: diagnosing tooth ache). Fails due to Laziness, Theoretical ignorance, and Practical ignorance, defined below. Theory of prob. summarizes the uncertainty the comes from humans laziness and ignorance, solving qualification problem. Decision theory = probablility theory + utility theory. \n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n Set of all worlds called sample space; mutually exclusive and exhaustive. Probablility model associates each possible with a numerical probability. Events satisfy an assertion. For each proposition, the corresponding worlds in which the proposition holds. Unconditional vs. Conditional probability examples given. A possible world is defined to be an assignment of values to all of the random variables under consideration. De Finetti's theorem implies that no rational agent can have beliefs that violate the axioms of probability. \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Section describes how to calculate probabilities and marginal probabilities given full joint distributions. Already understand very well. Conditional probability given as P(cavity | toothache) = P(cavity AND toothache) / P(toothache). Can use normalization as shortcut or if don't know some values. Full joint distrubution in tabular form seldom a practical tool. \n\n\n## AIMA Chapter 12.4 Independence\n Can decompose large distrubution tables, especially using independence between variables. Independence assertions usually based on knowledge of the domain. Very nice when able to use independence, but generally doesn't work for most real world problems.\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes rule (defined below) underlies most modern AI systems. Can also be written as P(cause|effect) = P(effect | cause)P(cause) / P(effect). P(effect|cause) is the causal direction, and P(cause|effect) is the diagnostic direction. Diagnostic knowledge usually more fragile than causal knowledge. KEY POINT: For n symptoms that are all conditionally independent given Cavity, the size of the representation grows as O(n) instead of O(2^n). Therefore, conditional independence assertions allows probabilistic systems to scale up; also they are more commonly available than absolute independence assertions. \n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n Naive Bayes model is P(cause, Effect_1, Effect_2, .... , Effect_n) = P(Cause)(product_over_i)P(Effect_i)|Cause). Considered Naive because its usually simplifying things, when in reality the effect varaibles are not strictly independent. However, even in this case it works very well. Run time is linear in the number of observed effects and doesn't depend on the number of unobserved effects. Decent at language classification, even though each word specifically isn't independent ('First quarter' example). Widely used for language determination, document retrieval, spam filtering, and other classifications. More sophisticated models should be used in fields like medicine. \n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Uncertainty can arise in the Wumpus world. Good example of how to use the previously discussed theorems to improve choosing a square in to move to in the Wumpus world.\n\n\n## SLP Chapter 3.1 N-Grams\n Intro: Predicting words important for applications like speech recognition, spelling correction, and grammatical error correction. Also useful for AAC (Augmentative and alternative communication) systems (used by people who are unable to speak). n-grams much simpler than state of the art, but demonstrate fundamental concepts.\n\nCh3_1: P(w/h) = probability of a word w given a history h. Method of estimating probs directly from word counts fine, but even web not big enough to have a large enough corpus; senteces are creative. Chain rule gives probability of a word given the previous words (covered in AIMA). Bigram model for P(the|Walden Pond's water is so transparant that) is approximated as P(the|that). n-gram model looks at n - 1 words into the past. Calculating probability of \"I want English food\" given a corpus given. Use log probabilities to avoid too small of numbers, since everything is less than or equal to 1.\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n Best way to evaulate performance of a language model is extrinsic evaluation (Defined below). Generally very expensive, so can be better to use intrinsic evaluation (test set and training set). Whichever model assigns a higher probability to the test set is the better model. Generally divide into 80% training, 10% development, and 10% test. Don't actually use raw probabilities, but perplexity (defined below). Minimizing perplexity is good. Perplexity can also be described as the weighted average branching factor of a language. The higher the 'n' of the n-gram model, the lower the perplexity. Note: Perplexity of two language models only comparable if they use identical vocabularies. Decreasing perplexity in instristic environment doesn't always decrease it in extrinsic test, so good to check extrinsicly too to make sure. \n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Sampling from a language model is to generate some sentences, choosing each sentence according to its likelihood defined by the model. \n\n\n## SLP Chapter 3.4 Generalization and Zeros\n n-grams do a better and better job of modeling the training corpus as we increase the value of N. Statistical models are mostly useless if training and test sets are as different as Shakespeare and the WSJ. Must use similar genre at least for training and test sets. Also issue of sparcity, any corpus could be missing perfectly logical sentences, thus giving the model a 0% chance of thinking they could exist. A sentence that never occurs in the training set but does in the test set is called a 'zero'. OOV rate = percentage of out-of-vocabulary words that appear in the test set. Two ways to fix. 1. Convert unknown words to just <UNK> and treat them as all one word. 2. Build vocabulary implicitely, and just call things with very low word-count as <UNK>. \n\n\n## SLP Chapter 3.5 Smoothing\n Smoothing defined below. Many ways to do this, Laplace, add-k, stupid backoff, and Kneser-Ney (Section 3_6). \n\nLaplace smoothing: Add 1 to all the n-gram counts before normalizing to probabilities. All 0's go to 1's with this. Not very robust, but good concept fundumentally. \n\nAdd-k smoothing: Add even less than 1 to the 0-counts. Can be chosen by optimizing on a devset. Still doesn't work very well for many applications\n\nBackoff and Interpolation: Backoff method is purposely using less context if model hasn't seen (use a bigram instead of a trigram). Interpolation is mixing all the probability estimates from many n-gram estimators (bigram, trigram, etc.). \n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Can prune language models, such as only use words with a count threshold > 40 like Googles does. Stupid back-off is sufficient in many cases, where there's no discounting of higher-order probabilities, you just backoff to a lower-order n-gram if there's a 0-count. \n\n\n## Module 10 Lecture Notes\n\n\nBigram model only considers i{w-1}\n\nIn trigram model, the probabilities of all words w given w{i-1} and w{i-2} add up to 1\n\nEffect of Markov assumption in n-gram models is it makes it possible to estimate the probabilities from data\n\nChain rule: P(x_1,x_2,x_3,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)...P(x_n|x1,...,x_(n-1))\n\nMaximum Likelihood Estimate: P(w_i|w_(i-1)) = count(w_(i-1), w_i) / count(w_(i-1))\n\n\n## Module 10 Definitions\n* **Belief state** - old way: represent all possible states, and have plan for everything\n* **Qualification problem** - Having infinitely many contigency plans (I.e. what if meteor hits the car)\n* **Laziness** - Too much work to think of all exceptions\n* **Theoretical ignorance** - No complete theory for a domain\n* **Practical ignorance** - Would need to many test to run, even if knew of all the rules\n* **Ontological commitments** - World is composed of facts that do or do not hold\n* **Epistemological commitments** - Logical agent believes true/false/no opinion, but probablistic agent believes between 0 and 1\n* **Decision theory** - An agent is rational iff it chooses action that yields highest expected utility, averaged over all outcomes\n* **Sample space** - Set of all possible worlds; mutuallyl exclusive and exhaustive\n* **Probability model** - Associates numerical probability with each possible world\n* **Event** - Sets that satisfy an assertion\n* **Unconditional/prior probabilities** - Degrees of belief in proposition in absence of any other information\n* **Conditional probability** - Evidence already. Prob of rolling eleven total given first die is a 5\n* **Factored representation** - possible world represented by set of variable/value pairs\n* **Random variable** - Variables in probability theory. Function that maps from domain of possible worlds to some range\n* **Probability function** - Probability that a random variable takes on some value x as a parameterized function of x\n* **Joint probability distribution** - Distributions on multiple variables\n* **Inclusion-exclusion principle** - P(a OR b) = P(a) + P(b) - P(a AND b)\n* **Probabilistic inference** - computatin of posterior probabilities for query propositions given evidence\n* **Marginilization/summing out** - sums up the probabilities for each possible value of the other variables\n* **Independence** - P(a|b) = P(a), P(b|a) = p(a), P(a,b) = P(a)P(b)\n* **Bayes' rule** - P(b|a) = P(a|b)P(b) / P(a)\n* **Conditional independence** - P(toothache AND catch | Cavity) = P(toothache | Cavity)P(catch | Cavity)\n* **Separation** - Cavity separates toothace and catch because its a direct cause of both\n* **Language models** - Models that assign probabilities to sequences of words\n* **Bigram model** - P(w_n|w_(1:n-1)) =~ P(w_n) | w_(n-1)\n* **Markov assumption** - Probability that a word depends only on the previous word\n* **Relative frequency** - ratio of observed frequency of a particular sequency to the observed frequency of a prefix\n* **Extrinsic evaluation** - Embed language model in an application and measure how much the application improves\n* **Test set** - The 'held out' data that will be used to test after model used on training set\n* **Development set (devset)** - A test set that is trained on a lot, giving need for a fresh new test set\n* **Perplexity** - The inverse probability of the test set, normalized by number of words. Also, 2^(power of cross-entropy)\n* **Sampling** - Choosing random points from a distribution according to their likelihood\n* **Zeros** - Sentences that occur in the training set but not in the test set\n* **Closed vocabulary** - test set can only contain words from lexicon (no unknowns)\n* **Smoothing/discounting** - Shave off some probability mass from frequent events and give to events we've never seen but know exist\n* **Held-out corpus** - additional training corpus used to set hyperparameters\n* **Katz backoff** - Rely on discounted prob P* if seen this n-gram, otherwise back off to the shorter history (N-1)gram\n* **Stupid back-off** - No discount of higher order n-gram, just back off to a lower order n-gram if count is 0\n* **Entropy** - A measure of information\n* **Cross-entropy** - The upper bound on the entropy\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Bayesian networks represent the dependencies among variables. Can represent *any* full joint probability \\\n",
        "distribution. Has 3 components:\n",
        "\n",
        "1. each node is a RV (disrete or continuous)\n",
        "\n",
        "2. Directed edges between nodes. X -> Y means X parent of Y. Is acyclic\n",
        "\n",
        "3. Node X_i has associated probability information (X_i | Parents(X_i)) that quantifies effect of parents\n",
        "\n",
        "Intuitive meaning of edge X -> Y is that X has a direct influence on Y. Each row in a conditional probability table must sum to 1 \\\n",
        "because they represent an exhaustive set for all cases for the variable. Generally, boolean variable with k Boolean parents \\\n",
        "contains 2^k independently specifiable probabilities. Node with no parents has one row that represents prior probabilities of each \\\n",
        "possible value of the variable. Bayesian networks allow a small agent to deal with a very large world by simplifying a potentially \\\n",
        "infinite set of circumstances. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter13_2 = \"\"\" Syntax of Bayes net: directed acyclic graph with some local probability info attached to each node. Probability of \\\n",
        "an event can be calculated by multiplying the Prob(a | parent(a)) for all a. When \\\n",
        "constructing Bayes net, put in a topological order. NOTE: A Bayesiant network is a correct representation of the domain only if \\\n",
        "each node is conditionally independent of its other predecessors in the node ordering, given its parents. Construct:\n",
        "\n",
        "1. order {X1....Xn}, will be more compact if ordered s.t. cause precedes effect\n",
        "\n",
        "2. choose a minimal set of parents fo Xi from X_1 to X_(i-1). For each parent insert link from parent \\\n",
        "to Xi.\n",
        "\n",
        "Parents of node Xi should contain all nodes in X1 to X_(i-1) that directly influence Xi. NOTE: Bayes nets should contain no redundant \\\n",
        "probability values. If no redundancy, no chance for inconsistency. Impossible to create a Bayesian network that violates \\\n",
        "prob-axioms. \n",
        "\n",
        "Bayes nets much more compact than full distribution. Example of general property locally structured (sparse) systems. \\\n",
        "Mostly, each random varaible directly influenced by at most k others. Amount of \\\n",
        "info needed to specify each conditional probability table at most 2^k numbers, and complete network specified by 2^k * n numbers. \\\n",
        "Contrast: joint dist. has 2^n numbers. \n",
        "\n",
        "**IMPORTANT**: If stick to causal model, end up having to specify fewer numbers, and numbers easier to come up with. Also, this shows \\\n",
        "that there can be many Bayesian networks that represent same full distribution, but the bad ones fail to take into account all the \\\n",
        "conditional independence relationships. \n",
        "\n",
        "Non-desenceds property: Each variable is conditionally independent of its non-descendants, given its parents. \n",
        "\n",
        "Markov blanket: A variable is conditionally independent of all other nodes in network, given its parents, children, and children's \\\n",
        "parents - that is, given its Markov blanket. \n",
        "\n",
        "Even if maximum number of parents k is small, stil requires O(2^k) numbers and experience to fill in. Can use a canonical \\\n",
        "distribution to fill in to make it easier. Some patterns are deterministic nodes and context-specific independence (defined below). \\\n",
        "Noisy logical relationships thta depent on k parents can be described in O(k) parameters instead of O(2^k) for full conditional \\\n",
        "probablity table.\n",
        "\n",
        "Discretization for continuous variables. Also use something like a Gaussian distribution \\\n",
        "or nonparametric representation - define the conditional distribution implicitly with collectin of instances, \\\n",
        ". Special properties of linear-Gaussian: network will have joint distribution that is a multivariate \\\n",
        "Gaussian distribution over all variables. Posterier distribution given any evidence will also have this property. When discrete \\\n",
        "varible are added as parents of continuous varaibles, the network defines a conditional Gaussian distribution \\\n",
        "given any assignment to the discrete variables.\n",
        "\n",
        "Disc. variables/Cont. parents: Probit better for real situations, but logistic function better mathematically. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter13_3 = \"\"\" Best description: Basic task is compute posterior probability distribution for a set of query variables, \\\n",
        "given an abserved event, whic his usually an assignment of values to a set of evidence variables. A query can be answered \\\n",
        "using a Bayes net by computing sums of products of conditional probabilities from the network. A naive implementation would \\\n",
        "have complexity O(n*2^n). Can be reduced to O(2^n) by taking advanteage of nested structure. \n",
        "\n",
        "Enumeration-ask algorithm runs in O(2^n). Better then naive, but not great. However, can avoid repeated calculations using strats \\\n",
        "such as variable elimination. Variable elimination sums out variables (right to left) from pointwise products of factors to \\\n",
        "produce new factors, eventually yielding the solution. \n",
        "\n",
        "Generally, time and space requirements of variable elimination dominated by sizze of largest factor constructed during the operation \\\n",
        "of the algorithm. This itself determined by order of elimination of varaibles and by the structure of network. Intractable to \\\n",
        "determine optimal ordering. Some heuristics, like greedy one: eliminate whichever variable minimizes the size of the next factor to be \\\n",
        "constructed. Also, can remove any leaf node that is not a query or evidence variable. NOTE: every variable that is not an ancestor \\\n",
        "of a query variable or evidence variable is irrelivent to the query. \n",
        "\n",
        "Time and space complexity linear in size of network in singly connecrted/poly trees. Multiply connected can have exponential time \\\n",
        "and space complexity, even if number of parents per node bounded. NOTE: inference in Bayes nets is NP-hard bc it includes \\\n",
        "inference in propositional logic as a special case. Can use Bayes net inference to solve 3-SAT problems (can reduce satisfiability \\\n",
        "problems to Bayes net inference problems). Bayes net #P-hard (strictly harder than NP-complete). Tree width can be used to bound \\\n",
        "complexity of Bayes nets. Can slo reduce Bayes net inference to satisfibility (weighted model counting). Bayes net inference is \\\n",
        "competitive with and someties superior to exact algorithms on networks with large tree width. \n",
        "\n",
        "If computing posterior probs for all variables, can use clustering to reduce time complexity from O(n^2) to \\\n",
        "O(n). Idea: Join nodes to form a cluster of nodes, resulting tree is polytree. meganodes share one variable. \\\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" GO OVER NOTES. Write down Active / Inactive paths on sheet and make sure can do example problems in notes!!!\n",
        "\n",
        "The conditional prob dist. of a variable in a Baysian network should be specified based on the prob dist. of all \\\n",
        "of the other variables is FALSE. JUST NEED THE PARENTS!\n",
        "\n",
        "Every variable in a Bayes net is independent of all its descendets given its children\n",
        "\n",
        "Locally structures (sparse) systems grow linearly in complexity.\n",
        "\n",
        "More than one Bayesian network can be used to represent same join distribution\n",
        "\n",
        "If two variables X and Y in Bayesian network don't share a path, then X and Y are conditionally independent\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesin Network\" : \"Directed graph that represents dependencies among variables\",\n",
        "\"Topological order\" : \"any order consistent with directed graph structure\",\n",
        "\"Locally structured / sparse\" : \"Each subcomponent interacts directly with only bounded number of other components (linear growth now)\",\n",
        "\"Markov blanket\" : \"parents, children, and children's parents for a single variable\",\n",
        "\"Canonical distribution\" : \"A standard pattern to fill in relationship between parent and child\",\n",
        "\"Deterministic node\" : \"A node with its value specified exactly by the values of its parents, with no uncertainty\", \n",
        "\"Context-specific independence\" : \"Exhibits CSI if variable is conditionally independent of some of its parents given certain values of others\",\n",
        "\"Noisy-OR\" : \"Generalization of the logical OR. Fever true iff Cold, Flu, or Malaria true.\",\n",
        "\"Leak node\" : \"Covers miscallaneous causes\",\n",
        "\"Discretization\" : \"dividing up values for continuous variables into fixed intervals\", \n",
        "\"Hybrid Bayesian network\" : \"A netweork with both discrete and continuous variables\",\n",
        "\"Linear-Gaussian\" : \"child has Gaussian distribgution whose mean varies linearly with value of parent and whose s.d is fixed\",\n",
        "\"Hidden variables\" : \"neither input nor output, but needed to structure network so its reasonably sparse\",\n",
        "\"Variable elmination\" : \"Versin of dynamic programming to eliminate repeated calculations. Simplest\", \n",
        "\"Singly connected/polytrees\" : \"At most one undirected path between any 2 nodes. T()/S() linear in size of network\",  \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f0de6247-2c27-4501-a20a-57bc8fb0346b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian networks represent the dependencies among variables. Can represent *any* full joint probability distribution. Has 3 components:\n\n1. each node is a RV (disrete or continuous)\n\n2. Directed edges between nodes. X -> Y means X parent of Y. Is acyclic\n\n3. Node X_i has associated probability information (X_i | Parents(X_i)) that quantifies effect of parents\n\nIntuitive meaning of edge X -> Y is that X has a direct influence on Y. Each row in a conditional probability table must sum to 1 because they represent an exhaustive set for all cases for the variable. Generally, boolean variable with k Boolean parents contains 2^k independently specifiable probabilities. Node with no parents has one row that represents prior probabilities of each possible value of the variable. Bayesian networks allow a small agent to deal with a very large world by simplifying a potentially infinite set of circumstances. \n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Syntax of Bayes net: directed acyclic graph with some local probability info attached to each node. Probability of an event can be calculated by multiplying the Prob(a | parent(a)) for all a. When constructing Bayes net, put in a topological order. NOTE: A Bayesiant network is a correct representation of the domain only if each node is conditionally independent of its other predecessors in the node ordering, given its parents. Construct:\n\n1. order {X1....Xn}, will be more compact if ordered s.t. cause precedes effect\n\n2. choose a minimal set of parents fo Xi from X_1 to X_(i-1). For each parent insert link from parent to Xi.\n\nParents of node Xi should contain all nodes in X1 to X_(i-1) that directly influence Xi. NOTE: Bayes nets should contain no redundant probability values. If no redundancy, no chance for inconsistency. Impossible to create a Bayesian network that violates prob-axioms. \n\nBayes nets much more compact than full distribution. Example of general property locally structured (sparse) systems. Mostly, each random varaible directly influenced by at most k others. Amount of info needed to specify each conditional probability table at most 2^k numbers, and complete network specified by 2^k * n numbers. Contrast: joint dist. has 2^n numbers. \n\n**IMPORTANT**: If stick to causal model, end up having to specify fewer numbers, and numbers easier to come up with. Also, this shows that there can be many Bayesian networks that represent same full distribution, but the bad ones fail to take into account all the conditional independence relationships. \n\nNon-desenceds property: Each variable is conditionally independent of its non-descendants, given its parents. \n\nMarkov blanket: A variable is conditionally independent of all other nodes in network, given its parents, children, and children's parents - that is, given its Markov blanket. \n\nEven if maximum number of parents k is small, stil requires O(2^k) numbers and experience to fill in. Can use a canonical distribution to fill in to make it easier. Some patterns are deterministic nodes and context-specific independence (defined below). Noisy logical relationships thta depent on k parents can be described in O(k) parameters instead of O(2^k) for full conditional probablity table.\n\nDiscretization for continuous variables. Also use something like a Gaussian distribution or nonparametric representation - define the conditional distribution implicitly with collectin of instances, . Special properties of linear-Gaussian: network will have joint distribution that is a multivariate Gaussian distribution over all variables. Posterier distribution given any evidence will also have this property. When discrete varible are added as parents of continuous varaibles, the network defines a conditional Gaussian distribution given any assignment to the discrete variables.\n\nDisc. variables/Cont. parents: Probit better for real situations, but logistic function better mathematically. \n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Best description: Basic task is compute posterior probability distribution for a set of query variables, given an abserved event, whic his usually an assignment of values to a set of evidence variables. A query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network. A naive implementation would have complexity O(n*2^n). Can be reduced to O(2^n) by taking advanteage of nested structure. \n\nEnumeration-ask algorithm runs in O(2^n). Better then naive, but not great. However, can avoid repeated calculations using strats such as variable elimination. Variable elimination sums out variables (right to left) from pointwise products of factors to produce new factors, eventually yielding the solution. \n\nGenerally, time and space requirements of variable elimination dominated by sizze of largest factor constructed during the operation of the algorithm. This itself determined by order of elimination of varaibles and by the structure of network. Intractable to determine optimal ordering. Some heuristics, like greedy one: eliminate whichever variable minimizes the size of the next factor to be constructed. Also, can remove any leaf node that is not a query or evidence variable. NOTE: every variable that is not an ancestor of a query variable or evidence variable is irrelivent to the query. \n\nTime and space complexity linear in size of network in singly connecrted/poly trees. Multiply connected can have exponential time and space complexity, even if number of parents per node bounded. NOTE: inference in Bayes nets is NP-hard bc it includes inference in propositional logic as a special case. Can use Bayes net inference to solve 3-SAT problems (can reduce satisfiability problems to Bayes net inference problems). Bayes net #P-hard (strictly harder than NP-complete). Tree width can be used to bound complexity of Bayes nets. Can slo reduce Bayes net inference to satisfibility (weighted model counting). Bayes net inference is competitive with and someties superior to exact algorithms on networks with large tree width. \n\nIf computing posterior probs for all variables, can use clustering to reduce time complexity from O(n^2) to O(n). Idea: Join nodes to form a cluster of nodes, resulting tree is polytree. meganodes share one variable. \n\n## Module 11 Lecture Notes\n GO OVER NOTES. Write down Active / Inactive paths on sheet and make sure can do example problems in notes!!!\n\nThe conditional prob dist. of a variable in a Baysian network should be specified based on the prob dist. of all of the other variables is FALSE. JUST NEED THE PARENTS!\n\nEvery variable in a Bayes net is independent of all its descendets given its children\n\nLocally structures (sparse) systems grow linearly in complexity.\n\nMore than one Bayesian network can be used to represent same join distribution\n\nIf two variables X and Y in Bayesian network don't share a path, then X and Y are conditionally independent\n\n\n## Module 11 Definitions\n* **Bayesin network** - Directed graph that represents dependencies among variables\n* **Topological order** - any order consistent with directed graph structure\n* **Locally structured / sparse** - Each subcomponent interacts directly with only bounded number of other components (linear growth now)\n* **Markov blanket** - parents, children, and children's parents for a single variable\n* **Canonical distribution** - A standard pattern to fill in relationship between parent and child\n* **Deterministic node** - A node with its value specified exactly by the values of its parents, with no uncertainty\n* **Context-specific independence** - Exhibits CSI if variable is conditionally independent of some of its parents given certain values of others\n* **Noisy-or** - Generalization of the logical OR. Fever true iff Cold, Flu, or Malaria true.\n* **Leak node** - Covers miscallaneous causes\n* **Discretization** - dividing up values for continuous variables into fixed intervals\n* **Hybrid bayesian network** - A netweork with both discrete and continuous variables\n* **Linear-gaussian** - child has Gaussian distribgution whose mean varies linearly with value of parent and whose s.d is fixed\n* **Hidden variables** - neither input nor output, but needed to structure network so its reasonably sparse\n* **Variable elmination** - Versin of dynamic programming to eliminate repeated calculations. Simplest\n* **Singly connected/polytrees** - At most one undirected path between any 2 nodes. T()/S() linear in size of network\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 = \"\"\" Each component of an agent can be improved by machine learning. This chapter assumes little prior knowledge, though another chapter focues on transfer learning. \\\n",
        "Induction, unlike deduction, not guarenteed to be correct. Input is factored representation (vector of attribute values), can be atomic or relational. Can be either classification \\\n",
        "or regression problems. Can be supervised learning, unsupervised learning, or reinforcement learning (defined below). \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter19_2 = \"\"\" Given a traning set, determine a model/hypothesis h that approximates true fuction f(x). Can't get consistent hypothesis with continuous function, so try to get \\\n",
        "bets-fit function. 'h' generalizes well if it accurately predicts the outputs of the test set. Must take into account the bias-variance tradeoff (complex, low-bias h that fits training \\\n",
        "data well and simpler, or low-variance h that generalizes better). There is a trade-off between the expressiveness of a hypothesis space and the computational complexity of finding a good \\\n",
        "hypothesis within that space. Most machine learning focuses on simple representations. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter19_3 = \"\"\" Boolean classification, mapping to either false or true. Want to find the smallest possible decision tree to represent a problem. Intractable to find the absolute \\\n",
        "smallest, but can get close with heuristics. A tree consists of tests on attributes in interior node, value of attribute on branches, and output value of leaf nodes. The \\\n",
        "learning algorithm looks at examples, not the correct function. Learning curves also known as Happy Graphs. Information gain from attribute test on 'A' is the expected \\\n",
        "reduction in entropy. Use decision tree pruning to combat overfitting. Prune irrelevent attributes by turning them into leaves. Use significance tests to see if an attribute is \\\n",
        "relevant or not. Pruned trees perform much better than unpruned when there's large amounts of noise. Early stopping would miss crutial situations where there's no one good \\\n",
        "attribute, but they lead to good attributes. Information gain ratio can be used to avoid splitting into lots of single-example subtrees. Equality tests also work. Need regression tree \\\n",
        "when output is continous. Decision trees are unstable: adding one new example can change the test at the root, changing whole tree. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter19_4 = \"\"\" Use stationary assumption, (future like past). Assume events are independent and identically distributed. Optimal fit minimizes error rate. Create training and \\\n",
        "test sets. Could try different thresholds, etc. by tuning hyperparameters. However, to truly tune hyperparametrs, should have a training set, validation set (devset), and test \\\n",
        "set. Can use k-fold cross-validation to squeeze more sets out of the data. Model selection chooses a good hypothesis space, and optimization finds the best hypothesis within that \\\n",
        "space. Strategies that when validation set error decreases, capacity increases = deep neural networks, kernel machines, random forests, boosted ensembles. In machine learning, \\\n",
        "typically look to minimze a loss function. Example of there's more loss when classifying a real email as spam than vise versa. Four reasons why h\\* may differ from true function: \\\n",
        "unrealizability, variance, noise, computational complexity. Noise cannot be predicted, only characterized. \n",
        "\n",
        "Can also work to minimize weighted sum of emperical loss and the complexity of the hypothesis, called the total cost. Feature selection can be used to discard attributes in addition to \\\n",
        "regularization.  Could also measure emperical loss and complexity on the same scale using minimum description length (minimize bits). \n",
        "\n",
        "Can tune hyperparameters through hand-tuning (manual). Could use grid search or random sampling. Could choose Bayesian optimization or population-based training to tune hyperparameters.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter19_5 = \"\"\" Computational learning theory lies in middle of AI, statistics, and theoretical computer science. Principle: any theory that is wrong will be found out after just \\\n",
        "a few examples. If a hypothesis consistent with large set of training examples, then must be \"probably appriximately correct\" (PAC). Use a small constant, ensure hypothesis \\\n",
        "error rate is is less than or equal to this. \n",
        "\n",
        "Three ways to restrict hypothesis space: 1. Bring prior knowledge. 2. Insist algorithm returns simple hypothesis. 3. Focus on learnable subsets of entire hypothesis space.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter19_6 = \"\"\" Univariate linear regression is fitting with a straight line. Can use gradient descent rather than solving for zeroes. Can use batch gradient descent or \\\n",
        "stochastic gradient descent to train on multiple training examples. Could also take advantage of parallel vector operations with some CPU's, making 'm' itself a hyperparameter. \\\n",
        "Convergence of stochastic gradient descent NOT guarenteed. SGD good in online setting where data coming in one at a time, (also known as online gradient descent for this reason). \\\n",
        "\n",
        "Multivariable linear regression - each example x_j is an n-element vector. Multivariable not much more complicated than linear regression. Univariate don't have to worry about \\\n",
        "overfitting, but you do in multivariable. Therefore, use regularization on multivariable linear functions. L_1 regularization produces a sparse model. \n",
        "\n",
        "A decision boundary separates two classes. Use a linear separateor for linearly separable data. Typically, learning rule applied one example at a time. Perceptron rule may not \\\n",
        "converge to a stable solution for fixed learning rate alpha, but if alpha decased as O(1/t) where t is the iteration number, then rule can converge to a minimum error \\\n",
        "solution when samples presented in random sequence. This is NP-hard. \n",
        "\n",
        "Can resolve many issues by softening the threshold function, making things likely zero or likely 1, instead of straight 0 or 1. Process of fitting weights on this is called \\\n",
        "logistic regression. No easy close-form solution for optimal w, but gradient descent strategy straightfoward. Logistic regression converges much faster and better on data that is \\\n",
        "not linearly separable (though does converge slower on data that is linearly separable). \n",
        "\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Intro: Classification is heart of both human and machine intelligence. One task of text categorization is sentiment analysis. Spam detection another. \\\n",
        "Language id usually first step in most language processing pipelines. Rules can be fragile, as data/situations change over time. Most cases done via supervised \\\n",
        "machine learning. Generative classifiers (naive Bayes), build model of how a class could generate some input data. Given observation, returns class most likely to \\\n",
        "have generated the observation. Discriminative classifiers (logistic regression) learn what features from the input are most useful to discriminate between different \\\n",
        "possible classes. \n",
        "\n",
        "Ch4_1: Naive Bayes generative model because first a class is sampled from P(c), then word generated by sampling from P(d|c). Naive Bayes assumpion gives \\\n",
        "the conditional independence assumption that probs P(f_i|c) are independent given 'c'. Naive Bayes and logistic regression called linear classifiers. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_2 = \"\"\" Simplest solution is add-one (Laplace) smoothing. Some systems ignore stop words (the, a). \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_3 = \"\"\" Worked example, go over before test.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_4 = \"\"\" Binary multinomial naive bays clips words count at 1. Put prefix NOT_ next to every word after a token of logical negation. Can use sentiment lexicons with \\\n",
        "words prelabeled as positive or negative. Add a feature that is counted each time a word from that lexicon is used. positive lexicon count vs. negative lexicon count. If data \\\n",
        "is sparse, use dense lexicon features instead of sparse individual-word features to generalize better.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_5 = \"\"\" Features in naive Baye can express any property of the input text we want. Spame - phrases. language ID - character n-grams. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_6 = \"\"\" Naive Bayes can be viewed as a set of class-specific unigram language models, in which model for each class instantiates a unigram language model. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_7 = \"\"\" Build a confusion matrix. \n",
        "\n",
        "Precision = tp / (tp + fp). Measures % of items that system detected as positive that are actually positive\n",
        "\n",
        "Recall = tp / (tp + fn). Measures % of items actually present in the input that were correctly identified by the system\n",
        "\n",
        "Accuracy = (tp + tn) / (tp + fp + tn + fn)\n",
        "\n",
        "Top left: True Positive. Top right: False positive. Bottem Left: False negative. Bottom right: True negative.\n",
        "\n",
        "F-measure: F_B = (B^2 + 1)PR / (B^2 * P + R). Single metric that incorporates both precision and recall.\n",
        "\n",
        "Macroaveraging can be used when more than 2 classes (compute performance for each class, then average over classes).  Can also use microaveraging (collect \\\n",
        "decisions for all classes into a single confusion matrix, then compute precision and recall from that table). Microaverage dominated by more frequent class, \\\n",
        "since counts pooled. Macroaverage reflects better the statistics of smaller classes, and is therefore better when performance on all classes equally important.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_8 = \"\"\" Use training set to train model, use devset to tune parameters, run on test set for performance measures. Can use cross-validation to get \"more\" data. \\\n",
        "Partition data into k disjoint subsets called folds. Train on k-1 folds, compute error rate on test set. Do sampling process k times and then average error rates. Do this \\\n",
        "inside the training set, then test on test set normally. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_9 = \"\"\" Statistical significance used to compare two different models to see which is better. Effect size: Bigger Delta(x) means A way better than B, small delta means \\\n",
        "A only a little better than B. Delta(x) = M(A,x)  - M(B,x). Use null hypothesis (Delta(x) <= 0). Like to know if we can confidently rule out this hypothesis. Small p-value means \\\n",
        "that difference observed is very unlikely under the null hypothesis, and can reject null hypothesis. Small is 0.05 or 0.01 typically. A is better than B is statistically \\\n",
        "significant if the delta seen has prob below the threshold and therefore can reject this null hypothesis. In NLP, use non-parametric tests based on sampling to determine p-value. \\\n",
        "Most common are approximate randomization and bootstrap test. Paired tests: Those that compare two sets of observations that are aligned. \n",
        "\n",
        "Bootstrap test can be applied to precision, recall, F1, BLEU (any metric). Bootstrapping is repeatedly drawing smaller smaples with replacement from an original larger sample. \\\n",
        "Can create many virtual test sets doing this. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter4_10 = \"\"\" Important to avoid harms in classification. Representational harms - system demeans a social group. Toxicity detection detects abuse, but can itself cause \\\n",
        "harm. ML replicate or even amplify biases in the training data. Problems can also be caused by the human labelers, resources used, or by the model architecture. Can use a model \\\n",
        "card to document information like algorithms/parameters, preprocessing, intended use, performance across different demographics, etc. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "Mistakes bound: maximum number of mistakes related to the margin or degree of separability. Mistakes < k/(sigma^2). \n",
        "\n",
        "Problems with perceptron: Noise - if data isn't separable, weights might thrash, averaging weight vectors over time can help. Mediocre generalization - finds a \"barely\" separable \\\n",
        "solution. Overtraining - test / held-out accuracy usually rises, then falls. \n",
        "\n",
        "Fixing Perceptron: adjust weight updtae to mitigate effects (MIRA). Using maximum step size usually converges faaster and is better on noisy data. \n",
        "\n",
        "Naive Bayes naive b/c assumes features are conditionally independent of each other\n",
        "\n",
        "Joint prob model P(X1, X2, X3, Y) for data using Naive bayes assumption is P(Y)P(X1|y)P(X2|Y)P(X3|Y)\n",
        "\n",
        "Perceptron - training is error-driven, weights only updated when predicted label incorrect\n",
        "\n",
        "Circle example, can separate two classes by using feature augmentation\n",
        "\n",
        "Perceptron not guarenteed to converge if data not linearly separable\n",
        "\n",
        "Inference procedure for perceptron describes as: compute a weighted sum, then apply a threshold\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"Induction\" : \"Going from specific set of observatins to a general rule\",\n",
        "\"Classification\" : \"Output is set of finite values (cloudy,sunny, etc.)\",\n",
        "\"Regression\" : \"When output is a number (temperature, etc.)\",\n",
        "\"Supervised learning\" : \"Observe input/ouput, create function mapping input to output\",\n",
        "\"Unsupervised learing\" : \"Learns input patterns with no feedback on output (clustering)\",\n",
        "\"Reinforcement learning\" : \"Learns from series of rewards / punishments\",\n",
        "\"Hypothesis\" : \"y=f(x). Discover 'h' that approximates true fucntion of f. Drawn from hypothesis space\",\n",
        "\"Ground truth\" : \"The output y_i, the true answer we are asking model to predict\",\n",
        "\"Consistent hypothesis\" : \"h s.t. each s_i in training set has h(x_i) = y_i.\",\n",
        "\"Bias\" : \"Tendency of predicitive hypothesis to deviate form expected values\",\n",
        "\"Underfit\" : \"Failure to find a pattern in data\",\n",
        "\"Variance\" : \"Amount of change in hypothesis just due to fluctuation in training data\",\n",
        "\"Overfit\" : \"Model pays too much attention to the exact data in the training set\",\n",
        "\"Ockham's razor\" : \"plurality of entities should not be posited without necessity (shave off dubious explanations)\",\n",
        "\"Decision Tree\" : \"Maps a vector of attriute value sto an output value\",\n",
        "\"Entropy\" : \"Fundamental quantity in information theory\",\n",
        "\"Significance test\" : \"Assume no underlying pattern. If degree of deviation statistically unlikely, then good evidence for presence of pattern in data\",\n",
        "\"Early stopping\" : \"Stop generating tree if no good attribute detected. Bad practice, could miss good attributes further down\",\n",
        "\"Split point test\" : \"Inequality test on value of an attribute. Most expensive part of algorithm application\",\n",
        "\"CART\" : \"Classification and Regression Trees\",\n",
        "\"Stationary assumption\" : \"Assume all future examples will be like the past\",\n",
        "\"IID\" : \"Independent and identically distrubuted (stationary Ej's)\",\n",
        "\"Hyperparameters\" : \"Parameters of the model class, not individual model\",\n",
        "\"K-fold cross-validation\" : \"Split data into k equal subsets, perform k rounds of learning, on each round 1/k data held out\",\n",
        "\"Leave-one-out cross-validation\" : \"LOOCV - k = n k-fold cross-validation\",\n",
        "\"Interpolated\" : \"A model that exactly fits the data\",\n",
        "\"Realizable\" : \"Hypothesis space H actually contains true function f\",\n",
        "\"Regularization\" : \"Penalizing complex hypotheses\",\n",
        "\"Minimum description length\" : \"Minimize total number of bits required\",\n",
        "\"Grid search\" : \"Try all combinations for hypermarametes (works when few and discrete)\",\n",
        "\"Random sampling\" : \"Random choosing from uniform distribution. Good for continuous variables\",\n",
        "\"Bayesian optimization\" : \"Task of choosing hypermarameter values an ML problem itself\",\n",
        "\"Population-based training\" : \"Alternative to Bayesian (above). Train parallely population of models. Do again, slightly based on previous results and slightly on randomness\",\n",
        "\"Sample complexity\" : \"Number of required examples, as a function of epsilon (error) and delta\",\n",
        "\"Weight space\" : \"Space defined by all possible settings of the weights\",\n",
        "\"Gradient descent\" : \"Compute estimate of gradient and move smallamount in steepest downhill direction until converge on local minimum loss\",\n",
        "\"Learning rate\" : \"Parameter alpha in gradient descent\",\n",
        "\"Batch gradient descent\" : \"Also called deterministic gradient descent. For N training samples. Convergence to global minima guarenteed\",\n",
        "\"Stochastic gradient descent\" : \"Faster version of above. Randomly selects small number of training examples, rather than 1 at a time\",\n",
        "\"Multivariable linear regression\" : \"each example x_j is an n-element vector\",\n",
        "\"Sparse model\" : \"Sets many weights to zero - simpler model\",\n",
        "\"Decision boundary\" : \"Separates two classes\",\n",
        "\"Threshhold function\" : \"Defines class separation\",\n",
        "\"Perceptron learning rule\" : \"The update rule for linear regression\",\n",
        "\"Sentiment analysis\" : \"The extraction of a sentiment - positve or negative orientation expressed by writer\",\n",
        "\"Binary multinomial naive Bayes (binary NB)\" : \"Clip word counts in each document at 1. (Preference whether a word occurs, not how many times)\",\n",
        "\"Gold labels\" : \"The human-made labels\",\n",
        "\"Precision\" : \"tp / (tp + fp). Measures % of items that system detected as positive that are actually positive\",\n",
        "\"Recall\" : \"tp / (tp + fn). Measures % of items actually present in the input that were correctly identified by the system\",\n",
        "\"Accuracy\" : \"(tp + tn) / (tp + fp + tn + fn)\",\n",
        "\"F-measure\" : \"F_B = (B^2 + 1)PR / (B^2 * P + R). Single metric that incorporates both precision and recall\",\n",
        "\"Macroaveraging\" : \"Compute performance for each class, then average over classes\",\n",
        "\"Microaverageing\" : \"collect decisions for all classes into a single confusion matrix, then compute precision and recall from that table\",\n",
        "\"p-value\" : \"The probability, assuming null hypothesis H_0 is true, of seeing the delta(x) that we saw or one even greater. \",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9c1dd795-34d0-4112-a724-4bafd2a57693"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Each component of an agent can be improved by machine learning. This chapter assumes little prior knowledge, though another chapter focues on transfer learning. Induction, unlike deduction, not guarenteed to be correct. Input is factored representation (vector of attribute values), can be atomic or relational. Can be either classification or regression problems. Can be supervised learning, unsupervised learning, or reinforcement learning (defined below). \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Given a traning set, determine a model/hypothesis h that approximates true fuction f(x). Can't get consistent hypothesis with continuous function, so try to get bets-fit function. 'h' generalizes well if it accurately predicts the outputs of the test set. Must take into account the bias-variance tradeoff (complex, low-bias h that fits training data well and simpler, or low-variance h that generalizes better). There is a trade-off between the expressiveness of a hypothesis space and the computational complexity of finding a good hypothesis within that space. Most machine learning focuses on simple representations. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Boolean classification, mapping to either false or true. Want to find the smallest possible decision tree to represent a problem. Intractable to find the absolute smallest, but can get close with heuristics. A tree consists of tests on attributes in interior node, value of attribute on branches, and output value of leaf nodes. The learning algorithm looks at examples, not the correct function. Learning curves also known as Happy Graphs. Information gain from attribute test on 'A' is the expected reduction in entropy. Use decision tree pruning to combat overfitting. Prune irrelevent attributes by turning them into leaves. Use significance tests to see if an attribute is relevant or not. Pruned trees perform much better than unpruned when there's large amounts of noise. Early stopping would miss crutial situations where there's no one good attribute, but they lead to good attributes. Information gain ratio can be used to avoid splitting into lots of single-example subtrees. Equality tests also work. Need regression tree when output is continous. Decision trees are unstable: adding one new example can change the test at the root, changing whole tree. \n\n\n## AIMA Chapter 5.5 Stochastic Games\n Use stationary assumption, (future like past). Assume events are independent and identically distributed. Optimal fit minimizes error rate. Create training and test sets. Could try different thresholds, etc. by tuning hyperparameters. However, to truly tune hyperparametrs, should have a training set, validation set (devset), and test set. Can use k-fold cross-validation to squeeze more sets out of the data. Model selection chooses a good hypothesis space, and optimization finds the best hypothesis within that space. Strategies that when validation set error decreases, capacity increases = deep neural networks, kernel machines, random forests, boosted ensembles. In machine learning, typically look to minimze a loss function. Example of there's more loss when classifying a real email as spam than vise versa. Four reasons why h\\* may differ from true function: unrealizability, variance, noise, computational complexity. Noise cannot be predicted, only characterized. \n\nCan also work to minimize weighted sum of emperical loss and the complexity of the hypothesis, called the total cost. Feature selection can be used to discard attributes in addition to regularization.  Could also measure emperical loss and complexity on the same scale using minimum description length (minimize bits). \n\nCan tune hyperparameters through hand-tuning (manual). Could use grid search or random sampling. Could choose Bayesian optimization or population-based training to tune hyperparameters.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Computational learning theory lies in middle of AI, statistics, and theoretical computer science. Principle: any theory that is wrong will be found out after just a few examples. If a hypothesis consistent with large set of training examples, then must be \"probably appriximately correct\" (PAC). Use a small constant, ensure hypothesis error rate is is less than or equal to this. \n\nThree ways to restrict hypothesis space: 1. Bring prior knowledge. 2. Insist algorithm returns simple hypothesis. 3. Focus on learnable subsets of entire hypothesis space.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Univariate linear regression is fitting with a straight line. Can use gradient descent rather than solving for zeroes. Can use batch gradient descent or stochastic gradient descent to train on multiple training examples. Could also take advantage of parallel vector operations with some CPU's, making 'm' itself a hyperparameter. Convergence of stochastic gradient descent NOT guarenteed. SGD good in online setting where data coming in one at a time, (also known as online gradient descent for this reason). \nMultivariable linear regression - each example x_j is an n-element vector. Multivariable not much more complicated than linear regression. Univariate don't have to worry about overfitting, but you do in multivariable. Therefore, use regularization on multivariable linear functions. L_1 regularization produces a sparse model. \n\nA decision boundary separates two classes. Use a linear separateor for linearly separable data. Typically, learning rule applied one example at a time. Perceptron rule may not converge to a stable solution for fixed learning rate alpha, but if alpha decased as O(1/t) where t is the iteration number, then rule can converge to a minimum error solution when samples presented in random sequence. This is NP-hard. \n\nCan resolve many issues by softening the threshold function, making things likely zero or likely 1, instead of straight 0 or 1. Process of fitting weights on this is called logistic regression. No easy close-form solution for optimal w, but gradient descent strategy straightfoward. Logistic regression converges much faster and better on data that is not linearly separable (though does converge slower on data that is linearly separable). \n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Intro: Classification is heart of both human and machine intelligence. One task of text categorization is sentiment analysis. Spam detection another. Language id usually first step in most language processing pipelines. Rules can be fragile, as data/situations change over time. Most cases done via supervised machine learning. Generative classifiers (naive Bayes), build model of how a class could generate some input data. Given observation, returns class most likely to have generated the observation. Discriminative classifiers (logistic regression) learn what features from the input are most useful to discriminate between different possible classes. \n\nCh4_1: Naive Bayes generative model because first a class is sampled from P(c), then word generated by sampling from P(d|c). Naive Bayes assumpion gives the conditional independence assumption that probs P(f_i|c) are independent given 'c'. Naive Bayes and logistic regression called linear classifiers. \n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Simplest solution is add-one (Laplace) smoothing. Some systems ignore stop words (the, a). \n\n\n## SLP Chapter 4.3 Worked Example\n Worked example, go over before test.\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Binary multinomial naive bays clips words count at 1. Put prefix NOT_ next to every word after a token of logical negation. Can use sentiment lexicons with words prelabeled as positive or negative. Add a feature that is counted each time a word from that lexicon is used. positive lexicon count vs. negative lexicon count. If data is sparse, use dense lexicon features instead of sparse individual-word features to generalize better.\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Features in naive Baye can express any property of the input text we want. Spame - phrases. language ID - character n-grams. \n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Naive Bayes can be viewed as a set of class-specific unigram language models, in which model for each class instantiates a unigram language model. \n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Build a confusion matrix. \n\nPrecision = tp / (tp + fp). Measures % of items that system detected as positive that are actually positive\n\nRecall = tp / (tp + fn). Measures % of items actually present in the input that were correctly identified by the system\n\nAccuracy = (tp + tn) / (tp + fp + tn + fn)\n\nTop left: True Positive. Top right: False positive. Bottem Left: False negative. Bottom right: True negative.\n\nF-measure: F_B = (B^2 + 1)PR / (B^2 * P + R). Single metric that incorporates both precision and recall.\n\nMacroaveraging can be used when more than 2 classes (compute performance for each class, then average over classes).  Can also use microaveraging (collect decisions for all classes into a single confusion matrix, then compute precision and recall from that table). Microaverage dominated by more frequent class, since counts pooled. Macroaverage reflects better the statistics of smaller classes, and is therefore better when performance on all classes equally important.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Use training set to train model, use devset to tune parameters, run on test set for performance measures. Can use cross-validation to get \"more\" data. Partition data into k disjoint subsets called folds. Train on k-1 folds, compute error rate on test set. Do sampling process k times and then average error rates. Do this inside the training set, then test on test set normally. \n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n Statistical significance used to compare two different models to see which is better. Effect size: Bigger Delta(x) means A way better than B, small delta means A only a little better than B. Delta(x) = M(A,x)  - M(B,x). Use null hypothesis (Delta(x) <= 0). Like to know if we can confidently rule out this hypothesis. Small p-value means that difference observed is very unlikely under the null hypothesis, and can reject null hypothesis. Small is 0.05 or 0.01 typically. A is better than B is statistically significant if the delta seen has prob below the threshold and therefore can reject this null hypothesis. In NLP, use non-parametric tests based on sampling to determine p-value. Most common are approximate randomization and bootstrap test. Paired tests: Those that compare two sets of observations that are aligned. \n\nBootstrap test can be applied to precision, recall, F1, BLEU (any metric). Bootstrapping is repeatedly drawing smaller smaples with replacement from an original larger sample. Can create many virtual test sets doing this. \n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Important to avoid harms in classification. Representational harms - system demeans a social group. Toxicity detection detects abuse, but can itself cause harm. ML replicate or even amplify biases in the training data. Problems can also be caused by the human labelers, resources used, or by the model architecture. Can use a model card to document information like algorithms/parameters, preprocessing, intended use, performance across different demographics, etc. \n\n\n## Module 12 Lecture Notes\n\nMistakes bound: maximum number of mistakes related to the margin or degree of separability. Mistakes < k/(sigma^2). \n\nProblems with perceptron: Noise - if data isn't separable, weights might thrash, averaging weight vectors over time can help. Mediocre generalization - finds a \"barely\" separable solution. Overtraining - test / held-out accuracy usually rises, then falls. \n\nFixing Perceptron: adjust weight updtae to mitigate effects (MIRA). Using maximum step size usually converges faaster and is better on noisy data. \n\nNaive Bayes naive b/c assumes features are conditionally independent of each other\n\nJoint prob model P(X1, X2, X3, Y) for data using Naive bayes assumption is P(Y)P(X1|y)P(X2|Y)P(X3|Y)\n\nPerceptron - training is error-driven, weights only updated when predicted label incorrect\n\nCircle example, can separate two classes by using feature augmentation\n\nPerceptron not guarenteed to converge if data not linearly separable\n\nInference procedure for perceptron describes as: compute a weighted sum, then apply a threshold\n\n\n## Module 12 Definitions\n* **Induction** - Going from specific set of observatins to a general rule\n* **Classification** - Output is set of finite values (cloudy,sunny, etc.)\n* **Regression** - When output is a number (temperature, etc.)\n* **Supervised learning** - Observe input/ouput, create function mapping input to output\n* **Unsupervised learing** - Learns input patterns with no feedback on output (clustering)\n* **Reinforcement learning** - Learns from series of rewards / punishments\n* **Hypothesis** - y=f(x). Discover 'h' that approximates true fucntion of f. Drawn from hypothesis space\n* **Ground truth** - The output y_i, the true answer we are asking model to predict\n* **Consistent hypothesis** - h s.t. each s_i in training set has h(x_i) = y_i.\n* **Bias** - Tendency of predicitive hypothesis to deviate form expected values\n* **Underfit** - Failure to find a pattern in data\n* **Variance** - Amount of change in hypothesis just due to fluctuation in training data\n* **Overfit** - Model pays too much attention to the exact data in the training set\n* **Ockham's razor** - plurality of entities should not be posited without necessity (shave off dubious explanations)\n* **Decision tree** - Maps a vector of attriute value sto an output value\n* **Entropy** - Fundamental quantity in information theory\n* **Significance test** - Assume no underlying pattern. If degree of deviation statistically unlikely, then good evidence for presence of pattern in data\n* **Early stopping** - Stop generating tree if no good attribute detected. Bad practice, could miss good attributes further down\n* **Split point test** - Inequality test on value of an attribute. Most expensive part of algorithm application\n* **Cart** - Classification and Regression Trees\n* **Stationary assumption** - Assume all future examples will be like the past\n* **Iid** - Independent and identically distrubuted (stationary Ej's)\n* **Hyperparameters** - Parameters of the model class, not individual model\n* **K-fold cross-validation** - Split data into k equal subsets, perform k rounds of learning, on each round 1/k data held out\n* **Leave-one-out cross-validation** - LOOCV - k = n k-fold cross-validation\n* **Interpolated** - A model that exactly fits the data\n* **Realizable** - Hypothesis space H actually contains true function f\n* **Regularization** - Penalizing complex hypotheses\n* **Minimum description length** - Minimize total number of bits required\n* **Grid search** - Try all combinations for hypermarametes (works when few and discrete)\n* **Random sampling** - Random choosing from uniform distribution. Good for continuous variables\n* **Bayesian optimization** - Task of choosing hypermarameter values an ML problem itself\n* **Population-based training** - Alternative to Bayesian (above). Train parallely population of models. Do again, slightly based on previous results and slightly on randomness\n* **Sample complexity** - Number of required examples, as a function of epsilon (error) and delta\n* **Weight space** - Space defined by all possible settings of the weights\n* **Gradient descent** - Compute estimate of gradient and move smallamount in steepest downhill direction until converge on local minimum loss\n* **Learning rate** - Parameter alpha in gradient descent\n* **Batch gradient descent** - Also called deterministic gradient descent. For N training samples. Convergence to global minima guarenteed\n* **Stochastic gradient descent** - Faster version of above. Randomly selects small number of training examples, rather than 1 at a time\n* **Multivariable linear regression** - each example x_j is an n-element vector\n* **Sparse model** - Sets many weights to zero - simpler model\n* **Decision boundary** - Separates two classes\n* **Threshhold function** - Defines class separation\n* **Perceptron learning rule** - The update rule for linear regression\n* **Sentiment analysis** - The extraction of a sentiment - positve or negative orientation expressed by writer\n* **Binary multinomial naive bayes (binary nb)** - Clip word counts in each document at 1. (Preference whether a word occurs, not how many times)\n* **Gold labels** - The human-made labels\n* **Precision** - tp / (tp + fp). Measures % of items that system detected as positive that are actually positive\n* **Recall** - tp / (tp + fn). Measures % of items actually present in the input that were correctly identified by the system\n* **Accuracy** - (tp + tn) / (tp + fp + tn + fn)\n* **F-measure** - F_B = (B^2 + 1)PR / (B^2 * P + R). Single metric that incorporates both precision and recall\n* **Macroaveraging** - Compute performance for each class, then average over classes\n* **Microaverageing** - collect decisions for all classes into a single confusion matrix, then compute precision and recall from that table\n* **P-value** - The probability, assuming null hypothesis H_0 is true, of seeing the delta(x) that we saw or one even greater. \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 = \"\"\" Intro: Logistic regression suited very well to link between features and some particular outcome. It is the baseline \\\n",
        "algorithm both for classifiers, and for neural networks. Important difference between Naive Bayes and logistic regression: \\\n",
        "Logistic regression is a discriminative classifier (only tries to know enough to discriminate between dogs and cats), \\\n",
        " Naive Bayes is a generative classifier (understand what dogs and cats look like). Generative model uses the likelihood term \\\n",
        " of what came before it (P(d|c) * P(c)). Discriminative tries to directly compute P(c|d). It could discriminate between possible \\\n",
        " classes, but couldn't generate an example of one of the classes. Components of probabilistic ML classifier: 1. Feature representation \\\n",
        " 2. Classification function. 3. Objective function for learning. 4. Algorithm for optimizing objective function. \n",
        "\n",
        "Ch5_1: Sigmoid classifier helps binary logistic regression make a decision about class of a new input observation. \\\n",
        "Logistic regression learns a set of weights and bias terms. Weights represent how important the feature is. Classifier multiplies \\\n",
        "each x_i by each w_i, sums up, and adds the bias term b. Sigmoid function also called the logistic function [1 / (1 + e^(-z))]. \\\n",
        "Sigmoid function advantages: Takes real-valued number and maps into [0,1] (good for probability). It squashes outlier variables, and \\\n",
        "is differentiable. Decision boundary, for example, could be decision(x) = 1 if P(y=1|x) > 0.5. 0 otherwise. Sentiment example, weights \\\n",
        "can indicate how stronlgy a certain word indicates positive or negative review. Also example of period disambiguation (Deciding \\\n",
        "whether period is end of sentence or part of word). \n",
        "\n",
        "Features generally designed by examining training set and using intuition. Have to combine feature interactions by hand. When \\\n",
        "large number of features needed, can use feature templates. Research ongoing for NLP on representation learning to avoid having \\\n",
        "to manually calculate features. \n",
        "\n",
        "Logistic regression has big advantage over naive Bayes in that Naive bayes has overly strong conditional independence assumptions. \\\n",
        "Logistic regression much better for larger data sets, and is thus default. Advantage of Naive Bayes is that it can work even better \\\n",
        "on very small data sets, and is easier and faster to train. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter5_2 = \"\"\" Logistic regression is a supervised learning model. Need metric for how close y_pred is to y_true. Distance between \\\n",
        "these two called the loss function or the cost function. Cross-entropy loss used for logistic regression and neural networks. Standard \\\n",
        "optimization algorithm for iteratively updating weights is gradient descent (stochastic gradient descent used for logistic \\\n",
        "regression). All these are covered later in chapter.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter5_3 = \"\"\" Use conditional maximum likelihood estimation to choose w, b s.t. log of probability of true y labels \\\n",
        "is maximized. Resulting loss is negative log of this, and is called the cross-entropy loss. NOTE: Put Loss equations on \\\n",
        "handwritten sheet for this part! Perfect classifier would assign 1 to correct answer and 0 to incorrect outcome. Called \\\n",
        "cross-entropy loss because formula is also formula for the cross-entropy between true prob dist 'y' and our estimated prob \\\n",
        "dist y_pred. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter5_4 = \"\"\" Goal is to find the set of weights which minimize the loss function, averaged over the samples. Gradient descent \\\n",
        "finds minimum of a function by determining which direction the slope rising more steeply, and moving in opposite direction. (Good \\\n",
        "intuition in slides). Loss function is convex when using logistic regression, so there's no local minima to get stuck in. The \\\n",
        "magnitude of the amount to move in gradient descent is learning weight eta. Faster learning rate means 'w' is moved more each step. \\\n",
        "Note: Again, many equations which may need for test. Put these on handwritten sheet before test! \n",
        "\n",
        "Stochastic gradient descent is an online function, minimizes loss function by computing gradient after each training example \\\n",
        "then nudging theta in correct direction. Can adjust learning rate Eta becaues it is a hyperparameter. Commonly, start high and then \\\n",
        "get low. Hyperparameters affect how the algorithm works. Stochastic gradient descent example shown, same as in slides. May be good \\\n",
        "to put on sheet. Called stochastic because it chooses one example randomly at a time. Can also use batch training or mini-batch \\\n",
        "training (both defined below). \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter5_5 = \"\"\" Issue: If a feature perfectly predictive only because it happens to occur in one class, assigned very high weight. \\\n",
        "May not reflect real data (data is now overfit!). Good model should generalize. Regularization term added to avoid overfitting. \\\n",
        "This penalizes large weights. Can use L2 regularization or L1 regularization (defined below). L2 aesier to optimize b/c simple \\\n",
        "derivative, L1 more complex. L2 prefers many small weights, L1 prefers sparse solutions with some larger weights and many weights \\\n",
        "set to zero. Both have Bayesian interpretations as constraints on the prior of how weights look.  \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter5_6 = \"\"\" Multinomial logistic regression used when need more than 2 classes. Also called softmax regression, or \\\n",
        "maxent classifier. Uses generalization of the sigmoid, called the softmax function. Write softmax functin on sheet. In multinimial, \\\n",
        "weights for features now represent evidence for or against each individual class. Loss function is generalized to 'k' terms instead \\\n",
        "of 2. One-hot vector is when only one value in vector is 1, and the rest are 0. Gradient for a single example similar to gradient \\\n",
        "for binary logistic regression. \n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Intro: Neural net name origin from Mculloh-Pitts neuron. Neural network is a network of small computing units, \\\n",
        "each take vector of inputs and output 1 value. Often called deep learning because of the many layers. In logistic regression, \\\n",
        "usually have rich feature templates, whereas in neural networks, prefer raw words as inputs and learn to induce features during \\\n",
        "the process. Deep neural nets correct tool when large data set and enough data to learn features automatically\n",
        "\n",
        "Ch7_1: This section describes the builing block (single unit) inside a neural network. Seems exactly like a perceptron (sigmoid \\\n",
        "function, bias term, dot product, etc.). However, also covers non-linear units that are needed for many neural networks. \\\n",
        "Vanishing gradient problem is when gradients that are almost 0 caues error signal to get smaller until too small to be used for training.\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_2 = \"\"\" Perceptron can easily compute AND and OR, but cannot handle XOR at all! This is because perceptron is a linear \\\n",
        "classifier, and thus decision boundary is a line. XOR can be calculated by a layered network of units. Example using two ReLU-based \\\n",
        "units. Can view hidden layer of the network as forming a representation for the input. Neural networks big advantage is they \\\n",
        "can automatically learn to form these representations well. Note: XOR requires network of units with non-linear activation functions, \\\n",
        "i.e. CANNOT do it with just perceptrons (simple linear units). This due to fact that many layers of linear units can be reduced to \\\n",
        "one layer with a certain weights function, which we know can't solve the XOR problem. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter7_3 = \"\"\" Feedforward network most simple. Misnomer that they're called multi-layer perceptrons, since most modern ones \\\n",
        "don't use perceptrons as units. Three types of units: input, hidden, and output. Input x is vector of simple scalar values. \\\n",
        "Hidden layer 'h' is the core (takes weighted sum of inputs and applies non-linearity). Standard: fully-connected, each unit takes all \\\n",
        "inputs from previous layer. Computation done simply with simple matrix operations. h = sigma (Wx + b). Once you have h, calculate \\\n",
        "final probabilities using z = Uh, then normalizing z using softmax. \n",
        "\n",
        "h = sigma (Wx + b)\n",
        "\n",
        "z = Uh\n",
        "\n",
        "y = softmax(z)\n",
        "\n",
        "This is a two layer network. Usually use a dummy node of 1 for each layer to represent bias, then apply a weight to the 1 that \\\n",
        "represents the bias. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter7_4 = \"\"\" Example using sentiment classifer in this section. Generally uses deep learning's ability to learn features \\\n",
        "by using word2vec to get a contatination of vector for input x. This is an example of pretraining - a central idea of deep \\\n",
        "learning. Relying on another algorithm to have already learned an embeded represenation for the input.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter7_5 = \"\"\" Example of another application: language  modeling - predicting upcoming words from prior words. \\\n",
        "\n",
        "\n",
        "Advantages of neural language models over n-gram models: 1. Can handle much longer histories. 2. Can generalize better over \\\n",
        "context of similar words. 2. More accurate at word-prediction.\n",
        "\n",
        "Disadvantages: complex, slower, less interpretable.\n",
        "\n",
        "Neural network similar, in that is predicts probability of next words based on N previous words. Difference: Neural LM represent \\\n",
        "words in prior context by their embeddings, rather than their word identity as in n-gram LM. Embeddings better for generalization \\\n",
        "to unseen data. Neural LM would generalize from cat to dog to realize dog needs to be fed. \n",
        "\n",
        "Forward interference important (defined below). First represent each of N previous words as one-hot vectors of length |V|. \\\n",
        "Moving window can see N words into past. Multiply one-hot encodings by matrix E. E has d x |V| dimensions, basically results in \\\n",
        "selecting the embedding for word 'i'. Resulting embedding vectors concatenated to produce 'e', the embedding layer. Example \\\n",
        "showing this process concatenating 3 embeddings shown here (go over before test!).  \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter7_6 = \"\"\" Common to use same loss function (cross-entropy loss) in neural nets. Also use gradient descent to minimize \\\n",
        "the loss function. Can't do simple derivative for gradient now though, and must use technique called error back propagation (also \\\n",
        "known as backward differentiation). \n",
        "\n",
        "Loss function is exatly the same equation. \n",
        "\n",
        "Example using L(a,b,c) = c(a + 2b) shown using backpropogation for much of rest of chapter. Make sure to go over before test and \\\n",
        "can do independently. Backward differentiation makes use of the chain rule. Put backward pass picture (Figure 7.16) on notes sheet. \\\n",
        "\n",
        "NOTE: Optimization in neural networks is a NON-convex optimization problem, much more complex than logistic regression. Must \\\n",
        "initialize weights with small random numbers rather than 0 now. Also good to normalize input to 0 mean and unit variance. \\\n",
        "Dropout (defined) used as form of regularization to avoid overfitting. Tuning of hyperparameters also very important. Include \\\n",
        "learning rate 'Eta', mini-batch size, model architecture, how to regularize, etc. Most modern neural networks built using \\\n",
        "computation graph formalisms to make better to do gradient computation and parallelization on vector-based GPU's.  \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter7_7 = \"\"\" This section deals with specifics on training a neural language model. Can either \"Freeze\" the \\\n",
        "embedding matrix E using word2vec, or let it update along with everything else being learned. Can train everything (theta = E,W,U,b) \\\n",
        "via gradient descent. Training proceeds by taking as input a long text, concatenating all sentences, starting with random \\\n",
        "weights, and iteratively moving through the text predicting each word w_t. At each w_t, use cross-entropy (negative log \\\n",
        "likelihood) loss. Training parameters that limit loss will result in an algorithm for the language model (word predictor) and \\\n",
        "also a new set of embeddings 'E' that ar used as word representations for other tasks. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Currently no additional notes from lectures, as lectures followed readings very closely. Many equations \\\n",
        "figures on hand-written sheet from this module however.\n",
        "\n",
        "Added:\n",
        "\n",
        "Linear classifiers - when using perceptron learning rule, weights updated when actual output does not match the \\\n",
        "hypothesis output. Can be used for both regression and classification. Not true that learning rule must be applied \\\n",
        "to one example at a time.\n",
        "\n",
        "A parametric model has a fixed size on the number of parameters, where a nonparametric model does not. \n",
        "\n",
        "It is false that 'When performing k-means clustering, each observation always tarts in its own cluster, and then pairs \\\n",
        "of clusters are merged in each iteration\" because its only true in agglomerative clustering.\n",
        "\n",
        "It is false that 'For lineraly separable data, there exists only one decision boundary that separates the classes' because \\\n",
        "there could be multiple boundaries, with varying performance.\n",
        "\n",
        "It is possible that assignment of observations to clusters do not change between successive iterations in K-means\n",
        "\n",
        "Nonlinear activiation function - make it possible to do gradient backprogagation, help learn nonlinear decision boundaries\n",
        "\n",
        "Nonlinear activation functions can be applied to layers other than output. Also, don't ALWAYS have to ouput values \\\n",
        "between 0 and 1. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Logistic regression\" : \"Algorithm suited to determining link between features and an outcome\",\n",
        "\"Generative model\" : \"Understands what dogs and cats look like\",\n",
        "\"Discriminative model\" : \"Can tell the difference between dogs and cats, but can't draw one\",\n",
        "\"Sigmoid\" : \"Logistic function, Takes real-valued number and maps into [0,1]\",\n",
        "\"Feature interaction\" : \"Features that are a combination of more primitive features\",\n",
        "\"Feature templates\" : \"Abstract specifications of features\",\n",
        "\"Loss function\" : \"Distance between y_pred and y_real\",\n",
        "\"Conditional maximum likelihood estimation\" : \"Loss function that prefers correct class labels to be more likely\",\n",
        "\"Cross-entropy loss\" : \"Negative log of the conditional maximum likelihood estimation\",\n",
        "\"Stochastic gradient descent\" : \"online function, minimizes loss function by computing gradient after each training example \\\n",
        "then nudging theta in correct direction\",\n",
        "\"Batch training\" : \"Compute gradient over entire dataset. Better estimate of direction to go, but much more processing\",\n",
        "\"Mini-batch training\" : \"Train on a group of 'm' samples. Good middle-ground. Can also process mini-batches in parallel\",\n",
        "\"L2 regularization\" : \"quadratic function of weight values. Same as Euclidiance distance of vector theta from origin (RIDGE REG)\",\n",
        "\"L1 regularization\" : \"Linear function of weight values. Sum of the Manhattan distance of absolute values of weights (LASSO REG)\",\n",
        "\"Vanishing gradient problem\" : \"gradients that are almost 0 caues error signal to \\\n",
        "get smaller until too small to be used for training\",\n",
        "\"ReLU\" : \"Rectified linear unit - simplest activation function (straight line from 0, linear up to 10?)\",\n",
        "\"Feedforward network\" : \"Simplest. Units connected with no cycles. No ouputs passed backwards\",\n",
        "\"Output of hidden layer\" : \"h = sigma (Wx + b)\",\n",
        "\"Pretraining\" : \"central idea of deep-learning. Relying on another algorithm to have already learned an embeded represenation for the input\",\n",
        "\"Forward Interference/Decoding\" : \"Fiven an input, run forward pass on network to produce prob dist over possible inputs\",\n",
        "\"One-hot vector\" : \"Vector that has one element equal to 1, others all 0\",\n",
        "\"Hard classification task\" : \"Only one class is correct one, and 1 output unit in y for each task\",\n",
        "\"dropout\" : \"Regularization technique to avoid overfitting. Randomly drop some units/connects while training\",\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "293aa86c-957a-48b9-98d6-dec1fc062786"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Intro: Logistic regression suited very well to link between features and some particular outcome. It is the baseline algorithm both for classifiers, and for neural networks. Important difference between Naive Bayes and logistic regression: Logistic regression is a discriminative classifier (only tries to know enough to discriminate between dogs and cats),  Naive Bayes is a generative classifier (understand what dogs and cats look like). Generative model uses the likelihood term  of what came before it (P(d|c) * P(c)). Discriminative tries to directly compute P(c|d). It could discriminate between possible  classes, but couldn't generate an example of one of the classes. Components of probabilistic ML classifier: 1. Feature representation  2. Classification function. 3. Objective function for learning. 4. Algorithm for optimizing objective function. \n\nCh5_1: Sigmoid classifier helps binary logistic regression make a decision about class of a new input observation. Logistic regression learns a set of weights and bias terms. Weights represent how important the feature is. Classifier multiplies each x_i by each w_i, sums up, and adds the bias term b. Sigmoid function also called the logistic function [1 / (1 + e^(-z))]. Sigmoid function advantages: Takes real-valued number and maps into [0,1] (good for probability). It squashes outlier variables, and is differentiable. Decision boundary, for example, could be decision(x) = 1 if P(y=1|x) > 0.5. 0 otherwise. Sentiment example, weights can indicate how stronlgy a certain word indicates positive or negative review. Also example of period disambiguation (Deciding whether period is end of sentence or part of word). \n\nFeatures generally designed by examining training set and using intuition. Have to combine feature interactions by hand. When large number of features needed, can use feature templates. Research ongoing for NLP on representation learning to avoid having to manually calculate features. \n\nLogistic regression has big advantage over naive Bayes in that Naive bayes has overly strong conditional independence assumptions. Logistic regression much better for larger data sets, and is thus default. Advantage of Naive Bayes is that it can work even better on very small data sets, and is easier and faster to train. \n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Logistic regression is a supervised learning model. Need metric for how close y_pred is to y_true. Distance between these two called the loss function or the cost function. Cross-entropy loss used for logistic regression and neural networks. Standard optimization algorithm for iteratively updating weights is gradient descent (stochastic gradient descent used for logistic regression). All these are covered later in chapter.\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n Use conditional maximum likelihood estimation to choose w, b s.t. log of probability of true y labels is maximized. Resulting loss is negative log of this, and is called the cross-entropy loss. NOTE: Put Loss equations on handwritten sheet for this part! Perfect classifier would assign 1 to correct answer and 0 to incorrect outcome. Called cross-entropy loss because formula is also formula for the cross-entropy between true prob dist 'y' and our estimated prob dist y_pred. \n\n\n## SLP Chapter 5.4 Gradient Descent\n Goal is to find the set of weights which minimize the loss function, averaged over the samples. Gradient descent finds minimum of a function by determining which direction the slope rising more steeply, and moving in opposite direction. (Good intuition in slides). Loss function is convex when using logistic regression, so there's no local minima to get stuck in. The magnitude of the amount to move in gradient descent is learning weight eta. Faster learning rate means 'w' is moved more each step. Note: Again, many equations which may need for test. Put these on handwritten sheet before test! \n\nStochastic gradient descent is an online function, minimizes loss function by computing gradient after each training example then nudging theta in correct direction. Can adjust learning rate Eta becaues it is a hyperparameter. Commonly, start high and then get low. Hyperparameters affect how the algorithm works. Stochastic gradient descent example shown, same as in slides. May be good to put on sheet. Called stochastic because it chooses one example randomly at a time. Can also use batch training or mini-batch training (both defined below). \n\n\n## SLP Chapter 5.5 Regularization\n Issue: If a feature perfectly predictive only because it happens to occur in one class, assigned very high weight. May not reflect real data (data is now overfit!). Good model should generalize. Regularization term added to avoid overfitting. This penalizes large weights. Can use L2 regularization or L1 regularization (defined below). L2 aesier to optimize b/c simple derivative, L1 more complex. L2 prefers many small weights, L1 prefers sparse solutions with some larger weights and many weights set to zero. Both have Bayesian interpretations as constraints on the prior of how weights look.  \n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Multinomial logistic regression used when need more than 2 classes. Also called softmax regression, or maxent classifier. Uses generalization of the sigmoid, called the softmax function. Write softmax functin on sheet. In multinimial, weights for features now represent evidence for or against each individual class. Loss function is generalized to 'k' terms instead of 2. One-hot vector is when only one value in vector is 1, and the rest are 0. Gradient for a single example similar to gradient for binary logistic regression. \n\n\n## SLP Chapter 7.1 Units\n Intro: Neural net name origin from Mculloh-Pitts neuron. Neural network is a network of small computing units, each take vector of inputs and output 1 value. Often called deep learning because of the many layers. In logistic regression, usually have rich feature templates, whereas in neural networks, prefer raw words as inputs and learn to induce features during the process. Deep neural nets correct tool when large data set and enough data to learn features automatically\n\nCh7_1: This section describes the builing block (single unit) inside a neural network. Seems exactly like a perceptron (sigmoid function, bias term, dot product, etc.). However, also covers non-linear units that are needed for many neural networks. Vanishing gradient problem is when gradients that are almost 0 caues error signal to get smaller until too small to be used for training.\n\n\n## SLP Chapter 7.2 The XOR problem\n Perceptron can easily compute AND and OR, but cannot handle XOR at all! This is because perceptron is a linear classifier, and thus decision boundary is a line. XOR can be calculated by a layered network of units. Example using two ReLU-based units. Can view hidden layer of the network as forming a representation for the input. Neural networks big advantage is they can automatically learn to form these representations well. Note: XOR requires network of units with non-linear activation functions, i.e. CANNOT do it with just perceptrons (simple linear units). This due to fact that many layers of linear units can be reduced to one layer with a certain weights function, which we know can't solve the XOR problem. \n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Feedforward network most simple. Misnomer that they're called multi-layer perceptrons, since most modern ones don't use perceptrons as units. Three types of units: input, hidden, and output. Input x is vector of simple scalar values. Hidden layer 'h' is the core (takes weighted sum of inputs and applies non-linearity). Standard: fully-connected, each unit takes all inputs from previous layer. Computation done simply with simple matrix operations. h = sigma (Wx + b). Once you have h, calculate final probabilities using z = Uh, then normalizing z using softmax. \n\nh = sigma (Wx + b)\n\nz = Uh\n\ny = softmax(z)\n\nThis is a two layer network. Usually use a dummy node of 1 for each layer to represent bias, then apply a weight to the 1 that represents the bias. \n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Example using sentiment classifer in this section. Generally uses deep learning's ability to learn features by using word2vec to get a contatination of vector for input x. This is an example of pretraining - a central idea of deep learning. Relying on another algorithm to have already learned an embeded represenation for the input.\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Example of another application: language  modeling - predicting upcoming words from prior words. \n\nAdvantages of neural language models over n-gram models: 1. Can handle much longer histories. 2. Can generalize better over context of similar words. 2. More accurate at word-prediction.\n\nDisadvantages: complex, slower, less interpretable.\n\nNeural network similar, in that is predicts probability of next words based on N previous words. Difference: Neural LM represent words in prior context by their embeddings, rather than their word identity as in n-gram LM. Embeddings better for generalization to unseen data. Neural LM would generalize from cat to dog to realize dog needs to be fed. \n\nForward interference important (defined below). First represent each of N previous words as one-hot vectors of length |V|. Moving window can see N words into past. Multiply one-hot encodings by matrix E. E has d x |V| dimensions, basically results in selecting the embedding for word 'i'. Resulting embedding vectors concatenated to produce 'e', the embedding layer. Example showing this process concatenating 3 embeddings shown here (go over before test!).  \n\n\n## SLP Chapter 7.6 Training Neural Nets\n Common to use same loss function (cross-entropy loss) in neural nets. Also use gradient descent to minimize the loss function. Can't do simple derivative for gradient now though, and must use technique called error back propagation (also known as backward differentiation). \n\nLoss function is exatly the same equation. \n\nExample using L(a,b,c) = c(a + 2b) shown using backpropogation for much of rest of chapter. Make sure to go over before test and can do independently. Backward differentiation makes use of the chain rule. Put backward pass picture (Figure 7.16) on notes sheet. \nNOTE: Optimization in neural networks is a NON-convex optimization problem, much more complex than logistic regression. Must initialize weights with small random numbers rather than 0 now. Also good to normalize input to 0 mean and unit variance. Dropout (defined) used as form of regularization to avoid overfitting. Tuning of hyperparameters also very important. Include learning rate 'Eta', mini-batch size, model architecture, how to regularize, etc. Most modern neural networks built using computation graph formalisms to make better to do gradient computation and parallelization on vector-based GPU's.  \n\n\n## SLP Chapter 7.7 Training the neural language model\n This section deals with specifics on training a neural language model. Can either \"Freeze\" the embedding matrix E using word2vec, or let it update along with everything else being learned. Can train everything (theta = E,W,U,b) via gradient descent. Training proceeds by taking as input a long text, concatenating all sentences, starting with random weights, and iteratively moving through the text predicting each word w_t. At each w_t, use cross-entropy (negative log likelihood) loss. Training parameters that limit loss will result in an algorithm for the language model (word predictor) and also a new set of embeddings 'E' that ar used as word representations for other tasks. \n\n\n## Module 13 Lecture Notes\n Currently no additional notes from lectures, as lectures followed readings very closely. Many equations figures on hand-written sheet from this module however.\n\nAdded:\n\nLinear classifiers - when using perceptron learning rule, weights updated when actual output does not match the hypothesis output. Can be used for both regression and classification. Not true that learning rule must be applied to one example at a time.\n\nA parametric model has a fixed size on the number of parameters, where a nonparametric model does not. \n\nIt is false that 'When performing k-means clustering, each observation always tarts in its own cluster, and then pairs of clusters are merged in each iteration\" because its only true in agglomerative clustering.\n\nIt is false that 'For lineraly separable data, there exists only one decision boundary that separates the classes' because there could be multiple boundaries, with varying performance.\n\nIt is possible that assignment of observations to clusters do not change between successive iterations in K-means\n\nNonlinear activiation function - make it possible to do gradient backprogagation, help learn nonlinear decision boundaries\n\nNonlinear activation functions can be applied to layers other than output. Also, don't ALWAYS have to ouput values between 0 and 1. \n\n\n## Module 13 Definitions\n* **Logistic regression** - Algorithm suited to determining link between features and an outcome\n* **Generative model** - Understands what dogs and cats look like\n* **Discriminative model** - Can tell the difference between dogs and cats, but can't draw one\n* **Sigmoid** - Logistic function, Takes real-valued number and maps into [0,1]\n* **Feature interaction** - Features that are a combination of more primitive features\n* **Feature templates** - Abstract specifications of features\n* **Loss function** - Distance between y_pred and y_real\n* **Conditional maximum likelihood estimation** - Loss function that prefers correct class labels to be more likely\n* **Cross-entropy loss** - Negative log of the conditional maximum likelihood estimation\n* **Stochastic gradient descent** - online function, minimizes loss function by computing gradient after each training example then nudging theta in correct direction\n* **Batch training** - Compute gradient over entire dataset. Better estimate of direction to go, but much more processing\n* **Mini-batch training** - Train on a group of 'm' samples. Good middle-ground. Can also process mini-batches in parallel\n* **L2 regularization** - quadratic function of weight values. Same as Euclidiance distance of vector theta from origin (RIDGE REG)\n* **L1 regularization** - Linear function of weight values. Sum of the Manhattan distance of absolute values of weights (LASSO REG)\n* **Vanishing gradient problem** - gradients that are almost 0 caues error signal to get smaller until too small to be used for training\n* **Relu** - Rectified linear unit - simplest activation function (straight line from 0, linear up to 10?)\n* **Feedforward network** - Simplest. Units connected with no cycles. No ouputs passed backwards\n* **Output of hidden layer** - h = sigma (Wx + b)\n* **Pretraining** - central idea of deep-learning. Relying on another algorithm to have already learned an embeded represenation for the input\n* **Forward interference/decoding** - Fiven an input, run forward pass on network to produce prob dist over possible inputs\n* **One-hot vector** - Vector that has one element equal to 1, others all 0\n* **Hard classification task** - Only one class is correct one, and 1 output unit in y for each task\n* **Dropout** - Regularization technique to avoid overfitting. Randomly drop some units/connects while training\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) (8 pages total)\n",
        "\n",
        "slp_chapter9_1 = \"\"\"\n",
        "\n",
        "Intro: Language inherently temporal. Recurrent network gives to way to represent prior context (now decision depends \\\n",
        "on hundreds of words into the past). Transformer method offers to mechanisms - self-attention and positional encoding - \\\n",
        "to represent time. This helps relate words over long distances. \n",
        "\n",
        "9_1: Good models are those that assign higher probabilities to unseens data. Use perplexity to measure quality of \\\n",
        "a language model. (Write down perplexity equation on sheet from here!).\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter9_2 = \"\"\" Recurrent neural networks (RNNs) contain a cycle within its connections. This means a value of a \\\n",
        "unit is directly and/or indirectly dependent on own earlier outputs as an input. Generally difficult to understand, but very \\\n",
        "powerful for language applications. Simple recurrent networks serve as basis for more complex networks. Difference now is \\\n",
        "sequences processed one item at a time in network (not window-based all at once). Key is that augmentation in hidden layer \\\n",
        "happens according to previous output from same hidden layer. Does not impose a fixed-length limit on this prior context. \\\n",
        "Various weight matrices are shared across time. New values for 'h' and 'y' are calculated with each time step. \\\n",
        "\n",
        "Similarity: still uses training set, loss function, and back-propagation to get gradients to change weights. Back-propagation \\\n",
        "now more complex, must know influence on all future time steps to calculate the current error. Leads to needing a two-pass \\\n",
        "algorithm. Pass 1: forward inference on h_t, y_t, accumulate loss, save value of hidden layer. Pass 2: process in reverse, \\\n",
        "compute required gradients as you go, compute and save error term for use in next step backward in time. Known as \\\n",
        "Backpropagation Through Time. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter9_3 = \"\"\" Train RNN as language model using a corpus of text. Train to minimize error in predicting next \\\n",
        "true word, use cross-entropy as loss function. Use teacher forcing (defined below). Use Weight Tying to dispense with redundancy \\\n",
        "and use a single set of embeddings at input and softmax layers (i.e., E = V). Do by setting dimensionality of final \\\n",
        "hidden layer to be the same d_h, then use same matrix for both layers. This improves complexity and reduces \\\n",
        "number of parameters required for the model. \n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12) (22 pages total)\n",
        "\n",
        "slp_chapter6_1 = \"\"\"\n",
        "\n",
        "Intro: Link between similarity of words and distribution of words (distributional hypothesis). Vector semantics use \\\n",
        "embeddings (both defined). Uses self-learning rather than feature represenation.  \n",
        "\n",
        "6_1: Many definitions defined below. Most words have a lot of similarties, but not synonyms. Relatedness / association \\\n",
        "refers to things like coffee and cup. These constitute a semantic field. Topic models use unsupervised learning on \\\n",
        "large texts to get associated words. Definitions down to sentiment cover this 6_1 section. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_2 = \"\"\"Vector semantics is standard way to represent a words meaning. Embeddings will group similar words \\\n",
        "even if you don't know the meaning of them. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_3 = \"\"\" Vector models of meaning generally based on co-occurence matrix (how often words co-occur). Can \\\n",
        "think of vector for a document as point in |V|-dimensional space.  Another model is the term-term matrix (also known as \\\n",
        "word-word matrix or term-context matrix). In this, columns labeled by words rather than documents. Could be: number of \\\n",
        "times column word occurs in a +-4 word window around the row word. |V| generally size of vocubulary in all models. These \\\n",
        "are usually sparse models because of this. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_4 = \"\"\" Most common similarity metric is the cosine of the angle between the vectors of two words. It \\\n",
        "is based on the dot product. However, raw dot product favors long vectors. Fix by normalizing by dividing by lengths \\\n",
        "of each of two vectors. This normalized dot product is same as cosine of angle between two vectors. Sometimes, we \\\n",
        "will pre-normalize each vector by dividing by length and creating unit vectors. Dot product same as cosine for \\\n",
        "unit vectors.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_8 = \"\"\" Embeddings are much shorter than vectors seen so far, usually 50-1000. Also they are dense. \\\n",
        "Dense vectors always work better in NLP tasks. Also better at recognizing similarity. Word2vec methods fast, \\\n",
        "efficient to train, an easily available online. They are static, i.e., the method learns one fixed embedding for each \\\n",
        "word in the vocabulary. Main difference: asks is word 'w' likely to show up near word 'w2'. Take learned weights as \\\n",
        "word embeddings.\n",
        "\n",
        "Revolutionary intuition: can use running text as impolicitely supervised training dat for a classifier; a word 'c' \\\n",
        "that occurs near 'apricot' acts as golden 'correct answer'. This is self-supervision, and therefore doesn't need \\\n",
        "any handlabeling. Word2vec simpler becaus simplifies task (binary), and simplifies architecture (logistic regression \\\n",
        "instead of multi-layer neural network). \n",
        "\n",
        "skip-gram: 1. Treat target word and neighboring context as positive. 2. Randomly sample other words for negatives. \\\n",
        "3. Logistic regression to distinguish between these. 4. Use learned weights as embeddings.\n",
        "\n",
        "Use a sigmoid to turn dot product into a probability.\n",
        "\n",
        "P(+|w,c) = 1 / (1 + exp(-c dot w)). \n",
        "\n",
        "P(-|w,c) = 1 / (1 + exp(c dot w)). \n",
        "\n",
        "skip-gram learns two separate embeddings for each word i - target embedding w_i and context embedding c_i. Can either \\\n",
        "add together at end, or just throw away C matrix and represent by w_i. \n",
        "\n",
        "fasttest is an extension of word2vec, better at dealing with unknown words. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_10 = \"\"\" size of context window usually +-1-10 words. Shorter context = more syntactic. High context = \\\n",
        "topically related but not similar. First order vs. second order occurence defined. Parallel model used by adding vectors \\\n",
        "to answer question a is to b as a* is to ____. Didn't work super well at first, but then works very well in word2vec. \\\n",
        "\n",
        "b* = argmin distance(x,a* - a + b)\n",
        "\n",
        "Works well in some cases, but not in others though in general. Some argue its too simplistic. Embeddings also useful \\\n",
        "to compute how meanings change over time. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_11 = \"\"\" Embeddings represent implicit bias that was embedded in texts too. Leads to allocation harm. \\\n",
        "Bias amplification actually occurs in vectors. Also demonstrate implicit associations, even bad ones, such as \\\n",
        "associating more negative words with African-American names. Causes representational harm - system demeans or \\\n",
        "ignores social groups. Can also use this in a historical context to see historical biases. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "slp_chapter6_12 = \"\"\" Extrinsic evaluation on tasks is most important metric. However, also useful to have \\\n",
        "intrinsic evaluations. Most common metric here is to test performance on similarity (correlation between \\\n",
        "algorithm's word similarty scores and a gold-standard assigned by humans). WordSim-353 a common tool used for this. \\\n",
        "SimLex-999 more difficult dataset. TOEFL has 80 questions, asks to choose most similar word from options. Also \\\n",
        "programs to compare context, not just similarity. Analogy tasks as well are used, like those described above.\n",
        "\n",
        "Important: Can suffer from variability. Very important to train multiple embeddings with bootsrap sampling and \\\n",
        "average the results. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"Notes cover same things as readings. When studying, go through and \\\n",
        "write down the equations on handwritten notes sheet\n",
        "\n",
        "Added:\n",
        "\n",
        "Benefits of log probabilities: avoids underflow from using small numbers, sometimes easier to optimize over sums than \\\n",
        "products.\n",
        "\n",
        "Markov models staionary because distribution of X_t after sufficiently long time that distribution of X_t doesn't change \\\n",
        "any more. It is not because probs are invariant with respect to shifts in data.\n",
        "\n",
        "IMPORTANT: Cross-entropy is an upper bound on entropy. The more accurate a model, the lower the cross-entropy.\n",
        "\n",
        "Vector representation using term-document matrices and word-word matrices can't account for polysemy.\n",
        "\n",
        "n-gram model for a corpus with vocab size V and total T tokens would have run time depending on n and T.\n",
        "\n",
        "Purpose of Laplace smoothing is to account for unseen words.\n",
        "\n",
        "When generating random text, given a context C, n-gram model can't generate next token T if model never saw the \\\n",
        "context-token pair (C,T) during training. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"Elman Networds / simple recurrent networks\" : \"RNN (simple version). Activation value of hidden layer depends on current input and activation val of previous time step\", \n",
        "\"Backprogation Through Time\" : \"2-pass backpropagation algorithm to deal with temporal nature of algorithm. Described in 9_2 above.\",   \n",
        "\"Teacher forcing\" : \"Always give model correct history sequence to predict next word, rather than bets case from previous time step\",  \n",
        "\"Weight tying\" : \"Uses a single set of embeddings at input and softmax layers. How to do it described in 9_3 above\",  \n",
        "\"Distributional hypothesis\" : \"Link between similarity in word distribution and similarity in their meaning\",  \n",
        "\"Vector semantics\" : \"learn representation of meaning of words (embeddings) directly from text distribution\",  \n",
        "\"Representation learning\" : \"Automaticalyl learn useful represenations - self-supervised\",  \n",
        "\"Lexical semantics\" : \"Word meaning\",  \n",
        "\"lemma\" : \"Basically the most basic form (mouse for mice)\",  \n",
        "\"Word sense\" : \"The aspect of the meaning of a word (Mouse has rodent or cursor as word senses)\",  \n",
        "\"Polysemous\" : \"multiple word senses\",  \n",
        "\"Synonym\" : \"Substitutable in a sentence without changing the truth of the sentence\",  \n",
        "\"Principle of contrast\" : \"Difference in form of word always connotates a different meaning (h20 vs water)\",  \n",
        "\"Relatedness\" : \"Coffee and cup\",\n",
        "\"Semantics field\" : \"Hospital - doctors, medical, etc.\",\n",
        "\"Semantic frame\" : \"Set of words that denote a perspective or participants - buying and selling\",\n",
        "\"Connotations\" : \"affective meaning, word's meaning changes with writer/readers emotions, opinions, etc. \",\n",
        "\"Sentiment\" : \"Positive or negative evaluation (measured by valence (pleasentess), arousal (intensity), and dominance (control)\",\n",
        "\"Term-document matrix\" : \"Each row represents word in vocabulary, each colum represents a document\",\n",
        "\"Vector space model\" : \"Document as a count vector if using term-document matrix model\",\n",
        "\"Information retrieval\" : \"task of finding document d from the D documents that best match query q\",\n",
        "\"term-term matrix\" : \"Both columns/rows words. Usually, how many times column word occurs in +-4 windown of row word\",\n",
        "\"First order occurence\" : \"Syntagmatic association - typically near each other\",\n",
        "\"Second order occurence\" : \"Paradigmatic association - similar neighbors\",\n",
        "\"Allocational harm\" : \"System allocates resources unfairly (father -> doctor, mother -> nurse)\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0785e912-b09e-47f1-d4a2-cb58f021d0ce"
      },
      "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 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\nIntro: Language inherently temporal. Recurrent network gives to way to represent prior context (now decision depends on hundreds of words into the past). Transformer method offers to mechanisms - self-attention and positional encoding - to represent time. This helps relate words over long distances. \n\n9_1: Good models are those that assign higher probabilities to unseens data. Use perplexity to measure quality of a language model. (Write down perplexity equation on sheet from here!).\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Recurrent neural networks (RNNs) contain a cycle within its connections. This means a value of a unit is directly and/or indirectly dependent on own earlier outputs as an input. Generally difficult to understand, but very powerful for language applications. Simple recurrent networks serve as basis for more complex networks. Difference now is sequences processed one item at a time in network (not window-based all at once). Key is that augmentation in hidden layer happens according to previous output from same hidden layer. Does not impose a fixed-length limit on this prior context. Various weight matrices are shared across time. New values for 'h' and 'y' are calculated with each time step. \nSimilarity: still uses training set, loss function, and back-propagation to get gradients to change weights. Back-propagation now more complex, must know influence on all future time steps to calculate the current error. Leads to needing a two-pass algorithm. Pass 1: forward inference on h_t, y_t, accumulate loss, save value of hidden layer. Pass 2: process in reverse, compute required gradients as you go, compute and save error term for use in next step backward in time. Known as Backpropagation Through Time. \n\n\n## SLP Chapter 9.3 RNNs as Language Models\n Train RNN as language model using a corpus of text. Train to minimize error in predicting next true word, use cross-entropy as loss function. Use teacher forcing (defined below). Use Weight Tying to dispense with redundancy and use a single set of embeddings at input and softmax layers (i.e., E = V). Do by setting dimensionality of final hidden layer to be the same d_h, then use same matrix for both layers. This improves complexity and reduces number of parameters required for the model. \n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n\nIntro: Link between similarity of words and distribution of words (distributional hypothesis). Vector semantics use embeddings (both defined). Uses self-learning rather than feature represenation.  \n\n6_1: Many definitions defined below. Most words have a lot of similarties, but not synonyms. Relatedness / association refers to things like coffee and cup. These constitute a semantic field. Topic models use unsupervised learning on large texts to get associated words. Definitions down to sentiment cover this 6_1 section. \n\n\n## SLP Chapter 6.2 Vector Semantics\nVector semantics is standard way to represent a words meaning. Embeddings will group similar words even if you don't know the meaning of them. \n\n\n## SLP Chapter 6.3 Words and Vectors\n Vector models of meaning generally based on co-occurence matrix (how often words co-occur). Can think of vector for a document as point in |V|-dimensional space.  Another model is the term-term matrix (also known as word-word matrix or term-context matrix). In this, columns labeled by words rather than documents. Could be: number of times column word occurs in a +-4 word window around the row word. |V| generally size of vocubulary in all models. These are usually sparse models because of this. \n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Most common similarity metric is the cosine of the angle between the vectors of two words. It is based on the dot product. However, raw dot product favors long vectors. Fix by normalizing by dividing by lengths of each of two vectors. This normalized dot product is same as cosine of angle between two vectors. Sometimes, we will pre-normalize each vector by dividing by length and creating unit vectors. Dot product same as cosine for unit vectors.\n\n\n## SLP Chapter 6.8 Word2vec\n Embeddings are much shorter than vectors seen so far, usually 50-1000. Also they are dense. Dense vectors always work better in NLP tasks. Also better at recognizing similarity. Word2vec methods fast, efficient to train, an easily available online. They are static, i.e., the method learns one fixed embedding for each word in the vocabulary. Main difference: asks is word 'w' likely to show up near word 'w2'. Take learned weights as word embeddings.\n\nRevolutionary intuition: can use running text as impolicitely supervised training dat for a classifier; a word 'c' that occurs near 'apricot' acts as golden 'correct answer'. This is self-supervision, and therefore doesn't need any handlabeling. Word2vec simpler becaus simplifies task (binary), and simplifies architecture (logistic regression instead of multi-layer neural network). \n\nskip-gram: 1. Treat target word and neighboring context as positive. 2. Randomly sample other words for negatives. 3. Logistic regression to distinguish between these. 4. Use learned weights as embeddings.\n\nUse a sigmoid to turn dot product into a probability.\n\nP(+|w,c) = 1 / (1 + exp(-c dot w)). \n\nP(-|w,c) = 1 / (1 + exp(c dot w)). \n\nskip-gram learns two separate embeddings for each word i - target embedding w_i and context embedding c_i. Can either add together at end, or just throw away C matrix and represent by w_i. \n\nfasttest is an extension of word2vec, better at dealing with unknown words. \n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n size of context window usually +-1-10 words. Shorter context = more syntactic. High context = topically related but not similar. First order vs. second order occurence defined. Parallel model used by adding vectors to answer question a is to b as a* is to ____. Didn't work super well at first, but then works very well in word2vec. \nb* = argmin distance(x,a* - a + b)\n\nWorks well in some cases, but not in others though in general. Some argue its too simplistic. Embeddings also useful to compute how meanings change over time. \n\n\n## SLP Chapter 6.11 Bias and Embeddings\n Embeddings represent implicit bias that was embedded in texts too. Leads to allocation harm. Bias amplification actually occurs in vectors. Also demonstrate implicit associations, even bad ones, such as associating more negative words with African-American names. Causes representational harm - system demeans or ignores social groups. Can also use this in a historical context to see historical biases. \n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n Extrinsic evaluation on tasks is most important metric. However, also useful to have intrinsic evaluations. Most common metric here is to test performance on similarity (correlation between algorithm's word similarty scores and a gold-standard assigned by humans). WordSim-353 a common tool used for this. SimLex-999 more difficult dataset. TOEFL has 80 questions, asks to choose most similar word from options. Also programs to compare context, not just similarity. Analogy tasks as well are used, like those described above.\n\nImportant: Can suffer from variability. Very important to train multiple embeddings with bootsrap sampling and average the results. \n\n\n## Module 14 Lecture Notes\nNotes cover same things as readings. When studying, go through and write down the equations on handwritten notes sheet\n\nAdded:\n\nBenefits of log probabilities: avoids underflow from using small numbers, sometimes easier to optimize over sums than products.\n\nMarkov models staionary because distribution of X_t after sufficiently long time that distribution of X_t doesn't change any more. It is not because probs are invariant with respect to shifts in data.\n\nIMPORTANT: Cross-entropy is an upper bound on entropy. The more accurate a model, the lower the cross-entropy.\n\nVector representation using term-document matrices and word-word matrices can't account for polysemy.\n\nn-gram model for a corpus with vocab size V and total T tokens would have run time depending on n and T.\n\nPurpose of Laplace smoothing is to account for unseen words.\n\nWhen generating random text, given a context C, n-gram model can't generate next token T if model never saw the context-token pair (C,T) during training. \n\n\n## Module 14 Definitions\n* **Elman networds / simple recurrent networks** - RNN (simple version). Activation value of hidden layer depends on current input and activation val of previous time step\n* **Backprogation through time** - 2-pass backpropagation algorithm to deal with temporal nature of algorithm. Described in 9_2 above.\n* **Teacher forcing** - Always give model correct history sequence to predict next word, rather than bets case from previous time step\n* **Weight tying** - Uses a single set of embeddings at input and softmax layers. How to do it described in 9_3 above\n* **Distributional hypothesis** - Link between similarity in word distribution and similarity in their meaning\n* **Vector semantics** - learn representation of meaning of words (embeddings) directly from text distribution\n* **Representation learning** - Automaticalyl learn useful represenations - self-supervised\n* **Lexical semantics** - Word meaning\n* **Lemma** - Basically the most basic form (mouse for mice)\n* **Word sense** - The aspect of the meaning of a word (Mouse has rodent or cursor as word senses)\n* **Polysemous** - multiple word senses\n* **Synonym** - Substitutable in a sentence without changing the truth of the sentence\n* **Principle of contrast** - Difference in form of word always connotates a different meaning (h20 vs water)\n* **Relatedness** - Coffee and cup\n* **Semantics field** - Hospital - doctors, medical, etc.\n* **Semantic frame** - Set of words that denote a perspective or participants - buying and selling\n* **Connotations** - affective meaning, word's meaning changes with writer/readers emotions, opinions, etc. \n* **Sentiment** - Positive or negative evaluation (measured by valence (pleasentess), arousal (intensity), and dominance (control)\n* **Term-document matrix** - Each row represents word in vocabulary, each colum represents a document\n* **Vector space model** - Document as a count vector if using term-document matrix model\n* **Information retrieval** - task of finding document d from the D documents that best match query q\n* **Term-term matrix** - Both columns/rows words. Usually, how many times column word occurs in +-4 windown of row word\n* **First order occurence** - Syntagmatic association - typically near each other\n* **Second order occurence** - Paradigmatic association - similar neighbors\n* **Allocational harm** - System allocates resources unfairly (father -> doctor, mother -> nurse)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "b2e938fb-29a8-40e1-e2a2-310dccf09e17"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Transition model for an agent written as P(s'|s, a), meaning the probability that action 'a' in state 's' reaches state s' Decision theory deals with choosing among actions based on the desirability of their immediate outcomes. The MEU principle formalizes that an agent should do the right thing, but doesn't operationalize the advice. If agent acts to maximize a correct utility function, then agent will achieve highest possible average performance score. Utility function applies to very next state, so it can be used to guide actions step by step.\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 The constraints for this section are covered in definitions. These are used to address the issue that utility theory needs to understand how preferences between complex lotteries are related to preverences between the underlying states of those lotteries. Rational preferences lead to utility. A utility function is proven to exist for an agent, but is not necessarily unique. \n\n\n## AIMA Chapter 16.3 Utility Functions\n No absolute scale for utilities, but useful to get some scale for a problem. Established by fixing utilities of any two outcomes. Given max/min utility, can assess utility of any prize S by having agent choose between S and standard lottery, adjusting p until agent is indifferent between S and the standard lottery. A micromort can be used to put a value on life itself. Utility is not proportional to monetary value. \n\nRational way to choose best action, a*, is to maximize expected utility. Real outcomes will usually be much worse than esteimated, even if estimate is unbiased. Leads to optimizers curse (defined). Difference between normative and descriptive theory illustrated in humans choosing money with probablities (Allais paradox). Many effects lead humans to choose non-rational choices, like the certainty effect, framing effect, ambiguity aversion, and anchoring effect.\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n In a sequential decision problem, utility functoin depends on the environment history rather than a single state. For every transition from s to s' via a, agent is given a reward bounded by +-Rmax. MDPs consist of set of states with initial state, set of actions for each state, transition model, and reward function. Solutions typically use dynamic programming. Solutions are called policy. If R is very negative, will take shortest path out if even leaving into a bad state. If R slightly negative, optimal policy takes no risks at all. If R > 0, life good, avoids both exits. \n\nPolicies for infinite horizenor simpler, as optimal policy is stationary. If discount factor gamma is close to 0, rewards in distant future seen as insignificant, whereas if close to 1, agent will wait for long term rewards. If discount = 1, then its just a purely additive model. Assume that agent's preferences between state sequences are stationary. I.e. if you prefer one future to another starting tomorrow, then you should still prefer that future if it were starting today. In infinite sequence, can compare using average reward per time step. If using discounted utilities with infinite horizons, optimal policy is independent of starting state. \nThe utility of a state is the expected reward for the next transition plus the discounted utility of the next state if agent chooses optimal action. Solutions to Bellman equation are unique. Interesting: In Tetris, if every policy is optimal, board will still eventually fill.\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value iteration, policy iteration, and linear programming all give exact solutions offline. Monte Carlo planning gives online approximate solutions. Bellman equation basis for value iteration algorithm to solve MDP. Gives unique solutoins that correspond to optimal policy. Can think of value iteration as propagating information through the state space by local updates. The Bellman update is a contraction by a factor of gamma on space of utility vectors. Can calculate when it converges. Agent really actually cares about how well it will do if it acts according to utility function.\n\nPolicy Iteration: iterates the following two steps - 1. Policy evaluation, given a policy pi_i, calculate U_i = U_pi_i, the utility of each state if pi_i were to be executed. 2. Policy improvement, calculate a new MEU policy pi_i+1 using one-step look-ahead based on U_i. Policy iteration terminates when step 2 makes no more changes to the utilities. For small state spaces, policy evaluation using exact solution methods is the generally most efficient. Large state spaces can use an approximation version. Don't necessarily have to update all values at once, can choose a subset, allowing for much more efficient algorithms. \n\nLinear Programming: Consider as variables in LP the utilities U(s) of each state s. LP solvers seldom as efficient as dynamic programming for MDP\n\nReal-time dynamic programming useful in moderate-sized domains such as grid worlds. \n\n\n## Module 8 Lecture Notes\n Convergence: how do we know Vk vectors going to converge? Case 1: If tree has maximum depth M, then V_m holds the actual untruncated values. \nCase 2: If the discount is less than 1: \n\n- Sketch: for any state V_k and V_(k+1) can be viewed as depth k+1 expectimax results in nearly identical search trees\n\n- The difference is that on the bottom layer, V_(k+1) has actual rewards while V_k has zeros\n\n- That last layer is at best all R_MAX\n\n- It is at worst R_MIN\n\n- Everything discounted by gamma^k that far out\n\n- V_k and V_(k+1) are at most gamma^k max|R| different\n\n- as k increases, the values converge\n\n______\n\nActions are easier to select from Q-values than values. \n\nProblems with Value Iteration: 1. It's slow O(S^2 * A) per iteration. 2. The \"max at each state rarely changes. 3. The policy often converges long before the values. \n\nPolicy iteration converges much faster under some conditions\n\nSummary: Value Iteration: - Every iteration updates both values and (implicitely) the policy. We don't track the policy, but taking the max over actions implicitely recomputes it. Policy Iteration: - Do several passes that update utilities with fixed policy (each pass fast because we consider only one action, not all). - After the policy is evalutated, a new policy is chosen (slow like a value iteration pass). New policy will be better (or we're done). Policy iteration converges in fewer iterations but has higher time cost per iteration O(S^3).\n\nBoth are Dynamic programs for solving MDPs\n\nA proper policy does NOT always exist for an MDP\n\nUtility function estimate does not have to be completely accurate to get an optimal policy\n\n\n## Module 8 Definitions\n* **Utility function** - assigns single number to express desirability of a state\n* **Expected utility** - The average utility value of outcomes, weighted by probability that that outcome occurs\n* **Maximum expected utility (meu)** - A rational agent should choose the action that maximizes the agent's expected utility\n* **Lottery** - The set of outcomes for each action; can think of each action as a ticket\n* **Orderability** - Exactly one of (A≻B),(B≻A), or (A~B) holds\n* **Transitivity** - (A≻B)∧(B≻A)⇒(A≻C)\n* **Continuity** - A≻B≻C⇒∃p[p,A;1-p,C]~B. If B between A,C preference, then prob p s.t. agent indifferent between B guarenteed and lottery that yields A\n* **Substitutability** - A\\~B⇒[p,A;1-p,C]\\~[p,B;1-p,C]. Agent indifferent b.t. A/B, then indifferent b.t. when B substituted for A\n* **Monotonicity** - A≻B⇒(p>q⇔[p,A;1-p,B]≻[q,A;1-q,B]). If prefers A over B, then must prefer lottery with higher prob for A\n* **Decomposability** - [p,A;1-p,[q,B;1-q,C]]~[p,A;(1-p)q,B;(1-p)(1-q),C]. Compound probabilities can be reduced to simpler ones (no fun in gambling)\n* **Value function/ordinal utility function** - agent needs only a preference ranking on the states, therefore the numbers don't matter\n* **Preference elicitation** - presenting choices to the human and observing to get utility function\n* **Standard lottery** - [p, u_max; (1-p), u_min]\n* **Micromort** - currency measuring the value of human life, one in a million chance of death\n* **Qaly** - Quality-adjusted life year, such as living 2 years in bad health vs. 1 year in good health\n* **Monotonic preference** - If money, agent prefers more money to less. Does not mean money behaves as utility function\n* **Risk-averse** - Prefer sur thing with payoff that is less than the expected monetary value involved in a gamble\n* **Certainty equivalent** - value an agent accepts in place of lottery\n* **Insurance premium** - The difference between EMV of lottery and its certainty equivalent\n* **Risk-neutral** - linear curve for agent\n* **Optimizers curse** - tendency for estimated expected utility of best coice to be too high\n* **Normative theory** - Describes how rational agent should act (as in decision theory)\n* **Descriptive theory** - Describes how actual agents really do act (like humans)\n* **Certainty effect** - People will make 'illogical' choices because they are much more attracted to certain gains.\n* **Ambiguity aversion** - People dislike ambiguity\n* **Framing effect** - How a question is asked influences the answer\n* **Anchoring effect** - 200 dollar wine presented first, 50 looks like a good deal now\n* **Markovian** - probability of reaching s' froms depends only on s, not history\n* **Markovian decision process** - Sequential decision problem for fuly observable, stochastic environment with Markovian transition model and additive rewards\n* **Policy** - A solution that specifies what agent should do for any state the agent could reach\n* **Finite horizen** - fixed time N that game must end by\n* **Nonstationary** - a policy that depends on time\n* **Additive discount rewards** - Sicount factor gamma applied to reward history when adding\n* **Proper policy** - A policy that is guaranteed to reach a termical state\n* **Bellman equation** - U(s) = max_a[sum_over_s']P(s'|s,a)[R(s,a,s') + gamma*U(s')]\n* **Q-function/action-utility function** - U(s) = max_a[Q(s,a)]. Expected utility of taking a given action in a given state\n* **Shaping theorem** - Following translation leaves optimal policy unchanged: R'(s,a,s') = R(s,a,s') + gamma*Theta(s') - Theta(s)\n* **Potential** - Theta(s). Gradient is gamma*Theta(s') - Theta(s)\n* **Dynamic decision networks** - factored representations of terminology in Chapter 2\n* **Value iteration** - Uses Bellman equation to update the utility value for state S at i'th iteration, applied to all states simultaneously\n* **Contraction** - Function of one argument, when applied to 2 inputs, produces 2 outputs closer together. Basis for value iteration convergence\n* **Max norm** - Measures length of vector by absolute value of biggest component. ||U|| = max_s|U(s)|\n* **Policy loss** - most the agent can lose by executing pi_i instead of optimal policy pi_star. pi_i optimal before U_i converged\n* **Modified policy iteration** - Made simpler to use on large spaces to give approximation of best policy\n* **Asynchronous policy iteration** - Can update utility or policy for any subset of states\n* **Linear programming** - Consider as variables in the LP the utilities U(s) of each state s\n* **Real-time dynamic programming** - Explored states constitute a sub-MDP of main MDP, which can be solved using a previous algorithm\n* **N-armed bandit** - bandit (slot machine) with n levers. Each lever has fixed and unknown prob dist. of winning\n* **Exploitation** - keep using current lever that's been giving best output. Opposite of 'exploration'\n* **Bandit problem** - Each arm M_i is Markov reward process. Overall bandit problem is an MDP.\n* **Markov reward process** - an MDP with only one possible action\n* **Gittens index** - Provides for simple policy, pull arm with highest Gittens index, then update Gittens indices\n* **Restart mdp** - Replace the choice to get infinite sequence of gamma-rewards with choice to back and restart M from initial state\n* **Bernoulli bandit** - Simple. Each arem M_i produces reward of 0 or 1 with unknown probablity\n* **Thompson sampling** - Choose arm randomly according to the probability that it is the most optimal\n* **Selection problems** - Similar to bandit, but different mathematically. No index function exists\n* **Bandit superprocess (bsp)** - each arm is a full Markov decision process, rather than Markov reward with only one action. Like multitasking\n* **Opportunity cost** - Useful to solve BSPs. How much utility is given up per time step by not using another arm\n* **Dominating policy** - An optimal policy can be applied, converting an arm into a Markov reward process\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Bandit problem good formal model for many real life problems. Key aspects are that arms are independent. Gittens index can be calcluated to provide a simple optimal policy: pull lever with highest Gittens index, then update gittens indeces. O(n) for initial indices, O(1) for each decision after. When calculating Gittens index, its essentially at tipping point of choosing arm M and choosing fixed arm M_lambda (i.e. value of choosing M is same as value of choosing infinite sequence of lambda-rewards) In Bernoulli bandit problem, arms with higher payoff probablities preferred, but an exploration bonus exists for arms only tried a few times so far. \n\nMany \"nearly as good\" solutions exist. First class uses upper confidence bound. Choose arm with highest upper bound of confidence. Another method Thompson chooses arm randomly based on probablity that that arm is the optimal once. Regret grows as O(logN). \n\nTask of choosing best option under similar conditions called Selection Problem. Similar to bandit but different mathematically: i.e., no index function exists for selection problems. \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n Goal in reinforcement learning is same as goal in Markoc Decision Processes, to maximize the expected sum of rewards. Difference is agent is not given an MDP to solve, it is in the MDP. Two types of reinforcement learning. \n\n1. Model-based. Uses a transition model to intreprety and make decisions. Model may be unkown or known. Generally learn a utility function U(s). \n\n2. Model-free reinforcement learning: two varieties: 2a) Action-utility learning - Q-learning, where Q denotes sum of rewards from state s onward if 'a' taken. 2b) Policy search - agent learns policy pi(s) that maps directly from states to actions. \n\nCan use passive reinforcement learning or active reinforcement learning (both defined below). \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Difference between policty evaluation and passive learning is that in passive learning, the agent doesn't know the transition model P(s'|s,a), nor the reward function R(s,a,s'). Passive learning agent must complete trials, then calculates direct utility estimation, where each trial provides a sample o this quantity for each state visited. In infinitely many trials, sample average will converge to true expectation for each state. Reduces to standard supervised learning problem where each example is a (state, reward-to-go) pair. This however ignores that the utility of a state is determined by the reward and the expected utility of the successor states. Direct learning misses opportunity for learning by ignoring connection between states. Converges very slowly because of this. \n\nAdaptive dynamic programming learns transition models connecting states and solves Marov decision processes using dynamic programming. Plugs in the learned transition model. Can also adopt approach of modified policy iteration to update utility estimates after each change in learned model. ADP agent limited only by its ability to laern the transition model. \n\nTemporal difference (TD) learning: Adjusts utility estimates toward the ideal equilibriumj that holds locally when the utility estimates are correct using a learning rate parameter. TD does not need a transition model to perform its updates! Environment itself supplies cnnection between neighboring states in form of observed transitions. Key difference between ADP and TD: TD adjusts a state to agree with observed successor, while ADP adjusts state to agree with all successors that might occur, weighted by their probs. Also, while TD makes adjustment per observed transition, ADP makes as many as it needs to restore consistency between utility estimates U and transition model P. TD basically first approximation of ADP. Approximate ADP can learn roughly as fast as full ADP using strategies such as prioritized sweeping heuristics. \n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Ative learning agent must decide what actions to take. Can be greedy, where it learns a path quickly and sticks to it, foregoing exploration, but rarely is an optimal solution. Non-optimal because the learned environment is not the same as the true environment. Can use GLIE scheme to eventually get the true environment. With f(u,n), actions that lead toward unexplored regions are weighted more highly, rather than just actions themselves that are unfamiliar. \n\nThree mathematical approaches that favor choosing a policy that works resasonably well for a whole of models reasonably accurate - Bayesian reinforcement learning, robust control theory, and (maybe?) Temporal-difference Q-learning. Bayesian essentially becomes an exploratin POMDP. Robust control theory basically has a set of possible models and solves for the bets outcome in the worst-case scenario. Issue is that it can become overly conservative. The Q-learning method avoids need of a model by learning action-utility function Q(s,a) rather than usility fucntion U(s). IMPORTANT: A TD Q-learning agent does not need a transtion model, P(s'|s,a) either for learning or for action selection. Difference between Q-learning and SARSA is that Q-learning backs up the Q-value from the best action in s', SARSA waits until action is ataken and backs up Q-value for that action. Q-learning is off-policy, SARSA is on-policy. Q-learning more flexible than SARSA. SARSA more appropriate if overall policy is even partly controlled by other agents or programs, where it's better to learn a Q-function for what will actually happen.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Convergence too slow on many real world problems. Must use function approximation, such as weighted linear features, to approximate. Most importantly, allows agents to generalize from states it has visited to those it hasn't. Changing parameters theta_i after seen a transition changes U_theta for every other state! Features can be arbitrary nonlinear combinations of the state variables. Catastrophic forgetting is a common problem, but can be solved by experience replay (defined below). \n\nDeep RL rarely applied in commercial settings compared to other applications of deep learning. \n\nCan use pseudorewards in sparse reward problems, but has issue that the agent my learn to maximize the pseudorewards rather than the actual rewards. Can use hierarchical reinforcement learning to break long action sequences into smaller chunks that are easier to learn. Hierarchcal learning begins with a partial program that outlines the hierarchical structure for the agent's behaviour. This provides the general know-how of a program, i.e. structural organization for complex behaviours, then learning process just works out details. Utilizes a joint state space. Machine state = current internal state of agent program. Choice state = program counter for 'm' is at choice point in agent program. Hierarchical structure provides natural additive decomposition of the overall utility function.\n\n\n## Module 9 Lecture Notes\n\n\nPassive reinforcement learning: Just execute policy and learn from experience. This is NOT offline planning!\n\nDirect evaluation problems: 1. waste information about state connections, each state must be learned separately, takes a long time to learn\n\nQ-learning converges to optimal policy, even if you're acting suboptimally\n\nRegret: Measure of total mistake cost. Difference between expected rewards and optimal rewards\n\nDirect utility estimation ONLY uses sample transitions\n\nADP and TD both adjust utility of state locally to agree with utility of at least one successor state \n\nQ-learning with linear function approximation will NOT always converge to the optimal policy\n\nA deterministic policy is a mapping from states to actions\n\n\n## Module 9 Definitions\n* **N-armed bandit** - bandit (slot machine) with n levers. Each lever has fixed and unknown prob dist. of winning\n* **Exploitation** - keep using current lever that's been giving best output. Opposite of 'exploration'\n* **Bandit problem** - Each arm M_i is Markov reward process. Overall bandit problem is an MDP.\n* **Markov reward process** - an MDP with only one possible action\n* **Gittens index** - Provides for simple policy, pull arm with highest Gittens index, then update Gittens indices\n* **Restart mdp** - Replace the choice to get infinite sequence of gamma-rewards with choice to back and restart M from initial state\n* **Bernoulli bandit** - Simple. Each arem M_i produces reward of 0 or 1 with unknown probablity\n* **Thompson sampling** - Choose arm randomly according to the probability that it is the most optimal\n* **Selection problems** - Similar to bandit, but different mathematically. No index function exists\n* **Bandit superprocess (bsp)** - each arm is a full Markov decision process, rather than Markov reward with only one action. Like multitasking\n* **Opportunity cost** - Useful to solve BSPs. How much utility is given up per time step by not using another arm\n* **Dominating policy** - An optimal policy can be applied, converting an arm into a Markov reward process\n* **Reinforcement learning** - agent interacts with rold and recieves rewards based on its performance\n* **Sparse rewards** - majority of states don't give the agent a reward signal at all\n* **Model-based reinforcement learning** - Uses a transition model to interpret reward signals and make decisions\n* **Model-free reinforcement learning** - Agent doesn't know transition model. Learns through more direct representation\n* **Action-utility learning** - Q-learning. Q denotes sum of rewards from state s onward if 'a' taken\n* **Policy search** - Keep changing policy as long as performance improves, then stop. Simplest strategy\n* **Passive reinforcement learning** - agent's policy is fixed and task is to learn utilities of states or state-action pairs\n* **Active reinforcement learning** - Agent must figure out what to do\n* **Direct utility estimation** - Utility of state defined as expected total reward from that state onward (expected reward-to-go). Trial=sample\n* **Adaptive dynamic programming** - Learns transition models connecting states and solves Marov decision processes using dynamic programming\n* **Tempral-difference equation** - U_pi(s) <- U_pi(s) _ alpha [R(s,pi(s),s') + gammaxU_pi(s') - U_pi(s)]\n* **Prioritized sweeping heuristic** - used to generate more efficient ADP by adjust states whose likely successors have had large adjusment in utility\n* **Active learning agent** - Agent gets to decide what actions to take\n* **Greedy agent** - Learns a sort-of-optimal policy really fast and sticks to it, foregoing future exploration\n* **Glie** - Greedy in the limit of infinite exploration. Try each action in each state over and over until probabilty optimal action missed is essentialy 0\n* **Exploration function** - f(u,n) determines how greed is traded off against curiosity. Increasing in u, decreasing in n\n* **Absorbing state** - when agent has no actions that have any effect and no rewards\n* **Bayesian reinforcement learning** - Assume prior probability P(h) over hypothese h about the true model. Posterior-prob obtained by Baye's rule\n* **Robust control thoery** - Set of models, solve for best-case scenario for worst-case model. Can be too conservative\n* **Sarsa** - (state,action,reward,state,action). Similar to Q-learning update, but SARSA updates with Q-value of the action a' that is actualy taken\n* **Function approximation** - Process of constructnig a compact approximation of true utility function / Q-function\n* **Widro-hoff rule / delta rule** - an error function and computing its gradient with respect to the parameters\n* **Catastrophic forgetting** - Car example. Drives in center too long, forgets the edges are dangerous\n* **Experience replay** - Relive early crashes often so it doesn't forget\n* **Reward shaping** - helps solve credit assignment by providing an agent with pseudorewards, strat known as reward shaping\n* **Hierarchical reinforcement learning** - Break long action sequences into smaller chunks until they are easy to learn\n* **Joint state space** - Each state (s,m) is composed of physical state and machine state\n* **Additive decomposition** - Can decompose problem, learn smaller utilitys, and add together back to entire problem\n* **Stochastic policy** - probablility of selecting action 'a' in state 's', used in policy search\n* **Coreelated sampling** - Give both programs the same set of hands\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Old way of using belief states and having a plan for everything only works on simple problems. The rational decision depends on both the relative importance of various goals and the likelihood that, and degree, they will be achieved. Real world diagnosis problems almost always have uncertainty. Can't use logic to cope with domains like this (example: diagnosing tooth ache). Fails due to Laziness, Theoretical ignorance, and Practical ignorance, defined below. Theory of prob. summarizes the uncertainty the comes from humans laziness and ignorance, solving qualification problem. Decision theory = probablility theory + utility theory. \n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n Set of all worlds called sample space; mutually exclusive and exhaustive. Probablility model associates each possible with a numerical probability. Events satisfy an assertion. For each proposition, the corresponding worlds in which the proposition holds. Unconditional vs. Conditional probability examples given. A possible world is defined to be an assignment of values to all of the random variables under consideration. De Finetti's theorem implies that no rational agent can have beliefs that violate the axioms of probability. \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Section describes how to calculate probabilities and marginal probabilities given full joint distributions. Already understand very well. Conditional probability given as P(cavity | toothache) = P(cavity AND toothache) / P(toothache). Can use normalization as shortcut or if don't know some values. Full joint distrubution in tabular form seldom a practical tool. \n\n\n## AIMA Chapter 12.4 Independence\n Can decompose large distrubution tables, especially using independence between variables. Independence assertions usually based on knowledge of the domain. Very nice when able to use independence, but generally doesn't work for most real world problems.\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes rule (defined below) underlies most modern AI systems. Can also be written as P(cause|effect) = P(effect | cause)P(cause) / P(effect). P(effect|cause) is the causal direction, and P(cause|effect) is the diagnostic direction. Diagnostic knowledge usually more fragile than causal knowledge. KEY POINT: For n symptoms that are all conditionally independent given Cavity, the size of the representation grows as O(n) instead of O(2^n). Therefore, conditional independence assertions allows probabilistic systems to scale up; also they are more commonly available than absolute independence assertions. \n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n Naive Bayes model is P(cause, Effect_1, Effect_2, .... , Effect_n) = P(Cause)(product_over_i)P(Effect_i)|Cause). Considered Naive because its usually simplifying things, when in reality the effect varaibles are not strictly independent. However, even in this case it works very well. Run time is linear in the number of observed effects and doesn't depend on the number of unobserved effects. Decent at language classification, even though each word specifically isn't independent ('First quarter' example). Widely used for language determination, document retrieval, spam filtering, and other classifications. More sophisticated models should be used in fields like medicine. \n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Uncertainty can arise in the Wumpus world. Good example of how to use the previously discussed theorems to improve choosing a square in to move to in the Wumpus world.\n\n\n## SLP Chapter 3.1 N-Grams\n Intro: Predicting words important for applications like speech recognition, spelling correction, and grammatical error correction. Also useful for AAC (Augmentative and alternative communication) systems (used by people who are unable to speak). n-grams much simpler than state of the art, but demonstrate fundamental concepts.\n\nCh3_1: P(w/h) = probability of a word w given a history h. Method of estimating probs directly from word counts fine, but even web not big enough to have a large enough corpus; senteces are creative. Chain rule gives probability of a word given the previous words (covered in AIMA). Bigram model for P(the|Walden Pond's water is so transparant that) is approximated as P(the|that). n-gram model looks at n - 1 words into the past. Calculating probability of \"I want English food\" given a corpus given. Use log probabilities to avoid too small of numbers, since everything is less than or equal to 1.\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n Best way to evaulate performance of a language model is extrinsic evaluation (Defined below). Generally very expensive, so can be better to use intrinsic evaluation (test set and training set). Whichever model assigns a higher probability to the test set is the better model. Generally divide into 80% training, 10% development, and 10% test. Don't actually use raw probabilities, but perplexity (defined below). Minimizing perplexity is good. Perplexity can also be described as the weighted average branching factor of a language. The higher the 'n' of the n-gram model, the lower the perplexity. Note: Perplexity of two language models only comparable if they use identical vocabularies. Decreasing perplexity in instristic environment doesn't always decrease it in extrinsic test, so good to check extrinsicly too to make sure. \n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Sampling from a language model is to generate some sentences, choosing each sentence according to its likelihood defined by the model. \n\n\n## SLP Chapter 3.4 Generalization and Zeros\n n-grams do a better and better job of modeling the training corpus as we increase the value of N. Statistical models are mostly useless if training and test sets are as different as Shakespeare and the WSJ. Must use similar genre at least for training and test sets. Also issue of sparcity, any corpus could be missing perfectly logical sentences, thus giving the model a 0% chance of thinking they could exist. A sentence that never occurs in the training set but does in the test set is called a 'zero'. OOV rate = percentage of out-of-vocabulary words that appear in the test set. Two ways to fix. 1. Convert unknown words to just <UNK> and treat them as all one word. 2. Build vocabulary implicitely, and just call things with very low word-count as <UNK>. \n\n\n## SLP Chapter 3.5 Smoothing\n Smoothing defined below. Many ways to do this, Laplace, add-k, stupid backoff, and Kneser-Ney (Section 3_6). \n\nLaplace smoothing: Add 1 to all the n-gram counts before normalizing to probabilities. All 0's go to 1's with this. Not very robust, but good concept fundumentally. \n\nAdd-k smoothing: Add even less than 1 to the 0-counts. Can be chosen by optimizing on a devset. Still doesn't work very well for many applications\n\nBackoff and Interpolation: Backoff method is purposely using less context if model hasn't seen (use a bigram instead of a trigram). Interpolation is mixing all the probability estimates from many n-gram estimators (bigram, trigram, etc.). \n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Can prune language models, such as only use words with a count threshold > 40 like Googles does. Stupid back-off is sufficient in many cases, where there's no discounting of higher-order probabilities, you just backoff to a lower-order n-gram if there's a 0-count. \n\n\n## Module 10 Lecture Notes\n\n\nBigram model only considers i{w-1}\n\nIn trigram model, the probabilities of all words w given w{i-1} and w{i-2} add up to 1\n\nEffect of Markov assumption in n-gram models is it makes it possible to estimate the probabilities from data\n\nChain rule: P(x_1,x_2,x_3,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)...P(x_n|x1,...,x_(n-1))\n\nMaximum Likelihood Estimate: P(w_i|w_(i-1)) = count(w_(i-1), w_i) / count(w_(i-1))\n\n\n## Module 10 Definitions\n* **Belief state** - old way: represent all possible states, and have plan for everything\n* **Qualification problem** - Having infinitely many contigency plans (I.e. what if meteor hits the car)\n* **Laziness** - Too much work to think of all exceptions\n* **Theoretical ignorance** - No complete theory for a domain\n* **Practical ignorance** - Would need to many test to run, even if knew of all the rules\n* **Ontological commitments** - World is composed of facts that do or do not hold\n* **Epistemological commitments** - Logical agent believes true/false/no opinion, but probablistic agent believes between 0 and 1\n* **Decision theory** - An agent is rational iff it chooses action that yields highest expected utility, averaged over all outcomes\n* **Sample space** - Set of all possible worlds; mutuallyl exclusive and exhaustive\n* **Probability model** - Associates numerical probability with each possible world\n* **Event** - Sets that satisfy an assertion\n* **Unconditional/prior probabilities** - Degrees of belief in proposition in absence of any other information\n* **Conditional probability** - Evidence already. Prob of rolling eleven total given first die is a 5\n* **Factored representation** - possible world represented by set of variable/value pairs\n* **Random variable** - Variables in probability theory. Function that maps from domain of possible worlds to some range\n* **Probability function** - Probability that a random variable takes on some value x as a parameterized function of x\n* **Joint probability distribution** - Distributions on multiple variables\n* **Inclusion-exclusion principle** - P(a OR b) = P(a) + P(b) - P(a AND b)\n* **Probabilistic inference** - computatin of posterior probabilities for query propositions given evidence\n* **Marginilization/summing out** - sums up the probabilities for each possible value of the other variables\n* **Independence** - P(a|b) = P(a), P(b|a) = p(a), P(a,b) = P(a)P(b)\n* **Bayes' rule** - P(b|a) = P(a|b)P(b) / P(a)\n* **Conditional independence** - P(toothache AND catch | Cavity) = P(toothache | Cavity)P(catch | Cavity)\n* **Separation** - Cavity separates toothace and catch because its a direct cause of both\n* **Language models** - Models that assign probabilities to sequences of words\n* **Bigram model** - P(w_n|w_(1:n-1)) =~ P(w_n) | w_(n-1)\n* **Markov assumption** - Probability that a word depends only on the previous word\n* **Relative frequency** - ratio of observed frequency of a particular sequency to the observed frequency of a prefix\n* **Extrinsic evaluation** - Embed language model in an application and measure how much the application improves\n* **Test set** - The 'held out' data that will be used to test after model used on training set\n* **Development set (devset)** - A test set that is trained on a lot, giving need for a fresh new test set\n* **Perplexity** - The inverse probability of the test set, normalized by number of words. Also, 2^(power of cross-entropy)\n* **Sampling** - Choosing random points from a distribution according to their likelihood\n* **Zeros** - Sentences that occur in the training set but not in the test set\n* **Closed vocabulary** - test set can only contain words from lexicon (no unknowns)\n* **Smoothing/discounting** - Shave off some probability mass from frequent events and give to events we've never seen but know exist\n* **Held-out corpus** - additional training corpus used to set hyperparameters\n* **Katz backoff** - Rely on discounted prob P* if seen this n-gram, otherwise back off to the shorter history (N-1)gram\n* **Stupid back-off** - No discount of higher order n-gram, just back off to a lower order n-gram if count is 0\n* **Entropy** - A measure of information\n* **Cross-entropy** - The upper bound on the entropy\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian networks represent the dependencies among variables. Can represent *any* full joint probability distribution. Has 3 components:\n\n1. each node is a RV (disrete or continuous)\n\n2. Directed edges between nodes. X -> Y means X parent of Y. Is acyclic\n\n3. Node X_i has associated probability information (X_i | Parents(X_i)) that quantifies effect of parents\n\nIntuitive meaning of edge X -> Y is that X has a direct influence on Y. Each row in a conditional probability table must sum to 1 because they represent an exhaustive set for all cases for the variable. Generally, boolean variable with k Boolean parents contains 2^k independently specifiable probabilities. Node with no parents has one row that represents prior probabilities of each possible value of the variable. Bayesian networks allow a small agent to deal with a very large world by simplifying a potentially infinite set of circumstances. \n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Syntax of Bayes net: directed acyclic graph with some local probability info attached to each node. Probability of an event can be calculated by multiplying the Prob(a | parent(a)) for all a. When constructing Bayes net, put in a topological order. NOTE: A Bayesiant network is a correct representation of the domain only if each node is conditionally independent of its other predecessors in the node ordering, given its parents. Construct:\n\n1. order {X1....Xn}, will be more compact if ordered s.t. cause precedes effect\n\n2. choose a minimal set of parents fo Xi from X_1 to X_(i-1). For each parent insert link from parent to Xi.\n\nParents of node Xi should contain all nodes in X1 to X_(i-1) that directly influence Xi. NOTE: Bayes nets should contain no redundant probability values. If no redundancy, no chance for inconsistency. Impossible to create a Bayesian network that violates prob-axioms. \n\nBayes nets much more compact than full distribution. Example of general property locally structured (sparse) systems. Mostly, each random varaible directly influenced by at most k others. Amount of info needed to specify each conditional probability table at most 2^k numbers, and complete network specified by 2^k * n numbers. Contrast: joint dist. has 2^n numbers. \n\n**IMPORTANT**: If stick to causal model, end up having to specify fewer numbers, and numbers easier to come up with. Also, this shows that there can be many Bayesian networks that represent same full distribution, but the bad ones fail to take into account all the conditional independence relationships. \n\nNon-desenceds property: Each variable is conditionally independent of its non-descendants, given its parents. \n\nMarkov blanket: A variable is conditionally independent of all other nodes in network, given its parents, children, and children's parents - that is, given its Markov blanket. \n\nEven if maximum number of parents k is small, stil requires O(2^k) numbers and experience to fill in. Can use a canonical distribution to fill in to make it easier. Some patterns are deterministic nodes and context-specific independence (defined below). Noisy logical relationships thta depent on k parents can be described in O(k) parameters instead of O(2^k) for full conditional probablity table.\n\nDiscretization for continuous variables. Also use something like a Gaussian distribution or nonparametric representation - define the conditional distribution implicitly with collectin of instances, . Special properties of linear-Gaussian: network will have joint distribution that is a multivariate Gaussian distribution over all variables. Posterier distribution given any evidence will also have this property. When discrete varible are added as parents of continuous varaibles, the network defines a conditional Gaussian distribution given any assignment to the discrete variables.\n\nDisc. variables/Cont. parents: Probit better for real situations, but logistic function better mathematically. \n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Best description: Basic task is compute posterior probability distribution for a set of query variables, given an abserved event, whic his usually an assignment of values to a set of evidence variables. A query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network. A naive implementation would have complexity O(n*2^n). Can be reduced to O(2^n) by taking advanteage of nested structure. \n\nEnumeration-ask algorithm runs in O(2^n). Better then naive, but not great. However, can avoid repeated calculations using strats such as variable elimination. Variable elimination sums out variables (right to left) from pointwise products of factors to produce new factors, eventually yielding the solution. \n\nGenerally, time and space requirements of variable elimination dominated by sizze of largest factor constructed during the operation of the algorithm. This itself determined by order of elimination of varaibles and by the structure of network. Intractable to determine optimal ordering. Some heuristics, like greedy one: eliminate whichever variable minimizes the size of the next factor to be constructed. Also, can remove any leaf node that is not a query or evidence variable. NOTE: every variable that is not an ancestor of a query variable or evidence variable is irrelivent to the query. \n\nTime and space complexity linear in size of network in singly connecrted/poly trees. Multiply connected can have exponential time and space complexity, even if number of parents per node bounded. NOTE: inference in Bayes nets is NP-hard bc it includes inference in propositional logic as a special case. Can use Bayes net inference to solve 3-SAT problems (can reduce satisfiability problems to Bayes net inference problems). Bayes net #P-hard (strictly harder than NP-complete). Tree width can be used to bound complexity of Bayes nets. Can slo reduce Bayes net inference to satisfibility (weighted model counting). Bayes net inference is competitive with and someties superior to exact algorithms on networks with large tree width. \n\nIf computing posterior probs for all variables, can use clustering to reduce time complexity from O(n^2) to O(n). Idea: Join nodes to form a cluster of nodes, resulting tree is polytree. meganodes share one variable. \n\n## Module 11 Lecture Notes\n GO OVER NOTES. Write down Active / Inactive paths on sheet and make sure can do example problems in notes!!!\n\nThe conditional prob dist. of a variable in a Baysian network should be specified based on the prob dist. of all of the other variables is FALSE. JUST NEED THE PARENTS!\n\nEvery variable in a Bayes net is independent of all its descendets given its children\n\nLocally structures (sparse) systems grow linearly in complexity.\n\nMore than one Bayesian network can be used to represent same join distribution\n\nIf two variables X and Y in Bayesian network don't share a path, then X and Y are conditionally independent\n\n\n## Module 11 Definitions\n* **Bayesin network** - Directed graph that represents dependencies among variables\n* **Topological order** - any order consistent with directed graph structure\n* **Locally structured / sparse** - Each subcomponent interacts directly with only bounded number of other components (linear growth now)\n* **Markov blanket** - parents, children, and children's parents for a single variable\n* **Canonical distribution** - A standard pattern to fill in relationship between parent and child\n* **Deterministic node** - A node with its value specified exactly by the values of its parents, with no uncertainty\n* **Context-specific independence** - Exhibits CSI if variable is conditionally independent of some of its parents given certain values of others\n* **Noisy-or** - Generalization of the logical OR. Fever true iff Cold, Flu, or Malaria true.\n* **Leak node** - Covers miscallaneous causes\n* **Discretization** - dividing up values for continuous variables into fixed intervals\n* **Hybrid bayesian network** - A netweork with both discrete and continuous variables\n* **Linear-gaussian** - child has Gaussian distribgution whose mean varies linearly with value of parent and whose s.d is fixed\n* **Hidden variables** - neither input nor output, but needed to structure network so its reasonably sparse\n* **Variable elmination** - Versin of dynamic programming to eliminate repeated calculations. Simplest\n* **Singly connected/polytrees** - At most one undirected path between any 2 nodes. T()/S() linear in size of network\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Each component of an agent can be improved by machine learning. This chapter assumes little prior knowledge, though another chapter focues on transfer learning. Induction, unlike deduction, not guarenteed to be correct. Input is factored representation (vector of attribute values), can be atomic or relational. Can be either classification or regression problems. Can be supervised learning, unsupervised learning, or reinforcement learning (defined below). \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Given a traning set, determine a model/hypothesis h that approximates true fuction f(x). Can't get consistent hypothesis with continuous function, so try to get bets-fit function. 'h' generalizes well if it accurately predicts the outputs of the test set. Must take into account the bias-variance tradeoff (complex, low-bias h that fits training data well and simpler, or low-variance h that generalizes better). There is a trade-off between the expressiveness of a hypothesis space and the computational complexity of finding a good hypothesis within that space. Most machine learning focuses on simple representations. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Boolean classification, mapping to either false or true. Want to find the smallest possible decision tree to represent a problem. Intractable to find the absolute smallest, but can get close with heuristics. A tree consists of tests on attributes in interior node, value of attribute on branches, and output value of leaf nodes. The learning algorithm looks at examples, not the correct function. Learning curves also known as Happy Graphs. Information gain from attribute test on 'A' is the expected reduction in entropy. Use decision tree pruning to combat overfitting. Prune irrelevent attributes by turning them into leaves. Use significance tests to see if an attribute is relevant or not. Pruned trees perform much better than unpruned when there's large amounts of noise. Early stopping would miss crutial situations where there's no one good attribute, but they lead to good attributes. Information gain ratio can be used to avoid splitting into lots of single-example subtrees. Equality tests also work. Need regression tree when output is continous. Decision trees are unstable: adding one new example can change the test at the root, changing whole tree. \n\n\n## AIMA Chapter 5.5 Stochastic Games\n Use stationary assumption, (future like past). Assume events are independent and identically distributed. Optimal fit minimizes error rate. Create training and test sets. Could try different thresholds, etc. by tuning hyperparameters. However, to truly tune hyperparametrs, should have a training set, validation set (devset), and test set. Can use k-fold cross-validation to squeeze more sets out of the data. Model selection chooses a good hypothesis space, and optimization finds the best hypothesis within that space. Strategies that when validation set error decreases, capacity increases = deep neural networks, kernel machines, random forests, boosted ensembles. In machine learning, typically look to minimze a loss function. Example of there's more loss when classifying a real email as spam than vise versa. Four reasons why h\\* may differ from true function: unrealizability, variance, noise, computational complexity. Noise cannot be predicted, only characterized. \n\nCan also work to minimize weighted sum of emperical loss and the complexity of the hypothesis, called the total cost. Feature selection can be used to discard attributes in addition to regularization.  Could also measure emperical loss and complexity on the same scale using minimum description length (minimize bits). \n\nCan tune hyperparameters through hand-tuning (manual). Could use grid search or random sampling. Could choose Bayesian optimization or population-based training to tune hyperparameters.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Computational learning theory lies in middle of AI, statistics, and theoretical computer science. Principle: any theory that is wrong will be found out after just a few examples. If a hypothesis consistent with large set of training examples, then must be \"probably appriximately correct\" (PAC). Use a small constant, ensure hypothesis error rate is is less than or equal to this. \n\nThree ways to restrict hypothesis space: 1. Bring prior knowledge. 2. Insist algorithm returns simple hypothesis. 3. Focus on learnable subsets of entire hypothesis space.\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Univariate linear regression is fitting with a straight line. Can use gradient descent rather than solving for zeroes. Can use batch gradient descent or stochastic gradient descent to train on multiple training examples. Could also take advantage of parallel vector operations with some CPU's, making 'm' itself a hyperparameter. Convergence of stochastic gradient descent NOT guarenteed. SGD good in online setting where data coming in one at a time, (also known as online gradient descent for this reason). \nMultivariable linear regression - each example x_j is an n-element vector. Multivariable not much more complicated than linear regression. Univariate don't have to worry about overfitting, but you do in multivariable. Therefore, use regularization on multivariable linear functions. L_1 regularization produces a sparse model. \n\nA decision boundary separates two classes. Use a linear separateor for linearly separable data. Typically, learning rule applied one example at a time. Perceptron rule may not converge to a stable solution for fixed learning rate alpha, but if alpha decased as O(1/t) where t is the iteration number, then rule can converge to a minimum error solution when samples presented in random sequence. This is NP-hard. \n\nCan resolve many issues by softening the threshold function, making things likely zero or likely 1, instead of straight 0 or 1. Process of fitting weights on this is called logistic regression. No easy close-form solution for optimal w, but gradient descent strategy straightfoward. Logistic regression converges much faster and better on data that is not linearly separable (though does converge slower on data that is linearly separable). \n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Intro: Classification is heart of both human and machine intelligence. One task of text categorization is sentiment analysis. Spam detection another. Language id usually first step in most language processing pipelines. Rules can be fragile, as data/situations change over time. Most cases done via supervised machine learning. Generative classifiers (naive Bayes), build model of how a class could generate some input data. Given observation, returns class most likely to have generated the observation. Discriminative classifiers (logistic regression) learn what features from the input are most useful to discriminate between different possible classes. \n\nCh4_1: Naive Bayes generative model because first a class is sampled from P(c), then word generated by sampling from P(d|c). Naive Bayes assumpion gives the conditional independence assumption that probs P(f_i|c) are independent given 'c'. Naive Bayes and logistic regression called linear classifiers. \n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Simplest solution is add-one (Laplace) smoothing. Some systems ignore stop words (the, a). \n\n\n## SLP Chapter 4.3 Worked Example\n Worked example, go over before test.\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Binary multinomial naive bays clips words count at 1. Put prefix NOT_ next to every word after a token of logical negation. Can use sentiment lexicons with words prelabeled as positive or negative. Add a feature that is counted each time a word from that lexicon is used. positive lexicon count vs. negative lexicon count. If data is sparse, use dense lexicon features instead of sparse individual-word features to generalize better.\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Features in naive Baye can express any property of the input text we want. Spame - phrases. language ID - character n-grams. \n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Naive Bayes can be viewed as a set of class-specific unigram language models, in which model for each class instantiates a unigram language model. \n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Build a confusion matrix. \n\nPrecision = tp / (tp + fp). Measures % of items that system detected as positive that are actually positive\n\nRecall = tp / (tp + fn). Measures % of items actually present in the input that were correctly identified by the system\n\nAccuracy = (tp + tn) / (tp + fp + tn + fn)\n\nTop left: True Positive. Top right: False positive. Bottem Left: False negative. Bottom right: True negative.\n\nF-measure: F_B = (B^2 + 1)PR / (B^2 * P + R). Single metric that incorporates both precision and recall.\n\nMacroaveraging can be used when more than 2 classes (compute performance for each class, then average over classes).  Can also use microaveraging (collect decisions for all classes into a single confusion matrix, then compute precision and recall from that table). Microaverage dominated by more frequent class, since counts pooled. Macroaverage reflects better the statistics of smaller classes, and is therefore better when performance on all classes equally important.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Use training set to train model, use devset to tune parameters, run on test set for performance measures. Can use cross-validation to get \"more\" data. Partition data into k disjoint subsets called folds. Train on k-1 folds, compute error rate on test set. Do sampling process k times and then average error rates. Do this inside the training set, then test on test set normally. \n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n Statistical significance used to compare two different models to see which is better. Effect size: Bigger Delta(x) means A way better than B, small delta means A only a little better than B. Delta(x) = M(A,x)  - M(B,x). Use null hypothesis (Delta(x) <= 0). Like to know if we can confidently rule out this hypothesis. Small p-value means that difference observed is very unlikely under the null hypothesis, and can reject null hypothesis. Small is 0.05 or 0.01 typically. A is better than B is statistically significant if the delta seen has prob below the threshold and therefore can reject this null hypothesis. In NLP, use non-parametric tests based on sampling to determine p-value. Most common are approximate randomization and bootstrap test. Paired tests: Those that compare two sets of observations that are aligned. \n\nBootstrap test can be applied to precision, recall, F1, BLEU (any metric). Bootstrapping is repeatedly drawing smaller smaples with replacement from an original larger sample. Can create many virtual test sets doing this. \n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Important to avoid harms in classification. Representational harms - system demeans a social group. Toxicity detection detects abuse, but can itself cause harm. ML replicate or even amplify biases in the training data. Problems can also be caused by the human labelers, resources used, or by the model architecture. Can use a model card to document information like algorithms/parameters, preprocessing, intended use, performance across different demographics, etc. \n\n\n## Module 12 Lecture Notes\n\nMistakes bound: maximum number of mistakes related to the margin or degree of separability. Mistakes < k/(sigma^2). \n\nProblems with perceptron: Noise - if data isn't separable, weights might thrash, averaging weight vectors over time can help. Mediocre generalization - finds a \"barely\" separable solution. Overtraining - test / held-out accuracy usually rises, then falls. \n\nFixing Perceptron: adjust weight updtae to mitigate effects (MIRA). Using maximum step size usually converges faaster and is better on noisy data. \n\nNaive Bayes naive b/c assumes features are conditionally independent of each other\n\nJoint prob model P(X1, X2, X3, Y) for data using Naive bayes assumption is P(Y)P(X1|y)P(X2|Y)P(X3|Y)\n\nPerceptron - training is error-driven, weights only updated when predicted label incorrect\n\nCircle example, can separate two classes by using feature augmentation\n\nPerceptron not guarenteed to converge if data not linearly separable\n\nInference procedure for perceptron describes as: compute a weighted sum, then apply a threshold\n\n\n## Module 12 Definitions\n* **Induction** - Going from specific set of observatins to a general rule\n* **Classification** - Output is set of finite values (cloudy,sunny, etc.)\n* **Regression** - When output is a number (temperature, etc.)\n* **Supervised learning** - Observe input/ouput, create function mapping input to output\n* **Unsupervised learing** - Learns input patterns with no feedback on output (clustering)\n* **Reinforcement learning** - Learns from series of rewards / punishments\n* **Hypothesis** - y=f(x). Discover 'h' that approximates true fucntion of f. Drawn from hypothesis space\n* **Ground truth** - The output y_i, the true answer we are asking model to predict\n* **Consistent hypothesis** - h s.t. each s_i in training set has h(x_i) = y_i.\n* **Bias** - Tendency of predicitive hypothesis to deviate form expected values\n* **Underfit** - Failure to find a pattern in data\n* **Variance** - Amount of change in hypothesis just due to fluctuation in training data\n* **Overfit** - Model pays too much attention to the exact data in the training set\n* **Ockham's razor** - plurality of entities should not be posited without necessity (shave off dubious explanations)\n* **Decision tree** - Maps a vector of attriute value sto an output value\n* **Entropy** - Fundamental quantity in information theory\n* **Significance test** - Assume no underlying pattern. If degree of deviation statistically unlikely, then good evidence for presence of pattern in data\n* **Early stopping** - Stop generating tree if no good attribute detected. Bad practice, could miss good attributes further down\n* **Split point test** - Inequality test on value of an attribute. Most expensive part of algorithm application\n* **Cart** - Classification and Regression Trees\n* **Stationary assumption** - Assume all future examples will be like the past\n* **Iid** - Independent and identically distrubuted (stationary Ej's)\n* **Hyperparameters** - Parameters of the model class, not individual model\n* **K-fold cross-validation** - Split data into k equal subsets, perform k rounds of learning, on each round 1/k data held out\n* **Leave-one-out cross-validation** - LOOCV - k = n k-fold cross-validation\n* **Interpolated** - A model that exactly fits the data\n* **Realizable** - Hypothesis space H actually contains true function f\n* **Regularization** - Penalizing complex hypotheses\n* **Minimum description length** - Minimize total number of bits required\n* **Grid search** - Try all combinations for hypermarametes (works when few and discrete)\n* **Random sampling** - Random choosing from uniform distribution. Good for continuous variables\n* **Bayesian optimization** - Task of choosing hypermarameter values an ML problem itself\n* **Population-based training** - Alternative to Bayesian (above). Train parallely population of models. Do again, slightly based on previous results and slightly on randomness\n* **Sample complexity** - Number of required examples, as a function of epsilon (error) and delta\n* **Weight space** - Space defined by all possible settings of the weights\n* **Gradient descent** - Compute estimate of gradient and move smallamount in steepest downhill direction until converge on local minimum loss\n* **Learning rate** - Parameter alpha in gradient descent\n* **Batch gradient descent** - Also called deterministic gradient descent. For N training samples. Convergence to global minima guarenteed\n* **Stochastic gradient descent** - Faster version of above. Randomly selects small number of training examples, rather than 1 at a time\n* **Multivariable linear regression** - each example x_j is an n-element vector\n* **Sparse model** - Sets many weights to zero - simpler model\n* **Decision boundary** - Separates two classes\n* **Threshhold function** - Defines class separation\n* **Perceptron learning rule** - The update rule for linear regression\n* **Sentiment analysis** - The extraction of a sentiment - positve or negative orientation expressed by writer\n* **Binary multinomial naive bayes (binary nb)** - Clip word counts in each document at 1. (Preference whether a word occurs, not how many times)\n* **Gold labels** - The human-made labels\n* **Precision** - tp / (tp + fp). Measures % of items that system detected as positive that are actually positive\n* **Recall** - tp / (tp + fn). Measures % of items actually present in the input that were correctly identified by the system\n* **Accuracy** - (tp + tn) / (tp + fp + tn + fn)\n* **F-measure** - F_B = (B^2 + 1)PR / (B^2 * P + R). Single metric that incorporates both precision and recall\n* **Macroaveraging** - Compute performance for each class, then average over classes\n* **Microaverageing** - collect decisions for all classes into a single confusion matrix, then compute precision and recall from that table\n* **P-value** - The probability, assuming null hypothesis H_0 is true, of seeing the delta(x) that we saw or one even greater. \n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Intro: Logistic regression suited very well to link between features and some particular outcome. It is the baseline algorithm both for classifiers, and for neural networks. Important difference between Naive Bayes and logistic regression: Logistic regression is a discriminative classifier (only tries to know enough to discriminate between dogs and cats),  Naive Bayes is a generative classifier (understand what dogs and cats look like). Generative model uses the likelihood term  of what came before it (P(d|c) * P(c)). Discriminative tries to directly compute P(c|d). It could discriminate between possible  classes, but couldn't generate an example of one of the classes. Components of probabilistic ML classifier: 1. Feature representation  2. Classification function. 3. Objective function for learning. 4. Algorithm for optimizing objective function. \n\nCh5_1: Sigmoid classifier helps binary logistic regression make a decision about class of a new input observation. Logistic regression learns a set of weights and bias terms. Weights represent how important the feature is. Classifier multiplies each x_i by each w_i, sums up, and adds the bias term b. Sigmoid function also called the logistic function [1 / (1 + e^(-z))]. Sigmoid function advantages: Takes real-valued number and maps into [0,1] (good for probability). It squashes outlier variables, and is differentiable. Decision boundary, for example, could be decision(x) = 1 if P(y=1|x) > 0.5. 0 otherwise. Sentiment example, weights can indicate how stronlgy a certain word indicates positive or negative review. Also example of period disambiguation (Deciding whether period is end of sentence or part of word). \n\nFeatures generally designed by examining training set and using intuition. Have to combine feature interactions by hand. When large number of features needed, can use feature templates. Research ongoing for NLP on representation learning to avoid having to manually calculate features. \n\nLogistic regression has big advantage over naive Bayes in that Naive bayes has overly strong conditional independence assumptions. Logistic regression much better for larger data sets, and is thus default. Advantage of Naive Bayes is that it can work even better on very small data sets, and is easier and faster to train. \n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Logistic regression is a supervised learning model. Need metric for how close y_pred is to y_true. Distance between these two called the loss function or the cost function. Cross-entropy loss used for logistic regression and neural networks. Standard optimization algorithm for iteratively updating weights is gradient descent (stochastic gradient descent used for logistic regression). All these are covered later in chapter.\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n Use conditional maximum likelihood estimation to choose w, b s.t. log of probability of true y labels is maximized. Resulting loss is negative log of this, and is called the cross-entropy loss. NOTE: Put Loss equations on handwritten sheet for this part! Perfect classifier would assign 1 to correct answer and 0 to incorrect outcome. Called cross-entropy loss because formula is also formula for the cross-entropy between true prob dist 'y' and our estimated prob dist y_pred. \n\n\n## SLP Chapter 5.4 Gradient Descent\n Goal is to find the set of weights which minimize the loss function, averaged over the samples. Gradient descent finds minimum of a function by determining which direction the slope rising more steeply, and moving in opposite direction. (Good intuition in slides). Loss function is convex when using logistic regression, so there's no local minima to get stuck in. The magnitude of the amount to move in gradient descent is learning weight eta. Faster learning rate means 'w' is moved more each step. Note: Again, many equations which may need for test. Put these on handwritten sheet before test! \n\nStochastic gradient descent is an online function, minimizes loss function by computing gradient after each training example then nudging theta in correct direction. Can adjust learning rate Eta becaues it is a hyperparameter. Commonly, start high and then get low. Hyperparameters affect how the algorithm works. Stochastic gradient descent example shown, same as in slides. May be good to put on sheet. Called stochastic because it chooses one example randomly at a time. Can also use batch training or mini-batch training (both defined below). \n\n\n## SLP Chapter 5.5 Regularization\n Issue: If a feature perfectly predictive only because it happens to occur in one class, assigned very high weight. May not reflect real data (data is now overfit!). Good model should generalize. Regularization term added to avoid overfitting. This penalizes large weights. Can use L2 regularization or L1 regularization (defined below). L2 aesier to optimize b/c simple derivative, L1 more complex. L2 prefers many small weights, L1 prefers sparse solutions with some larger weights and many weights set to zero. Both have Bayesian interpretations as constraints on the prior of how weights look.  \n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Multinomial logistic regression used when need more than 2 classes. Also called softmax regression, or maxent classifier. Uses generalization of the sigmoid, called the softmax function. Write softmax functin on sheet. In multinimial, weights for features now represent evidence for or against each individual class. Loss function is generalized to 'k' terms instead of 2. One-hot vector is when only one value in vector is 1, and the rest are 0. Gradient for a single example similar to gradient for binary logistic regression. \n\n\n## SLP Chapter 7.1 Units\n Intro: Neural net name origin from Mculloh-Pitts neuron. Neural network is a network of small computing units, each take vector of inputs and output 1 value. Often called deep learning because of the many layers. In logistic regression, usually have rich feature templates, whereas in neural networks, prefer raw words as inputs and learn to induce features during the process. Deep neural nets correct tool when large data set and enough data to learn features automatically\n\nCh7_1: This section describes the builing block (single unit) inside a neural network. Seems exactly like a perceptron (sigmoid function, bias term, dot product, etc.). However, also covers non-linear units that are needed for many neural networks. Vanishing gradient problem is when gradients that are almost 0 caues error signal to get smaller until too small to be used for training.\n\n\n## SLP Chapter 7.2 The XOR problem\n Perceptron can easily compute AND and OR, but cannot handle XOR at all! This is because perceptron is a linear classifier, and thus decision boundary is a line. XOR can be calculated by a layered network of units. Example using two ReLU-based units. Can view hidden layer of the network as forming a representation for the input. Neural networks big advantage is they can automatically learn to form these representations well. Note: XOR requires network of units with non-linear activation functions, i.e. CANNOT do it with just perceptrons (simple linear units). This due to fact that many layers of linear units can be reduced to one layer with a certain weights function, which we know can't solve the XOR problem. \n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Feedforward network most simple. Misnomer that they're called multi-layer perceptrons, since most modern ones don't use perceptrons as units. Three types of units: input, hidden, and output. Input x is vector of simple scalar values. Hidden layer 'h' is the core (takes weighted sum of inputs and applies non-linearity). Standard: fully-connected, each unit takes all inputs from previous layer. Computation done simply with simple matrix operations. h = sigma (Wx + b). Once you have h, calculate final probabilities using z = Uh, then normalizing z using softmax. \n\nh = sigma (Wx + b)\n\nz = Uh\n\ny = softmax(z)\n\nThis is a two layer network. Usually use a dummy node of 1 for each layer to represent bias, then apply a weight to the 1 that represents the bias. \n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Example using sentiment classifer in this section. Generally uses deep learning's ability to learn features by using word2vec to get a contatination of vector for input x. This is an example of pretraining - a central idea of deep learning. Relying on another algorithm to have already learned an embeded represenation for the input.\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Example of another application: language  modeling - predicting upcoming words from prior words. \n\nAdvantages of neural language models over n-gram models: 1. Can handle much longer histories. 2. Can generalize better over context of similar words. 2. More accurate at word-prediction.\n\nDisadvantages: complex, slower, less interpretable.\n\nNeural network similar, in that is predicts probability of next words based on N previous words. Difference: Neural LM represent words in prior context by their embeddings, rather than their word identity as in n-gram LM. Embeddings better for generalization to unseen data. Neural LM would generalize from cat to dog to realize dog needs to be fed. \n\nForward interference important (defined below). First represent each of N previous words as one-hot vectors of length |V|. Moving window can see N words into past. Multiply one-hot encodings by matrix E. E has d x |V| dimensions, basically results in selecting the embedding for word 'i'. Resulting embedding vectors concatenated to produce 'e', the embedding layer. Example showing this process concatenating 3 embeddings shown here (go over before test!).  \n\n\n## SLP Chapter 7.6 Training Neural Nets\n Common to use same loss function (cross-entropy loss) in neural nets. Also use gradient descent to minimize the loss function. Can't do simple derivative for gradient now though, and must use technique called error back propagation (also known as backward differentiation). \n\nLoss function is exatly the same equation. \n\nExample using L(a,b,c) = c(a + 2b) shown using backpropogation for much of rest of chapter. Make sure to go over before test and can do independently. Backward differentiation makes use of the chain rule. Put backward pass picture (Figure 7.16) on notes sheet. \nNOTE: Optimization in neural networks is a NON-convex optimization problem, much more complex than logistic regression. Must initialize weights with small random numbers rather than 0 now. Also good to normalize input to 0 mean and unit variance. Dropout (defined) used as form of regularization to avoid overfitting. Tuning of hyperparameters also very important. Include learning rate 'Eta', mini-batch size, model architecture, how to regularize, etc. Most modern neural networks built using computation graph formalisms to make better to do gradient computation and parallelization on vector-based GPU's.  \n\n\n## SLP Chapter 7.7 Training the neural language model\n This section deals with specifics on training a neural language model. Can either \"Freeze\" the embedding matrix E using word2vec, or let it update along with everything else being learned. Can train everything (theta = E,W,U,b) via gradient descent. Training proceeds by taking as input a long text, concatenating all sentences, starting with random weights, and iteratively moving through the text predicting each word w_t. At each w_t, use cross-entropy (negative log likelihood) loss. Training parameters that limit loss will result in an algorithm for the language model (word predictor) and also a new set of embeddings 'E' that ar used as word representations for other tasks. \n\n\n## Module 13 Lecture Notes\n Currently no additional notes from lectures, as lectures followed readings very closely. Many equations figures on hand-written sheet from this module however.\n\nAdded:\n\nLinear classifiers - when using perceptron learning rule, weights updated when actual output does not match the hypothesis output. Can be used for both regression and classification. Not true that learning rule must be applied to one example at a time.\n\nA parametric model has a fixed size on the number of parameters, where a nonparametric model does not. \n\nIt is false that 'When performing k-means clustering, each observation always tarts in its own cluster, and then pairs of clusters are merged in each iteration\" because its only true in agglomerative clustering.\n\nIt is false that 'For lineraly separable data, there exists only one decision boundary that separates the classes' because there could be multiple boundaries, with varying performance.\n\nIt is possible that assignment of observations to clusters do not change between successive iterations in K-means\n\nNonlinear activiation function - make it possible to do gradient backprogagation, help learn nonlinear decision boundaries\n\nNonlinear activation functions can be applied to layers other than output. Also, don't ALWAYS have to ouput values between 0 and 1. \n\n\n## Module 13 Definitions\n* **Logistic regression** - Algorithm suited to determining link between features and an outcome\n* **Generative model** - Understands what dogs and cats look like\n* **Discriminative model** - Can tell the difference between dogs and cats, but can't draw one\n* **Sigmoid** - Logistic function, Takes real-valued number and maps into [0,1]\n* **Feature interaction** - Features that are a combination of more primitive features\n* **Feature templates** - Abstract specifications of features\n* **Loss function** - Distance between y_pred and y_real\n* **Conditional maximum likelihood estimation** - Loss function that prefers correct class labels to be more likely\n* **Cross-entropy loss** - Negative log of the conditional maximum likelihood estimation\n* **Stochastic gradient descent** - online function, minimizes loss function by computing gradient after each training example then nudging theta in correct direction\n* **Batch training** - Compute gradient over entire dataset. Better estimate of direction to go, but much more processing\n* **Mini-batch training** - Train on a group of 'm' samples. Good middle-ground. Can also process mini-batches in parallel\n* **L2 regularization** - quadratic function of weight values. Same as Euclidiance distance of vector theta from origin (RIDGE REG)\n* **L1 regularization** - Linear function of weight values. Sum of the Manhattan distance of absolute values of weights (LASSO REG)\n* **Vanishing gradient problem** - gradients that are almost 0 caues error signal to get smaller until too small to be used for training\n* **Relu** - Rectified linear unit - simplest activation function (straight line from 0, linear up to 10?)\n* **Feedforward network** - Simplest. Units connected with no cycles. No ouputs passed backwards\n* **Output of hidden layer** - h = sigma (Wx + b)\n* **Pretraining** - central idea of deep-learning. Relying on another algorithm to have already learned an embeded represenation for the input\n* **Forward interference/decoding** - Fiven an input, run forward pass on network to produce prob dist over possible inputs\n* **One-hot vector** - Vector that has one element equal to 1, others all 0\n* **Hard classification task** - Only one class is correct one, and 1 output unit in y for each task\n* **Dropout** - Regularization technique to avoid overfitting. Randomly drop some units/connects while training\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\nIntro: Language inherently temporal. Recurrent network gives to way to represent prior context (now decision depends on hundreds of words into the past). Transformer method offers to mechanisms - self-attention and positional encoding - to represent time. This helps relate words over long distances. \n\n9_1: Good models are those that assign higher probabilities to unseens data. Use perplexity to measure quality of a language model. (Write down perplexity equation on sheet from here!).\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Recurrent neural networks (RNNs) contain a cycle within its connections. This means a value of a unit is directly and/or indirectly dependent on own earlier outputs as an input. Generally difficult to understand, but very powerful for language applications. Simple recurrent networks serve as basis for more complex networks. Difference now is sequences processed one item at a time in network (not window-based all at once). Key is that augmentation in hidden layer happens according to previous output from same hidden layer. Does not impose a fixed-length limit on this prior context. Various weight matrices are shared across time. New values for 'h' and 'y' are calculated with each time step. \nSimilarity: still uses training set, loss function, and back-propagation to get gradients to change weights. Back-propagation now more complex, must know influence on all future time steps to calculate the current error. Leads to needing a two-pass algorithm. Pass 1: forward inference on h_t, y_t, accumulate loss, save value of hidden layer. Pass 2: process in reverse, compute required gradients as you go, compute and save error term for use in next step backward in time. Known as Backpropagation Through Time. \n\n\n## SLP Chapter 9.3 RNNs as Language Models\n Train RNN as language model using a corpus of text. Train to minimize error in predicting next true word, use cross-entropy as loss function. Use teacher forcing (defined below). Use Weight Tying to dispense with redundancy and use a single set of embeddings at input and softmax layers (i.e., E = V). Do by setting dimensionality of final hidden layer to be the same d_h, then use same matrix for both layers. This improves complexity and reduces number of parameters required for the model. \n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n\nIntro: Link between similarity of words and distribution of words (distributional hypothesis). Vector semantics use embeddings (both defined). Uses self-learning rather than feature represenation.  \n\n6_1: Many definitions defined below. Most words have a lot of similarties, but not synonyms. Relatedness / association refers to things like coffee and cup. These constitute a semantic field. Topic models use unsupervised learning on large texts to get associated words. Definitions down to sentiment cover this 6_1 section. \n\n\n## SLP Chapter 6.2 Vector Semantics\nVector semantics is standard way to represent a words meaning. Embeddings will group similar words even if you don't know the meaning of them. \n\n\n## SLP Chapter 6.3 Words and Vectors\n Vector models of meaning generally based on co-occurence matrix (how often words co-occur). Can think of vector for a document as point in |V|-dimensional space.  Another model is the term-term matrix (also known as word-word matrix or term-context matrix). In this, columns labeled by words rather than documents. Could be: number of times column word occurs in a +-4 word window around the row word. |V| generally size of vocubulary in all models. These are usually sparse models because of this. \n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Most common similarity metric is the cosine of the angle between the vectors of two words. It is based on the dot product. However, raw dot product favors long vectors. Fix by normalizing by dividing by lengths of each of two vectors. This normalized dot product is same as cosine of angle between two vectors. Sometimes, we will pre-normalize each vector by dividing by length and creating unit vectors. Dot product same as cosine for unit vectors.\n\n\n## SLP Chapter 6.8 Word2vec\n Embeddings are much shorter than vectors seen so far, usually 50-1000. Also they are dense. Dense vectors always work better in NLP tasks. Also better at recognizing similarity. Word2vec methods fast, efficient to train, an easily available online. They are static, i.e., the method learns one fixed embedding for each word in the vocabulary. Main difference: asks is word 'w' likely to show up near word 'w2'. Take learned weights as word embeddings.\n\nRevolutionary intuition: can use running text as impolicitely supervised training dat for a classifier; a word 'c' that occurs near 'apricot' acts as golden 'correct answer'. This is self-supervision, and therefore doesn't need any handlabeling. Word2vec simpler becaus simplifies task (binary), and simplifies architecture (logistic regression instead of multi-layer neural network). \n\nskip-gram: 1. Treat target word and neighboring context as positive. 2. Randomly sample other words for negatives. 3. Logistic regression to distinguish between these. 4. Use learned weights as embeddings.\n\nUse a sigmoid to turn dot product into a probability.\n\nP(+|w,c) = 1 / (1 + exp(-c dot w)). \n\nP(-|w,c) = 1 / (1 + exp(c dot w)). \n\nskip-gram learns two separate embeddings for each word i - target embedding w_i and context embedding c_i. Can either add together at end, or just throw away C matrix and represent by w_i. \n\nfasttest is an extension of word2vec, better at dealing with unknown words. \n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n size of context window usually +-1-10 words. Shorter context = more syntactic. High context = topically related but not similar. First order vs. second order occurence defined. Parallel model used by adding vectors to answer question a is to b as a* is to ____. Didn't work super well at first, but then works very well in word2vec. \nb* = argmin distance(x,a* - a + b)\n\nWorks well in some cases, but not in others though in general. Some argue its too simplistic. Embeddings also useful to compute how meanings change over time. \n\n\n## SLP Chapter 6.11 Bias and Embeddings\n Embeddings represent implicit bias that was embedded in texts too. Leads to allocation harm. Bias amplification actually occurs in vectors. Also demonstrate implicit associations, even bad ones, such as associating more negative words with African-American names. Causes representational harm - system demeans or ignores social groups. Can also use this in a historical context to see historical biases. \n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n Extrinsic evaluation on tasks is most important metric. However, also useful to have intrinsic evaluations. Most common metric here is to test performance on similarity (correlation between algorithm's word similarty scores and a gold-standard assigned by humans). WordSim-353 a common tool used for this. SimLex-999 more difficult dataset. TOEFL has 80 questions, asks to choose most similar word from options. Also programs to compare context, not just similarity. Analogy tasks as well are used, like those described above.\n\nImportant: Can suffer from variability. Very important to train multiple embeddings with bootsrap sampling and average the results. \n\n\n## Module 14 Lecture Notes\nNotes cover same things as readings. When studying, go through and write down the equations on handwritten notes sheet\n\nAdded:\n\nBenefits of log probabilities: avoids underflow from using small numbers, sometimes easier to optimize over sums than products.\n\nMarkov models staionary because distribution of X_t after sufficiently long time that distribution of X_t doesn't change any more. It is not because probs are invariant with respect to shifts in data.\n\nIMPORTANT: Cross-entropy is an upper bound on entropy. The more accurate a model, the lower the cross-entropy.\n\nVector representation using term-document matrices and word-word matrices can't account for polysemy.\n\nn-gram model for a corpus with vocab size V and total T tokens would have run time depending on n and T.\n\nPurpose of Laplace smoothing is to account for unseen words.\n\nWhen generating random text, given a context C, n-gram model can't generate next token T if model never saw the context-token pair (C,T) during training. \n\n\n## Module 14 Definitions\n* **Elman networds / simple recurrent networks** - RNN (simple version). Activation value of hidden layer depends on current input and activation val of previous time step\n* **Backprogation through time** - 2-pass backpropagation algorithm to deal with temporal nature of algorithm. Described in 9_2 above.\n* **Teacher forcing** - Always give model correct history sequence to predict next word, rather than bets case from previous time step\n* **Weight tying** - Uses a single set of embeddings at input and softmax layers. How to do it described in 9_3 above\n* **Distributional hypothesis** - Link between similarity in word distribution and similarity in their meaning\n* **Vector semantics** - learn representation of meaning of words (embeddings) directly from text distribution\n* **Representation learning** - Automaticalyl learn useful represenations - self-supervised\n* **Lexical semantics** - Word meaning\n* **Lemma** - Basically the most basic form (mouse for mice)\n* **Word sense** - The aspect of the meaning of a word (Mouse has rodent or cursor as word senses)\n* **Polysemous** - multiple word senses\n* **Synonym** - Substitutable in a sentence without changing the truth of the sentence\n* **Principle of contrast** - Difference in form of word always connotates a different meaning (h20 vs water)\n* **Relatedness** - Coffee and cup\n* **Semantics field** - Hospital - doctors, medical, etc.\n* **Semantic frame** - Set of words that denote a perspective or participants - buying and selling\n* **Connotations** - affective meaning, word's meaning changes with writer/readers emotions, opinions, etc. \n* **Sentiment** - Positive or negative evaluation (measured by valence (pleasentess), arousal (intensity), and dominance (control)\n* **Term-document matrix** - Each row represents word in vocabulary, each colum represents a document\n* **Vector space model** - Document as a count vector if using term-document matrix model\n* **Information retrieval** - task of finding document d from the D documents that best match query q\n* **Term-term matrix** - Both columns/rows words. Usually, how many times column word occurs in +-4 windown of row word\n* **First order occurence** - Syntagmatic association - typically near each other\n* **Second order occurence** - Paradigmatic association - similar neighbors\n* **Allocational harm** - System allocates resources unfairly (father -> doctor, mother -> nurse)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}