{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_final_exam_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",
      "source": [
        ""
      ],
      "metadata": {
        "id": "j0y4In92KBHo"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "7a429cb5-a477-45e5-a708-75604055e2fd"
      },
      "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": 142,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "caa87b7c-2bcb-44b2-fde6-65c7d2615c5f"
      },
      "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": 143,
      "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": 144,
      "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 = \"\"\"\n",
        "- Expected utility is sum of utilities for being in a given state, weighted by probability that the state occurs\n",
        "- Rational agent should try and maximize expected utility\n",
        "    - leads to richer framework compared to goal directed agents (binary yes/no), or logical agents (can't deal with uncertainty)\n",
        "- But just a framework, need to operationalize\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"\n",
        "- Preferences defined over lotteries\n",
        "    - probabilities attached to outcomes\n",
        "- **Orderability**: can always express preference\n",
        "- Transitivity\n",
        "- Continuity: can always weight two lotteries so that we are indifferent between weighted lottery and some other lottery\n",
        "- **Substitutability**: If indifferent between A and B, then can substitute in more complex lotteries without changing preference\n",
        "- **Monotonocity**: compound lotteries are equivalent to simpler lotteries\n",
        "- Can be proven that if agent has rational preferences, then can define a utility function U so that value of U obeys ordering of preferences\n",
        "- East to prove that agent's behavior won't change if positive affine transformation (linear) on utility\n",
        "    - equivalent to converting from fahrenheit to Celsius\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "- standardized, normalized, lottery: assign value of 1 to best state, 0 to worse\n",
        "    - can then express any other lottery as combination of worse and best...\n",
        "- Money not same as utility - money has expected utility also\n",
        "    - utility increasing at slower rate with more money\n",
        "    - risk averse\n",
        "    - at low levels of money, stop being risk averse (nothing to lose). S shape\n",
        "- optimizer's curse: don't actually know expected utility, just estimate. Since choosing largest estimate, likely to have positive errors. As a result, almost always get lower utility than expected. Post-decision disappointment\n",
        "- Human's don't always express rational preferences\n",
        "    - People might have preference for certainty\n",
        "    - framing effect. anchoring effect\n",
        "    - people don't interpret word problems well\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = r\"\"\"\n",
        "- Markov decision process:\n",
        "    - Stochastic environment with Markovian transition model and additive rewards\n",
        "- develop policies, not action plans\n",
        "- optimal policy maximized expected utility\n",
        "- a policy that depends on time is call **non-stationery**\n",
        "- easier to work with infinite time horizon. Means that optimal policy doesn't depend on starting state.\n",
        "    - assumption of stationary preferences support additive discounting\n",
        "    Bellman equation:\n",
        "$$U(s) = \\max_{a \\in A(s)}\\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma U(s')]$$\n",
        "- can develop a Bellman equation for Q values also: $$Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma U(s')] = \\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma \\max_{a' Q(s',a')}]$$\n",
        "- optimal policy indifferent to positive affine transformation of reward function $R(s, a, a')$\n",
        "- can \"shape\" reward so that optimal policy stays the same : $R(s, a, s') = R(s, a, s') + \\gamma \\sigma(s') - \\sigma(s')$\n",
        "    - can help with training\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "- **Value iteration**: need to solve a Bellman equation for every state\n",
        "- Can't use linear programming, since max operation is not linear\n",
        "- **PROOF OF CONVERGENCE OF VALUE** iteration:\n",
        "    - contraction: function of one argument, when applied to two different arguments, returns two values that are closer together than original inputs\n",
        "    - single fixed point\n",
        "    - Bellman update is a contraction by a factor of $\\gamma$: fixed point is when it has converged..\n",
        "- estimated utility function of state can be wrong and still give correct policy\n",
        "- policy loss: most agent can lose from following policy based on incorrect estimated utility compared to optimal policy based on correct utility\n",
        "- policy iteration has two parts: policy evaluation and policy improvement\n",
        "    - **policy evaluation:** faster than value iteration, since not using max\n",
        "    - policy improvement needs to use max operation to find better policy.\n",
        "- if state space is large, then can't completely solve upfront\n",
        "    - can do some sort of modified expectimax, depth limited...\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "### 1.1: Introduction\n",
        "MDPs also have reward function, triggered at every time step $R(s, a, s')$\n",
        "\n",
        "Difference is that transition function is probabilistic $p(s'|s,a)$\n",
        "\n",
        "It is markovian because probability of getting to next state only depends on previous/current state (and action), not on longer sequence\n",
        "\n",
        "MDPs also have reward function, triggered at every time step $R(s, a, s')$\n",
        "\n",
        "Rewards are additive (summed)\n",
        "\n",
        "### Lessong 2: MDP Formulation\n",
        "MDPs are:\n",
        "\n",
        "- sequential\n",
        "- fully observable\n",
        "- stochastic\n",
        "- with additive rewards\n",
        "\n",
        "AKA: non-deterministic search problems. Can use exptimax search (like min-max, but with chance nodes)\n",
        "\n",
        "Unlike normal search, can't plan out all actions ahead of time. So instead planning actions, develop a policy $\\pi(s)$ that gives action based on state. $\\pi^{*}(s)$ is optimal policy\n",
        "\n",
        "Also due to stochastic environment (transition function), can't maximize score, but rather maxizing expected score/utility.\n",
        "\n",
        "Reward function shapes policy. Reward for non goal states usually slightly negative to encourage agent to prefer goal. If positive, then agent will never go for goal state, especially if infinite number of actions.\n",
        "\n",
        "Usually have infinite number of actions. Actually easier to calculate policy this way. If finite actions, then best policy would depend on number of remaining moves (ex: if positive rewards for all transitions, then go in circles till close to end, then go to goal for bigger reward.)\n",
        "\n",
        "Usually apply a discount term on reward to decrease value of future rewards and increase relative importance of closer ones. Logical, since closer to real life. Future rewards also more uncertain..\n",
        "\n",
        "Discount term is $\\gamma$. Multiplied by reward. Between 0 and 1.\n",
        "\n",
        "helps with convergence also, since don't need to search infinitely deep?\n",
        "\n",
        "If have stationery preferences (preferences are stationery if rewards sequence A is preferred to reward sequence B and we add a reward r to start of each sequence, then we must still prefer A to B), then discounting (potentially equal to 1), is only logical utility way to define utilities\n",
        "\n",
        "### Lesson 3: MDP Examples\n",
        "- a state $s$ action $a$ pair (s,a) is called a q state\n",
        "- Q*(s,a) is s the expected utility starting off at state s, taking aciton a, thereafter acting optimally\n",
        "\n",
        "- V*(s) is the expected utility of starting in s and acting optimally\n",
        "\n",
        "Recursive definiton of value:\n",
        "\n",
        "$V*(s) = max_{a}Q*(s,a)$\n",
        "\n",
        "$Q^*(s,a) = \\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$\n",
        "\n",
        "$V^*(s,a) = \\max_{a}\\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V^(s')]$\n",
        "\n",
        "### Lesson 4:\n",
        "Can solve for $V^*(s)$ with dynamic programing\n",
        "\n",
        "$V_{k+1}(s,a) = \\max_{a}\\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n",
        "\n",
        "- Start at end step (bottom of expecti-max tree). All values are 0 because with no steps left, expected rewards sum to 0\n",
        "- Calculate next layer up...\n",
        "- Repeat until convergence\n",
        "- With gamma less than 1, know that we will converge\n",
        "- Complexity of each iteration: $O(S^2A)$ (S is number of state, A is number of actions...)\n",
        "\n",
        "**Hint!**  Proof of convergence likely on exam!!\n",
        "\n",
        "### Lesson 5: Policy Evaluation\n",
        "If given a policy, can use to calculate values of states\n",
        "\n",
        "Can do recursively, like value iteration, or solve as system of linear equations?\n",
        "\n",
        "Even once have values, can't just choose action that will lead to next state with highest state, since transition function is probabilistic. Need to calculate expected values of actions\n",
        "\n",
        "Better if we have Q values (mapping from state actions pairs to expected values). Can just choose action with highest Q value.\n",
        "\n",
        "Important lesson: actions easier to select from q-values than values\n",
        "\n",
        "### Policy Iteration Algorithm\n",
        "Value iteration is slow O(S^2A). And don't actually need to  know values in order to decide on best action\n",
        "\n",
        "Also, max at each state (best action), rarely changes, even if values change.\n",
        "\n",
        "Instead: do policy iteration for some fixed polucy until values converge\n",
        "\n",
        "Then update policy to be optimal based on new values\n",
        "\n",
        "Repeat until policy converges\n",
        "\n",
        "Still optimal! Can  converge much faster\n",
        "\n",
        "Value iteration updates both values implicitly policy. Don't explicitly track policy, but can extract (taking max)\n",
        "\n",
        "With fixed policy, fast to update utilities\n",
        "\n",
        "Getting new policy is slower\n",
        "\n",
        "Keep doing until have new policy\n",
        "\n",
        "### Lesson 7: Maximum Expected Utility\n",
        "Scales of utility:\n",
        "\n",
        " - normalized (between 0 and 1)\n",
        "\n",
        " - micromorts = chance of death in a million\n",
        "\n",
        "- quality adjusted years\n",
        "\n",
        "if have all 5 axioms of preference, then can represent with utility and agent will be raitonal trying to maximize expected utility.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"proper policy\": \"Policy that is guaranteed to reach terminal state after finite number of steps\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 145,
      "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": "996a97e7-df56-4ffd-c7aa-6ed2c62f8658"
      },
      "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": 146,
      "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\n- Expected utility is sum of utilities for being in a given state, weighted by probability that the state occurs\n- Rational agent should try and maximize expected utility\n    - leads to richer framework compared to goal directed agents (binary yes/no), or logical agents (can't deal with uncertainty)\n- But just a framework, need to operationalize\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\n- Preferences defined over lotteries\n    - probabilities attached to outcomes\n- **Orderability**: can always express preference\n- Transitivity\n- Continuity: can always weight two lotteries so that we are indifferent between weighted lottery and some other lottery\n- **Substitutability**: If indifferent between A and B, then can substitute in more complex lotteries without changing preference\n- **Monotonocity**: compound lotteries are equivalent to simpler lotteries\n- Can be proven that if agent has rational preferences, then can define a utility function U so that value of U obeys ordering of preferences\n- East to prove that agent's behavior won't change if positive affine transformation (linear) on utility\n    - equivalent to converting from fahrenheit to Celsius\n \n\n## AIMA Chapter 16.3 Utility Functions\n \n- standardized, normalized, lottery: assign value of 1 to best state, 0 to worse\n    - can then express any other lottery as combination of worse and best...\n- Money not same as utility - money has expected utility also\n    - utility increasing at slower rate with more money\n    - risk averse\n    - at low levels of money, stop being risk averse (nothing to lose). S shape\n- optimizer's curse: don't actually know expected utility, just estimate. Since choosing largest estimate, likely to have positive errors. As a result, almost always get lower utility than expected. Post-decision disappointment\n- Human's don't always express rational preferences\n    - People might have preference for certainty\n    - framing effect. anchoring effect\n    - people don't interpret word problems well\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- Markov decision process:\n    - Stochastic environment with Markovian transition model and additive rewards\n- develop policies, not action plans\n- optimal policy maximized expected utility\n- a policy that depends on time is call **non-stationery**\n- easier to work with infinite time horizon. Means that optimal policy doesn't depend on starting state.\n    - assumption of stationary preferences support additive discounting\n    Bellman equation:\n$$U(s) = \\max_{a \\in A(s)}\\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma U(s')]$$\n- can develop a Bellman equation for Q values also: $$Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma U(s')] = \\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma \\max_{a' Q(s',a')}]$$\n- optimal policy indifferent to positive affine transformation of reward function $R(s, a, a')$\n- can \"shape\" reward so that optimal policy stays the same : $R(s, a, s') = R(s, a, s') + \\gamma \\sigma(s') - \\sigma(s')$\n    - can help with training\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- **Value iteration**: need to solve a Bellman equation for every state\n- Can't use linear programming, since max operation is not linear\n- **PROOF OF CONVERGENCE OF VALUE** iteration:\n    - contraction: function of one argument, when applied to two different arguments, returns two values that are closer together than original inputs\n    - single fixed point\n    - Bellman update is a contraction by a factor of $\\gamma$: fixed point is when it has converged..\n- estimated utility function of state can be wrong and still give correct policy\n- policy loss: most agent can lose from following policy based on incorrect estimated utility compared to optimal policy based on correct utility\n- policy iteration has two parts: policy evaluation and policy improvement\n    - **policy evaluation:** faster than value iteration, since not using max\n    - policy improvement needs to use max operation to find better policy.\n- if state space is large, then can't completely solve upfront\n    - can do some sort of modified expectimax, depth limited...\n \n\n## Module 8 Lecture Notes\n \n### 1.1: Introduction\nMDPs also have reward function, triggered at every time step $R(s, a, s')$\n\nDifference is that transition function is probabilistic $p(s'|s,a)$\n\nIt is markovian because probability of getting to next state only depends on previous/current state (and action), not on longer sequence\n\nMDPs also have reward function, triggered at every time step $R(s, a, s')$\n\nRewards are additive (summed)\n\n### Lessong 2: MDP Formulation\nMDPs are:\n\n- sequential\n- fully observable\n- stochastic\n- with additive rewards\n\nAKA: non-deterministic search problems. Can use exptimax search (like min-max, but with chance nodes)\n\nUnlike normal search, can't plan out all actions ahead of time. So instead planning actions, develop a policy $\\pi(s)$ that gives action based on state. $\\pi^{*}(s)$ is optimal policy\n\nAlso due to stochastic environment (transition function), can't maximize score, but rather maxizing expected score/utility.\n\nReward function shapes policy. Reward for non goal states usually slightly negative to encourage agent to prefer goal. If positive, then agent will never go for goal state, especially if infinite number of actions.\n\nUsually have infinite number of actions. Actually easier to calculate policy this way. If finite actions, then best policy would depend on number of remaining moves (ex: if positive rewards for all transitions, then go in circles till close to end, then go to goal for bigger reward.)\n\nUsually apply a discount term on reward to decrease value of future rewards and increase relative importance of closer ones. Logical, since closer to real life. Future rewards also more uncertain..\n\nDiscount term is $\\gamma$. Multiplied by reward. Between 0 and 1.\n\nhelps with convergence also, since don't need to search infinitely deep?\n\nIf have stationery preferences (preferences are stationery if rewards sequence A is preferred to reward sequence B and we add a reward r to start of each sequence, then we must still prefer A to B), then discounting (potentially equal to 1), is only logical utility way to define utilities\n\n### Lesson 3: MDP Examples\n- a state $s$ action $a$ pair (s,a) is called a q state\n- Q*(s,a) is s the expected utility starting off at state s, taking aciton a, thereafter acting optimally\n\n- V*(s) is the expected utility of starting in s and acting optimally\n\nRecursive definiton of value:\n\n$V*(s) = max_{a}Q*(s,a)$\n\n$Q^*(s,a) = \\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$\n\n$V^*(s,a) = \\max_{a}\\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V^(s')]$\n\n### Lesson 4:\nCan solve for $V^*(s)$ with dynamic programing\n\n$V_{k+1}(s,a) = \\max_{a}\\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n\n- Start at end step (bottom of expecti-max tree). All values are 0 because with no steps left, expected rewards sum to 0\n- Calculate next layer up...\n- Repeat until convergence\n- With gamma less than 1, know that we will converge\n- Complexity of each iteration: $O(S^2A)$ (S is number of state, A is number of actions...)\n\n**Hint!**  Proof of convergence likely on exam!!\n\n### Lesson 5: Policy Evaluation\nIf given a policy, can use to calculate values of states\n\nCan do recursively, like value iteration, or solve as system of linear equations?\n\nEven once have values, can't just choose action that will lead to next state with highest state, since transition function is probabilistic. Need to calculate expected values of actions\n\nBetter if we have Q values (mapping from state actions pairs to expected values). Can just choose action with highest Q value.\n\nImportant lesson: actions easier to select from q-values than values\n\n### Policy Iteration Algorithm\nValue iteration is slow O(S^2A). And don't actually need to  know values in order to decide on best action\n\nAlso, max at each state (best action), rarely changes, even if values change.\n\nInstead: do policy iteration for some fixed polucy until values converge\n\nThen update policy to be optimal based on new values\n\nRepeat until policy converges\n\nStill optimal! Can  converge much faster\n\nValue iteration updates both values implicitly policy. Don't explicitly track policy, but can extract (taking max)\n\nWith fixed policy, fast to update utilities\n\nGetting new policy is slower\n\nKeep doing until have new policy\n\n### Lesson 7: Maximum Expected Utility\nScales of utility:\n\n - normalized (between 0 and 1)\n\n - micromorts = chance of death in a million\n\n- quality adjusted years\n\nif have all 5 axioms of preference, then can represent with utility and agent will be raitonal trying to maximize expected utility.\n\n\n\n## Module 8 Definitions\n* **Proper policy** - Policy that is guaranteed to reach terminal state after finite number of steps\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 =  \"\"\"\n",
        "- bandit problems = Markov reward process\n",
        "    - MDP: states are WIN/LOSS\n",
        "- Gittins index:\n",
        "    - sum of discounted rewards thous far divided by \"discounted time\"\n",
        "    - Value of arm in terms of its ability to deliver stream of timely rewards\n",
        "    - optimal policy for any bandit problem: pull arm with highest Gittins index, then update indexes\n",
        "        - problem is that we don't know $\\lambda$? (fixed reward we can get)\n",
        "        - solution is to solve a MDP that allows a \"restart\" to get sequence of rewards already obtained?\n",
        "        - don't understand...\n",
        "- Upper confidence bound: select arm with highest\n",
        "    - rather than highest mean, since want to explore...\n",
        "- bandit super process (BSP)\n",
        "- dominating policy\n",
        "    - relaxed version of problem?\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "model based vs model free reinforcement learning\n",
        " \"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "**Passive reinforcement learning**\n",
        "\n",
        "- Direct utility estimation\n",
        "    - model free: don't learn transition function\n",
        "    - estimate values directly: sum of discounted rewards earned from that state onwards, averaged\n",
        "    - converges slowly\n",
        "    - Model free\n",
        "- adaptive dynamic programming\n",
        "    - estimate transition function: just maintain counts of what state end up in\n",
        "    - then use value iteration, or policy evaluation\n",
        "    - Model based\n",
        "- temporal difference learning:\n",
        "    - exponential moving average.\n",
        "    - Model free\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "- tradeoff between exploration and exploitation\n",
        "    - similar to bandit problems\n",
        "- hard to get optimal exploration scheme\n",
        "- don't want to be greedy in terms of next move, but \"greedy in the limit of infinite exploration\" GLIE\n",
        "    - must try each action in each state an unbounded number of times to avoid having finite probability that an optimal action is missed\n",
        "    - this will guarantee that we can eventually yearn optimal policy\n",
        "- rather choosing random action with prob $\\epsilon$ and best action with $1-\\epsilon$, better to give higher weight to action not tried\n",
        "- this extra value also assigned during update, in order to propagate back higher value of unexplored state to entice exploration towards that state\n",
        "- sometime actions are irreversible (death). So might want to have exploration that avoid this\n",
        "    - bayesian reinforcement learning or robust control theory\n",
        "    - temporal difference q learning\n",
        "        - update q value as exponential moving average\n",
        "        - off policy learning..\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\n",
        "- can use a linear function of features to approximate state\n",
        "- not only does this help with learning when many states, also helps to generalize to unseen states\n",
        "- update rules becomes: feature_weight = feature_weight + alpha * (actual reward - expected reward) * feature_value\n",
        "    - now update for observing a single transition between two states leads to an updates that affects expected values for all other states\n",
        "- can always model state as linear function by inventing non-linear functions, but can be tricky.\n",
        "    - Can use neural nets, but parameters might go to infinity. Use back prop, gradient descent, but very tricky\n",
        "- Catastrophic forgetting: learn too well. Stay in safe spot. If accidentally end up in unsafe spot, don't know what to do.\n",
        "- Can shape rewards, with a potential function that doesn't change optimal policy to give more reward to \"good\" intermediate actions\n",
        "- Alternative is hierarchical reinforcement learning. More general. Have series of \"choose\" functions\n",
        "- Example: keep away. Check if have ball or no, then choose appropriate action. Learn what action to choose.\n",
        "- Benefit is that intent (such who we are planning to pass to ) end up in state? Can shape reward?\n",
        " \"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "**policy search**\n",
        "- can specify policy as function as parameters. Different from Q learning with parameters, since don't need value to be close to actual. Just need to make right decision\n",
        "- policy value is expected reward to got when policy is executed\n",
        "- take derivative of policy value with respect to parameters\n",
        "    - (Need to have policy return a probability using softmax, rather than hard decision)\n",
        "- problem is that total reward for each trial may vary wildly, so estimates of policy value from small number of trials may be quite unreliable\n",
        "- can instead take an average gradients from each trial? But need to divide by probability?\n",
        "- Correlated sampling: to compare to policies, apply them to sets of same example. Example would be blackjack policy. Deal same hands. Much easier to estimate which one is better.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "### Introduction to Reinforcement Learning\n",
        "- **reinforcement learning:**\n",
        "    - don't know transition function or reward, need to learn\n",
        "    - know what state we're in.... and reward we just got\n",
        "- multi/two armed bandit: different payouts\n",
        "    - don't know probability of different rewards, need to learn.\n",
        "- Concepts:\n",
        "    - Exploration\n",
        "    - exploitation\n",
        "    - regret: deviance from optimal policy?\n",
        "    - sampling\n",
        "    - difficulty\n",
        "- General concepts:\n",
        "    - receive feedback in terms of rewards\n",
        "    - want to maximize expected rewards\n",
        "    - must learn through experience\n",
        "    - same as MDP, just don't know transition function $T(s,a,a')$  or reward function $R(s,a,s')$\n",
        "    - still developing policy\n",
        "    - \"online\" not \"offline\" learning/solution\n",
        "\n",
        "2 approaches:\n",
        "- Model based learning: learn reward and transition function, then solve using techniques for MDP (value iteration or policy iteration..\n",
        "-  model free: action-utility learning, or policy search\n",
        "\n",
        "### Passive Reinforcement Learning\n",
        "- start with a fixed policy\n",
        "- want to learn state values (utilities)\n",
        "    - then will develop policy\n",
        "- direct evaluation:\n",
        "    - compute values for each sate under policy\n",
        "    - act according to policy\n",
        "    - Then calculate sum of discounted rewards for each state\n",
        "    - Pros:\n",
        "        - easy to understand\n",
        "        - don't need to calculate R or T\n",
        "        - eventually will get right values?\n",
        "    - Cons:\n",
        "        - doesn't take constraints into account?\n",
        "        - connections between states - learn values separately for each state. so inefficient.\n",
        "- sample based policy evaluation?\n",
        "    - But can't guarantee that we will end up in certain state n times?\n",
        "\n",
        "### Temporal Difference Learning\n",
        "- learn V(s) by making iterative updates. Weighted by alpha. Exponential moving average\n",
        "- Policy still fixed; still doing evaluation\n",
        "- Model free\n",
        "- Not learning transition function\n",
        "- Good way of learning values\n",
        "- But won't be able to extract policy, since don't have transition function...\n",
        "- Better to learn Q values, rather than values\n",
        "\n",
        "### Active Reincforcement Learning (Q-Learning)\n",
        "- update Q values iteratively, weighted average,, fashion, like temporal learning\n",
        "- off policy learning, since updating q values, based on max, even if following policy that is not optimal\n",
        "- Q-learning converges to optimal policy\n",
        "- In limit, doesn't matter how you select action\n",
        "- Caveats:\n",
        "    - have to explore enough\n",
        "    - Have to make learning rate small enough, but not decrease too fast\n",
        "\n",
        "### Exploration vs Exploitation\n",
        "For active learning, different ways of deciding what action to take. Called exploration function..\n",
        "\n",
        "Can take best action (highest Q value), but might not lead to optimal policy, since won't explore new states. this is called greedy approach\n",
        "\n",
        "Can just flip coin, with small probability epsilon , act randomly, and with 1- epsilon, take best action ($\\epsilon$ greedy). issue is that we keep on taking actions we know are bad.\n",
        "\n",
        "Alternative is to give bonus for unexplored actions/states. can give fixed bonus k to estimate, divide k by n, number of times taken. So large bonus when unexplored, decline more times explored\n",
        "\n",
        "**Regret** is a measure of total cost of mistakes : the difference between expected rewards, including youthful suboptimal, and optimal expected rewards\n",
        "\n",
        "Want to minimize regret; need to learn optimally, not just learn optimal policy\n",
        "\n",
        "Ex: random exploration and epsilon functions both end up with same policy, but random exploration higher regret.\n",
        "\n",
        "### Approximate Q-Learning\n",
        "Can express value or q value as linear function, to help generalize\n",
        "\n",
        "Have features, Learn weights\n",
        "\n",
        "Update weights, rather than exact q values\n",
        "\n",
        "w_i ← w_i + alpha[difference] f_i(s,a) \n",
        "\n",
        "f is feature...\n",
        "\n",
        "Formal justification: online least squares. if something bad happens \"blame\" large active features. If good, then \"credit\" large active features\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 147,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "50c82a48-93b7-4ed1-9688-c907a61fb035"
      },
      "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": 148,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- bandit problems = Markov reward process\n    - MDP: states are WIN/LOSS\n- Gittins index:\n    - sum of discounted rewards thous far divided by \"discounted time\"\n    - Value of arm in terms of its ability to deliver stream of timely rewards\n    - optimal policy for any bandit problem: pull arm with highest Gittins index, then update indexes\n        - problem is that we don't know $\\lambda$? (fixed reward we can get)\n        - solution is to solve a MDP that allows a \"restart\" to get sequence of rewards already obtained?\n        - don't understand...\n- Upper confidence bound: select arm with highest\n    - rather than highest mean, since want to explore...\n- bandit super process (BSP)\n- dominating policy\n    - relaxed version of problem?\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n\nmodel based vs model free reinforcement learning\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n**Passive reinforcement learning**\n\n- Direct utility estimation\n    - model free: don't learn transition function\n    - estimate values directly: sum of discounted rewards earned from that state onwards, averaged\n    - converges slowly\n    - Model free\n- adaptive dynamic programming\n    - estimate transition function: just maintain counts of what state end up in\n    - then use value iteration, or policy evaluation\n    - Model based\n- temporal difference learning:\n    - exponential moving average.\n    - Model free\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- tradeoff between exploration and exploitation\n    - similar to bandit problems\n- hard to get optimal exploration scheme\n- don't want to be greedy in terms of next move, but \"greedy in the limit of infinite exploration\" GLIE\n    - must try each action in each state an unbounded number of times to avoid having finite probability that an optimal action is missed\n    - this will guarantee that we can eventually yearn optimal policy\n- rather choosing random action with prob $\\epsilon$ and best action with $1-\\epsilon$, better to give higher weight to action not tried\n- this extra value also assigned during update, in order to propagate back higher value of unexplored state to entice exploration towards that state\n- sometime actions are irreversible (death). So might want to have exploration that avoid this\n    - bayesian reinforcement learning or robust control theory\n    - temporal difference q learning\n        - update q value as exponential moving average\n        - off policy learning..\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n- can use a linear function of features to approximate state\n- not only does this help with learning when many states, also helps to generalize to unseen states\n- update rules becomes: feature_weight = feature_weight + alpha * (actual reward - expected reward) * feature_value\n    - now update for observing a single transition between two states leads to an updates that affects expected values for all other states\n- can always model state as linear function by inventing non-linear functions, but can be tricky.\n    - Can use neural nets, but parameters might go to infinity. Use back prop, gradient descent, but very tricky\n- Catastrophic forgetting: learn too well. Stay in safe spot. If accidentally end up in unsafe spot, don't know what to do.\n- Can shape rewards, with a potential function that doesn't change optimal policy to give more reward to \"good\" intermediate actions\n- Alternative is hierarchical reinforcement learning. More general. Have series of \"choose\" functions\n- Example: keep away. Check if have ball or no, then choose appropriate action. Learn what action to choose.\n- Benefit is that intent (such who we are planning to pass to ) end up in state? Can shape reward?\n \n\n## Module 9 Lecture Notes\n\n### Introduction to Reinforcement Learning\n- **reinforcement learning:**\n    - don't know transition function or reward, need to learn\n    - know what state we're in.... and reward we just got\n- multi/two armed bandit: different payouts\n    - don't know probability of different rewards, need to learn.\n- Concepts:\n    - Exploration\n    - exploitation\n    - regret: deviance from optimal policy?\n    - sampling\n    - difficulty\n- General concepts:\n    - receive feedback in terms of rewards\n    - want to maximize expected rewards\n    - must learn through experience\n    - same as MDP, just don't know transition function $T(s,a,a')$  or reward function $R(s,a,s')$\n    - still developing policy\n    - \"online\" not \"offline\" learning/solution\n\n2 approaches:\n- Model based learning: learn reward and transition function, then solve using techniques for MDP (value iteration or policy iteration..\n-  model free: action-utility learning, or policy search\n\n### Passive Reinforcement Learning\n- start with a fixed policy\n- want to learn state values (utilities)\n    - then will develop policy\n- direct evaluation:\n    - compute values for each sate under policy\n    - act according to policy\n    - Then calculate sum of discounted rewards for each state\n    - Pros:\n        - easy to understand\n        - don't need to calculate R or T\n        - eventually will get right values?\n    - Cons:\n        - doesn't take constraints into account?\n        - connections between states - learn values separately for each state. so inefficient.\n- sample based policy evaluation?\n    - But can't guarantee that we will end up in certain state n times?\n\n### Temporal Difference Learning\n- learn V(s) by making iterative updates. Weighted by alpha. Exponential moving average\n- Policy still fixed; still doing evaluation\n- Model free\n- Not learning transition function\n- Good way of learning values\n- But won't be able to extract policy, since don't have transition function...\n- Better to learn Q values, rather than values\n\n### Active Reincforcement Learning (Q-Learning)\n- update Q values iteratively, weighted average,, fashion, like temporal learning\n- off policy learning, since updating q values, based on max, even if following policy that is not optimal\n- Q-learning converges to optimal policy\n- In limit, doesn't matter how you select action\n- Caveats:\n    - have to explore enough\n    - Have to make learning rate small enough, but not decrease too fast\n\n### Exploration vs Exploitation\nFor active learning, different ways of deciding what action to take. Called exploration function..\n\nCan take best action (highest Q value), but might not lead to optimal policy, since won't explore new states. this is called greedy approach\n\nCan just flip coin, with small probability epsilon , act randomly, and with 1- epsilon, take best action ($\\epsilon$ greedy). issue is that we keep on taking actions we know are bad.\n\nAlternative is to give bonus for unexplored actions/states. can give fixed bonus k to estimate, divide k by n, number of times taken. So large bonus when unexplored, decline more times explored\n\n**Regret** is a measure of total cost of mistakes : the difference between expected rewards, including youthful suboptimal, and optimal expected rewards\n\nWant to minimize regret; need to learn optimally, not just learn optimal policy\n\nEx: random exploration and epsilon functions both end up with same policy, but random exploration higher regret.\n\n### Approximate Q-Learning\nCan express value or q value as linear function, to help generalize\n\nHave features, Learn weights\n\nUpdate weights, rather than exact q values\n\nw_i ← w_i + alpha[difference] f_i(s,a) \n\nf is feature...\n\nFormal justification: online least squares. if something bad happens \"blame\" large active features. If good, then \"credit\" large active features\n\n\n \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"\n",
        "- like logical propositions, in probability, statements either true or false\n",
        "    - but probabilities represent confidence given ignorance/laziness of all factors. Just take what we know into account\n",
        "- decision theory combines probability theory and utility theory\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "- Associate each world with a probability\n",
        "- all prob of all words sum to one\n",
        "- each prob greater than equal to 0\n",
        "- set of worlds = event/proposition\n",
        "- probability of a event = sum of probabilities of its worlds\n",
        "- conditional/posterior probability vs unconditional probabilities (prior)\n",
        "- only draw conclusions from conditional probabilities when don't have further evidence. Otherwise, incorporate further evidence\n",
        "- going from joint to conditional probability using product rule\n",
        "- random variables map from domain of possible worlds to a possible range\n",
        "- if range is 1/0, then Bernoulli RV\n",
        "- **Probability density function (PDF)**: probability that variable takes on value in certain range\n",
        "    - for continuous variables\n",
        "    - for points, PDF give probability that X falls in arbitrarily small region beginning at x, divided by size of region. Doesn't give probability that X = x, since actual prob is 0, infinitesimal.\n",
        "    - Density function measured in units, inverse of normal units. So for temperature, units are 1/C (Celsius)\n",
        "- joint probability\n",
        "    - can sum out the variable we don't care about to go from joint to single\n",
        "- Axioms (Komlograv’s):\n",
        "    - inclusion exclusion principal: probability(A or B) = P(A) + P(B) - P(A and B)\n",
        "    - P(a) = 1 - P( not a)\n",
        "    - if don’t follow axioms when stipulating probabilities, possible to formulate set of bets based on probabilities that opponent always wins money, and you always lose money\n",
        "\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "- want to get posterior probability for a query variable given evidence\n",
        "- sum to get marginal/unconditional probability from full joint probability distribution (table form)\n",
        "    - called marginalization/summingout\n",
        "- use logic of product rule get conditional from joint by dividing\n",
        "    - quotient (denominator) called normalization term, alpha. Makes certain probabilities sum to 1\n",
        "- Marginalization with many variables doesn't work well (O2^n) time.\n",
        "- need independence assumptions to make simpler..\n",
        "\"\"\"\n",
        "chapter12_4 = r\"\"\"\n",
        "a and b are independent if $P(a|b) = P(a)$ or $P(b|a) = P(b)$ or $P(a \\land b) = P(a)P(b)$\"\"\"\n",
        "chapter12_5 = r\"\"\"\n",
        "- Sometimes know prior probability of effect, prior probability of cause and conditional probability of effect given cause, but want conditional probability of cause given effect\n",
        "Can apply Baye's rule:\n",
        "$$P(Y|X) = \\frac{P(X|Y)P(Y)}{P(X)}$$\n",
        "**Conditional independence**: A and B are conditionally independent on C if: $P(A, B|C) = P(A|C)P(B|C)$ or $P(A|B,C) = P(A|C)$ or $ P(B|A,C) = P(B|C)$\n",
        "- for n evidence variables that conditional independent on query variable, the size of the representation grows as O(n) instead of O(2^n)\n",
        "    - Means that conditional independence helps reduce problem tractable size. Conditional independence much more common/realistic than absolute independence\n",
        "\"\"\"\n",
        "chapter12_6 = r\"\"\"\n",
        "- Naive Bayes model assumes that all effect variables are conditionally independent given cause\n",
        "- Want to know probability of cause given effect\n",
        "- can use Bayes rule: $$P(Cause|e_1,,e_2....e_n) = P(Cause)\\prod_{i}P(e_i|Cause) * \\alpha$$\n",
        "where $\\alpha$ is scaling factor. Don't actually need to calculate scaling factor. Just take cause/class with highest probability\n",
        "- For text classifier, effects are word. Y is label of text\n",
        "- Need to use Laplacian smoothing to account for words that haven't been seen.\n",
        "- Calculate in log space, since can use sums instead of multiplying (low values)\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\"\n",
        "- can use probability to check for breezes instead of logic\n",
        "- query variable is if breeze in certain square, conditional on what we know\n",
        "- breezes conditionally independent on what we know (frontier and query variables)\n",
        " \"\"\"\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 = \"\"\"\n",
        "- ngrams\n",
        "- Markovian assumption\n",
        "    - Decent approximation\n",
        "- Apply chain rule\n",
        "- normalize - Maximum Likelihood Estimation\n",
        "    - to get conditional, sum counts of n-gram (next word and context), divide by count of context\n",
        "- use log probabilities\n",
        " \"\"\"\n",
        "SLP_chapter3_2 = r\"\"\"\n",
        "- training set\n",
        "- test set (hod out)\n",
        "- dev set = validation set\n",
        "- **perplexity of a sentence**: $P(w_{1}w{2}...w_{N})^{-\\frac{1}{N}} = (\\prod_{i=1}\\frac{1}{P(w_i|w_{i-1})})^{\\frac{1}{N}}$\n",
        "    - want lower perplexity\n",
        "        - basically geometric mean of inverse probabilities..\n",
        " \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" To generater sentence:\n",
        "- assign each word a number between 0 and 1, based on probablity (mightr be conitonal on context /n-grams)\n",
        "- nmber is such between prebious and this word, inerval is probalbityt\n",
        "- generate random number betweon 0 anbd 1 anbd eslect\n",
        "- sparsity anb 0 words:\n",
        "  - can have an <UNK> token\n",
        "- perxpl;icites should only be compared across language models with the same vocabularies\n",
        "  - otherwise, could achieve low probablity by choosing a small vocabularly and assigning the unknown word a high probablity\n",
        "\"\"\"\n",
        "SLP_chapter3_4 = \"\"\" \n",
        "- assign each word a number between 0 and 1, based on probability (might be cognitional on context /n-grams)\n",
        "    - number is such between that difference between previous word’s number and this word’s number is probability of this word\n",
        "- generate random number between 0 and 1 and select the corresponding word\n",
        "- sparsity and 0 words:\n",
        "    - can have use an <UNK> token\n",
        "- perplexities  should only be compared across language models with the same vocabularies\n",
        "    - otherwise, could achieve low probability by choosing a small vocabulary and assigning the unknown word a high probability\n",
        " \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" \n",
        "- Laplacian smoothing: add 1 to each count. Can adjust just numerator by normalizing. Adjust count\n",
        "    - Adjust counts makes it so that counts add up original total, even after adding one to all vocab\n",
        "- Add k smoothing: like laplace, but add less than 1\n",
        "- useful for text classification, but bad for language modelling (generation?): high variances\n",
        "- backoff: if using context of 3 words, but no examples for 3 words, reduce to looking at 2 words.\n",
        "    - ie: use less context\n",
        "- interpolation: always mix probabilities from n grams of different lengths\n",
        "    - can give linear weight to probability from context of different length\n",
        "    - can give higher weights to contexts with more counts\n",
        "    - can use a test set to get weights\n",
        "    - similar to laplacian smoothing, need to discount probability of higher order n grams to \"save probability mass\" for lower\n",
        "    - otherwise, sum of probabilities would be greater than 1\n",
        "        - backoff with discounting called Katz backoff\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "**Stupid backoff**: backoff, but use just a fixed discount. Means that probabilities don't sum to one.\n",
        "\n",
        "Works well for large models/corpus/vocabs\n",
        "\n",
        "Want to discount lower order, since otherwise probabilities will be too high (since see lower order contexts more often ) \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "### Review on Probablities\n",
        "- Many different worlds (outcomes)\n",
        "- Collection of outcomes = events\n",
        "- Random variables track something about outcome/world\n",
        "- Observed variables = evidence\n",
        "    - can condition on these\n",
        "- Unobserved variables = states\n",
        "    - want to calculate probability for these\n",
        "- Model = what agent knows about relationships between observed and unobserved variables\n",
        "- Better than logical reasoning\n",
        "    - Even if can't say for sure if square in wumpus world is clear, can still reason about it (e.g. low probability)\n",
        "- P(w) associates probablity with each world\n",
        "- Random variables RV: Rain = it is raining in this world\n",
        "- sum of probability is one, greater than equal to 0..\n",
        "\n",
        "### Distributions\n",
        "- **Joint distribution:** probability of all happening together. Example P(Rain=is raining, Sun=is shining), can also write P(x_1, x_2..._)\n",
        "- Can have table of probabilities: is a probability distribution\n",
        "    - Need to sum to one\n",
        "- Can calculate probability of an event by summing\n",
        "- **Marginalization**: combine collapsed rows by summing\n",
        "- Conditional probabilities: divide joint probability by probability of world to condition on that world\n",
        "- Multiply conditional probability with prior to get joint\n",
        "\n",
        "### Probabilistic Inference and Rules\n",
        "Know evidence variables, want to know probabilities of a certain \"query\" variable\n",
        "\n",
        "Start by calculating joint probability of query variable and evidence variables by summing over hidden/unobserved variables\n",
        "\n",
        "If know probability of evidence variable, can then use the product rule (divide by probability of evidence variable), to get conditional probability\n",
        "\n",
        "Chain rule is more general rule. Can always write any joint distribution as an incremental product of conditional distributions\n",
        "\n",
        "Leads to **Bayes rule**: $P(x|y) = \\frac{P(y|x)}{P(x)}P(y)$\n",
        "\n",
        "Very useful since sometime know conditional probability for evidence variable given hidden but want to calculate probability of hidden given evidence (ex: Naive Bayes - know probability of word given class, want to know probability of class given word)\n",
        "\n",
        "### Probabilistic Language Models\n",
        "Want to be able to calculate probability of a sentence given words in it. useful for machine translation, spell check etc..\n",
        "\n",
        "Leads to probability of next word give words thus far\n",
        "\n",
        "Naive approach is to calculate joint distribution by using chain rule and multiplying conditional probabilities for full sequence of words.\n",
        "\n",
        "Problem is that this state space is huge! Don't have enough data, let alone enough compute power\n",
        "\n",
        "Solution is to make simplifying assumption that probability of each word is only conditional on the past *k* words. **Markovian assumption**, similar to MDP, where assumption was that transition function only depended on current state, not sequence of previous sates\n",
        "\n",
        "With this simplifying assumption, we can calculate the probability of a sentence as the produce of the probabilities of all words in sentence, each conditioned on past k words\n",
        "\n",
        "N-gram model.\n",
        "\n",
        "Confusing, since unigram ⇒ k=0\n",
        "\n",
        "bigram = condition on past word\n",
        "\n",
        "Etc..\n",
        "\n",
        "n-gram means total of n words. condition on n-1 words.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 149,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "97bef380-e327-40f7-b1f6-1a8b19e948a0"
      },
      "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": 150,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- like logical propositions, in probability, statements either true or false\n    - but probabilities represent confidence given ignorance/laziness of all factors. Just take what we know into account\n- decision theory combines probability theory and utility theory\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- Associate each world with a probability\n- all prob of all words sum to one\n- each prob greater than equal to 0\n- set of worlds = event/proposition\n- probability of a event = sum of probabilities of its worlds\n- conditional/posterior probability vs unconditional probabilities (prior)\n- only draw conclusions from conditional probabilities when don't have further evidence. Otherwise, incorporate further evidence\n- going from joint to conditional probability using product rule\n- random variables map from domain of possible worlds to a possible range\n- if range is 1/0, then Bernoulli RV\n- **Probability density function (PDF)**: probability that variable takes on value in certain range\n    - for continuous variables\n    - for points, PDF give probability that X falls in arbitrarily small region beginning at x, divided by size of region. Doesn't give probability that X = x, since actual prob is 0, infinitesimal.\n    - Density function measured in units, inverse of normal units. So for temperature, units are 1/C (Celsius)\n- joint probability\n    - can sum out the variable we don't care about to go from joint to single\n- Axioms (Komlograv’s):\n    - inclusion exclusion principal: probability(A or B) = P(A) + P(B) - P(A and B)\n    - P(a) = 1 - P( not a)\n    - if don’t follow axioms when stipulating probabilities, possible to formulate set of bets based on probabilities that opponent always wins money, and you always lose money\n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- want to get posterior probability for a query variable given evidence\n- sum to get marginal/unconditional probability from full joint probability distribution (table form)\n    - called marginalization/summingout\n- use logic of product rule get conditional from joint by dividing\n    - quotient (denominator) called normalization term, alpha. Makes certain probabilities sum to 1\n- Marginalization with many variables doesn't work well (O2^n) time.\n- need independence assumptions to make simpler..\n\n\n## AIMA Chapter 12.4 Independence\n\na and b are independent if $P(a|b) = P(a)$ or $P(b|a) = P(b)$ or $P(a \\land b) = P(a)P(b)$\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n- Sometimes know prior probability of effect, prior probability of cause and conditional probability of effect given cause, but want conditional probability of cause given effect\nCan apply Baye's rule:\n$$P(Y|X) = \\frac{P(X|Y)P(Y)}{P(X)}$$\n**Conditional independence**: A and B are conditionally independent on C if: $P(A, B|C) = P(A|C)P(B|C)$ or $P(A|B,C) = P(A|C)$ or $ P(B|A,C) = P(B|C)$\n- for n evidence variables that conditional independent on query variable, the size of the representation grows as O(n) instead of O(2^n)\n    - Means that conditional independence helps reduce problem tractable size. Conditional independence much more common/realistic than absolute independence\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- Naive Bayes model assumes that all effect variables are conditionally independent given cause\n- Want to know probability of cause given effect\n- can use Bayes rule: $$P(Cause|e_1,,e_2....e_n) = P(Cause)\\prod_{i}P(e_i|Cause) * \\alpha$$\nwhere $\\alpha$ is scaling factor. Don't actually need to calculate scaling factor. Just take cause/class with highest probability\n- For text classifier, effects are word. Y is label of text\n- Need to use Laplacian smoothing to account for words that haven't been seen.\n- Calculate in log space, since can use sums instead of multiplying (low values)\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n- can use probability to check for breezes instead of logic\n- query variable is if breeze in certain square, conditional on what we know\n- breezes conditionally independent on what we know (frontier and query variables)\n \n\n## SLP Chapter 3.1 N-Grams\n\n- ngrams\n- Markovian assumption\n    - Decent approximation\n- Apply chain rule\n- normalize - Maximum Likelihood Estimation\n    - to get conditional, sum counts of n-gram (next word and context), divide by count of context\n- use log probabilities\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- training set\n- test set (hod out)\n- dev set = validation set\n- **perplexity of a sentence**: $P(w_{1}w{2}...w_{N})^{-\\frac{1}{N}} = (\\prod_{i=1}\\frac{1}{P(w_i|w_{i-1})})^{\\frac{1}{N}}$\n    - want lower perplexity\n        - basically geometric mean of inverse probabilities..\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n To generater sentence:\n- assign each word a number between 0 and 1, based on probablity (mightr be conitonal on context /n-grams)\n- nmber is such between prebious and this word, inerval is probalbityt\n- generate random number betweon 0 anbd 1 anbd eslect\n- sparsity anb 0 words:\n  - can have an <UNK> token\n- perxpl;icites should only be compared across language models with the same vocabularies\n  - otherwise, could achieve low probablity by choosing a small vocabularly and assigning the unknown word a high probablity\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n \n- assign each word a number between 0 and 1, based on probability (might be cognitional on context /n-grams)\n    - number is such between that difference between previous word’s number and this word’s number is probability of this word\n- generate random number between 0 and 1 and select the corresponding word\n- sparsity and 0 words:\n    - can have use an <UNK> token\n- perplexities  should only be compared across language models with the same vocabularies\n    - otherwise, could achieve low probability by choosing a small vocabulary and assigning the unknown word a high probability\n \n\n## SLP Chapter 3.5 Smoothing\n \n- Laplacian smoothing: add 1 to each count. Can adjust just numerator by normalizing. Adjust count\n    - Adjust counts makes it so that counts add up original total, even after adding one to all vocab\n- Add k smoothing: like laplace, but add less than 1\n- useful for text classification, but bad for language modelling (generation?): high variances\n- backoff: if using context of 3 words, but no examples for 3 words, reduce to looking at 2 words.\n    - ie: use less context\n- interpolation: always mix probabilities from n grams of different lengths\n    - can give linear weight to probability from context of different length\n    - can give higher weights to contexts with more counts\n    - can use a test set to get weights\n    - similar to laplacian smoothing, need to discount probability of higher order n grams to \"save probability mass\" for lower\n    - otherwise, sum of probabilities would be greater than 1\n        - backoff with discounting called Katz backoff\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n**Stupid backoff**: backoff, but use just a fixed discount. Means that probabilities don't sum to one.\n\nWorks well for large models/corpus/vocabs\n\nWant to discount lower order, since otherwise probabilities will be too high (since see lower order contexts more often ) \n\n## Module 10 Lecture Notes\n \n### Review on Probablities\n- Many different worlds (outcomes)\n- Collection of outcomes = events\n- Random variables track something about outcome/world\n- Observed variables = evidence\n    - can condition on these\n- Unobserved variables = states\n    - want to calculate probability for these\n- Model = what agent knows about relationships between observed and unobserved variables\n- Better than logical reasoning\n    - Even if can't say for sure if square in wumpus world is clear, can still reason about it (e.g. low probability)\n- P(w) associates probablity with each world\n- Random variables RV: Rain = it is raining in this world\n- sum of probability is one, greater than equal to 0..\n\n### Distributions\n- **Joint distribution:** probability of all happening together. Example P(Rain=is raining, Sun=is shining), can also write P(x_1, x_2..._)\n- Can have table of probabilities: is a probability distribution\n    - Need to sum to one\n- Can calculate probability of an event by summing\n- **Marginalization**: combine collapsed rows by summing\n- Conditional probabilities: divide joint probability by probability of world to condition on that world\n- Multiply conditional probability with prior to get joint\n\n### Probabilistic Inference and Rules\nKnow evidence variables, want to know probabilities of a certain \"query\" variable\n\nStart by calculating joint probability of query variable and evidence variables by summing over hidden/unobserved variables\n\nIf know probability of evidence variable, can then use the product rule (divide by probability of evidence variable), to get conditional probability\n\nChain rule is more general rule. Can always write any joint distribution as an incremental product of conditional distributions\n\nLeads to **Bayes rule**: $P(x|y) = \frac{P(y|x)}{P(x)}P(y)$\n\nVery useful since sometime know conditional probability for evidence variable given hidden but want to calculate probability of hidden given evidence (ex: Naive Bayes - know probability of word given class, want to know probability of class given word)\n\n### Probabilistic Language Models\nWant to be able to calculate probability of a sentence given words in it. useful for machine translation, spell check etc..\n\nLeads to probability of next word give words thus far\n\nNaive approach is to calculate joint distribution by using chain rule and multiplying conditional probabilities for full sequence of words.\n\nProblem is that this state space is huge! Don't have enough data, let alone enough compute power\n\nSolution is to make simplifying assumption that probability of each word is only conditional on the past *k* words. **Markovian assumption**, similar to MDP, where assumption was that transition function only depended on current state, not sequence of previous sates\n\nWith this simplifying assumption, we can calculate the probability of a sentence as the produce of the probabilities of all words in sentence, each conditioned on past k words\n\nN-gram model.\n\nConfusing, since unigram ⇒ k=0\n\nbigram = condition on past word\n\nEtc..\n\nn-gram means total of n words. condition on n-1 words.\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "- in Bayesian network, children are conditionally independent of all other nodes conditional on parent(s)\n",
        "- Bayesian networks are DAGs (no cycles)\n",
        "- For Bayesian network, can write joint probability as: $P(x_1,...x_n) = \\prod_{i=1}^{n}P(x_i|parents(X_i))$\n",
        "- to construct a Bayesian network, iterate over nodes in any order. When processing a node, make it have parents of all earlier nodes on which it depends\n",
        "    - better to order nodes with causes first, then effect. Leads to a sparser, more compact, graph. Easier to interpret.\n",
        "- D separation:\n",
        "    - question if evidence variable \"blocks\" or \"d-separates\", the two other variables\n",
        "        - undirected, so can “block” as child\n",
        "    - **Key idea**: evidence variable needs to block all paths between two variables in quesiton\n",
        "        - paths are directed, and can include parents\n",
        "- can mix discrete and continuous variables\n",
        "    - one strategy to discretize/bin continuous variables\n",
        "    - can also model as Gaussian, or non-parametric\n",
        "- logit or probit?\n",
        "    - for going from discrete to continuous (binary.)\n",
        "\"\"\"\n",
        "chapter13_3 = r\"\"\"\n",
        "- Enumeration algorithm for inference with Bayesian network\n",
        "$$ O(2^n) $$\n",
        "    - Very inefficient...\n",
        "    - Involves summing up to evidence variables, then multiplying?...\n",
        "- Variable elimination algorithm: more efficient\n",
        "    - bottom up approach - dynamic programming.\n",
        "    - Avoid repeated calculation\n",
        "- In general, Bayes net inference is \\#P hard?\n",
        "    - Need to compute number of 3 SAT solutions?...\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "### Review on Independence\n",
        "Conditional independence vs absolute independence \n",
        "\n",
        "Conditional more common. Two ways of writing conditional independence (similar to absolute independence)\n",
        "\n",
        "### Bayes Net Properties\n",
        "Arrows from parent to children. Causal chain\n",
        "\n",
        "Conditional on parents, children conditionally independent of all other variables (not true? need to condition on children and children’s parents also? Markovian blanket..\n",
        "\n",
        "**Common cause** -children independent of each other given parent\n",
        "\n",
        "Observed evidence \"block\"s influence of other variables\n",
        "\n",
        "**Common effect:** two parents. Absolute independence, but **not** conditionally independent given common child. Knowing child gives us more information about parents.\n",
        " \n",
        "### Reachability & Path\n",
        "Given three cases (common cause, common effect,  and causal chain), can calculate if any two variables in Bayesian network are independent given some evidence variables\n",
        "\n",
        "Look at all paths (undirected) between the two variables. Check all triples. If all triples are active, then path is active. If a path is active, then variables are not independent given evidence variables (relationship not \"blocked\")\n",
        "\n",
        "**Active triples**\n",
        "\n",
        "- Cause chain with no evidence (all hidden?)\n",
        "- Common parent, no evidence\n",
        "- Common effect, effect is observed (evidence)\n",
        "- or any descendant of common child is observed\n",
        "\n",
        "**Inactive triples:**\n",
        "\n",
        "- Causal china where middle node is evidence/observed (blocks influence)\n",
        "- Common parent, where parent is observed/evidence variable (blocks influence_\n",
        "- common child, child is not observed (and no descents of common child are observed)\n",
        "    - influence can’t “flow” through child if not observed\n",
        "\n",
        "### D-Seperation Algorithm\n",
        "Check all (undirected) paths between two variables. Check all tupleson path. If all triples active, then path active. If a single path active, then independence not guaranteed (doesn't mean NOT independent, just not guaranteed). If all paths inactive, then independence guaranteed, conditional on evidence\n",
        "\n",
        "### Inference\n",
        "Inference by enumeration:\n",
        "\n",
        "- Evidence variables\n",
        "- Query variables\n",
        "- Hidden variables\n",
        "\n",
        "Want to know conditional (posterior) probability of query variable given evidence\n",
        "\n",
        "Step 1: select all entries from joint distribution consistent with the evidnce\n",
        "\n",
        "Step 2: sum out H (hidden variable) to get joint probability\n",
        "\n",
        "Can write out probabilities based on independence assumptions coded into Bayes Ne\n",
        "\n",
        "Worst case O(2^n) if binary variables. Worse if more than binary?\n",
        "\n",
        "Variable elimination is more efficient?\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 151,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6d4951b5-6803-4b25-cf44-e6c06b3e7373"
      },
      "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": 152,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- in Bayesian network, children are conditionally independent of all other nodes conditional on parent(s)\n- Bayesian networks are DAGs (no cycles)\n- For Bayesian network, can write joint probability as: $P(x_1,...x_n) = \\prod_{i=1}^{n}P(x_i|parents(X_i))$\n- to construct a Bayesian network, iterate over nodes in any order. When processing a node, make it have parents of all earlier nodes on which it depends\n    - better to order nodes with causes first, then effect. Leads to a sparser, more compact, graph. Easier to interpret.\n- D separation:\n    - question if evidence variable \"blocks\" or \"d-separates\", the two other variables\n        - undirected, so can “block” as child\n    - **Key idea**: evidence variable needs to block all paths between two variables in quesiton\n        - paths are directed, and can include parents\n- can mix discrete and continuous variables\n    - one strategy to discretize/bin continuous variables\n    - can also model as Gaussian, or non-parametric\n- logit or probit?\n    - for going from discrete to continuous (binary.)\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- Enumeration algorithm for inference with Bayesian network\n$$ O(2^n) $$\n    - Very inefficient...\n    - Involves summing up to evidence variables, then multiplying?...\n- Variable elimination algorithm: more efficient\n    - bottom up approach - dynamic programming.\n    - Avoid repeated calculation\n- In general, Bayes net inference is \\#P hard?\n    - Need to compute number of 3 SAT solutions?...\n\n\n## Module 11 Lecture Notes\n\n### Review on Independence\nConditional independence vs absolute independence \n\nConditional more common. Two ways of writing conditional independence (similar to absolute independence)\n\n### Bayes Net Properties\nArrows from parent to children. Causal chain\n\nConditional on parents, children conditionally independent of all other variables (not true? need to condition on children and children’s parents also? Markovian blanket..\n\n**Common cause** -children independent of each other given parent\n\nObserved evidence \"block\"s influence of other variables\n\n**Common effect:** two parents. Absolute independence, but **not** conditionally independent given common child. Knowing child gives us more information about parents.\n \n### Reachability & Path\nGiven three cases (common cause, common effect,  and causal chain), can calculate if any two variables in Bayesian network are independent given some evidence variables\n\nLook at all paths (undirected) between the two variables. Check all triples. If all triples are active, then path is active. If a path is active, then variables are not independent given evidence variables (relationship not \"blocked\")\n\n**Active triples**\n\n- Cause chain with no evidence (all hidden?)\n- Common parent, no evidence\n- Common effect, effect is observed (evidence)\n- or any descendant of common child is observed\n\n**Inactive triples:**\n\n- Causal china where middle node is evidence/observed (blocks influence)\n- Common parent, where parent is observed/evidence variable (blocks influence_\n- common child, child is not observed (and no descents of common child are observed)\n    - influence can’t “flow” through child if not observed\n\n### D-Seperation Algorithm\nCheck all (undirected) paths between two variables. Check all tupleson path. If all triples active, then path active. If a single path active, then independence not guaranteed (doesn't mean NOT independent, just not guaranteed). If all paths inactive, then independence guaranteed, conditional on evidence\n\n### Inference\nInference by enumeration:\n\n- Evidence variables\n- Query variables\n- Hidden variables\n\nWant to know conditional (posterior) probability of query variable given evidence\n\nStep 1: select all entries from joint distribution consistent with the evidnce\n\nStep 2: sum out H (hidden variable) to get joint probability\n\nCan write out probabilities based on independence assumptions coded into Bayes Ne\n\nWorst case O(2^n) if binary variables. Worse if more than binary?\n\nVariable elimination is more efficient?\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "- machine learning can be applied to various parts of an agent:\n",
        "    - map from current state to action\n",
        "    - extract info from perceptions (image processing?)\n",
        "    - evolution of the world. Time series\n",
        "    - Utilities about desirability of different states\n",
        "    - Etc..\n",
        "- Classification vs regression\n",
        "    - called regression from Galton 1886 paper; regression to the mean. Confusing, misnomer\n",
        "- supervised vs unsupervised\n",
        " \"\"\"\n",
        "chapter19_2 = \"\"\"\n",
        "- label/output generated from features/inputs by function\n",
        "- want to choose a hypothesis function h that approximates f\n",
        "- can also call h a model\n",
        "- draw h from an hypothesis space\n",
        "- choose hypothesis space based on expert knowledge or hyperparameter tuning\n",
        "- ideally want a consistent hypothesis (always matches ground truth), but impossible. So settle for best approximation\n",
        "- bias variance tradeoff:\n",
        "    - bias is tendency for predictive hypothesis to differ from expected value when averaged over many training sets\n",
        "        - often comes from having restricted form, such as linear when function should be polynomial\n",
        "    - variance is amount of change in hypothesis due to fluctuation in the training data\n",
        "        - higher order polynomial can overfit\n",
        "    - prefer simplest hypothesis that is powerful to explain the data\n",
        "    - in other words, want hypothesis with higher prior probability\n",
        "- \n",
        "\"\"\"\n",
        "chapter19_3 = r\"\"\" \n",
        "- choose variable to split on in greedy fashion\n",
        "- not binary split\n",
        "- pruning\n",
        "    - look at splits that only have leaf nodes as children, and decide whether to drop split\n",
        "    - under null hypothesis (that attribute is irrelevant and splits have same proportion as as overall dataset), summed difference between actual and observed \\\n",
        "    false/negative is distributed according to chi-squared\n",
        "    - can do test to see if statistically different\n",
        "    - if not, then prune\n",
        "    - do pruning at end, cause sometimes need to make split with low information gain to get better split later\n",
        "        - example: XOR function. First split doesn't lead to any information gain. Second one is very good.\n",
        "- choose to split on feature with largest information gain\n",
        "    - define information gain as decrease in cross entropy\n",
        "    - Cross entropy: $-\\sum_{k}P(v_k) \\log_2 P (v_k)$\n",
        "        - highest when probabilities are all equal.\n",
        "        - is 0 when one prob is 1, and all else are 0\n",
        "    - for binary: $B(q) = -(q \\log_2 q + (1-q) \\log_2(1-1))$\n",
        "    - $Remainder(A) = \\sum_{k=1}^{d} \\frac{p_k + n_k}{p + n} B(\\frac{p+k}{p_k + n_k})$\n",
        "        - p and n are number of positive and negative examples in whole datasets\n",
        "        - so weighting cross entropy at every split by proportion of examples with that value for feature\n",
        "    - $Gain(A) = B(\\frac{p}{p + n}) - Remainder(A)$\n",
        "        - A is attribute under consideration\n",
        "- can use decision trees for continuous variables also\n",
        "    - if input, then do a range (split point test )\n",
        "    - if output, then CART: do linear regression at end, for every leaf.\n",
        "- can use trees to impute missing values\n",
        "\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\"\n",
        "- always assume that future examples will be like past (stationary assumption)\n",
        "    - and that each sample is independent of previous examples\n",
        "    - put toegehter, get i.i.d (independence and identically distributed) assumption\n",
        "- training, test, and validation/dev set\n",
        "    - if don't have enough data for validation/dev set, can use k fold cross validation\n",
        "    - hold out 1/k th of data to tests result of training, do training leaving out all k different sets\n",
        "    - can do leave out out one cross validation\n",
        "    - always need test set\n",
        "- some models such as decision trees (or SVMs? higher order polynomials), more prone to overfitting\n",
        "    - decrease in accuracy on validation set\n",
        "    - others, such as random forest or neural net, less prone to over-fitting\n",
        "    - model that fits all training data has interpolated or memorized the training data: likely overfitting\n",
        "- better to use a general loss function, such as log loss, compared to accuracy\n",
        "- regularize: increase loss for more complex functions\n",
        "- can do grid search, random search, Bayesian optimization or genetic algorithms (population based training) to find optimal hyperparameters\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\"\n",
        "- Probably approximate learning algorithms (PAC)\n",
        "    - any algorithm that returns hypotheses that are probably approximately correct (in large number of samples)\n",
        "- decision lists are an example....\n",
        " \"\"\"\n",
        "chapter19_6 = \"\"\"\n",
        "- linear regression: loss is sum of squared error\n",
        "- can solve for weights by setting (partial) derivatives to 0\n",
        "- but sometimes easier (when large matrices?) to solve using gradient descent\n",
        "    - can do stochastic/mini-batch gradient descent, faster, since calculation time decreases linearly, but error increases in squared manner?\n",
        "- With multivariate regression, need worry to about overfitting\n",
        "- can do regularization, l1 or l2\n",
        "- l1 leads to sparser weights\n",
        "- linear classifier with hard threshold (for classification) = perceptron\n",
        "- better to use logistic/sigmoid function\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "- Naive bayes (multinomial)\n",
        "    - calculate conditional probability of class given document, using Bayes rule to transform conditional probability of document give class\n",
        "- Bag of words: position doesn't matter\n",
        "- naive bayes assumption: features independent of each other, given class\n",
        "    - so can multiply\n",
        "- log space to avoid overflow\n",
        " \"\"\"\n",
        "slp_chapter4_2 = \"\"\" \n",
        "- can estimate probabilities of features (words), using counts from corpus\n",
        "- but need Laplace (add-one) smoothing to avoid 0 probabilities\n",
        "    - More common in naive bayes than language modelling\n",
        "- ignore unkown words at testing time\n",
        "- don't need to worry about stop words - can include\n",
        "    - most of time, doesn't improve performance\n",
        "-  \n",
        " \"\"\"\n",
        "slp_chapter4_3 = \"\"\"\n",
        "- worked example\n",
        " \"\"\"\n",
        "slp_chapter4_4 = \"\"\"\n",
        "- Improvement for sentiment analysis:\n",
        "    - use binary presence as feature\n",
        "- can apply negation to next words to create different tokens\n",
        "- can use a sentiment lexicon to get sentiment value of words, if don't have from our data or whatever\"\"\"\n",
        "slp_chapter4_5 = \"\"\"\n",
        "- can use features other than words for classification. Example: ratio of text to image in email for spam detection\n",
        "- can just use byte ngrams (don't bother decoding unicode)\n",
        "    - good for language detection?\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_6 = \"\"\"\n",
        "- Can use naive bayes to estimate probability of sentence - see which sentence is more likely given class\n",
        "    - But probably not very good results. Naive Bayes is better at classification than language modelling\n",
        " \"\"\"\n",
        "slp_chapter4_7 = \"\"\" \n",
        "- human labelled = gold labels\n",
        "- confusion matrix\n",
        "- accuracy not a good metric a lot of time (imbalance classes)\n",
        "- prefer precision (what % of predicted positives are actually positive?) and recall (what % of labelled positives have been correctly predicted?)\n",
        "- f2 = harmonic mean of precision and recall = 2 * P * R / (P + R)\n",
        "    - lower than arithmetic\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_8 = \"\"\"\n",
        "- Easy to do confusion matrix for multiple classes\n",
        "- harder to do recall (what % of labelled positives correctly predicted) and precision (what % of predicted positive are actually positive)\n",
        "- can macro average: calculate precision and recall individually for each class and average\n",
        "- or micro average: pool number of tp, fp, and fn then calculate precision and recall from these pooled numbers \"\"\"\n",
        "slp_chapter4_9 = \"\"\"\n",
        "- can use bootstrapping to compare different models\n",
        "    - very similar to k-fold validation\n",
        "    - but compare different models on same data\n",
        "    - and draw with replacement..\n",
        " \"\"\"\n",
        "slp_chapter4_10 = \"\"\"\n",
        "don't want to classify a sentence as toxic just because it reference homosexuality, women or uses African American vernacular\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = r\"\"\"\n",
        "### Classification Task\n",
        "GRE uses machine learning to grade essays. Compares with one human grader. A second human grader reviews if two scores don't match.\n",
        "\n",
        "Model based classification build a model (Baye's net) where labels and features are random values. relationships between random values. Estimate. Then query to get distribution of label conditional on features.\n",
        "\n",
        "### Naive Bayes\n",
        "Naive Bayes assumes that features are independent of each other conditional on label\n",
        "\n",
        "$P(Y|F_1, F2, ... F_n)  \\propto P(Y) \\prod_{i} P(F_i|Y)$\n",
        "\n",
        "$\\propto$ means \"proportional to\"\n",
        "\n",
        "Above is in fact joint? If divide by probability of features, then condition Y on features\n",
        "\n",
        "Can easily P(Y) and conditional probabilities of features from data....\n",
        "\n",
        "For text classifier, assume that each word is identically distributed?\n",
        "\n",
        "### Basic Concepts in ML\n",
        "- split data into training, test, and dev/validation/held out set\n",
        "    - tune hyperparameters on dev/validation\n",
        "- Overfitting in Naive bayes: low/0 probability for feature never seen for class\n",
        "    - Can fix with laplacian smoothing: add 1, or add k\n",
        "    - Can figure out how much to add based on validation set\n",
        "- Backoff/interpolation works well too\n",
        "    - Remove last context variable from probability, weight...\n",
        "- Maximum likelihood to estimate parameters from naive bayes\n",
        "    - just counting, empirical estimate\n",
        "- Can add new features to get better fit.\n",
        "- Need to compare results to baseline\n",
        "    - Majority class, or simple linear classifier\n",
        "    - can also compare to state of the art\n",
        "\n",
        "### Perceptron\n",
        "- Threshold; if dot product of weights and features greater than 0, then output 1 (\"True\" class)\n",
        "    - if less than 0, then output 0 (or maybe -1?)\n",
        "- Bias shifts thresholds\n",
        "- If wrong prediction, then add or subtract features to weight vector\n",
        "    - Add if actual class was 1, since this will increase dot product, more likely to be greater than 0\n",
        "    - Subtract if actual class was -1, since this will decrease dot product\n",
        "- If doing multi-class, then one perceptron per class\n",
        "    - Take class with highest value\n",
        "    - If wrong, add feature value to weights for real label, and subtract from wrong label\n",
        "    - Don't do anything if correct\n",
        "\n",
        "### Improvements on Perceptrons and SVMs\n",
        "- Can show that number of mistakes that perceptron algorithm makes during training is $\\leq \\frac{1}{\\gamma}$ where $\\gamma$ is the margin of the set of examples (normalized to be based on weight with l2 norm or l1),\n",
        "    - can think of margin as cosine between the example x and weight vector. Choose example to minimize margin. So ..\n",
        "- Written as $mistakes \\leq \\frac{kl}{\\delta^2}$ in slides\n",
        "- But problem is examples aren't linearly separably, then iterate forever.\n",
        "    - Also finds \"barely separating\" solutions: overfit to training.\n",
        "    - Can use validation/dev set to avoid overfitting\n",
        "- Can use MIRA = margin infused relaxation algorithm\n",
        "    - basically scale update based on how far off we were\n",
        "    - Also cap size of update\n",
        "    - Help converge faster and generalize better\n",
        "- SVM = support vector machine\n",
        "    - choose examples (support vectors) and try to maximize distance/margin between support vectors and separating hyperplane\n",
        "    - With SVM, can use \"kernel\" trick to calculate distance in higher dimensions space efficiently\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 153,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "befdedfa-1d9d-4d0e-9d89-adfba9bc1063"
      },
      "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 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 The Theory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 Linear Regression and Classification\", 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": 154,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n\n- machine learning can be applied to various parts of an agent:\n    - map from current state to action\n    - extract info from perceptions (image processing?)\n    - evolution of the world. Time series\n    - Utilities about desirability of different states\n    - Etc..\n- Classification vs regression\n    - called regression from Galton 1886 paper; regression to the mean. Confusing, misnomer\n- supervised vs unsupervised\n \n\n## AIMA Chapter 19.2 Supervised Learning\n\n- label/output generated from features/inputs by function\n- want to choose a hypothesis function h that approximates f\n- can also call h a model\n- draw h from an hypothesis space\n- choose hypothesis space based on expert knowledge or hyperparameter tuning\n- ideally want a consistent hypothesis (always matches ground truth), but impossible. So settle for best approximation\n- bias variance tradeoff:\n    - bias is tendency for predictive hypothesis to differ from expected value when averaged over many training sets\n        - often comes from having restricted form, such as linear when function should be polynomial\n    - variance is amount of change in hypothesis due to fluctuation in the training data\n        - higher order polynomial can overfit\n    - prefer simplest hypothesis that is powerful to explain the data\n    - in other words, want hypothesis with higher prior probability\n- \n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n \n- choose variable to split on in greedy fashion\n- not binary split\n- pruning\n    - look at splits that only have leaf nodes as children, and decide whether to drop split\n    - under null hypothesis (that attribute is irrelevant and splits have same proportion as as overall dataset), summed difference between actual and observed \\\n    false/negative is distributed according to chi-squared\n    - can do test to see if statistically different\n    - if not, then prune\n    - do pruning at end, cause sometimes need to make split with low information gain to get better split later\n        - example: XOR function. First split doesn't lead to any information gain. Second one is very good.\n- choose to split on feature with largest information gain\n    - define information gain as decrease in cross entropy\n    - Cross entropy: $-\\sum_{k}P(v_k) \\log_2 P (v_k)$\n        - highest when probabilities are all equal.\n        - is 0 when one prob is 1, and all else are 0\n    - for binary: $B(q) = -(q \\log_2 q + (1-q) \\log_2(1-1))$\n    - $Remainder(A) = \\sum_{k=1}^{d} \\frac{p_k + n_k}{p + n} B(\\frac{p+k}{p_k + n_k})$\n        - p and n are number of positive and negative examples in whole datasets\n        - so weighting cross entropy at every split by proportion of examples with that value for feature\n    - $Gain(A) = B(\\frac{p}{p + n}) - Remainder(A)$\n        - A is attribute under consideration\n- can use decision trees for continuous variables also\n    - if input, then do a range (split point test )\n    - if output, then CART: do linear regression at end, for every leaf.\n- can use trees to impute missing values\n\n\n\n## AIMA Chapter 19.4 Model Selection and Optimization\n\n- always assume that future examples will be like past (stationary assumption)\n    - and that each sample is independent of previous examples\n    - put toegehter, get i.i.d (independence and identically distributed) assumption\n- training, test, and validation/dev set\n    - if don't have enough data for validation/dev set, can use k fold cross validation\n    - hold out 1/k th of data to tests result of training, do training leaving out all k different sets\n    - can do leave out out one cross validation\n    - always need test set\n- some models such as decision trees (or SVMs? higher order polynomials), more prone to overfitting\n    - decrease in accuracy on validation set\n    - others, such as random forest or neural net, less prone to over-fitting\n    - model that fits all training data has interpolated or memorized the training data: likely overfitting\n- better to use a general loss function, such as log loss, compared to accuracy\n- regularize: increase loss for more complex functions\n- can do grid search, random search, Bayesian optimization or genetic algorithms (population based training) to find optimal hyperparameters\n\n\n## AIMA Chapter 19.5 The Theory of Learning\n\n- Probably approximate learning algorithms (PAC)\n    - any algorithm that returns hypotheses that are probably approximately correct (in large number of samples)\n- decision lists are an example....\n \n\n## AIMA Chapter 19.6 Linear Regression and Classification\n\n- linear regression: loss is sum of squared error\n- can solve for weights by setting (partial) derivatives to 0\n- but sometimes easier (when large matrices?) to solve using gradient descent\n    - can do stochastic/mini-batch gradient descent, faster, since calculation time decreases linearly, but error increases in squared manner?\n- With multivariate regression, need worry to about overfitting\n- can do regularization, l1 or l2\n- l1 leads to sparser weights\n- linear classifier with hard threshold (for classification) = perceptron\n- better to use logistic/sigmoid function\n\n\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n- Naive bayes (multinomial)\n    - calculate conditional probability of class given document, using Bayes rule to transform conditional probability of document give class\n- Bag of words: position doesn't matter\n- naive bayes assumption: features independent of each other, given class\n    - so can multiply\n- log space to avoid overflow\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \n- can estimate probabilities of features (words), using counts from corpus\n- but need Laplace (add-one) smoothing to avoid 0 probabilities\n    - More common in naive bayes than language modelling\n- ignore unkown words at testing time\n- don't need to worry about stop words - can include\n    - most of time, doesn't improve performance\n-  \n \n\n## SLP Chapter 4.3 Worked Example\n\n- worked example\n \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n- Improvement for sentiment analysis:\n    - use binary presence as feature\n- can apply negation to next words to create different tokens\n- can use a sentiment lexicon to get sentiment value of words, if don't have from our data or whatever\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n- can use features other than words for classification. Example: ratio of text to image in email for spam detection\n- can just use byte ngrams (don't bother decoding unicode)\n    - good for language detection?\n\n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n- Can use naive bayes to estimate probability of sentence - see which sentence is more likely given class\n    - But probably not very good results. Naive Bayes is better at classification than language modelling\n \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n \n- human labelled = gold labels\n- confusion matrix\n- accuracy not a good metric a lot of time (imbalance classes)\n- prefer precision (what % of predicted positives are actually positive?) and recall (what % of labelled positives have been correctly predicted?)\n- f2 = harmonic mean of precision and recall = 2 * P * R / (P + R)\n    - lower than arithmetic\n\n \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n- Easy to do confusion matrix for multiple classes\n- harder to do recall (what % of labelled positives correctly predicted) and precision (what % of predicted positive are actually positive)\n- can macro average: calculate precision and recall individually for each class and average\n- or micro average: pool number of tp, fp, and fn then calculate precision and recall from these pooled numbers \n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n- can use bootstrapping to compare different models\n    - very similar to k-fold validation\n    - but compare different models on same data\n    - and draw with replacement..\n \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\ndon't want to classify a sentence as toxic just because it reference homosexuality, women or uses African American vernacular\n\n## Module 12 Lecture Notes\n\n### Classification Task\nGRE uses machine learning to grade essays. Compares with one human grader. A second human grader reviews if two scores don't match.\n\nModel based classification build a model (Baye's net) where labels and features are random values. relationships between random values. Estimate. Then query to get distribution of label conditional on features.\n\n### Naive Bayes\nNaive Bayes assumes that features are independent of each other conditional on label\n\n$P(Y|F_1, F2, ... F_n)  \\propto P(Y) \\prod_{i} P(F_i|Y)$\n\n$\\propto$ means \"proportional to\"\n\nAbove is in fact joint? If divide by probability of features, then condition Y on features\n\nCan easily P(Y) and conditional probabilities of features from data....\n\nFor text classifier, assume that each word is identically distributed?\n\n### Basic Concepts in ML\n- split data into training, test, and dev/validation/held out set\n    - tune hyperparameters on dev/validation\n- Overfitting in Naive bayes: low/0 probability for feature never seen for class\n    - Can fix with laplacian smoothing: add 1, or add k\n    - Can figure out how much to add based on validation set\n- Backoff/interpolation works well too\n    - Remove last context variable from probability, weight...\n- Maximum likelihood to estimate parameters from naive bayes\n    - just counting, empirical estimate\n- Can add new features to get better fit.\n- Need to compare results to baseline\n    - Majority class, or simple linear classifier\n    - can also compare to state of the art\n\n### Perceptron\n- Threshold; if dot product of weights and features greater than 0, then output 1 (\"True\" class)\n    - if less than 0, then output 0 (or maybe -1?)\n- Bias shifts thresholds\n- If wrong prediction, then add or subtract features to weight vector\n    - Add if actual class was 1, since this will increase dot product, more likely to be greater than 0\n    - Subtract if actual class was -1, since this will decrease dot product\n- If doing multi-class, then one perceptron per class\n    - Take class with highest value\n    - If wrong, add feature value to weights for real label, and subtract from wrong label\n    - Don't do anything if correct\n\n### Improvements on Perceptrons and SVMs\n- Can show that number of mistakes that perceptron algorithm makes during training is $\\leq \\frac{1}{\\gamma}$ where $\\gamma$ is the margin of the set of examples (normalized to be based on weight with l2 norm or l1),\n    - can think of margin as cosine between the example x and weight vector. Choose example to minimize margin. So ..\n- Written as $mistakes \\leq \\frac{kl}{\\delta^2}$ in slides\n- But problem is examples aren't linearly separably, then iterate forever.\n    - Also finds \"barely separating\" solutions: overfit to training.\n    - Can use validation/dev set to avoid overfitting\n- Can use MIRA = margin infused relaxation algorithm\n    - basically scale update based on how far off we were\n    - Also cap size of update\n    - Help converge faster and generalize better\n- SVM = support vector machine\n    - choose examples (support vectors) and try to maximize distance/margin between support vectors and separating hyperplane\n    - With SVM, can use \"kernel\" trick to calculate distance in higher dimensions space efficiently\n\n \n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = r\"\"\"\n",
        "- Naive Bayes is generative (makes use of conditional probalitty of seeing document based on class), whil logistic is distimaintve :\\\n",
        "learn probablity of class conditional on document directly\n",
        "-  $$\\sigma(z) = \\frac{1}{1 + e^{-z}}$$\n",
        "$$ 1- \\sigma(z) = \\sigma(-z)$$\n",
        "Need to manually add features (interactions) for logistic regreesion\n",
        "- generally losistic regression is better cause can handle correlated features, but Naive Bayes usually works well, especially on small data sets\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" \n",
        "Need a loss funtion (cross entropy) and optimization function (stochastic gradient descent) to learn weights\n",
        " \"\"\"\n",
        "slp_chapter5_3 = \"\"\" \n",
        "- loss defines how far our prediction is from true label\n",
        "$$p(y|x) = \\hat{y}^{y}(1 - \\hat{y})^{1-y}$$\n",
        "$$\\log p(y|x) = y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})$$\n",
        "Since want to maximize conditional probablity, can take negative and minimize\n",
        "$$ CrossEntropyLoss = -[y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})]$$ \n",
        "\n",
        " \"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "- loss functoin is convext\n",
        "  - means that there is just one minimum,so can't get stuck in local minima\n",
        "- The gradient is a vecot moint in the direction of the gretst increase in a function\n",
        "- Is dervitaive of loss funtion with respect to weights, weighted by a learning rate\n",
        "- Want small learning weight, since don't want to move too much in single step\n",
        "- Each element of gradient vector is partial derivative of loss function with respect to single feature, evaluated at current weights and features.\n",
        "- Subtract this gradient vector from current weights, weighting by learning weight\n",
        "Partial deriviate for Cross Entropy with respect to weight j: $$[\\sigma(w \\cdot x + b) - y]x_j$$\n",
        "- Stochastic gradient descent makes update after each training example, while mini-batch use a batch of certain size\n",
        "  - take average over batch\n",
        "- If only update after seeing whole dataset, this is called batch training\n",
        " \"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "Regularizatoin: add penalty term to loss to penalize large norms on weight vector\n",
        "- L2 = ridge, l1 = lasso (sparser)\n",
        "- helps prevent overfitting and leads to better generalization\n",
        "\"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "- can do multinomial regression with softmax\n",
        "- just e^z \\ sum of all e^z\n",
        "- seperat wight vector for each class\n",
        "- loss is just negative of y^, where y^k is predicted proablity of correct class k\n",
        "- parital  derivative is similar to noirmal cross entrpoy?\n",
        "  - difference between true value for class k, which is 1, and predicted proabity, wieghted by input/feautre\n",
        " \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = r\"\"\" \n",
        "- neural unit: takes vector and produces real number\n",
        "- common activation functions: sigmoid, tanh and relue\n",
        " - tanh preferred over sigmoid since more \"squashing\", easier to differnetaite. Between -1 and 1. $y = \\frac{e^z - e^{-z}}{e^z + e^{-z}}$\n",
        " - very high values for sigmoid can \"saturated\" y, means that derivates are very close to 0\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_2 = \"\"\"\n",
        "- linear classifier can't model XOR function\n",
        "  - cause no linear seperator\n",
        "- but easy to do with a simple neural netowrk with 3 ReLU units\n",
        "- can't have linear activatino funciotn, just becomes a linear function.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_3 = \"\"\"\n",
        " - feed forward: no cycles and Fully connected (all outputs of previous layer input to every unit in next layer)\n",
        "   - misnomer: Multilyaer perceprtons\n",
        "   - supposedly perceptrons only linear, but in lectures, prof say perceprtons can have activation functions\n",
        "     - alothoug I suppoose that they do in a way, with thresholding leading to 1 or 0 (or -1?)\n",
        "- 3 layers: input, hidden and output\n",
        "  - don't usually count input in number of layers. So logisitc regresion is a one layer network\n",
        "- can represent whole layer as single weight matrix\n",
        "  - more efficinet for calculations\n",
        "- stack different layer = more representativeness\n",
        "- use sigmoid as output for classifier\n",
        "- easy to simplify bias by using a feature that always take value of 1\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_4 = \"\"\" \n",
        "- generally use word embeddings instead of n-grams/bag of words\n",
        "- \n",
        " \"\"\"\n",
        "slp_chapter7_5 = \"\"\"\n",
        "- Can use feedforward network for lanuage modelling (predicting next word), even if recurrent of transformer model generally preferred.\n",
        "- Have certain number of words we are conditgioning on\n",
        "- embed them\n",
        "- concatenate them into a single vector\n",
        "- apply a hidden layer with activation function\n",
        "- then softmax to get probabltiies over every word!\n",
        "  - that's a lot of words!\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_6 = \"\"\"\n",
        "- use same cross-entropy loss for classifciaiotn\n",
        "- use backward differentation\n",
        "- Use a graph to model relationships between different units\n",
        "- Apply chain rule: Derivative of function f(g) with respect to x is df/dg * dg/dx\n",
        "- So in \"backwards pass\", calcualte derviative of first, output, unit first with respect to loss (is one), then go backwards, brining info from further up the line\n",
        "- optimiization is non convex. Some best practices:\n",
        "  - drop out for refgualtization\n",
        "  - initial to random werights, small, normalized\n",
        "  - adjust learning weight\n",
        "  - computaiton graph\n",
        " \"\"\"\n",
        "slp_chapter7_7 = \"\"\" \n",
        "- can \"freeze\" embedding layer to keep same, or fine trune and back peopograte error to update\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = r\"\"\"\n",
        "### Logistic Regresion\n",
        "Classifier components:\n",
        "\n",
        " 1. Feature Representation\n",
        "\n",
        "1. Classification function\n",
        "2. Objective function\n",
        "3. Algorithm for optimizing the classification function\n",
        "\n",
        "Sigmoid/logistic function:\n",
        "\n",
        " $y = \\frac{1}{1 + e^{-w \\cdot f}}$\n",
        "\n",
        "Can get features from lexicon, bag of words, etc...\n",
        "\n",
        "Need loss function( cross entropy) and way of adjusting weights to minimize loss (stochastic gradient descent)\n",
        "\n",
        "###Loss Function\n",
        "- Log loss (cross entropy) = negative log likelihood loss\n",
        "    - Better than MSE, since MSE is not convex for probability\n",
        "- If assign correct probability (1 if y = 1), then cross entropy loss is 0\n",
        "- Sum (average?) loss over all training examples\n",
        "\n",
        "### Stochastic Gradient Descent\n",
        "- gradient descent\n",
        "- Find slope\n",
        "- learning rate to control step size\n",
        "- Since cross entropy is convex (with sigmoid function), then won’t get stuck in lock min\n",
        "- Can generalize from single feature to multiple\n",
        "    - Have a derivative vector\n",
        "    - Partial derivatives\n",
        "- Use regularization to avoid over fitting\n",
        "    - Add penalty to loss function for having weights with high absolute values\n",
        "    - L2 = ridge; l1 = lasso\n",
        "- Multinational:\n",
        "    - softmax\n",
        "    - e^w_1 / (sum of e w_i; i from 1 to n)\n",
        "### Neural Networks\n",
        "- stack multiple neural “units” to form “deep”, many layered networks\n",
        "- Use non linear activation functions such as sigmoid, tanh or Relu\n",
        "- Feed forward network: multilayered, fully connected (usually), no cycles\n",
        "    - Sometimes called MLP\n",
        "- Same as before, need:\n",
        "    - loss function\n",
        "    - some algorithm for optimizing classification function (MLP)\n",
        "- Loss function is cross entropy again\n",
        "- Optimization algorithm is gradient descent\n",
        "- Form graph\n",
        "- Use chain rule\n",
        "- Start from right, calculate derivative with respect to loss\n",
        "- Then have what need for next layer\n",
        "- Need activation functions to be differentiable\n",
        "    - But RELU isn’t differentiable at 0...\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 155,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9901a362-dd93-4ca5-905d-d34b53cede32"
      },
      "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": 156,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n- Naive Bayes is generative (makes use of conditional probalitty of seeing document based on class), whil logistic is distimaintve :\\\nlearn probablity of class conditional on document directly\n-  $$\\sigma(z) = \\frac{1}{1 + e^{-z}}$$\n$$ 1- \\sigma(z) = \\sigma(-z)$$\nNeed to manually add features (interactions) for logistic regreesion\n- generally losistic regression is better cause can handle correlated features, but Naive Bayes usually works well, especially on small data sets\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nNeed a loss funtion (cross entropy) and optimization function (stochastic gradient descent) to learn weights\n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \n- loss defines how far our prediction is from true label\n$$p(y|x) = \\hat{y}^{y}(1 - \\hat{y})^{1-y}$$\n$$\\log p(y|x) = y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})$$\nSince want to maximize conditional probablity, can take negative and minimize\n$$ CrossEntropyLoss = -[y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})]$$ \n\n \n\n## SLP Chapter 5.4 Gradient Descent\n\n- loss functoin is convext\n  - means that there is just one minimum,so can't get stuck in local minima\n- The gradient is a vecot moint in the direction of the gretst increase in a function\n- Is dervitaive of loss funtion with respect to weights, weighted by a learning rate\n- Want small learning weight, since don't want to move too much in single step\n- Each element of gradient vector is partial derivative of loss function with respect to single feature, evaluated at current weights and features.\n- Subtract this gradient vector from current weights, weighting by learning weight\nPartial deriviate for Cross Entropy with respect to weight j: $$[\\sigma(w \\cdot x + b) - y]x_j$$\n- Stochastic gradient descent makes update after each training example, while mini-batch use a batch of certain size\n  - take average over batch\n- If only update after seeing whole dataset, this is called batch training\n \n\n## SLP Chapter 5.5 Regularization\n\nRegularizatoin: add penalty term to loss to penalize large norms on weight vector\n- L2 = ridge, l1 = lasso (sparser)\n- helps prevent overfitting and leads to better generalization\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n- can do multinomial regression with softmax\n- just e^z \\ sum of all e^z\n- seperat wight vector for each class\n- loss is just negative of y^, where y^k is predicted proablity of correct class k\n- parital  derivative is similar to noirmal cross entrpoy?\n  - difference between true value for class k, which is 1, and predicted proabity, wieghted by input/feautre\n \n\n## SLP Chapter 7.1 Units\n \n- neural unit: takes vector and produces real number\n- common activation functions: sigmoid, tanh and relue\n - tanh preferred over sigmoid since more \"squashing\", easier to differnetaite. Between -1 and 1. $y = \\frac{e^z - e^{-z}}{e^z + e^{-z}}$\n - very high values for sigmoid can \"saturated\" y, means that derivates are very close to 0\n\n\n\n## SLP Chapter 7.2 The XOR problem\n\n- linear classifier can't model XOR function\n  - cause no linear seperator\n- but easy to do with a simple neural netowrk with 3 ReLU units\n- can't have linear activatino funciotn, just becomes a linear function.\n\n \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n - feed forward: no cycles and Fully connected (all outputs of previous layer input to every unit in next layer)\n   - misnomer: Multilyaer perceprtons\n   - supposedly perceptrons only linear, but in lectures, prof say perceprtons can have activation functions\n     - alothoug I suppoose that they do in a way, with thresholding leading to 1 or 0 (or -1?)\n- 3 layers: input, hidden and output\n  - don't usually count input in number of layers. So logisitc regresion is a one layer network\n- can represent whole layer as single weight matrix\n  - more efficinet for calculations\n- stack different layer = more representativeness\n- use sigmoid as output for classifier\n- easy to simplify bias by using a feature that always take value of 1\n\n \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n \n- generally use word embeddings instead of n-grams/bag of words\n- \n \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n- Can use feedforward network for lanuage modelling (predicting next word), even if recurrent of transformer model generally preferred.\n- Have certain number of words we are conditgioning on\n- embed them\n- concatenate them into a single vector\n- apply a hidden layer with activation function\n- then softmax to get probabltiies over every word!\n  - that's a lot of words!\n\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n- use same cross-entropy loss for classifciaiotn\n- use backward differentation\n- Use a graph to model relationships between different units\n- Apply chain rule: Derivative of function f(g) with respect to x is df/dg * dg/dx\n- So in \"backwards pass\", calcualte derviative of first, output, unit first with respect to loss (is one), then go backwards, brining info from further up the line\n- optimiization is non convex. Some best practices:\n  - drop out for refgualtization\n  - initial to random werights, small, normalized\n  - adjust learning weight\n  - computaiton graph\n \n\n## SLP Chapter 7.7 Training the neural language model\n \n- can \"freeze\" embedding layer to keep same, or fine trune and back peopograte error to update\n \n\n## Module 13 Lecture Notes\n\n### Logistic Regresion\nClassifier components:\n\n 1. Feature Representation\n\n1. Classification function\n2. Objective function\n3. Algorithm for optimizing the classification function\n\nSigmoid/logistic function:\n\n $y = \\frac{1}{1 + e^{-w \\cdot f}}$\n\nCan get features from lexicon, bag of words, etc...\n\nNeed loss function( cross entropy) and way of adjusting weights to minimize loss (stochastic gradient descent)\n\n###Loss Function\n- Log loss (cross entropy) = negative log likelihood loss\n    - Better than MSE, since MSE is not convex for probability\n- If assign correct probability (1 if y = 1), then cross entropy loss is 0\n- Sum (average?) loss over all training examples\n\n### Stochastic Gradient Descent\n- gradient descent\n- Find slope\n- learning rate to control step size\n- Since cross entropy is convex (with sigmoid function), then won’t get stuck in lock min\n- Can generalize from single feature to multiple\n    - Have a derivative vector\n    - Partial derivatives\n- Use regularization to avoid over fitting\n    - Add penalty to loss function for having weights with high absolute values\n    - L2 = ridge; l1 = lasso\n- Multinational:\n    - softmax\n    - e^w_1 / (sum of e w_i; i from 1 to n)\n### Neural Networks\n- stack multiple neural “units” to form “deep”, many layered networks\n- Use non linear activation functions such as sigmoid, tanh or Relu\n- Feed forward network: multilayered, fully connected (usually), no cycles\n    - Sometimes called MLP\n- Same as before, need:\n    - loss function\n    - some algorithm for optimizing classification function (MLP)\n- Loss function is cross entropy again\n- Optimization algorithm is gradient descent\n- Form graph\n- Use chain rule\n- Start from right, calculate derivative with respect to loss\n- Then have what need for next layer\n- Need activation functions to be differentiable\n    - But RELU isn’t differentiable at 0...\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 157,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 945
        },
        "outputId": "44ca86f1-f3a2-478b-880d-ba00e1e670f6"
      },
      "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": 158,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T3cm1WV542_a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4ba4db8c-1946-44b5-9d7e-e410d3922c06"
      },
      "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": 159,
      "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\n- Expected utility is sum of utilities for being in a given state, weighted by probability that the state occurs\n- Rational agent should try and maximize expected utility\n    - leads to richer framework compared to goal directed agents (binary yes/no), or logical agents (can't deal with uncertainty)\n- But just a framework, need to operationalize\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\n- Preferences defined over lotteries\n    - probabilities attached to outcomes\n- **Orderability**: can always express preference\n- Transitivity\n- Continuity: can always weight two lotteries so that we are indifferent between weighted lottery and some other lottery\n- **Substitutability**: If indifferent between A and B, then can substitute in more complex lotteries without changing preference\n- **Monotonocity**: compound lotteries are equivalent to simpler lotteries\n- Can be proven that if agent has rational preferences, then can define a utility function U so that value of U obeys ordering of preferences\n- East to prove that agent's behavior won't change if positive affine transformation (linear) on utility\n    - equivalent to converting from fahrenheit to Celsius\n \n\n## AIMA Chapter 16.3 Utility Functions\n \n- standardized, normalized, lottery: assign value of 1 to best state, 0 to worse\n    - can then express any other lottery as combination of worse and best...\n- Money not same as utility - money has expected utility also\n    - utility increasing at slower rate with more money\n    - risk averse\n    - at low levels of money, stop being risk averse (nothing to lose). S shape\n- optimizer's curse: don't actually know expected utility, just estimate. Since choosing largest estimate, likely to have positive errors. As a result, almost always get lower utility than expected. Post-decision disappointment\n- Human's don't always express rational preferences\n    - People might have preference for certainty\n    - framing effect. anchoring effect\n    - people don't interpret word problems well\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- Markov decision process:\n    - Stochastic environment with Markovian transition model and additive rewards\n- develop policies, not action plans\n- optimal policy maximized expected utility\n- a policy that depends on time is call **non-stationery**\n- easier to work with infinite time horizon. Means that optimal policy doesn't depend on starting state.\n    - assumption of stationary preferences support additive discounting\n    Bellman equation:\n$$U(s) = \\max_{a \\in A(s)}\\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma U(s')]$$\n- can develop a Bellman equation for Q values also: $$Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma U(s')] = \\sum_{s'}P(s'|s,a)[R(s,a,s') + \\gamma \\max_{a' Q(s',a')}]$$\n- optimal policy indifferent to positive affine transformation of reward function $R(s, a, a')$\n- can \"shape\" reward so that optimal policy stays the same : $R(s, a, s') = R(s, a, s') + \\gamma \\sigma(s') - \\sigma(s')$\n    - can help with training\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- **Value iteration**: need to solve a Bellman equation for every state\n- Can't use linear programming, since max operation is not linear\n- **PROOF OF CONVERGENCE OF VALUE** iteration:\n    - contraction: function of one argument, when applied to two different arguments, returns two values that are closer together than original inputs\n    - single fixed point\n    - Bellman update is a contraction by a factor of $\\gamma$: fixed point is when it has converged..\n- estimated utility function of state can be wrong and still give correct policy\n- policy loss: most agent can lose from following policy based on incorrect estimated utility compared to optimal policy based on correct utility\n- policy iteration has two parts: policy evaluation and policy improvement\n    - **policy evaluation:** faster than value iteration, since not using max\n    - policy improvement needs to use max operation to find better policy.\n- if state space is large, then can't completely solve upfront\n    - can do some sort of modified expectimax, depth limited...\n \n\n## Module 8 Lecture Notes\n \n### 1.1: Introduction\nMDPs also have reward function, triggered at every time step $R(s, a, s')$\n\nDifference is that transition function is probabilistic $p(s'|s,a)$\n\nIt is markovian because probability of getting to next state only depends on previous/current state (and action), not on longer sequence\n\nMDPs also have reward function, triggered at every time step $R(s, a, s')$\n\nRewards are additive (summed)\n\n### Lessong 2: MDP Formulation\nMDPs are:\n\n- sequential\n- fully observable\n- stochastic\n- with additive rewards\n\nAKA: non-deterministic search problems. Can use exptimax search (like min-max, but with chance nodes)\n\nUnlike normal search, can't plan out all actions ahead of time. So instead planning actions, develop a policy $\\pi(s)$ that gives action based on state. $\\pi^{*}(s)$ is optimal policy\n\nAlso due to stochastic environment (transition function), can't maximize score, but rather maxizing expected score/utility.\n\nReward function shapes policy. Reward for non goal states usually slightly negative to encourage agent to prefer goal. If positive, then agent will never go for goal state, especially if infinite number of actions.\n\nUsually have infinite number of actions. Actually easier to calculate policy this way. If finite actions, then best policy would depend on number of remaining moves (ex: if positive rewards for all transitions, then go in circles till close to end, then go to goal for bigger reward.)\n\nUsually apply a discount term on reward to decrease value of future rewards and increase relative importance of closer ones. Logical, since closer to real life. Future rewards also more uncertain..\n\nDiscount term is $\\gamma$. Multiplied by reward. Between 0 and 1.\n\nhelps with convergence also, since don't need to search infinitely deep?\n\nIf have stationery preferences (preferences are stationery if rewards sequence A is preferred to reward sequence B and we add a reward r to start of each sequence, then we must still prefer A to B), then discounting (potentially equal to 1), is only logical utility way to define utilities\n\n### Lesson 3: MDP Examples\n- a state $s$ action $a$ pair (s,a) is called a q state\n- Q*(s,a) is s the expected utility starting off at state s, taking aciton a, thereafter acting optimally\n\n- V*(s) is the expected utility of starting in s and acting optimally\n\nRecursive definiton of value:\n\n$V*(s) = max_{a}Q*(s,a)$\n\n$Q^*(s,a) = \\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$\n\n$V^*(s,a) = \\max_{a}\\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V^(s')]$\n\n### Lesson 4:\nCan solve for $V^*(s)$ with dynamic programing\n\n$V_{k+1}(s,a) = \\max_{a}\\sum_{s'}T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n\n- Start at end step (bottom of expecti-max tree). All values are 0 because with no steps left, expected rewards sum to 0\n- Calculate next layer up...\n- Repeat until convergence\n- With gamma less than 1, know that we will converge\n- Complexity of each iteration: $O(S^2A)$ (S is number of state, A is number of actions...)\n\n**Hint!**  Proof of convergence likely on exam!!\n\n### Lesson 5: Policy Evaluation\nIf given a policy, can use to calculate values of states\n\nCan do recursively, like value iteration, or solve as system of linear equations?\n\nEven once have values, can't just choose action that will lead to next state with highest state, since transition function is probabilistic. Need to calculate expected values of actions\n\nBetter if we have Q values (mapping from state actions pairs to expected values). Can just choose action with highest Q value.\n\nImportant lesson: actions easier to select from q-values than values\n\n### Policy Iteration Algorithm\nValue iteration is slow O(S^2A). And don't actually need to  know values in order to decide on best action\n\nAlso, max at each state (best action), rarely changes, even if values change.\n\nInstead: do policy iteration for some fixed polucy until values converge\n\nThen update policy to be optimal based on new values\n\nRepeat until policy converges\n\nStill optimal! Can  converge much faster\n\nValue iteration updates both values implicitly policy. Don't explicitly track policy, but can extract (taking max)\n\nWith fixed policy, fast to update utilities\n\nGetting new policy is slower\n\nKeep doing until have new policy\n\n### Lesson 7: Maximum Expected Utility\nScales of utility:\n\n - normalized (between 0 and 1)\n\n - micromorts = chance of death in a million\n\n- quality adjusted years\n\nif have all 5 axioms of preference, then can represent with utility and agent will be raitonal trying to maximize expected utility.\n\n\n\n## Module 8 Definitions\n* **Proper policy** - Policy that is guaranteed to reach terminal state after finite number of steps\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- bandit problems = Markov reward process\n    - MDP: states are WIN/LOSS\n- Gittins index:\n    - sum of discounted rewards thous far divided by \"discounted time\"\n    - Value of arm in terms of its ability to deliver stream of timely rewards\n    - optimal policy for any bandit problem: pull arm with highest Gittins index, then update indexes\n        - problem is that we don't know $\\lambda$? (fixed reward we can get)\n        - solution is to solve a MDP that allows a \"restart\" to get sequence of rewards already obtained?\n        - don't understand...\n- Upper confidence bound: select arm with highest\n    - rather than highest mean, since want to explore...\n- bandit super process (BSP)\n- dominating policy\n    - relaxed version of problem?\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n\nmodel based vs model free reinforcement learning\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n**Passive reinforcement learning**\n\n- Direct utility estimation\n    - model free: don't learn transition function\n    - estimate values directly: sum of discounted rewards earned from that state onwards, averaged\n    - converges slowly\n    - Model free\n- adaptive dynamic programming\n    - estimate transition function: just maintain counts of what state end up in\n    - then use value iteration, or policy evaluation\n    - Model based\n- temporal difference learning:\n    - exponential moving average.\n    - Model free\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- tradeoff between exploration and exploitation\n    - similar to bandit problems\n- hard to get optimal exploration scheme\n- don't want to be greedy in terms of next move, but \"greedy in the limit of infinite exploration\" GLIE\n    - must try each action in each state an unbounded number of times to avoid having finite probability that an optimal action is missed\n    - this will guarantee that we can eventually yearn optimal policy\n- rather choosing random action with prob $\\epsilon$ and best action with $1-\\epsilon$, better to give higher weight to action not tried\n- this extra value also assigned during update, in order to propagate back higher value of unexplored state to entice exploration towards that state\n- sometime actions are irreversible (death). So might want to have exploration that avoid this\n    - bayesian reinforcement learning or robust control theory\n    - temporal difference q learning\n        - update q value as exponential moving average\n        - off policy learning..\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n- can use a linear function of features to approximate state\n- not only does this help with learning when many states, also helps to generalize to unseen states\n- update rules becomes: feature_weight = feature_weight + alpha * (actual reward - expected reward) * feature_value\n    - now update for observing a single transition between two states leads to an updates that affects expected values for all other states\n- can always model state as linear function by inventing non-linear functions, but can be tricky.\n    - Can use neural nets, but parameters might go to infinity. Use back prop, gradient descent, but very tricky\n- Catastrophic forgetting: learn too well. Stay in safe spot. If accidentally end up in unsafe spot, don't know what to do.\n- Can shape rewards, with a potential function that doesn't change optimal policy to give more reward to \"good\" intermediate actions\n- Alternative is hierarchical reinforcement learning. More general. Have series of \"choose\" functions\n- Example: keep away. Check if have ball or no, then choose appropriate action. Learn what action to choose.\n- Benefit is that intent (such who we are planning to pass to ) end up in state? Can shape reward?\n \n\n## Module 9 Lecture Notes\n\n### Introduction to Reinforcement Learning\n- **reinforcement learning:**\n    - don't know transition function or reward, need to learn\n    - know what state we're in.... and reward we just got\n- multi/two armed bandit: different payouts\n    - don't know probability of different rewards, need to learn.\n- Concepts:\n    - Exploration\n    - exploitation\n    - regret: deviance from optimal policy?\n    - sampling\n    - difficulty\n- General concepts:\n    - receive feedback in terms of rewards\n    - want to maximize expected rewards\n    - must learn through experience\n    - same as MDP, just don't know transition function $T(s,a,a')$  or reward function $R(s,a,s')$\n    - still developing policy\n    - \"online\" not \"offline\" learning/solution\n\n2 approaches:\n- Model based learning: learn reward and transition function, then solve using techniques for MDP (value iteration or policy iteration..\n-  model free: action-utility learning, or policy search\n\n### Passive Reinforcement Learning\n- start with a fixed policy\n- want to learn state values (utilities)\n    - then will develop policy\n- direct evaluation:\n    - compute values for each sate under policy\n    - act according to policy\n    - Then calculate sum of discounted rewards for each state\n    - Pros:\n        - easy to understand\n        - don't need to calculate R or T\n        - eventually will get right values?\n    - Cons:\n        - doesn't take constraints into account?\n        - connections between states - learn values separately for each state. so inefficient.\n- sample based policy evaluation?\n    - But can't guarantee that we will end up in certain state n times?\n\n### Temporal Difference Learning\n- learn V(s) by making iterative updates. Weighted by alpha. Exponential moving average\n- Policy still fixed; still doing evaluation\n- Model free\n- Not learning transition function\n- Good way of learning values\n- But won't be able to extract policy, since don't have transition function...\n- Better to learn Q values, rather than values\n\n### Active Reincforcement Learning (Q-Learning)\n- update Q values iteratively, weighted average,, fashion, like temporal learning\n- off policy learning, since updating q values, based on max, even if following policy that is not optimal\n- Q-learning converges to optimal policy\n- In limit, doesn't matter how you select action\n- Caveats:\n    - have to explore enough\n    - Have to make learning rate small enough, but not decrease too fast\n\n### Exploration vs Exploitation\nFor active learning, different ways of deciding what action to take. Called exploration function..\n\nCan take best action (highest Q value), but might not lead to optimal policy, since won't explore new states. this is called greedy approach\n\nCan just flip coin, with small probability epsilon , act randomly, and with 1- epsilon, take best action ($\\epsilon$ greedy). issue is that we keep on taking actions we know are bad.\n\nAlternative is to give bonus for unexplored actions/states. can give fixed bonus k to estimate, divide k by n, number of times taken. So large bonus when unexplored, decline more times explored\n\n**Regret** is a measure of total cost of mistakes : the difference between expected rewards, including youthful suboptimal, and optimal expected rewards\n\nWant to minimize regret; need to learn optimally, not just learn optimal policy\n\nEx: random exploration and epsilon functions both end up with same policy, but random exploration higher regret.\n\n### Approximate Q-Learning\nCan express value or q value as linear function, to help generalize\n\nHave features, Learn weights\n\nUpdate weights, rather than exact q values\n\nw_i ← w_i + alpha[difference] f_i(s,a) \n\nf is feature...\n\nFormal justification: online least squares. if something bad happens \"blame\" large active features. If good, then \"credit\" large active features\n\n\n \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- like logical propositions, in probability, statements either true or false\n    - but probabilities represent confidence given ignorance/laziness of all factors. Just take what we know into account\n- decision theory combines probability theory and utility theory\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- Associate each world with a probability\n- all prob of all words sum to one\n- each prob greater than equal to 0\n- set of worlds = event/proposition\n- probability of a event = sum of probabilities of its worlds\n- conditional/posterior probability vs unconditional probabilities (prior)\n- only draw conclusions from conditional probabilities when don't have further evidence. Otherwise, incorporate further evidence\n- going from joint to conditional probability using product rule\n- random variables map from domain of possible worlds to a possible range\n- if range is 1/0, then Bernoulli RV\n- **Probability density function (PDF)**: probability that variable takes on value in certain range\n    - for continuous variables\n    - for points, PDF give probability that X falls in arbitrarily small region beginning at x, divided by size of region. Doesn't give probability that X = x, since actual prob is 0, infinitesimal.\n    - Density function measured in units, inverse of normal units. So for temperature, units are 1/C (Celsius)\n- joint probability\n    - can sum out the variable we don't care about to go from joint to single\n- Axioms (Komlograv’s):\n    - inclusion exclusion principal: probability(A or B) = P(A) + P(B) - P(A and B)\n    - P(a) = 1 - P( not a)\n    - if don’t follow axioms when stipulating probabilities, possible to formulate set of bets based on probabilities that opponent always wins money, and you always lose money\n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- want to get posterior probability for a query variable given evidence\n- sum to get marginal/unconditional probability from full joint probability distribution (table form)\n    - called marginalization/summingout\n- use logic of product rule get conditional from joint by dividing\n    - quotient (denominator) called normalization term, alpha. Makes certain probabilities sum to 1\n- Marginalization with many variables doesn't work well (O2^n) time.\n- need independence assumptions to make simpler..\n\n\n## AIMA Chapter 12.4 Independence\n\na and b are independent if $P(a|b) = P(a)$ or $P(b|a) = P(b)$ or $P(a \\land b) = P(a)P(b)$\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n- Sometimes know prior probability of effect, prior probability of cause and conditional probability of effect given cause, but want conditional probability of cause given effect\nCan apply Baye's rule:\n$$P(Y|X) = \\frac{P(X|Y)P(Y)}{P(X)}$$\n**Conditional independence**: A and B are conditionally independent on C if: $P(A, B|C) = P(A|C)P(B|C)$ or $P(A|B,C) = P(A|C)$ or $ P(B|A,C) = P(B|C)$\n- for n evidence variables that conditional independent on query variable, the size of the representation grows as O(n) instead of O(2^n)\n    - Means that conditional independence helps reduce problem tractable size. Conditional independence much more common/realistic than absolute independence\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- Naive Bayes model assumes that all effect variables are conditionally independent given cause\n- Want to know probability of cause given effect\n- can use Bayes rule: $$P(Cause|e_1,,e_2....e_n) = P(Cause)\\prod_{i}P(e_i|Cause) * \\alpha$$\nwhere $\\alpha$ is scaling factor. Don't actually need to calculate scaling factor. Just take cause/class with highest probability\n- For text classifier, effects are word. Y is label of text\n- Need to use Laplacian smoothing to account for words that haven't been seen.\n- Calculate in log space, since can use sums instead of multiplying (low values)\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n- can use probability to check for breezes instead of logic\n- query variable is if breeze in certain square, conditional on what we know\n- breezes conditionally independent on what we know (frontier and query variables)\n \n\n## SLP Chapter 3.1 N-Grams\n\n- ngrams\n- Markovian assumption\n    - Decent approximation\n- Apply chain rule\n- normalize - Maximum Likelihood Estimation\n    - to get conditional, sum counts of n-gram (next word and context), divide by count of context\n- use log probabilities\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n\n- training set\n- test set (hod out)\n- dev set = validation set\n- **perplexity of a sentence**: $P(w_{1}w{2}...w_{N})^{-\\frac{1}{N}} = (\\prod_{i=1}\\frac{1}{P(w_i|w_{i-1})})^{\\frac{1}{N}}$\n    - want lower perplexity\n        - basically geometric mean of inverse probabilities..\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n To generater sentence:\n- assign each word a number between 0 and 1, based on probablity (mightr be conitonal on context /n-grams)\n- nmber is such between prebious and this word, inerval is probalbityt\n- generate random number betweon 0 anbd 1 anbd eslect\n- sparsity anb 0 words:\n  - can have an <UNK> token\n- perxpl;icites should only be compared across language models with the same vocabularies\n  - otherwise, could achieve low probablity by choosing a small vocabularly and assigning the unknown word a high probablity\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n \n- assign each word a number between 0 and 1, based on probability (might be cognitional on context /n-grams)\n    - number is such between that difference between previous word’s number and this word’s number is probability of this word\n- generate random number between 0 and 1 and select the corresponding word\n- sparsity and 0 words:\n    - can have use an <UNK> token\n- perplexities  should only be compared across language models with the same vocabularies\n    - otherwise, could achieve low probability by choosing a small vocabulary and assigning the unknown word a high probability\n \n\n## SLP Chapter 3.5 Smoothing\n \n- Laplacian smoothing: add 1 to each count. Can adjust just numerator by normalizing. Adjust count\n    - Adjust counts makes it so that counts add up original total, even after adding one to all vocab\n- Add k smoothing: like laplace, but add less than 1\n- useful for text classification, but bad for language modelling (generation?): high variances\n- backoff: if using context of 3 words, but no examples for 3 words, reduce to looking at 2 words.\n    - ie: use less context\n- interpolation: always mix probabilities from n grams of different lengths\n    - can give linear weight to probability from context of different length\n    - can give higher weights to contexts with more counts\n    - can use a test set to get weights\n    - similar to laplacian smoothing, need to discount probability of higher order n grams to \"save probability mass\" for lower\n    - otherwise, sum of probabilities would be greater than 1\n        - backoff with discounting called Katz backoff\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n**Stupid backoff**: backoff, but use just a fixed discount. Means that probabilities don't sum to one.\n\nWorks well for large models/corpus/vocabs\n\nWant to discount lower order, since otherwise probabilities will be too high (since see lower order contexts more often ) \n\n## Module 10 Lecture Notes\n \n### Review on Probablities\n- Many different worlds (outcomes)\n- Collection of outcomes = events\n- Random variables track something about outcome/world\n- Observed variables = evidence\n    - can condition on these\n- Unobserved variables = states\n    - want to calculate probability for these\n- Model = what agent knows about relationships between observed and unobserved variables\n- Better than logical reasoning\n    - Even if can't say for sure if square in wumpus world is clear, can still reason about it (e.g. low probability)\n- P(w) associates probablity with each world\n- Random variables RV: Rain = it is raining in this world\n- sum of probability is one, greater than equal to 0..\n\n### Distributions\n- **Joint distribution:** probability of all happening together. Example P(Rain=is raining, Sun=is shining), can also write P(x_1, x_2..._)\n- Can have table of probabilities: is a probability distribution\n    - Need to sum to one\n- Can calculate probability of an event by summing\n- **Marginalization**: combine collapsed rows by summing\n- Conditional probabilities: divide joint probability by probability of world to condition on that world\n- Multiply conditional probability with prior to get joint\n\n### Probabilistic Inference and Rules\nKnow evidence variables, want to know probabilities of a certain \"query\" variable\n\nStart by calculating joint probability of query variable and evidence variables by summing over hidden/unobserved variables\n\nIf know probability of evidence variable, can then use the product rule (divide by probability of evidence variable), to get conditional probability\n\nChain rule is more general rule. Can always write any joint distribution as an incremental product of conditional distributions\n\nLeads to **Bayes rule**: $P(x|y) = \frac{P(y|x)}{P(x)}P(y)$\n\nVery useful since sometime know conditional probability for evidence variable given hidden but want to calculate probability of hidden given evidence (ex: Naive Bayes - know probability of word given class, want to know probability of class given word)\n\n### Probabilistic Language Models\nWant to be able to calculate probability of a sentence given words in it. useful for machine translation, spell check etc..\n\nLeads to probability of next word give words thus far\n\nNaive approach is to calculate joint distribution by using chain rule and multiplying conditional probabilities for full sequence of words.\n\nProblem is that this state space is huge! Don't have enough data, let alone enough compute power\n\nSolution is to make simplifying assumption that probability of each word is only conditional on the past *k* words. **Markovian assumption**, similar to MDP, where assumption was that transition function only depended on current state, not sequence of previous sates\n\nWith this simplifying assumption, we can calculate the probability of a sentence as the produce of the probabilities of all words in sentence, each conditioned on past k words\n\nN-gram model.\n\nConfusing, since unigram ⇒ k=0\n\nbigram = condition on past word\n\nEtc..\n\nn-gram means total of n words. condition on n-1 words.\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- in Bayesian network, children are conditionally independent of all other nodes conditional on parent(s)\n- Bayesian networks are DAGs (no cycles)\n- For Bayesian network, can write joint probability as: $P(x_1,...x_n) = \\prod_{i=1}^{n}P(x_i|parents(X_i))$\n- to construct a Bayesian network, iterate over nodes in any order. When processing a node, make it have parents of all earlier nodes on which it depends\n    - better to order nodes with causes first, then effect. Leads to a sparser, more compact, graph. Easier to interpret.\n- D separation:\n    - question if evidence variable \"blocks\" or \"d-separates\", the two other variables\n        - undirected, so can “block” as child\n    - **Key idea**: evidence variable needs to block all paths between two variables in quesiton\n        - paths are directed, and can include parents\n- can mix discrete and continuous variables\n    - one strategy to discretize/bin continuous variables\n    - can also model as Gaussian, or non-parametric\n- logit or probit?\n    - for going from discrete to continuous (binary.)\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n- Enumeration algorithm for inference with Bayesian network\n$$ O(2^n) $$\n    - Very inefficient...\n    - Involves summing up to evidence variables, then multiplying?...\n- Variable elimination algorithm: more efficient\n    - bottom up approach - dynamic programming.\n    - Avoid repeated calculation\n- In general, Bayes net inference is \\#P hard?\n    - Need to compute number of 3 SAT solutions?...\n\n\n## Module 11 Lecture Notes\n\n### Review on Independence\nConditional independence vs absolute independence \n\nConditional more common. Two ways of writing conditional independence (similar to absolute independence)\n\n### Bayes Net Properties\nArrows from parent to children. Causal chain\n\nConditional on parents, children conditionally independent of all other variables (not true? need to condition on children and children’s parents also? Markovian blanket..\n\n**Common cause** -children independent of each other given parent\n\nObserved evidence \"block\"s influence of other variables\n\n**Common effect:** two parents. Absolute independence, but **not** conditionally independent given common child. Knowing child gives us more information about parents.\n \n### Reachability & Path\nGiven three cases (common cause, common effect,  and causal chain), can calculate if any two variables in Bayesian network are independent given some evidence variables\n\nLook at all paths (undirected) between the two variables. Check all triples. If all triples are active, then path is active. If a path is active, then variables are not independent given evidence variables (relationship not \"blocked\")\n\n**Active triples**\n\n- Cause chain with no evidence (all hidden?)\n- Common parent, no evidence\n- Common effect, effect is observed (evidence)\n- or any descendant of common child is observed\n\n**Inactive triples:**\n\n- Causal china where middle node is evidence/observed (blocks influence)\n- Common parent, where parent is observed/evidence variable (blocks influence_\n- common child, child is not observed (and no descents of common child are observed)\n    - influence can’t “flow” through child if not observed\n\n### D-Seperation Algorithm\nCheck all (undirected) paths between two variables. Check all tupleson path. If all triples active, then path active. If a single path active, then independence not guaranteed (doesn't mean NOT independent, just not guaranteed). If all paths inactive, then independence guaranteed, conditional on evidence\n\n### Inference\nInference by enumeration:\n\n- Evidence variables\n- Query variables\n- Hidden variables\n\nWant to know conditional (posterior) probability of query variable given evidence\n\nStep 1: select all entries from joint distribution consistent with the evidnce\n\nStep 2: sum out H (hidden variable) to get joint probability\n\nCan write out probabilities based on independence assumptions coded into Bayes Ne\n\nWorst case O(2^n) if binary variables. Worse if more than binary?\n\nVariable elimination is more efficient?\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n\n- machine learning can be applied to various parts of an agent:\n    - map from current state to action\n    - extract info from perceptions (image processing?)\n    - evolution of the world. Time series\n    - Utilities about desirability of different states\n    - Etc..\n- Classification vs regression\n    - called regression from Galton 1886 paper; regression to the mean. Confusing, misnomer\n- supervised vs unsupervised\n \n\n## AIMA Chapter 19.2 Supervised Learning\n\n- label/output generated from features/inputs by function\n- want to choose a hypothesis function h that approximates f\n- can also call h a model\n- draw h from an hypothesis space\n- choose hypothesis space based on expert knowledge or hyperparameter tuning\n- ideally want a consistent hypothesis (always matches ground truth), but impossible. So settle for best approximation\n- bias variance tradeoff:\n    - bias is tendency for predictive hypothesis to differ from expected value when averaged over many training sets\n        - often comes from having restricted form, such as linear when function should be polynomial\n    - variance is amount of change in hypothesis due to fluctuation in the training data\n        - higher order polynomial can overfit\n    - prefer simplest hypothesis that is powerful to explain the data\n    - in other words, want hypothesis with higher prior probability\n- \n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n \n- choose variable to split on in greedy fashion\n- not binary split\n- pruning\n    - look at splits that only have leaf nodes as children, and decide whether to drop split\n    - under null hypothesis (that attribute is irrelevant and splits have same proportion as as overall dataset), summed difference between actual and observed \\\n    false/negative is distributed according to chi-squared\n    - can do test to see if statistically different\n    - if not, then prune\n    - do pruning at end, cause sometimes need to make split with low information gain to get better split later\n        - example: XOR function. First split doesn't lead to any information gain. Second one is very good.\n- choose to split on feature with largest information gain\n    - define information gain as decrease in cross entropy\n    - Cross entropy: $-\\sum_{k}P(v_k) \\log_2 P (v_k)$\n        - highest when probabilities are all equal.\n        - is 0 when one prob is 1, and all else are 0\n    - for binary: $B(q) = -(q \\log_2 q + (1-q) \\log_2(1-1))$\n    - $Remainder(A) = \\sum_{k=1}^{d} \\frac{p_k + n_k}{p + n} B(\\frac{p+k}{p_k + n_k})$\n        - p and n are number of positive and negative examples in whole datasets\n        - so weighting cross entropy at every split by proportion of examples with that value for feature\n    - $Gain(A) = B(\\frac{p}{p + n}) - Remainder(A)$\n        - A is attribute under consideration\n- can use decision trees for continuous variables also\n    - if input, then do a range (split point test )\n    - if output, then CART: do linear regression at end, for every leaf.\n- can use trees to impute missing values\n\n\n\n## AIMA Chapter 19.4 Model Selection and Optimization\n\n- always assume that future examples will be like past (stationary assumption)\n    - and that each sample is independent of previous examples\n    - put toegehter, get i.i.d (independence and identically distributed) assumption\n- training, test, and validation/dev set\n    - if don't have enough data for validation/dev set, can use k fold cross validation\n    - hold out 1/k th of data to tests result of training, do training leaving out all k different sets\n    - can do leave out out one cross validation\n    - always need test set\n- some models such as decision trees (or SVMs? higher order polynomials), more prone to overfitting\n    - decrease in accuracy on validation set\n    - others, such as random forest or neural net, less prone to over-fitting\n    - model that fits all training data has interpolated or memorized the training data: likely overfitting\n- better to use a general loss function, such as log loss, compared to accuracy\n- regularize: increase loss for more complex functions\n- can do grid search, random search, Bayesian optimization or genetic algorithms (population based training) to find optimal hyperparameters\n\n\n## AIMA Chapter 19.5 The Theory of Learning\n\n- Probably approximate learning algorithms (PAC)\n    - any algorithm that returns hypotheses that are probably approximately correct (in large number of samples)\n- decision lists are an example....\n \n\n## AIMA Chapter 19.6 Linear Regression and Classification\n\n- linear regression: loss is sum of squared error\n- can solve for weights by setting (partial) derivatives to 0\n- but sometimes easier (when large matrices?) to solve using gradient descent\n    - can do stochastic/mini-batch gradient descent, faster, since calculation time decreases linearly, but error increases in squared manner?\n- With multivariate regression, need worry to about overfitting\n- can do regularization, l1 or l2\n- l1 leads to sparser weights\n- linear classifier with hard threshold (for classification) = perceptron\n- better to use logistic/sigmoid function\n\n\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n- Naive bayes (multinomial)\n    - calculate conditional probability of class given document, using Bayes rule to transform conditional probability of document give class\n- Bag of words: position doesn't matter\n- naive bayes assumption: features independent of each other, given class\n    - so can multiply\n- log space to avoid overflow\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \n- can estimate probabilities of features (words), using counts from corpus\n- but need Laplace (add-one) smoothing to avoid 0 probabilities\n    - More common in naive bayes than language modelling\n- ignore unkown words at testing time\n- don't need to worry about stop words - can include\n    - most of time, doesn't improve performance\n-  \n \n\n## SLP Chapter 4.3 Worked Example\n\n- worked example\n \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n- Improvement for sentiment analysis:\n    - use binary presence as feature\n- can apply negation to next words to create different tokens\n- can use a sentiment lexicon to get sentiment value of words, if don't have from our data or whatever\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n- can use features other than words for classification. Example: ratio of text to image in email for spam detection\n- can just use byte ngrams (don't bother decoding unicode)\n    - good for language detection?\n\n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n- Can use naive bayes to estimate probability of sentence - see which sentence is more likely given class\n    - But probably not very good results. Naive Bayes is better at classification than language modelling\n \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n \n- human labelled = gold labels\n- confusion matrix\n- accuracy not a good metric a lot of time (imbalance classes)\n- prefer precision (what % of predicted positives are actually positive?) and recall (what % of labelled positives have been correctly predicted?)\n- f2 = harmonic mean of precision and recall = 2 * P * R / (P + R)\n    - lower than arithmetic\n\n \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n- Easy to do confusion matrix for multiple classes\n- harder to do recall (what % of labelled positives correctly predicted) and precision (what % of predicted positive are actually positive)\n- can macro average: calculate precision and recall individually for each class and average\n- or micro average: pool number of tp, fp, and fn then calculate precision and recall from these pooled numbers \n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n- can use bootstrapping to compare different models\n    - very similar to k-fold validation\n    - but compare different models on same data\n    - and draw with replacement..\n \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\ndon't want to classify a sentence as toxic just because it reference homosexuality, women or uses African American vernacular\n\n## Module 12 Lecture Notes\n\n### Classification Task\nGRE uses machine learning to grade essays. Compares with one human grader. A second human grader reviews if two scores don't match.\n\nModel based classification build a model (Baye's net) where labels and features are random values. relationships between random values. Estimate. Then query to get distribution of label conditional on features.\n\n### Naive Bayes\nNaive Bayes assumes that features are independent of each other conditional on label\n\n$P(Y|F_1, F2, ... F_n)  \\propto P(Y) \\prod_{i} P(F_i|Y)$\n\n$\\propto$ means \"proportional to\"\n\nAbove is in fact joint? If divide by probability of features, then condition Y on features\n\nCan easily P(Y) and conditional probabilities of features from data....\n\nFor text classifier, assume that each word is identically distributed?\n\n### Basic Concepts in ML\n- split data into training, test, and dev/validation/held out set\n    - tune hyperparameters on dev/validation\n- Overfitting in Naive bayes: low/0 probability for feature never seen for class\n    - Can fix with laplacian smoothing: add 1, or add k\n    - Can figure out how much to add based on validation set\n- Backoff/interpolation works well too\n    - Remove last context variable from probability, weight...\n- Maximum likelihood to estimate parameters from naive bayes\n    - just counting, empirical estimate\n- Can add new features to get better fit.\n- Need to compare results to baseline\n    - Majority class, or simple linear classifier\n    - can also compare to state of the art\n\n### Perceptron\n- Threshold; if dot product of weights and features greater than 0, then output 1 (\"True\" class)\n    - if less than 0, then output 0 (or maybe -1?)\n- Bias shifts thresholds\n- If wrong prediction, then add or subtract features to weight vector\n    - Add if actual class was 1, since this will increase dot product, more likely to be greater than 0\n    - Subtract if actual class was -1, since this will decrease dot product\n- If doing multi-class, then one perceptron per class\n    - Take class with highest value\n    - If wrong, add feature value to weights for real label, and subtract from wrong label\n    - Don't do anything if correct\n\n### Improvements on Perceptrons and SVMs\n- Can show that number of mistakes that perceptron algorithm makes during training is $\\leq \\frac{1}{\\gamma}$ where $\\gamma$ is the margin of the set of examples (normalized to be based on weight with l2 norm or l1),\n    - can think of margin as cosine between the example x and weight vector. Choose example to minimize margin. So ..\n- Written as $mistakes \\leq \\frac{kl}{\\delta^2}$ in slides\n- But problem is examples aren't linearly separably, then iterate forever.\n    - Also finds \"barely separating\" solutions: overfit to training.\n    - Can use validation/dev set to avoid overfitting\n- Can use MIRA = margin infused relaxation algorithm\n    - basically scale update based on how far off we were\n    - Also cap size of update\n    - Help converge faster and generalize better\n- SVM = support vector machine\n    - choose examples (support vectors) and try to maximize distance/margin between support vectors and separating hyperplane\n    - With SVM, can use \"kernel\" trick to calculate distance in higher dimensions space efficiently\n\n \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n- Naive Bayes is generative (makes use of conditional probalitty of seeing document based on class), whil logistic is distimaintve :\\\nlearn probablity of class conditional on document directly\n-  $$\\sigma(z) = \\frac{1}{1 + e^{-z}}$$\n$$ 1- \\sigma(z) = \\sigma(-z)$$\nNeed to manually add features (interactions) for logistic regreesion\n- generally losistic regression is better cause can handle correlated features, but Naive Bayes usually works well, especially on small data sets\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nNeed a loss funtion (cross entropy) and optimization function (stochastic gradient descent) to learn weights\n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \n- loss defines how far our prediction is from true label\n$$p(y|x) = \\hat{y}^{y}(1 - \\hat{y})^{1-y}$$\n$$\\log p(y|x) = y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})$$\nSince want to maximize conditional probablity, can take negative and minimize\n$$ CrossEntropyLoss = -[y \\log \\hat{y} + (1-y) \\log (1 - \\hat{y})]$$ \n\n \n\n## SLP Chapter 5.4 Gradient Descent\n\n- loss functoin is convext\n  - means that there is just one minimum,so can't get stuck in local minima\n- The gradient is a vecot moint in the direction of the gretst increase in a function\n- Is dervitaive of loss funtion with respect to weights, weighted by a learning rate\n- Want small learning weight, since don't want to move too much in single step\n- Each element of gradient vector is partial derivative of loss function with respect to single feature, evaluated at current weights and features.\n- Subtract this gradient vector from current weights, weighting by learning weight\nPartial deriviate for Cross Entropy with respect to weight j: $$[\\sigma(w \\cdot x + b) - y]x_j$$\n- Stochastic gradient descent makes update after each training example, while mini-batch use a batch of certain size\n  - take average over batch\n- If only update after seeing whole dataset, this is called batch training\n \n\n## SLP Chapter 5.5 Regularization\n\nRegularizatoin: add penalty term to loss to penalize large norms on weight vector\n- L2 = ridge, l1 = lasso (sparser)\n- helps prevent overfitting and leads to better generalization\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n- can do multinomial regression with softmax\n- just e^z \\ sum of all e^z\n- seperat wight vector for each class\n- loss is just negative of y^, where y^k is predicted proablity of correct class k\n- parital  derivative is similar to noirmal cross entrpoy?\n  - difference between true value for class k, which is 1, and predicted proabity, wieghted by input/feautre\n \n\n## SLP Chapter 7.1 Units\n \n- neural unit: takes vector and produces real number\n- common activation functions: sigmoid, tanh and relue\n - tanh preferred over sigmoid since more \"squashing\", easier to differnetaite. Between -1 and 1. $y = \\frac{e^z - e^{-z}}{e^z + e^{-z}}$\n - very high values for sigmoid can \"saturated\" y, means that derivates are very close to 0\n\n\n\n## SLP Chapter 7.2 The XOR problem\n\n- linear classifier can't model XOR function\n  - cause no linear seperator\n- but easy to do with a simple neural netowrk with 3 ReLU units\n- can't have linear activatino funciotn, just becomes a linear function.\n\n \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n - feed forward: no cycles and Fully connected (all outputs of previous layer input to every unit in next layer)\n   - misnomer: Multilyaer perceprtons\n   - supposedly perceptrons only linear, but in lectures, prof say perceprtons can have activation functions\n     - alothoug I suppoose that they do in a way, with thresholding leading to 1 or 0 (or -1?)\n- 3 layers: input, hidden and output\n  - don't usually count input in number of layers. So logisitc regresion is a one layer network\n- can represent whole layer as single weight matrix\n  - more efficinet for calculations\n- stack different layer = more representativeness\n- use sigmoid as output for classifier\n- easy to simplify bias by using a feature that always take value of 1\n\n \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n \n- generally use word embeddings instead of n-grams/bag of words\n- \n \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n- Can use feedforward network for lanuage modelling (predicting next word), even if recurrent of transformer model generally preferred.\n- Have certain number of words we are conditgioning on\n- embed them\n- concatenate them into a single vector\n- apply a hidden layer with activation function\n- then softmax to get probabltiies over every word!\n  - that's a lot of words!\n\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n- use same cross-entropy loss for classifciaiotn\n- use backward differentation\n- Use a graph to model relationships between different units\n- Apply chain rule: Derivative of function f(g) with respect to x is df/dg * dg/dx\n- So in \"backwards pass\", calcualte derviative of first, output, unit first with respect to loss (is one), then go backwards, brining info from further up the line\n- optimiization is non convex. Some best practices:\n  - drop out for refgualtization\n  - initial to random werights, small, normalized\n  - adjust learning weight\n  - computaiton graph\n \n\n## SLP Chapter 7.7 Training the neural language model\n \n- can \"freeze\" embedding layer to keep same, or fine trune and back peopograte error to update\n \n\n## Module 13 Lecture Notes\n\n### Logistic Regresion\nClassifier components:\n\n 1. Feature Representation\n\n1. Classification function\n2. Objective function\n3. Algorithm for optimizing the classification function\n\nSigmoid/logistic function:\n\n $y = \\frac{1}{1 + e^{-w \\cdot f}}$\n\nCan get features from lexicon, bag of words, etc...\n\nNeed loss function( cross entropy) and way of adjusting weights to minimize loss (stochastic gradient descent)\n\n###Loss Function\n- Log loss (cross entropy) = negative log likelihood loss\n    - Better than MSE, since MSE is not convex for probability\n- If assign correct probability (1 if y = 1), then cross entropy loss is 0\n- Sum (average?) loss over all training examples\n\n### Stochastic Gradient Descent\n- gradient descent\n- Find slope\n- learning rate to control step size\n- Since cross entropy is convex (with sigmoid function), then won’t get stuck in lock min\n- Can generalize from single feature to multiple\n    - Have a derivative vector\n    - Partial derivatives\n- Use regularization to avoid over fitting\n    - Add penalty to loss function for having weights with high absolute values\n    - L2 = ridge; l1 = lasso\n- Multinational:\n    - softmax\n    - e^w_1 / (sum of e w_i; i from 1 to n)\n### Neural Networks\n- stack multiple neural “units” to form “deep”, many layered networks\n- Use non linear activation functions such as sigmoid, tanh or Relu\n- Feed forward network: multilayered, fully connected (usually), no cycles\n    - Sometimes called MLP\n- Same as before, need:\n    - loss function\n    - some algorithm for optimizing classification function (MLP)\n- Loss function is cross entropy again\n- Optimization algorithm is gradient descent\n- Form graph\n- Use chain rule\n- Start from right, calculate derivative with respect to loss\n- Then have what need for next layer\n- Need activation functions to be differentiable\n    - But RELU isn’t differentiable at 0...\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}