{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Sara CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "iZiNfkO_PhMa"
      },
      "source": [
        ""
      ],
      "execution_count": 42,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "c48d689b-65d7-440e-beef-803d9bcceef4"
      },
      "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": 43,
      "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": "877df9f7-4b0a-4b4f-a85a-b282a1c47643"
      },
      "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": 44,
      "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": 45,
      "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 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "MDPs \n",
        "- non-deterministic search problems in fully observable task env, where you have to make a sequence of actions (sequential),\n",
        "- outcomes are non-deterministic (stochastic)\n",
        "- expectimax is a way to solve\n",
        "- Transitions are markovian if the probability of arriving at s' deponds on s and not earlier history.\n",
        "- Like search problem, has set of states, actions, intial and terminal statets but now has transition and reward function.\n",
        "- solution is going to be a policy, returns best action based on input state. \n",
        "\n",
        "- To determrine optimal policy, compute expected utility of all possible paths generated by a policy. \n",
        "- if reward for each move is < negative terminal (like -1.65) state than going to this negative terminal CAN be betterr, if -.03 < r < 0\n",
        "it will try to get to positive terminal state. \n",
        "- If r > 0 then it will stay at non-terminal states.\n",
        "- To deal with inifinite utilities, have a finite horizon like in depth-limited search.\n",
        "  - (terminate after fixed steps or give non-stationary policies, pi depends on time left, or just discounting). \n",
        "- expectimax is too much work, there are better options.\n",
        "\n",
        "Value Iteration: start with V_0(s) = 0: no time steps left means an expected reward sum of zero (this is the \"terminal state\"). Then do formula for each V_k+1(s) which is\n",
        "V*(s) but replace V*(s') with V_k(s').\n",
        "Repeat this until convergence...complexity of each iteration is O(S^2*A). guranteed to converge to unique optimal values (because of decay). \n",
        "\n",
        "\n",
        "Rather than just calculating values, can evaluate which policy is best ->iteration over policies. calculate expected values for a policy, previously picked optimal action after evaluating values of each action.\n",
        "Nowe can just pick action that pi(s) says. Easier to compute utility/value of statee. Same as before but with out max action. Can solve V's as a system of linear equations.\n",
        "\n",
        "\n",
        "when given optimal values: For each pi*(s) -> do mini expectimax (policy extraction)\n",
        "when given optimal q-values:, trivial just choose max q value out of all actions\n",
        "\n",
        "policy iteration: \n",
        "Step 1: Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n",
        "• Step 2: Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future\n",
        "values\n",
        "• Repeat steps until policy converges\n",
        "\n",
        "Policy vs value iteration: both take in MDP and output optimal quanity. in value: update valuese and implictly policy (doeesn't actually track policy)\n",
        "\n",
        "in policy: several passes that update utilities with ONE fixed policy, then pick new policy, new policy will be better or we're done\n",
        "- both are dp solutions to MDPs\n",
        "\n",
        "Maximum Expected Utility: in expectimax and MDPs, averaging over utlities\n",
        "  - utilities should summarize the agents goals, any ratiinal preferences can be summarized as a utility func\n",
        "  - rather than prescribe behaviors to agents, we do utilities and let them pick (also have to consider uncertainities)\n",
        "agent must have preferences: A >- B is prefers A. A ~ B means indifferent\n",
        "\n",
        "To deteeremine rational preferences, put some constraints:\n",
        "  1. axiom of transivitity: if A >- B and B >- C then A >- C\n",
        "  2. Orderability: eithere A >- B OR b >- A OR A~ B\n",
        "  3. Continuity: A >- B >- C => theere's a threshold p in lotterry of A and C where they are indifferent to that and B\n",
        "  4. Subitituatbility: A ~ B => loterry with A and C ~ loterry with B and C\n",
        "  5. Monotonicity: A >- B, want a lottery with A and B where prob for A is higher\n",
        "*If follow these, then maximize utility and can make a real valued utility function out of it\n",
        "MEU -> choose action that miximizes expected utility\n",
        "\n",
        "Utility Scale for people:\n",
        "Normalized utilites: between 0 and 1\n",
        "micromort: one-millionh chance of death\n",
        "QALYS: quality adjustetd life years, for medical decisions involving risk\n",
        "these are invariant under positive linear rtansformation: reason abou risk and probailitties\n",
        "  U'(x) = k1U(x) + k2 where k1 > 0\n",
        "  -use standard lottrey to enumerate, adjust until lottery p until indiffeerence: A ~ Lp\n",
        "-money doesn't behave as a utility function - U(L) < U(EMV(L)) is what people believe as peeople are risk-averse\n",
        "\n",
        "\n",
        "\"Policy Iteratiton alg\": \"two steps: 1. policy evaulatiion -> calculate utilities for a fixed policy until convergence (not yet optimal), 2. policy improvement: update policy using one-step look-ahead with resulting converged utilities. repeat both until policy converges, optimal\",\n",
        "\n",
        "\"q-state\": \"(s,a) -> you have your state and action you want to take (like expectimax), transition gives u prob for each next state from this. Q*(s,a) is expected utility/value starting out with taking (s,a) and acting optimally\",\n",
        "\n",
        "\"Value/utility (V*(s))\": \"expected utiility starting in s and acting optimally. compute expectimax for each state: expected utility from picking optimal action, sum of rewards\",\n",
        "\n",
        "\"Value Iteration\": \"start with V_0(s) = 0: no time steps left means an eexpected reward sum of zero, very slow tho, values keep changing but actions converge earlier\",\n",
        "\n",
        "\"Principal of maximizing expecteed utility\": \"a rational agent should choose the action that maximized its expected utility, given its knowledge (probabiliyt districution, outcomes) (not neccessarily worry about worstcase)\",\n",
        "\n",
        "\"Discounting\": \"value of rewards decay exponentially, represent sooner rewards are better, done via a decay factor so each n step is decay^n * reward, helps with convergence\",\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",
        "\"Stochastic Transition Model\" : \"Gives probability of different outcomes based on action - T(s,a,s')\",\n",
        "\"Transition Function\" : \"Takes in current state, action, and desired state and gives probabillity of this desired state occuring\",\n",
        "\"reward function.\": \"gives reward for each action (can be + or -), R(s,a,s') or defined in any way like R(s'), shapes agents behavior\",\n",
        "\"Total Utiliity.\": \"add up rewards at each step along a path. preferences for agent: highest reward, ASAP - discounting\",\n",
        "\"Policy(pi)\": \"function that retuns best action based on input state. try to find optimal policy (pi*) which can be achieved based on reward function\",\n",
        "\"Absorbing state:\": \"gurantee that for every policy, terminal state will be reached eventually\",\n",
        "\"Lotteries\": \"situations with uncertain prizes (L = [p, A; (1-p), B]) where A and B are prizes\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 63,
      "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": 1802
        },
        "outputId": "cbad1a1b-41c0-4790-fc67-16dc8ffaa2ce"
      },
      "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": 64,
      "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 Chapter 16.1 summary.  $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 Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nMDPs \n- non-deterministic search problems in fully observable task env, where you have to make a sequence of actions (sequential),\n- outcomes are non-deterministic (stochastic)\n- expectimax is a way to solve\n- Transitions are markovian if the probability of arriving at s' deponds on s and not earlier history.\n- Like search problem, has set of states, actions, intial and terminal statets but now has transition and reward function.\n- solution is going to be a policy, returns best action based on input state. \n\n- To determrine optimal policy, compute expected utility of all possible paths generated by a policy. \n- if reward for each move is < negative terminal (like -1.65) state than going to this negative terminal CAN be betterr, if -.03 < r < 0\nit will try to get to positive terminal state. \n- If r > 0 then it will stay at non-terminal states.\n- To deal with inifinite utilities, have a finite horizon like in depth-limited search.\n  - (terminate after fixed steps or give non-stationary policies, pi depends on time left, or just discounting). \n- expectimax is too much work, there are better options.\n\nValue Iteration: start with V_0(s) = 0: no time steps left means an expected reward sum of zero (this is the \"terminal state\"). Then do formula for each V_k+1(s) which is\nV*(s) but replace V*(s') with V_k(s').\nRepeat this until convergence...complexity of each iteration is O(S^2*A). guranteed to converge to unique optimal values (because of decay). \n\n\nRather than just calculating values, can evaluate which policy is best ->iteration over policies. calculate expected values for a policy, previously picked optimal action after evaluating values of each action.\nNowe can just pick action that pi(s) says. Easier to compute utility/value of statee. Same as before but with out max action. Can solve V's as a system of linear equations.\n\n\nwhen given optimal values: For each pi*(s) -> do mini expectimax (policy extraction)\nwhen given optimal q-values:, trivial just choose max q value out of all actions\n\npolicy iteration: \nStep 1: Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n• Step 2: Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future\nvalues\n• Repeat steps until policy converges\n\nPolicy vs value iteration: both take in MDP and output optimal quanity. in value: update valuese and implictly policy (doeesn't actually track policy)\n\nin policy: several passes that update utilities with ONE fixed policy, then pick new policy, new policy will be better or we're done\n- both are dp solutions to MDPs\n\nMaximum Expected Utility: in expectimax and MDPs, averaging over utlities\n  - utilities should summarize the agents goals, any ratiinal preferences can be summarized as a utility func\n  - rather than prescribe behaviors to agents, we do utilities and let them pick (also have to consider uncertainities)\nagent must have preferences: A >- B is prefers A. A ~ B means indifferent\n\nTo deteeremine rational preferences, put some constraints:\n  1. axiom of transivitity: if A >- B and B >- C then A >- C\n  2. Orderability: eithere A >- B OR b >- A OR A~ B\n  3. Continuity: A >- B >- C => theere's a threshold p in lotterry of A and C where they are indifferent to that and B\n  4. Subitituatbility: A ~ B => loterry with A and C ~ loterry with B and C\n  5. Monotonicity: A >- B, want a lottery with A and B where prob for A is higher\n*If follow these, then maximize utility and can make a real valued utility function out of it\nMEU -> choose action that miximizes expected utility\n\nUtility Scale for people:\nNormalized utilites: between 0 and 1\nmicromort: one-millionh chance of death\nQALYS: quality adjustetd life years, for medical decisions involving risk\nthese are invariant under positive linear rtansformation: reason abou risk and probailitties\n  U'(x) = k1U(x) + k2 where k1 > 0\n  -use standard lottrey to enumerate, adjust until lottery p until indiffeerence: A ~ Lp\n-money doesn't behave as a utility function - U(L) < U(EMV(L)) is what people believe as peeople are risk-averse\n\n\n\"Policy Iteratiton alg\": \"two steps: 1. policy evaulatiion -> calculate utilities for a fixed policy until convergence (not yet optimal), 2. policy improvement: update policy using one-step look-ahead with resulting converged utilities. repeat both until policy converges, optimal\",\n\n\"q-state\": \"(s,a) -> you have your state and action you want to take (like expectimax), transition gives u prob for each next state from this. Q*(s,a) is expected utility/value starting out with taking (s,a) and acting optimally\",\n\n\"Value/utility (V*(s))\": \"expected utiility starting in s and acting optimally. compute expectimax for each state: expected utility from picking optimal action, sum of rewards\",\n\n\"Value Iteration\": \"start with V_0(s) = 0: no time steps left means an eexpected reward sum of zero, very slow tho, values keep changing but actions converge earlier\",\n\n\"Principal of maximizing expecteed utility\": \"a rational agent should choose the action that maximized its expected utility, given its knowledge (probabiliyt districution, outcomes) (not neccessarily worry about worstcase)\",\n\n\"Discounting\": \"value of rewards decay exponentially, represent sooner rewards are better, done via a decay factor so each n step is decay^n * reward, helps with convergence\",\n\n  \n\n## Module 8 Definitions\n* **Stochastic transition model** - Gives probability of different outcomes based on action - T(s,a,s')\n* **Transition function** - Takes in current state, action, and desired state and gives probabillity of this desired state occuring\n* **Reward function.** - gives reward for each action (can be + or -), R(s,a,s') or defined in any way like R(s'), shapes agents behavior\n* **Total utiliity.** - add up rewards at each step along a path. preferences for agent: highest reward, ASAP - discounting\n* **Policy(pi)** - function that retuns best action based on input state. try to find optimal policy (pi*) which can be achieved based on reward function\n* **Absorbing state:** - gurantee that for every policy, terminal state will be reached eventually\n* **Lotteries** - situations with uncertain prizes (L = [p, A; (1-p), B]) where A and B are prizes\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" RL: Agent must learn reward function and transition function rather than being given it (MDP, it was stochastic but we knew probability distribution and reward). It learns by interacting\n",
        "with the world. For every action, it recieved feedback (\"observe sample\") as a reward and state and goal is to maximize expected reward. Agent's utility is defined by reward function.\n",
        "There is a tradeoff between exploration and exploitation. Reinforcement Learning, still uncertain envrionments so need to act to learn not just computations. \n",
        "\n",
        "Model-based learning: learn approximate probability distribution of transition function based. learn by taking a bunch of samples and normalize\n",
        "to get values for T. Discover R when we expereince (s,a,s'). Finally solve as MDP. \n",
        "\n",
        "Model-free learning: we don't construct explicit T function. Every time we take an action, compare what happened to what we expected to happen and whenever something\n",
        "deviates, takee values and adjust up or down. Just track of values of a state. \n",
        "\n",
        "Passive Reinforcement Learning: \n",
        "  more so like policy evaluation: we have a fixed policy pi (without knowing T or R)and determine value of being in this state\n",
        "\n",
        "Direct evaluation: \n",
        "  - goal -> compute values for each state under pi, idea: average together observed sample values -> act according to pi and write down sum of \n",
        "  - discounted rewards (rewards from that state to the end state) and average all the samples for each state.\n",
        "    - PROS-> easy to understand, doesn't require T, R, and eventually will compute correct avg values\n",
        "    - CONS-> wastes info about how states connected, requires lots of estimates for good vals, each state must be learned separtely\n",
        "Sample based policy eval not feasible as we can't gurantee we can go to each state n times.\n",
        "\n",
        "Temporal Difference Learning: compare current estimates against new value (model free)\n",
        "  - update V(s) each time we experience a transition (policy is still fixed and doing eval)\n",
        "  - outcomes s' that are more likely will contribute updates more often\n",
        "  - like before V(s) : sample = R(s, pi, s') + decay*Vpi(s')\n",
        "  - update V(s) right away: Vpi(s) <- (1 - alpha)Vpi(s) + (alpha)*sample, alpha is learning rate that controls how much new samples contribute (interprolating)\n",
        "  Exponential moving average: observations in past worth less than newer ones as (1-alpha) is essnetially exponentiated, which is beter as these are more random\n",
        "  - can keep decreasing leearning rrate to help converge alpha\n",
        "  - hard to turn values into policy -> idea learn Q-values, not values so that it can still be model free\n",
        "\n",
        "Acive Reinforcement Learning: way of taking MDP and learning paramers of model but you choose actions to try.\n",
        "\n",
        "Q-value iteration: (q vals are more useful than values of a state as rather than picking action with higher state, can determine which (state, action) prepare has best value)\n",
        "    - Can still start with Q0(s,a) = 0 and build up recursively. Given Qk can calculate k+1 q-val for all q-states\n",
        "  We can now do Q-Learning, which is sample-based Q-value iteration:\n",
        "    - recieve a samplle (s,a,s',r)\n",
        "    - consider your old estimate: Q(s,a) and new sample estimate: sample = R + decay*max(a')Q(s',a')\n",
        "    - incorporate new estimate into a running average: Q(s, a) <- (1 - alpha)Q(s, a) + (alpha)*sample\n",
        "    - eventhough taking subopimal actions can converge to optimal policy : called off-policy learning\n",
        "      - requires enough exploring, make learning rate small enough and decrease over time (not to quickly)\n",
        "\n",
        "Exploration vs Exploitation: find right balance\n",
        "  - Q-Learning requires notion of exploring before optimal policy can be reached\n",
        "  - several schemes for forcing exploration: \n",
        "      simplest way: episilon greedy alg -> every time step, randomly generate value, if smaller than episilon then act randomly, otherwise act on current policy\n",
        "                    - this can be bad because we may know that these random paths are bad, but keep taking them\n",
        "                        -solns: lower episilon over time, remove bad policies, encode specific exploration functions\n",
        "    exploration functions: when and what should we explore?\n",
        "      -explore states where we haven't established how good or bad htey are, uncertain areas (optimistic approach)\n",
        "      -f(u, n)= (u is currenet estimate of utility, n is # of times we've visited state) u + k(constant bonus) / n\n",
        "        Modified q-update function: max(a')f(Q(s',a'), N(s',a')) instead of max(a')Q(s',a'), this gives bonus to good and unknown states\n",
        "\n",
        "Regret: quantify goodness of exploration strategies\n",
        "  -how many mistakes we made over time (would be much higher for episilon approach)\n",
        "  -difference betweeen your (expected) rewards (youthful suboptimality) and optimal (expected) rewards\n",
        "\n",
        "Approximate Q-Learning:\n",
        "  - basic q-learn keeps a table of q-values but for some states like chess there are too many states\n",
        "  - instead generalize them and learn faster\n",
        "  - learn from small number of states from experience and then generalize to new and similar states (important in ML)\n",
        "  - can do a weighted linear sum of features: Eval(s) = w1*f1(s) + w2*f2(s)...\n",
        "      -example: f1(s) = num white queens - black queens and w1 would be high since this is an important feature\n",
        "      - this is a liner value function -> can do V or Q also as Q(s,a) = w1*f1(s, a) + w2*f2(s, a)...\n",
        "      -advantage: -expereince can be summed up with a few features, learning alg just has to tweak weights\n",
        "                  -states may share features but actually be very diff in value, depends on how well this is implemented\n",
        "  -Update q value weights rather than entire Q(s,a) like was done for Exact Q-learning\n",
        "    - wi <- wi + alpha[difference]fi(s,a) (fi(s,a) so that it can adjust weights of active features)\n",
        "    -difference = diff between old Q(s,a) and new calculated one \n",
        "\n",
        "\n",
        "\"Regret\" : \"measure total rewards that we got from exploration stratetgy and compare againt total expected reewards had the ageent followed optimal policy whole time (sometimes you make mistakes still)\",\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Sampling\" : \"because of chance and stochastic environment, you have to try things repeatedly\",\n",
        "\"Difficulty\" : \"learning can be much harder than computation for solving MDP\",\n",
        "\"Exploitation\" : \"use knowledge it has so far to choose actions with best known rewards\",\n",
        "\"Exploration\" : \"trying new unknown actions and paths to find information (better reward or potentially face worse)\",\n",
        "\"monte carlo/one armed bandit\" : \"gambling terms, in multi-arm bandits in ML, each has a probability distribution -> what policy maximizes utility\",\n",
        "\"Passive Reinforcement Learning\" : \"someone else picks policy and we try it\",\n",
        "\n",
        "}"
      ],
      "execution_count": 65,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1807
        },
        "cellView": "form",
        "outputId": "33aa99ac-8f89-4137-bf28-fc4c71bac02c"
      },
      "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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Regret' is too long!\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n RL: Agent must learn reward function and transition function rather than being given it (MDP, it was stochastic but we knew probability distribution and reward). It learns by interacting\nwith the world. For every action, it recieved feedback (\"observe sample\") as a reward and state and goal is to maximize expected reward. Agent's utility is defined by reward function.\nThere is a tradeoff between exploration and exploitation. Reinforcement Learning, still uncertain envrionments so need to act to learn not just computations. \n\nModel-based learning: learn approximate probability distribution of transition function based. learn by taking a bunch of samples and normalize\nto get values for T. Discover R when we expereince (s,a,s'). Finally solve as MDP. \n\nModel-free learning: we don't construct explicit T function. Every time we take an action, compare what happened to what we expected to happen and whenever something\ndeviates, takee values and adjust up or down. Just track of values of a state. \n\nPassive Reinforcement Learning: \n  more so like policy evaluation: we have a fixed policy pi (without knowing T or R)and determine value of being in this state\n\nDirect evaluation: \n  - goal -> compute values for each state under pi, idea: average together observed sample values -> act according to pi and write down sum of \n  - discounted rewards (rewards from that state to the end state) and average all the samples for each state.\n    - PROS-> easy to understand, doesn't require T, R, and eventually will compute correct avg values\n    - CONS-> wastes info about how states connected, requires lots of estimates for good vals, each state must be learned separtely\nSample based policy eval not feasible as we can't gurantee we can go to each state n times.\n\nTemporal Difference Learning: compare current estimates against new value (model free)\n  - update V(s) each time we experience a transition (policy is still fixed and doing eval)\n  - outcomes s' that are more likely will contribute updates more often\n  - like before V(s) : sample = R(s, pi, s') + decay*Vpi(s')\n  - update V(s) right away: Vpi(s) <- (1 - alpha)Vpi(s) + (alpha)*sample, alpha is learning rate that controls how much new samples contribute (interprolating)\n  Exponential moving average: observations in past worth less than newer ones as (1-alpha) is essnetially exponentiated, which is beter as these are more random\n  - can keep decreasing leearning rrate to help converge alpha\n  - hard to turn values into policy -> idea learn Q-values, not values so that it can still be model free\n\nAcive Reinforcement Learning: way of taking MDP and learning paramers of model but you choose actions to try.\n\nQ-value iteration: (q vals are more useful than values of a state as rather than picking action with higher state, can determine which (state, action) prepare has best value)\n    - Can still start with Q0(s,a) = 0 and build up recursively. Given Qk can calculate k+1 q-val for all q-states\n  We can now do Q-Learning, which is sample-based Q-value iteration:\n    - recieve a samplle (s,a,s',r)\n    - consider your old estimate: Q(s,a) and new sample estimate: sample = R + decay*max(a')Q(s',a')\n    - incorporate new estimate into a running average: Q(s, a) <- (1 - alpha)Q(s, a) + (alpha)*sample\n    - eventhough taking subopimal actions can converge to optimal policy : called off-policy learning\n      - requires enough exploring, make learning rate small enough and decrease over time (not to quickly)\n\nExploration vs Exploitation: find right balance\n  - Q-Learning requires notion of exploring before optimal policy can be reached\n  - several schemes for forcing exploration: \n      simplest way: episilon greedy alg -> every time step, randomly generate value, if smaller than episilon then act randomly, otherwise act on current policy\n                    - this can be bad because we may know that these random paths are bad, but keep taking them\n                        -solns: lower episilon over time, remove bad policies, encode specific exploration functions\n    exploration functions: when and what should we explore?\n      -explore states where we haven't established how good or bad htey are, uncertain areas (optimistic approach)\n      -f(u, n)= (u is currenet estimate of utility, n is # of times we've visited state) u + k(constant bonus) / n\n        Modified q-update function: max(a')f(Q(s',a'), N(s',a')) instead of max(a')Q(s',a'), this gives bonus to good and unknown states\n\nRegret: quantify goodness of exploration strategies\n  -how many mistakes we made over time (would be much higher for episilon approach)\n  -difference betweeen your (expected) rewards (youthful suboptimality) and optimal (expected) rewards\n\nApproximate Q-Learning:\n  - basic q-learn keeps a table of q-values but for some states like chess there are too many states\n  - instead generalize them and learn faster\n  - learn from small number of states from experience and then generalize to new and similar states (important in ML)\n  - can do a weighted linear sum of features: Eval(s) = w1*f1(s) + w2*f2(s)...\n      -example: f1(s) = num white queens - black queens and w1 would be high since this is an important feature\n      - this is a liner value function -> can do V or Q also as Q(s,a) = w1*f1(s, a) + w2*f2(s, a)...\n      -advantage: -expereince can be summed up with a few features, learning alg just has to tweak weights\n                  -states may share features but actually be very diff in value, depends on how well this is implemented\n  -Update q value weights rather than entire Q(s,a) like was done for Exact Q-learning\n    - wi <- wi + alpha[difference]fi(s,a) (fi(s,a) so that it can adjust weights of active features)\n    -difference = diff between old Q(s,a) and new calculated one \n\n \n\n## Module 9 Definitions\n* **Sampling** - because of chance and stochastic environment, you have to try things repeatedly\n* **Difficulty** - learning can be much harder than computation for solving MDP\n* **Exploitation** - use knowledge it has so far to choose actions with best known rewards\n* **Exploration** - trying new unknown actions and paths to find information (better reward or potentially face worse)\n* **Monte carlo/one armed bandit** - gambling terms, in multi-arm bandits in ML, each has a probability distribution -> what policy maximizes utility\n* **Regret** - measure total rewards that we got from exploration stratetgy and compare againt total expected reewards had the ageent followed optimal policy whole time (sometimes you make mistakes still)\n* **Passive reinforcement learning** - someone else picks policy and we try it\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "Probabiility Review: good for reasoning about world especially with uncertainty\n",
        "- let's us quantify how likely or unlikely something is in the next state rather than ruling out possibilities with logical assertions (ex: pit in star wars world)\n",
        "- fully specified probability model associates with a probability P(w) each possible world w (random variable)\n",
        "  - between 0 and 1 \n",
        "  - total set of all possible worlds is 1\n",
        "- we don't care about complete state of world just some: RANDOM VARIABLES (denoted with capital letter)\n",
        "\n",
        "Join Distribution: size of distribution if n variables with domain sizes d is d^n so impractical to write it out, normalized so adds to 1\n",
        "\n",
        "Probabilistic Inference: compute a desired prob from other known probs (ex: conditional frm joint)\n",
        "  - can update beliefs from new observations (these beliefs can increase or decrease)\n",
        "  - Inference by enumeration: split RV into 3 sets of things\n",
        "    - EVidencee variables (things we've observed)\n",
        "    - Query var (things we want to reason about)\n",
        "    - Hidden var (occur in big JD but aren;t observations and things we're actively reasoning about)\n",
        "    - we care about P(Q | e1...ek) -> too arrive here\n",
        "      1. select entries consistent with the evidence we observed\n",
        "      2. marginalization, kick out hidden var by summing over all of the value assignments for Hidden vars\n",
        "      3. normalize: multiply by 1/Z where Z is computed by summing over all Q\n",
        "\n",
        "Probabilistic Language Models:\n",
        "  - assign a probability to a sentence (ex: autocomplete for texting, machine translation, spelling correction, speech recognition)\n",
        "  - with a few observations, esttimate the probability distribution over all assignments of words in english language to that next \"random variable\" ie next word\n",
        "\n",
        "  Goals:  compute probability of a sentence or sequence of words\n",
        "  related tasks: probability of an upcoming word, given sequence of previous ones -> leads to languge model to compute this. \n",
        "    - P(W) = P(w_n|w1,w2...wn-1), calcualte ewith chain rule\n",
        "\n",
        "How to estimate these probabilities:\n",
        "  1. maximum likelihood estimation, counting up things and dividing...just find what fraction of time, x came after y when we saw y from some text\n",
        "    - not great: inefficient, words may not be in set already (hard to have this much data)\n",
        "  2. Markov assumption: probabilitiy of what happens in next state only depends on current state (ignores history)\n",
        "    - much morre efficient approach... instead of P(won | the underdog team), do P(won | team), only depends on previous k words, not whole context of sentence\n",
        "      - k << n, easier to estimate from data -> improved maximum likelihood estimation\n",
        "\n",
        "n-gram models, start to get fairly accurate when n = 4 or 5\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Observed Variable\" : \"agenet knows certain things about state of world\",\n",
        "\"Unobserved Variable\" : \"agent need to reason about other aspects\",\n",
        "\"Model\" : \"agent knows something about how the known variables relate to the unknown\",\n",
        "\"sample space\" : \"possible worlds in probability theory (exhaustive and mutually exclusive\",\n",
        "\"Random Variable\" : \"some aspect of ther world about which we may have uncertainty\",\n",
        "\"Joint Distribtion\" : \"specifies a real number assignment over a set of random var, ex: P(X1 = x1, X2 = x2 ...) or as P(x1, x2)\",\n",
        "\"Probabilistic Models\" : \"joint distribution overe a set of random variables\",\n",
        "\"Event\" : \"set of E outcomes, sum of probabilities in join distribution where E's conditions are true (usually has ORs and ANDs)\",\n",
        "\"Marginal Distributions\": \"subtable of JD which eliminate variables that don't care about (summing out and collapsing rows)\",\n",
        "\"Conditional Probabilities\": \"probability of something happening conditioned (or given) that something else has happened. can go from JD table to this\",\n",
        "\"Product Rule\": \"P(Y) * P(X|Y) = P(X,Y) let's you get back big JD table from subtables (marginal * conditional)\",\n",
        "\"Chain Rule\": \"generalizes product rule so can do more than 2 var\",\n",
        "\"Bayes' Rule\": \"P(X|Y) = P(Y|X) / P(Y) * P(X), build one conditional from reverse, super important\",\n",
        "\"\": \"\",\n",
        "}"
      ],
      "execution_count": 50,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2023
        },
        "cellView": "form",
        "outputId": "e80c3fc5-3c5d-432b-99b5-2893edc8f9c9"
      },
      "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": 51,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \nProbabiility Review: good for reasoning about world especially with uncertainty\n- let's us quantify how likely or unlikely something is in the next state rather than ruling out possibilities with logical assertions (ex: pit in star wars world)\n- fully specified probability model associates with a probability P(w) each possible world w (random variable)\n  - between 0 and 1 \n  - total set of all possible worlds is 1\n- we don't care about complete state of world just some: RANDOM VARIABLES (denoted with capital letter)\n\nJoin Distribution: size of distribution if n variables with domain sizes d is d^n so impractical to write it out, normalized so adds to 1\n\nProbabilistic Inference: compute a desired prob from other known probs (ex: conditional frm joint)\n  - can update beliefs from new observations (these beliefs can increase or decrease)\n  - Inference by enumeration: split RV into 3 sets of things\n    - EVidencee variables (things we've observed)\n    - Query var (things we want to reason about)\n    - Hidden var (occur in big JD but aren;t observations and things we're actively reasoning about)\n    - we care about P(Q | e1...ek) -> too arrive here\n      1. select entries consistent with the evidence we observed\n      2. marginalization, kick out hidden var by summing over all of the value assignments for Hidden vars\n      3. normalize: multiply by 1/Z where Z is computed by summing over all Q\n\nProbabilistic Language Models:\n  - assign a probability to a sentence (ex: autocomplete for texting, machine translation, spelling correction, speech recognition)\n  - with a few observations, esttimate the probability distribution over all assignments of words in english language to that next \"random variable\" ie next word\n\n  Goals:  compute probability of a sentence or sequence of words\n  related tasks: probability of an upcoming word, given sequence of previous ones -> leads to languge model to compute this. \n    - P(W) = P(w_n|w1,w2...wn-1), calcualte ewith chain rule\n\nHow to estimate these probabilities:\n  1. maximum likelihood estimation, counting up things and dividing...just find what fraction of time, x came after y when we saw y from some text\n    - not great: inefficient, words may not be in set already (hard to have this much data)\n  2. Markov assumption: probabilitiy of what happens in next state only depends on current state (ignores history)\n    - much morre efficient approach... instead of P(won | the underdog team), do P(won | team), only depends on previous k words, not whole context of sentence\n      - k << n, easier to estimate from data -> improved maximum likelihood estimation\n\nn-gram models, start to get fairly accurate when n = 4 or 5\n\n \n\n## Module 10 Definitions\n* **Observed variable** - agenet knows certain things about state of world\n* **Unobserved variable** - agent need to reason about other aspects\n* **Model** - agent knows something about how the known variables relate to the unknown\n* **Sample space** - possible worlds in probability theory (exhaustive and mutually exclusive\n* **Random variable** - some aspect of ther world about which we may have uncertainty\n* **Joint distribtion** - specifies a real number assignment over a set of random var, ex: P(X1 = x1, X2 = x2 ...) or as P(x1, x2)\n* **Probabilistic models** - joint distribution overe a set of random variables\n* **Event** - set of E outcomes, sum of probabilities in join distribution where E's conditions are true (usually has ORs and ANDs)\n* **Marginal distributions** - subtable of JD which eliminate variables that don't care about (summing out and collapsing rows)\n* **Conditional probabilities** - probability of something happening conditioned (or given) that something else has happened. can go from JD table to this\n* **Product rule** - P(Y) * P(X|Y) = P(X,Y) let's you get back big JD table from subtables (marginal * conditional)\n* **Chain rule** - generalizes product rule so can do more than 2 var\n* **Bayes' rule** - P(X|Y) = P(Y|X) / P(Y) * P(X), build one conditional from reverse, super important\n* **** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "Baye's net is a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n",
        "  - directed acyclic graph\n",
        "  - A conditional distribution for each node\n",
        "    - A collection of distributions over X, one for each combination of parents’ values\n",
        "    - CPT: conditional probability table\n",
        "\n",
        "X and Y are indepedent if  P(x,y) = P(x)P(y), these random variables occurring don't influence each other's probability. pretty rare in real world and not that useful.\n",
        "\n",
        "conditional independence, independent if some variable Z occurs, otherwise they wouldn't be independent. important for reasoning about unobserved variables and the probability of them.\n",
        "\n",
        "P(xi | x1...xi-1) = P(xi|parents(Xi)) -> graphically encoded like this to get conditional independece assumptions\n",
        "  - often additional conditional independences that aren't as explicit but can still be enumerated from graph via an algo\n",
        "  - Baye's net allows us to model world with assumptions that we believe\n",
        "\n",
        "D-separation alg:\n",
        "  - alg for answering whether things are indepedent of each other\n",
        "  - Causal Chains: x causes y causes z.\n",
        "    - ex: low pressure causes rain which causes traffic, P(x,y,z) = P(x)P(y|x)P(z|y). Note no guranteed independece of x and z because of causal relation.\n",
        "    - Prove x independent of Z given y. P(z|x,y) = P(x,y,z) / P(x,y) = P(x)P(y|x)P(z|y) / P(x)P(y|x) = P(z|y). \n",
        "      - Because evidence along the chain \"blocks\" influence. Y's influence on Z makes X's irrelevent.\n",
        "  - Common Cause: x and z both caused by Y\n",
        "    - X: forums busy, Z: office hours fulls, Y: project due. No guranteed independece of x and z because of common cause once again (look at conditional prob tables).\n",
        "    - x independent of Z given y once again. Y can similarly block chain.\n",
        "  - Common Effect: two causes (X and Y) lead to Z\n",
        "    - are X and Y independent: Yes ex: X: raining, Y: ballgame, Z: traffic\n",
        "    - are X and Y independent gievn Z: NO since seeing Z (traffic) puts the rain and ballgame in competition\n",
        "      - backwards from other 2 cases, observing an effect activates influence between possible causes\n",
        "\n",
        "General Q: in a given BN, are two variables independent?\n",
        "Solution: Analyze the graph and any complex examples can be broken into repetitions of of the three canoncial cases.\n",
        "\n",
        "How to break down:\n",
        " - reachibility: find path between two variables (if it exists) and see if its blocked by some evidence...if so influence is blocked between them and conditinally independent\n",
        "    - one exception: third cases where there's a v structure\n",
        "\n",
        "Active/Inactive paths:\n",
        "  - Question: are X and Y conditionally indepdendent given evidence of variables {z}\n",
        "      - yes if X and Y \"d-separated\" by Z (consider all undirected paths from X to Y)\n",
        "      - NO active paths = independence\n",
        "  -Path is active if EACH triple is active in the path:\n",
        "    - causal chain A -> B -> C where B is unobserved (doesn't block influence)\n",
        "    - common cause A <- B -> C where B is unobserved\n",
        "    - common effect (v-structure): A -> B <- C where B or one of its descendenants is observed\n",
        "    - takes a single inactive segment to BLOCK a path\n",
        "\n",
        "D-separation:\n",
        "  - check for all undirected paths between Xi and Xj with query: Xi _|_ Xj | {Xk1,...Xkn} where {Xk1,...Xkn} are observed\n",
        "  - look at all triples and if one or more path is active, then independence not guranteed\n",
        "\n",
        "Inference: calculate some useful quantity from a joint probability distribution\n",
        "  - what's probability of each variable assignment to query but also which is most likely explanantion\n",
        "\n",
        "inference by enumeration:\n",
        "  - Evidence vars (what we have), Query vars(what we want), hidden variables (what we have but don't care about)\n",
        "  - want: P(Q | e1...ek)\n",
        "  - Step 1: select entries consistent with evidence\n",
        "  - Step 2: sum out H to get join of Query and Evidence\n",
        "  - Step 3: normalize by 1/z\n",
        "\n",
        "Bayes Net with Infer by Enumer Ex with alarm, burrglary, earthquake, mary calling, john calling (diagram on notes)\n",
        "  - P(B | +j, +m) \n",
        "  - start with summing over hidden variables (earthquake and alarm) which means probabilities with/without earthquake and alarm combos\n",
        "    - this operation is not very efficient especially when you # of hidden variables increase\n",
        "    - use variable elimination to speed up operation\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Baye's Net\" : \"probabilistic model -- graphical model where the nodes represent variables and the arcs represent the relationship between them\",    \n",
        "}\n"
      ],
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1614
        },
        "cellView": "form",
        "outputId": "b2dda893-a2f5-40ad-ec81-353933e11159"
      },
      "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": 53,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \nBaye's net is a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n  - directed acyclic graph\n  - A conditional distribution for each node\n    - A collection of distributions over X, one for each combination of parents’ values\n    - CPT: conditional probability table\n\nX and Y are indepedent if  P(x,y) = P(x)P(y), these random variables occurring don't influence each other's probability. pretty rare in real world and not that useful.\n\nconditional independence, independent if some variable Z occurs, otherwise they wouldn't be independent. important for reasoning about unobserved variables and the probability of them.\n\nP(xi | x1...xi-1) = P(xi|parents(Xi)) -> graphically encoded like this to get conditional independece assumptions\n  - often additional conditional independences that aren't as explicit but can still be enumerated from graph via an algo\n  - Baye's net allows us to model world with assumptions that we believe\n\nD-separation alg:\n  - alg for answering whether things are indepedent of each other\n  - Causal Chains: x causes y causes z.\n    - ex: low pressure causes rain which causes traffic, P(x,y,z) = P(x)P(y|x)P(z|y). Note no guranteed independece of x and z because of causal relation.\n    - Prove x independent of Z given y. P(z|x,y) = P(x,y,z) / P(x,y) = P(x)P(y|x)P(z|y) / P(x)P(y|x) = P(z|y). \n      - Because evidence along the chain \"blocks\" influence. Y's influence on Z makes X's irrelevent.\n  - Common Cause: x and z both caused by Y\n    - X: forums busy, Z: office hours fulls, Y: project due. No guranteed independece of x and z because of common cause once again (look at conditional prob tables).\n    - x independent of Z given y once again. Y can similarly block chain.\n  - Common Effect: two causes (X and Y) lead to Z\n    - are X and Y independent: Yes ex: X: raining, Y: ballgame, Z: traffic\n    - are X and Y independent gievn Z: NO since seeing Z (traffic) puts the rain and ballgame in competition\n      - backwards from other 2 cases, observing an effect activates influence between possible causes\n\nGeneral Q: in a given BN, are two variables independent?\nSolution: Analyze the graph and any complex examples can be broken into repetitions of of the three canoncial cases.\n\nHow to break down:\n - reachibility: find path between two variables (if it exists) and see if its blocked by some evidence...if so influence is blocked between them and conditinally independent\n    - one exception: third cases where there's a v structure\n\nActive/Inactive paths:\n  - Question: are X and Y conditionally indepdendent given evidence of variables {z}\n      - yes if X and Y \"d-separated\" by Z (consider all undirected paths from X to Y)\n      - NO active paths = independence\n  -Path is active if EACH triple is active in the path:\n    - causal chain A -> B -> C where B is unobserved (doesn't block influence)\n    - common cause A <- B -> C where B is unobserved\n    - common effect (v-structure): A -> B <- C where B or one of its descendenants is observed\n    - takes a single inactive segment to BLOCK a path\n\nD-separation:\n  - check for all undirected paths between Xi and Xj with query: Xi _|_ Xj | {Xk1,...Xkn} where {Xk1,...Xkn} are observed\n  - look at all triples and if one or more path is active, then independence not guranteed\n\nInference: calculate some useful quantity from a joint probability distribution\n  - what's probability of each variable assignment to query but also which is most likely explanantion\n\ninference by enumeration:\n  - Evidence vars (what we have), Query vars(what we want), hidden variables (what we have but don't care about)\n  - want: P(Q | e1...ek)\n  - Step 1: select entries consistent with evidence\n  - Step 2: sum out H to get join of Query and Evidence\n  - Step 3: normalize by 1/z\n\nBayes Net with Infer by Enumer Ex with alarm, burrglary, earthquake, mary calling, john calling (diagram on notes)\n  - P(B | +j, +m) \n  - start with summing over hidden variables (earthquake and alarm) which means probabilities with/without earthquake and alarm combos\n    - this operation is not very efficient especially when you # of hidden variables increase\n    - use variable elimination to speed up operation\n\n \n\n## Module 11 Definitions\n* **Baye's net** - probabilistic model -- graphical model where the nodes represent variables and the arcs represent the relationship between them\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Naive Bayes learns a set of probabilities while perceptrons have a weight associated with each feature and update weights accordingly (if current weight casuses misclassification) \n",
        "\n",
        "machine learning will give us a mechanism for acquiring the data/experiences that we need to use a model from data\n",
        "  - learnring parameters(eg probabilities)\n",
        "  - learning structure and predicting them(eg BN graphs)\n",
        "  - learring hidden concepts(eg clustering, don't have data to learn)\n",
        "\n",
        "Naive Bayes -> makes independence assumptions in order to achieve classification\n",
        "  - input for system may be some kind of feature vector\n",
        "  - output : classification: choose frm a small/finite set of a classes, regresssion: assign and determine a real number\n",
        "  - ML Steps:\n",
        "      - have a set/collection of training data labeled with their class\n",
        "      - with that collection, learn a function that will take in new data and predict a class for it\n",
        "      - for each data point, transform it into a vector of features. Ex: for email, features could be the word \"viagra\" appeearing or \"free\" appearing\n",
        "\n",
        "Model-Based Classification:\n",
        "  - build a model (eg Bayes' net) where both the llabels and features are random variables\n",
        "  - instantiate any observed features\n",
        "  - query model in same way..what class is this?\n",
        "Naive Bayes:\n",
        "  - assume all features are independent effects of the label (of each other)\n",
        "    - have probaulities set up as P(Feature | Class)\n",
        "    - digit ocr example:\n",
        "      - have each coordinate <i,j> be feature Fij which is either off or on\n",
        "      - Naive Bayes model query would say: P(Class_Y, F00..F01...F1515) ie probability that it's class X given this feature list = P(Y)*product of each of P(Fi|Y) where P(Y) is prior probability of class Y\n",
        "      - have Y labels, then n * F * Y parameters whereas a full joint distrib would have Y * F^n...n is number of vals f can have.\n",
        "      - this model is simiplisitc and doesn't perfectly capture reality since total number of parameters is linear in number of features\n",
        "  - inference method in NB\n",
        "    - step 1: get joint probability of a label and evidence for each label, P(Y,f1...fn)\n",
        "    - step 2: sum to get probability of evidence -> P(f1..fn)\n",
        "    - step 3: normalize by dividing step 1 by step 2 to get P(Y|f1...fn)\n",
        "  - estimates of local conditional probability tables\n",
        "    - P(Y) - prior prob of labels\n",
        "    - P(Fi | Y) - for each feature (evidence variable)\n",
        "    - these probabilities are collectively the \"parameters\" of the model and denoted by theta which we'll get from training\n",
        "\n",
        "3 types of data:\n",
        "  - training data (estimate model params like probabilities)\n",
        "  - test data (use it this to test and compute accuracy)\n",
        "  - held out set (used for fine tuning hyperparamters)\n",
        "\n",
        "overfitting: when you too closely model training data that don't generalize to other test data\n",
        "  - should never (or sparingly) assign a probability of 0 to a feature since we compute by calculating a product, especially if it's just a unseen event\n",
        "  - to generalize better: smooth or regularize the estimates\n",
        "\n",
        "Paramter Estimation:\n",
        "  - elicitation (ask human/expert)\n",
        "  - empirically: use training data to learn, and look at empirical rate of any value.\n",
        "    - choose the estimate that meximizes likelihood of the datat (via liklihood function)\n",
        "    - add all occurences and divide by total samples: count(x)/# samples\n",
        "\n",
        "Laplace Smoothing:\n",
        "  - pretend you saw every outcome once more than you actually did (prevent 0's)\n",
        "  - instead of maximizes likelihood, (count(x) + 1) / (# things in samples + |X|) where |X| is # unique things in sample\n",
        "  - instead of doiing by 1, can do by some constant k so : P_lap,k(x) = (count(x) + k) / (# things in samples + k|X|)\n",
        "  - add to and smooth condittiional probabilities: P_lap,k(x|y) = (count(x,y) + k) / (count(y) + k|X|)\n",
        "  - not greate for conditionals when |X| or |Y| is large\n",
        "\n",
        "Linear Interpolation: another technique to remove 0's and help generalize\n",
        "  - hyperparam is alpha: P_lin(x|y) = alpha*P(x|y) + (1-alpha)*P(x), so how much you want to weigh prior probability of class label over conditional (maximum likelihood calc)\n",
        "\n",
        "Tuning models:\n",
        "  - in general learn probabiities with training set and tune hyperparams with held out/dev set\n",
        "  - potentially changing features\n",
        "\n",
        "Baseline:\n",
        "  - simplee \"straw man\" procedures to determine how hard the task is and what a \"good\" accuracy is\n",
        "  - for real researrch use prervious work as a (strong) baseline\n",
        "  - weak baseline could be skewed, eex: most freq label classifier is only one in test data\n",
        "\n",
        "Perceptron: a decision making device by weighing inputs\n",
        "  - have a bunch of inputs, each of which is associated with a weight\n",
        "  - take the weighted sum and the activation function will compare it to some threshold to determine the output, ex: 0 (spam) if <= thresh else 1 (ham)\n",
        "  - w is weight vector and x is input/feature vector\n",
        "  - can call bias, b, - threshold. so say 0 if w * x + b <= 0 and 1 if w * x + b > 0\n",
        "  - separating hyperplane is orthogonal to weight vector so (if < 90 degrees than take on positive classification, > 90 degrees takes on negative)\n",
        "    - bias term allows you to move decision boundary towards or away a classification\n",
        "\n",
        "Learning (binary classification so spam or not): \n",
        "  - Uses error driven learning to adjust weights\n",
        "  - initially start with weights = 0\n",
        "  - for each training instance:\n",
        "    - classifiy with current weights. if correct, no change, if wrong adjust weight vector by adding or subtracting and repeat this.\n",
        "    - if the guess was negativee classification, subtract as this adjusts hyperplane boundary by shifting weight vector\n",
        "\n",
        "Multiclass Decision Rule\n",
        "  - weight vector for every class\n",
        "  - score (activation) of every class so that y = argmax_y w_y * f(x) and highest dot product wins\n",
        " Learning (Multiclass classification): \n",
        "  - initially start with weights = 0\n",
        "  - for each training instance:\n",
        "    - classifiy with current weights. if correct, no change, if wrong adjust the two relevent weight vectors. \n",
        "    - subtract from the one that was incorrectly chosen as label (w_y = w_y - f(x)) and increase weights it should have predicted\n",
        "\n",
        "Properties of Perceptrons:\n",
        "  - for binary cases\n",
        "  - if data is linearly separable (So can separate data into two classes) than you CAN converge on set of weights that classify\n",
        "  - if not linearly separable, you have to come up with mistake bound, maximum number of mistakes related to the margin or degree of seeparabiliity\n",
        "    - mistakes < k / margin ^ 2\n",
        "\n",
        "Problems with perceptron:\n",
        "  - if non-separable than weights might thrash (go back and forth between weights)\n",
        "    - can address this by averaging weight vectors over time\n",
        "  - which hyperplane to pick as best?\n",
        "  - overtraining: type of overfitting\n",
        "    - training accuracy goes up but it's too fit to this data, too much training\n",
        "    - can use held-out development set so that if performance starts to decrease for this, then stop training\n",
        "\n",
        "Fixing perceptron:\n",
        "MIRA: margin infused relaxed algo\n",
        "  - instead of updating weights by big amount, just a little to fix current mistake\n",
        "  - instead of w_y = w'_y - f(x) scaled it down with constant tau so w_y = w'_y - tau*f(x) (one that was wrongly predicted) and w_y* = w'_y* + tau*f(x) (one that should've been predicted)\n",
        "  - tau = (*w'y - w'y*) * f + 1)/ 2f * f .. + 1 helps to generalize\n",
        "  - sometimes do tau* = min (tau, C) where C is a capped max that you want to adjust by\n",
        "  - this can help converge faster, and is better when you may not have enough features, and better on noisy data and non-separable data\n",
        "\n",
        "Linear Separators:\n",
        "  - which separator to use?\n",
        "  - SVM or support vector machine find separator with max margin\n",
        "  - essentiallly MIRA but you optimize over all examples at once\n",
        "Non-Linear Separators:\n",
        "  - add another dimension, ex: value squared, then you can now linearly separate\n",
        "  - essentially just transforms your inputs\n",
        "  \n",
        "perceptrons are generally more accurate then Navie Bayes, makes less assumptions about data, and require multiple pass throughs the data (NB just does once)\n",
        "\n",
        "  \n",
        "\"\"\"\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3521
        },
        "cellView": "form",
        "outputId": "1f5331bd-fd75-4615-8e8e-36d86c71e7a2"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 55,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Naive Bayes learns a set of probabilities while perceptrons have a weight associated with each feature and update weights accordingly (if current weight casuses misclassification) \n\nmachine learning will give us a mechanism for acquiring the data/experiences that we need to use a model from data\n  - learnring parameters(eg probabilities)\n  - learning structure and predicting them(eg BN graphs)\n  - learring hidden concepts(eg clustering, don't have data to learn)\n\nNaive Bayes -> makes independence assumptions in order to achieve classification\n  - input for system may be some kind of feature vector\n  - output : classification: choose frm a small/finite set of a classes, regresssion: assign and determine a real number\n  - ML Steps:\n      - have a set/collection of training data labeled with their class\n      - with that collection, learn a function that will take in new data and predict a class for it\n      - for each data point, transform it into a vector of features. Ex: for email, features could be the word \"viagra\" appeearing or \"free\" appearing\n\nModel-Based Classification:\n  - build a model (eg Bayes' net) where both the llabels and features are random variables\n  - instantiate any observed features\n  - query model in same way..what class is this?\nNaive Bayes:\n  - assume all features are independent effects of the label (of each other)\n    - have probaulities set up as P(Feature | Class)\n    - digit ocr example:\n      - have each coordinate <i,j> be feature Fij which is either off or on\n      - Naive Bayes model query would say: P(Class_Y, F00..F01...F1515) ie probability that it's class X given this feature list = P(Y)*product of each of P(Fi|Y) where P(Y) is prior probability of class Y\n      - have Y labels, then n * F * Y parameters whereas a full joint distrib would have Y * F^n...n is number of vals f can have.\n      - this model is simiplisitc and doesn't perfectly capture reality since total number of parameters is linear in number of features\n  - inference method in NB\n    - step 1: get joint probability of a label and evidence for each label, P(Y,f1...fn)\n    - step 2: sum to get probability of evidence -> P(f1..fn)\n    - step 3: normalize by dividing step 1 by step 2 to get P(Y|f1...fn)\n  - estimates of local conditional probability tables\n    - P(Y) - prior prob of labels\n    - P(Fi | Y) - for each feature (evidence variable)\n    - these probabilities are collectively the \"parameters\" of the model and denoted by theta which we'll get from training\n\n3 types of data:\n  - training data (estimate model params like probabilities)\n  - test data (use it this to test and compute accuracy)\n  - held out set (used for fine tuning hyperparamters)\n\noverfitting: when you too closely model training data that don't generalize to other test data\n  - should never (or sparingly) assign a probability of 0 to a feature since we compute by calculating a product, especially if it's just a unseen event\n  - to generalize better: smooth or regularize the estimates\n\nParamter Estimation:\n  - elicitation (ask human/expert)\n  - empirically: use training data to learn, and look at empirical rate of any value.\n    - choose the estimate that meximizes likelihood of the datat (via liklihood function)\n    - add all occurences and divide by total samples: count(x)/# samples\n\nLaplace Smoothing:\n  - pretend you saw every outcome once more than you actually did (prevent 0's)\n  - instead of maximizes likelihood, (count(x) + 1) / (# things in samples + |X|) where |X| is # unique things in sample\n  - instead of doiing by 1, can do by some constant k so : P_lap,k(x) = (count(x) + k) / (# things in samples + k|X|)\n  - add to and smooth condittiional probabilities: P_lap,k(x|y) = (count(x,y) + k) / (count(y) + k|X|)\n  - not greate for conditionals when |X| or |Y| is large\n\nLinear Interpolation: another technique to remove 0's and help generalize\n  - hyperparam is alpha: P_lin(x|y) = alpha*P(x|y) + (1-alpha)*P(x), so how much you want to weigh prior probability of class label over conditional (maximum likelihood calc)\n\nTuning models:\n  - in general learn probabiities with training set and tune hyperparams with held out/dev set\n  - potentially changing features\n\nBaseline:\n  - simplee \"straw man\" procedures to determine how hard the task is and what a \"good\" accuracy is\n  - for real researrch use prervious work as a (strong) baseline\n  - weak baseline could be skewed, eex: most freq label classifier is only one in test data\n\nPerceptron: a decision making device by weighing inputs\n  - have a bunch of inputs, each of which is associated with a weight\n  - take the weighted sum and the activation function will compare it to some threshold to determine the output, ex: 0 (spam) if <= thresh else 1 (ham)\n  - w is weight vector and x is input/feature vector\n  - can call bias, b, - threshold. so say 0 if w * x + b <= 0 and 1 if w * x + b > 0\n  - separating hyperplane is orthogonal to weight vector so (if < 90 degrees than take on positive classification, > 90 degrees takes on negative)\n    - bias term allows you to move decision boundary towards or away a classification\n\nLearning (binary classification so spam or not): \n  - Uses error driven learning to adjust weights\n  - initially start with weights = 0\n  - for each training instance:\n    - classifiy with current weights. if correct, no change, if wrong adjust weight vector by adding or subtracting and repeat this.\n    - if the guess was negativee classification, subtract as this adjusts hyperplane boundary by shifting weight vector\n\nMulticlass Decision Rule\n  - weight vector for every class\n  - score (activation) of every class so that y = argmax_y w_y * f(x) and highest dot product wins\n Learning (Multiclass classification): \n  - initially start with weights = 0\n  - for each training instance:\n    - classifiy with current weights. if correct, no change, if wrong adjust the two relevent weight vectors. \n    - subtract from the one that was incorrectly chosen as label (w_y = w_y - f(x)) and increase weights it should have predicted\n\nProperties of Perceptrons:\n  - for binary cases\n  - if data is linearly separable (So can separate data into two classes) than you CAN converge on set of weights that classify\n  - if not linearly separable, you have to come up with mistake bound, maximum number of mistakes related to the margin or degree of seeparabiliity\n    - mistakes < k / margin ^ 2\n\nProblems with perceptron:\n  - if non-separable than weights might thrash (go back and forth between weights)\n    - can address this by averaging weight vectors over time\n  - which hyperplane to pick as best?\n  - overtraining: type of overfitting\n    - training accuracy goes up but it's too fit to this data, too much training\n    - can use held-out development set so that if performance starts to decrease for this, then stop training\n\nFixing perceptron:\nMIRA: margin infused relaxed algo\n  - instead of updating weights by big amount, just a little to fix current mistake\n  - instead of w_y = w'_y - f(x) scaled it down with constant tau so w_y = w'_y - tau*f(x) (one that was wrongly predicted) and w_y* = w'_y* + tau*f(x) (one that should've been predicted)\n  - tau = (*w'y - w'y*) * f + 1)/ 2f * f .. + 1 helps to generalize\n  - sometimes do tau* = min (tau, C) where C is a capped max that you want to adjust by\n  - this can help converge faster, and is better when you may not have enough features, and better on noisy data and non-separable data\n\nLinear Separators:\n  - which separator to use?\n  - SVM or support vector machine find separator with max margin\n  - essentiallly MIRA but you optimize over all examples at once\nNon-Linear Separators:\n  - add another dimension, ex: value squared, then you can now linearly separate\n  - essentially just transforms your inputs\n  \nperceptrons are generally more accurate then Navie Bayes, makes less assumptions about data, and require multiple pass throughs the data (NB just does once)\n\n  \n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "Classifier Components:\n",
        "  - feature representation of the input, has become less important over time\n",
        "  - classification function that computes the estimated class y_hat (highest probability class) via p(y|x)\n",
        "  - an objective/loss function for learning that shows performance, usually involving minimizing error on training examples.\n",
        "  - an algo for optimizing the obj function (stochastic gradient descent) and updating the params\n",
        "\n",
        "Logistic Regression: another classifier like Perceptron (sentiment analysis ex):\n",
        "  - solves estimating P(y = 1 | x) by learning from a training set, a vector of weights and a bias term so z = w * x + b\n",
        "  - LR changes range of outputs, rather than set classes, it is a range of number values like -inf to inf\n",
        "    - the z value is squished via a sigmoid function : y = 1/ (1 + e^-z) (vals range from 0 to 1)\n",
        "    - to have proper probability distribution, all of the possible label values have to sum up to 1\n",
        "    - For binary: P(y = 1) = sigmoid(W * x + b) so P(y = 0) = 1 - sigmoid... with threshold of .5\n",
        "  - need to consider extracting features (ex: count of positive llexicon words, does ! appear, how many \"no\" occured)\n",
        "  - associate weights with these (can be positive or negative)\n",
        "\n",
        "Learning with LR using loss function:\n",
        "  - obj or loss function tells us distance between system and gold output (even if picked correct class, want to see what percent it predicted)\n",
        "  - (L(y_hat, y)) = how much y_hat differs from true y)\n",
        "  - example is mean squarerd error Lmse = 1/2(y_hat - y)^2 (not great though)\n",
        "  - cross entropy loss function (negative log liklihood loss) -> maximize probability of true labels by minimizing negative probability (in log space)\n",
        "  - use sotachstic gradient descent to minimize the loss function\n",
        "\n",
        "Cross Entropy loss function:\n",
        "  - maximize probability of true label y: p(y|x) = y_hat^y(1-y_hat)^(1-y)\n",
        "    - if we say correct label is y = 1, then plugging in y = 1 gives y_hat when you simplify (*want y_hat as close to 1 as possible)\n",
        "    - if we say correct labe is y = 0, then we get 1 - y_hat (*want y_hat to as close to 0 as possible)\n",
        "    - put log space by log both sides of equation to maximize log property and to finally minimize negative log, flip sign (eq on sheet)\n",
        "\n",
        "Gradient Descent: find good settings for our weights and bias (both encompassed in theta) by minimizing loss function\n",
        "  - alg to find theta (optimal weights and bias) that results in minimium loss\n",
        "  - finds a minimum of a function by by finding which direction in the space of theta that the function's slope is rising the most steeply and moving in opposite direc by a step\n",
        "    - size of step taken is learning rate: eta (consider decreasing over time)\n",
        "    - slope is negative, moving in right direction and if it's positive, we passed the minimum\n",
        "    - *we want to apply this to a n-dimensional space so can do this for and update multiple weights\n",
        "  - for linear regression, the loss function is convenitently convex (there is only one minimum) so gradient descent always guranteed to find minimum\n",
        "\n",
        "-With loss functions/deriv of loss functions can figure out Cost(w,b) by summing over all features and dividing by number to get average.\n",
        "\n",
        "Mini batch training: \n",
        "  - stochastic gradient desc chooses a single random example at a time and updates its weights on that example. updates can fluctuate\n",
        "  - alt: batch training, computees gradient over entire dataset which gives better estimate of whiich direction to move the weights BUT takes longer\n",
        "  - BETTER: mini batch -> train on a small batch (~512 or 1024), and loss is then accumalted\n",
        "\n",
        "Regularization:\n",
        "  - overfitting: poor generlaization...for LR if a feature only occurs in one class then it will get a high weight\n",
        "    - sometimes this feature is just a noisy factor and this can have too much weight\n",
        "  - regularization: way to penallize large weights, a regularizatin term is added to the loss function\n",
        "    - lasso regression uses L1 regul (linear func of weight vals)\n",
        "    - ridge reg L2 (quadratic function, easier to optimize)\n",
        "\n",
        "Multinomial logisitic regression:\n",
        "  - instead of binary class so we wantt to know prob of y for eaech class c : P(y=c | x)\n",
        "  - use a generalization of the sigmoid function (softmax func) so that having multiple classes still sums to 1\n",
        "\n",
        "Neural network:\n",
        "  - perceptron network\n",
        "  - multiplee inputs that all go to different hidden layer perceptrons that will then serve as inputs to another perceptron layer until reaching an output layer\n",
        "  - LR better than perceptron because sigmoid adds a gradual change/smoothness while small weight changes in perceptron can quickly flip 0 to 1\n",
        "    - smoothness important for derivatives\n",
        "  - NN uses activation function (ensure its differentiable)\n",
        "    - outputs an activation value, a = f(z), and applies a non-linaer function to z = w*x + b.\n",
        "    - output of NN is called y so if activation is the final output of a network then y = a\n",
        "    - f is generally a sigmoid func, tanh func, or rectified linear unit ReLU\n",
        "\n",
        "Feed-forward NN:\n",
        "  - simples kind of NN\n",
        "  - multilayer network, all units are usually fully-connected, and no cycles\n",
        "  - outputs frm each layer are passed to units in the next layer\n",
        "\n",
        "Training NN:\n",
        "  - loss function (Cross entropy loss), optim alg (gradient descent), AND * a way of computing the gradient of the loss function (error propagation)\n",
        "  - gradient descent like before would only work for one layer. we need to look back through all the earlier layers in the network to compute gradient\n",
        "  - SOLTN: error back propagation (similar to backwatd differentiation):\n",
        "    - define computation graph and then figure out how much each element contributes -> loss function can than be a graph\n",
        "    - computation is broken down into separate operations where each op is a node in graph\n",
        "    - backward diff uses chain rules frm calculus to compute derivatives needed for the weight update\n",
        "    - with the graph on sheet, can pass deriv. backwards\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2547
        },
        "cellView": "form",
        "outputId": "a657f722-1bb5-4ffc-a124-09bb5fc462ae"
      },
      "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": 57,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier Components:\n  - feature representation of the input, has become less important over time\n  - classification function that computes the estimated class y_hat (highest probability class) via p(y|x)\n  - an objective/loss function for learning that shows performance, usually involving minimizing error on training examples.\n  - an algo for optimizing the obj function (stochastic gradient descent) and updating the params\n\nLogistic Regression: another classifier like Perceptron (sentiment analysis ex):\n  - solves estimating P(y = 1 | x) by learning from a training set, a vector of weights and a bias term so z = w * x + b\n  - LR changes range of outputs, rather than set classes, it is a range of number values like -inf to inf\n    - the z value is squished via a sigmoid function : y = 1/ (1 + e^-z) (vals range from 0 to 1)\n    - to have proper probability distribution, all of the possible label values have to sum up to 1\n    - For binary: P(y = 1) = sigmoid(W * x + b) so P(y = 0) = 1 - sigmoid... with threshold of .5\n  - need to consider extracting features (ex: count of positive llexicon words, does ! appear, how many \"no\" occured)\n  - associate weights with these (can be positive or negative)\n\nLearning with LR using loss function:\n  - obj or loss function tells us distance between system and gold output (even if picked correct class, want to see what percent it predicted)\n  - (L(y_hat, y)) = how much y_hat differs from true y)\n  - example is mean squarerd error Lmse = 1/2(y_hat - y)^2 (not great though)\n  - cross entropy loss function (negative log liklihood loss) -> maximize probability of true labels by minimizing negative probability (in log space)\n  - use sotachstic gradient descent to minimize the loss function\n\nCross Entropy loss function:\n  - maximize probability of true label y: p(y|x) = y_hat^y(1-y_hat)^(1-y)\n    - if we say correct label is y = 1, then plugging in y = 1 gives y_hat when you simplify (*want y_hat as close to 1 as possible)\n    - if we say correct labe is y = 0, then we get 1 - y_hat (*want y_hat to as close to 0 as possible)\n    - put log space by log both sides of equation to maximize log property and to finally minimize negative log, flip sign (eq on sheet)\n\nGradient Descent: find good settings for our weights and bias (both encompassed in theta) by minimizing loss function\n  - alg to find theta (optimal weights and bias) that results in minimium loss\n  - finds a minimum of a function by by finding which direction in the space of theta that the function's slope is rising the most steeply and moving in opposite direc by a step\n    - size of step taken is learning rate: eta (consider decreasing over time)\n    - slope is negative, moving in right direction and if it's positive, we passed the minimum\n    - *we want to apply this to a n-dimensional space so can do this for and update multiple weights\n  - for linear regression, the loss function is convenitently convex (there is only one minimum) so gradient descent always guranteed to find minimum\n\n-With loss functions/deriv of loss functions can figure out Cost(w,b) by summing over all features and dividing by number to get average.\n\nMini batch training: \n  - stochastic gradient desc chooses a single random example at a time and updates its weights on that example. updates can fluctuate\n  - alt: batch training, computees gradient over entire dataset which gives better estimate of whiich direction to move the weights BUT takes longer\n  - BETTER: mini batch -> train on a small batch (~512 or 1024), and loss is then accumalted\n\nRegularization:\n  - overfitting: poor generlaization...for LR if a feature only occurs in one class then it will get a high weight\n    - sometimes this feature is just a noisy factor and this can have too much weight\n  - regularization: way to penallize large weights, a regularizatin term is added to the loss function\n    - lasso regression uses L1 regul (linear func of weight vals)\n    - ridge reg L2 (quadratic function, easier to optimize)\n\nMultinomial logisitic regression:\n  - instead of binary class so we wantt to know prob of y for eaech class c : P(y=c | x)\n  - use a generalization of the sigmoid function (softmax func) so that having multiple classes still sums to 1\n\nNeural network:\n  - perceptron network\n  - multiplee inputs that all go to different hidden layer perceptrons that will then serve as inputs to another perceptron layer until reaching an output layer\n  - LR better than perceptron because sigmoid adds a gradual change/smoothness while small weight changes in perceptron can quickly flip 0 to 1\n    - smoothness important for derivatives\n  - NN uses activation function (ensure its differentiable)\n    - outputs an activation value, a = f(z), and applies a non-linaer function to z = w*x + b.\n    - output of NN is called y so if activation is the final output of a network then y = a\n    - f is generally a sigmoid func, tanh func, or rectified linear unit ReLU\n\nFeed-forward NN:\n  - simples kind of NN\n  - multilayer network, all units are usually fully-connected, and no cycles\n  - outputs frm each layer are passed to units in the next layer\n\nTraining NN:\n  - loss function (Cross entropy loss), optim alg (gradient descent), AND * a way of computing the gradient of the loss function (error propagation)\n  - gradient descent like before would only work for one layer. we need to look back through all the earlier layers in the network to compute gradient\n  - SOLTN: error back propagation (similar to backwatd differentiation):\n    - define computation graph and then figure out how much each element contributes -> loss function can than be a graph\n    - computation is broken down into separate operations where each op is a node in graph\n    - backward diff uses chain rules frm calculus to compute derivatives needed for the weight update\n    - with the graph on sheet, can pass deriv. backwards\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2414
        },
        "outputId": "8d4c69d7-bdef-40d9-cd33-529eb5dc9542"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier Components:\n  - feature representation of the input, has become less important over time\n  - classification function that computes the estimated class y_hat (highest probability class) via p(y|x)\n  - an objective/loss function for learning that shows performance, usually involving minimizing error on training examples.\n  - an algo for optimizing the obj function (stochastic gradient descent) and updating the params\n\nLogistic Regression: another classifier like Perceptron (sentiment analysis ex):\n  - solves estimating P(y = 1 | x) by learning from a training set, a vector of weights and a bias term so z = w * x + b\n  - LR changes range of outputs, rather than set classes, it is a range of number values like -inf to inf\n    - the z value is squished via a sigmoid function : y = 1/ (1 + e^-z) (vals range from 0 to 1)\n    - to have proper probability distribution, all of the possible label values have to sum up to 1\n    - For binary: P(y = 1) = sigmoid(W * x + b) so P(y = 0) = 1 - sigmoid... with threshold of .5\n  - need to consider extracting features (ex: count of positive llexicon words, does ! appear, how many \"no\" occured)\n  - associate weights with these (can be positive or negative)\n\nLearning with LR using loss function:\n  - obj or loss function tells us distance between system and gold output (even if picked correct class, want to see what percent it predicted)\n  - (L(y_hat, y)) = how much y_hat differs from true y)\n  - example is mean squarerd error Lmse = 1/2(y_hat - y)^2 (not great though)\n  - cross entropy loss function (negative log liklihood loss) -> maximize probability of true labels by minimizing negative probability (in log space)\n  - use sotachstic gradient descent to minimize the loss function\n\nCross Entropy loss function:\n  - maximize probability of true label y: p(y|x) = y_hat^y(1-y_hat)^(1-y)\n    - if we say correct label is y = 1, then plugging in y = 1 gives y_hat when you simplify (*want y_hat as close to 1 as possible)\n    - if we say correct labe is y = 0, then we get 1 - y_hat (*want y_hat to as close to 0 as possible)\n    - put log space by log both sides of equation to maximize log property and to finally minimize negative log, flip sign (eq on sheet)\n\nGradient Descent: find good settings for our weights and bias (both encompassed in theta) by minimizing loss function\n  - alg to find theta (optimal weights and bias) that results in minimium loss\n  - finds a minimum of a function by by finding which direction in the space of theta that the function's slope is rising the most steeply and moving in opposite direc by a step\n    - size of step taken is learning rate: eta (consider decreasing over time)\n    - slope is negative, moving in right direction and if it's positive, we passed the minimum\n    - *we want to apply this to a n-dimensional space so can do this for and update multiple weights\n  - for linear regression, the loss function is convenitently convex (there is only one minimum) so gradient descent always guranteed to find minimum\n\n-With loss functions/deriv of loss functions can figure out Cost(w,b) by summing over all features and dividing by number to get average.\n\nMini batch training: \n  - stochastic gradient desc chooses a single random example at a time and updates its weights on that example. updates can fluctuate\n  - alt: batch training, computees gradient over entire dataset which gives better estimate of whiich direction to move the weights BUT takes longer\n  - BETTER: mini batch -> train on a small batch (~512 or 1024), and loss is then accumalted\n\nRegularization:\n  - overfitting: poor generlaization...for LR if a feature only occurs in one class then it will get a high weight\n    - sometimes this feature is just a noisy factor and this can have too much weight\n  - regularization: way to penallize large weights, a regularizatin term is added to the loss function\n    - lasso regression uses L1 regul (linear func of weight vals)\n    - ridge reg L2 (quadratic function, easier to optimize)\n\nMultinomial logisitic regression:\n  - instead of binary class so we wantt to know prob of y for eaech class c : P(y=c | x)\n  - use a generalization of the sigmoid function (softmax func) so that having multiple classes still sums to 1\n\nNeural network:\n  - perceptron network\n  - multiplee inputs that all go to different hidden layer perceptrons that will then serve as inputs to another perceptron layer until reaching an output layer\n  - LR better than perceptron because sigmoid adds a gradual change/smoothness while small weight changes in perceptron can quickly flip 0 to 1\n    - smoothness important for derivatives\n  - NN uses activation function (ensure its differentiable)\n    - outputs an activation value, a = f(z), and applies a non-linaer function to z = w*x + b.\n    - output of NN is called y so if activation is the final output of a network then y = a\n    - f is generally a sigmoid func, tanh func, or rectified linear unit ReLU\n\nFeed-forward NN:\n  - simples kind of NN\n  - multilayer network, all units are usually fully-connected, and no cycles\n  - outputs frm each layer are passed to units in the next layer\n\nTraining NN:\n  - loss function (Cross entropy loss), optim alg (gradient descent), AND * a way of computing the gradient of the loss function (error propagation)\n  - gradient descent like before would only work for one layer. we need to look back through all the earlier layers in the network to compute gradient\n  - SOLTN: error back propagation (similar to backwatd differentiation):\n    - define computation graph and then figure out how much each element contributes -> loss function can than be a graph\n    - computation is broken down into separate operations where each op is a node in graph\n    - backward diff uses chain rules frm calculus to compute derivatives needed for the weight update\n    - with the graph on sheet, can pass deriv. backwards\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 15592
        },
        "id": "T3cm1WV542_a",
        "outputId": "e07dc21a-ee3f-4265-b538-826e213b90a9"
      },
      "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": 66,
      "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 Chapter 16.1 summary.  $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 Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nMDPs \n- non-deterministic search problems in fully observable task env, where you have to make a sequence of actions (sequential),\n- outcomes are non-deterministic (stochastic)\n- expectimax is a way to solve\n- Transitions are markovian if the probability of arriving at s' deponds on s and not earlier history.\n- Like search problem, has set of states, actions, intial and terminal statets but now has transition and reward function.\n- solution is going to be a policy, returns best action based on input state. \n\n- To determrine optimal policy, compute expected utility of all possible paths generated by a policy. \n- if reward for each move is < negative terminal (like -1.65) state than going to this negative terminal CAN be betterr, if -.03 < r < 0\nit will try to get to positive terminal state. \n- If r > 0 then it will stay at non-terminal states.\n- To deal with inifinite utilities, have a finite horizon like in depth-limited search.\n  - (terminate after fixed steps or give non-stationary policies, pi depends on time left, or just discounting). \n- expectimax is too much work, there are better options.\n\nValue Iteration: start with V_0(s) = 0: no time steps left means an expected reward sum of zero (this is the \"terminal state\"). Then do formula for each V_k+1(s) which is\nV*(s) but replace V*(s') with V_k(s').\nRepeat this until convergence...complexity of each iteration is O(S^2*A). guranteed to converge to unique optimal values (because of decay). \n\n\nRather than just calculating values, can evaluate which policy is best ->iteration over policies. calculate expected values for a policy, previously picked optimal action after evaluating values of each action.\nNowe can just pick action that pi(s) says. Easier to compute utility/value of statee. Same as before but with out max action. Can solve V's as a system of linear equations.\n\n\nwhen given optimal values: For each pi*(s) -> do mini expectimax (policy extraction)\nwhen given optimal q-values:, trivial just choose max q value out of all actions\n\npolicy iteration: \nStep 1: Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n• Step 2: Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future\nvalues\n• Repeat steps until policy converges\n\nPolicy vs value iteration: both take in MDP and output optimal quanity. in value: update valuese and implictly policy (doeesn't actually track policy)\n\nin policy: several passes that update utilities with ONE fixed policy, then pick new policy, new policy will be better or we're done\n- both are dp solutions to MDPs\n\nMaximum Expected Utility: in expectimax and MDPs, averaging over utlities\n  - utilities should summarize the agents goals, any ratiinal preferences can be summarized as a utility func\n  - rather than prescribe behaviors to agents, we do utilities and let them pick (also have to consider uncertainities)\nagent must have preferences: A >- B is prefers A. A ~ B means indifferent\n\nTo deteeremine rational preferences, put some constraints:\n  1. axiom of transivitity: if A >- B and B >- C then A >- C\n  2. Orderability: eithere A >- B OR b >- A OR A~ B\n  3. Continuity: A >- B >- C => theere's a threshold p in lotterry of A and C where they are indifferent to that and B\n  4. Subitituatbility: A ~ B => loterry with A and C ~ loterry with B and C\n  5. Monotonicity: A >- B, want a lottery with A and B where prob for A is higher\n*If follow these, then maximize utility and can make a real valued utility function out of it\nMEU -> choose action that miximizes expected utility\n\nUtility Scale for people:\nNormalized utilites: between 0 and 1\nmicromort: one-millionh chance of death\nQALYS: quality adjustetd life years, for medical decisions involving risk\nthese are invariant under positive linear rtansformation: reason abou risk and probailitties\n  U'(x) = k1U(x) + k2 where k1 > 0\n  -use standard lottrey to enumerate, adjust until lottery p until indiffeerence: A ~ Lp\n-money doesn't behave as a utility function - U(L) < U(EMV(L)) is what people believe as peeople are risk-averse\n\n\n\"Policy Iteratiton alg\": \"two steps: 1. policy evaulatiion -> calculate utilities for a fixed policy until convergence (not yet optimal), 2. policy improvement: update policy using one-step look-ahead with resulting converged utilities. repeat both until policy converges, optimal\",\n\n\"q-state\": \"(s,a) -> you have your state and action you want to take (like expectimax), transition gives u prob for each next state from this. Q*(s,a) is expected utility/value starting out with taking (s,a) and acting optimally\",\n\n\"Value/utility (V*(s))\": \"expected utiility starting in s and acting optimally. compute expectimax for each state: expected utility from picking optimal action, sum of rewards\",\n\n\"Value Iteration\": \"start with V_0(s) = 0: no time steps left means an eexpected reward sum of zero, very slow tho, values keep changing but actions converge earlier\",\n\n\"Principal of maximizing expecteed utility\": \"a rational agent should choose the action that maximized its expected utility, given its knowledge (probabiliyt districution, outcomes) (not neccessarily worry about worstcase)\",\n\n\"Discounting\": \"value of rewards decay exponentially, represent sooner rewards are better, done via a decay factor so each n step is decay^n * reward, helps with convergence\",\n\n  \n\n## Module 8 Definitions\n* **Stochastic transition model** - Gives probability of different outcomes based on action - T(s,a,s')\n* **Transition function** - Takes in current state, action, and desired state and gives probabillity of this desired state occuring\n* **Reward function.** - gives reward for each action (can be + or -), R(s,a,s') or defined in any way like R(s'), shapes agents behavior\n* **Total utiliity.** - add up rewards at each step along a path. preferences for agent: highest reward, ASAP - discounting\n* **Policy(pi)** - function that retuns best action based on input state. try to find optimal policy (pi*) which can be achieved based on reward function\n* **Absorbing state:** - gurantee that for every policy, terminal state will be reached eventually\n* **Lotteries** - situations with uncertain prizes (L = [p, A; (1-p), B]) where A and B are prizes\n\n\n## WARNING: Your definition of 'Regret' is too long!\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n RL: Agent must learn reward function and transition function rather than being given it (MDP, it was stochastic but we knew probability distribution and reward). It learns by interacting\nwith the world. For every action, it recieved feedback (\"observe sample\") as a reward and state and goal is to maximize expected reward. Agent's utility is defined by reward function.\nThere is a tradeoff between exploration and exploitation. Reinforcement Learning, still uncertain envrionments so need to act to learn not just computations. \n\nModel-based learning: learn approximate probability distribution of transition function based. learn by taking a bunch of samples and normalize\nto get values for T. Discover R when we expereince (s,a,s'). Finally solve as MDP. \n\nModel-free learning: we don't construct explicit T function. Every time we take an action, compare what happened to what we expected to happen and whenever something\ndeviates, takee values and adjust up or down. Just track of values of a state. \n\nPassive Reinforcement Learning: \n  more so like policy evaluation: we have a fixed policy pi (without knowing T or R)and determine value of being in this state\n\nDirect evaluation: \n  - goal -> compute values for each state under pi, idea: average together observed sample values -> act according to pi and write down sum of \n  - discounted rewards (rewards from that state to the end state) and average all the samples for each state.\n    - PROS-> easy to understand, doesn't require T, R, and eventually will compute correct avg values\n    - CONS-> wastes info about how states connected, requires lots of estimates for good vals, each state must be learned separtely\nSample based policy eval not feasible as we can't gurantee we can go to each state n times.\n\nTemporal Difference Learning: compare current estimates against new value (model free)\n  - update V(s) each time we experience a transition (policy is still fixed and doing eval)\n  - outcomes s' that are more likely will contribute updates more often\n  - like before V(s) : sample = R(s, pi, s') + decay*Vpi(s')\n  - update V(s) right away: Vpi(s) <- (1 - alpha)Vpi(s) + (alpha)*sample, alpha is learning rate that controls how much new samples contribute (interprolating)\n  Exponential moving average: observations in past worth less than newer ones as (1-alpha) is essnetially exponentiated, which is beter as these are more random\n  - can keep decreasing leearning rrate to help converge alpha\n  - hard to turn values into policy -> idea learn Q-values, not values so that it can still be model free\n\nAcive Reinforcement Learning: way of taking MDP and learning paramers of model but you choose actions to try.\n\nQ-value iteration: (q vals are more useful than values of a state as rather than picking action with higher state, can determine which (state, action) prepare has best value)\n    - Can still start with Q0(s,a) = 0 and build up recursively. Given Qk can calculate k+1 q-val for all q-states\n  We can now do Q-Learning, which is sample-based Q-value iteration:\n    - recieve a samplle (s,a,s',r)\n    - consider your old estimate: Q(s,a) and new sample estimate: sample = R + decay*max(a')Q(s',a')\n    - incorporate new estimate into a running average: Q(s, a) <- (1 - alpha)Q(s, a) + (alpha)*sample\n    - eventhough taking subopimal actions can converge to optimal policy : called off-policy learning\n      - requires enough exploring, make learning rate small enough and decrease over time (not to quickly)\n\nExploration vs Exploitation: find right balance\n  - Q-Learning requires notion of exploring before optimal policy can be reached\n  - several schemes for forcing exploration: \n      simplest way: episilon greedy alg -> every time step, randomly generate value, if smaller than episilon then act randomly, otherwise act on current policy\n                    - this can be bad because we may know that these random paths are bad, but keep taking them\n                        -solns: lower episilon over time, remove bad policies, encode specific exploration functions\n    exploration functions: when and what should we explore?\n      -explore states where we haven't established how good or bad htey are, uncertain areas (optimistic approach)\n      -f(u, n)= (u is currenet estimate of utility, n is # of times we've visited state) u + k(constant bonus) / n\n        Modified q-update function: max(a')f(Q(s',a'), N(s',a')) instead of max(a')Q(s',a'), this gives bonus to good and unknown states\n\nRegret: quantify goodness of exploration strategies\n  -how many mistakes we made over time (would be much higher for episilon approach)\n  -difference betweeen your (expected) rewards (youthful suboptimality) and optimal (expected) rewards\n\nApproximate Q-Learning:\n  - basic q-learn keeps a table of q-values but for some states like chess there are too many states\n  - instead generalize them and learn faster\n  - learn from small number of states from experience and then generalize to new and similar states (important in ML)\n  - can do a weighted linear sum of features: Eval(s) = w1*f1(s) + w2*f2(s)...\n      -example: f1(s) = num white queens - black queens and w1 would be high since this is an important feature\n      - this is a liner value function -> can do V or Q also as Q(s,a) = w1*f1(s, a) + w2*f2(s, a)...\n      -advantage: -expereince can be summed up with a few features, learning alg just has to tweak weights\n                  -states may share features but actually be very diff in value, depends on how well this is implemented\n  -Update q value weights rather than entire Q(s,a) like was done for Exact Q-learning\n    - wi <- wi + alpha[difference]fi(s,a) (fi(s,a) so that it can adjust weights of active features)\n    -difference = diff between old Q(s,a) and new calculated one \n\n \n\n## Module 9 Definitions\n* **Sampling** - because of chance and stochastic environment, you have to try things repeatedly\n* **Difficulty** - learning can be much harder than computation for solving MDP\n* **Exploitation** - use knowledge it has so far to choose actions with best known rewards\n* **Exploration** - trying new unknown actions and paths to find information (better reward or potentially face worse)\n* **Monte carlo/one armed bandit** - gambling terms, in multi-arm bandits in ML, each has a probability distribution -> what policy maximizes utility\n* **Regret** - measure total rewards that we got from exploration stratetgy and compare againt total expected reewards had the ageent followed optimal policy whole time (sometimes you make mistakes still)\n* **Passive reinforcement learning** - someone else picks policy and we try it\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \nProbabiility Review: good for reasoning about world especially with uncertainty\n- let's us quantify how likely or unlikely something is in the next state rather than ruling out possibilities with logical assertions (ex: pit in star wars world)\n- fully specified probability model associates with a probability P(w) each possible world w (random variable)\n  - between 0 and 1 \n  - total set of all possible worlds is 1\n- we don't care about complete state of world just some: RANDOM VARIABLES (denoted with capital letter)\n\nJoin Distribution: size of distribution if n variables with domain sizes d is d^n so impractical to write it out, normalized so adds to 1\n\nProbabilistic Inference: compute a desired prob from other known probs (ex: conditional frm joint)\n  - can update beliefs from new observations (these beliefs can increase or decrease)\n  - Inference by enumeration: split RV into 3 sets of things\n    - EVidencee variables (things we've observed)\n    - Query var (things we want to reason about)\n    - Hidden var (occur in big JD but aren;t observations and things we're actively reasoning about)\n    - we care about P(Q | e1...ek) -> too arrive here\n      1. select entries consistent with the evidence we observed\n      2. marginalization, kick out hidden var by summing over all of the value assignments for Hidden vars\n      3. normalize: multiply by 1/Z where Z is computed by summing over all Q\n\nProbabilistic Language Models:\n  - assign a probability to a sentence (ex: autocomplete for texting, machine translation, spelling correction, speech recognition)\n  - with a few observations, esttimate the probability distribution over all assignments of words in english language to that next \"random variable\" ie next word\n\n  Goals:  compute probability of a sentence or sequence of words\n  related tasks: probability of an upcoming word, given sequence of previous ones -> leads to languge model to compute this. \n    - P(W) = P(w_n|w1,w2...wn-1), calcualte ewith chain rule\n\nHow to estimate these probabilities:\n  1. maximum likelihood estimation, counting up things and dividing...just find what fraction of time, x came after y when we saw y from some text\n    - not great: inefficient, words may not be in set already (hard to have this much data)\n  2. Markov assumption: probabilitiy of what happens in next state only depends on current state (ignores history)\n    - much morre efficient approach... instead of P(won | the underdog team), do P(won | team), only depends on previous k words, not whole context of sentence\n      - k << n, easier to estimate from data -> improved maximum likelihood estimation\n\nn-gram models, start to get fairly accurate when n = 4 or 5\n\n \n\n## Module 10 Definitions\n* **Observed variable** - agenet knows certain things about state of world\n* **Unobserved variable** - agent need to reason about other aspects\n* **Model** - agent knows something about how the known variables relate to the unknown\n* **Sample space** - possible worlds in probability theory (exhaustive and mutually exclusive\n* **Random variable** - some aspect of ther world about which we may have uncertainty\n* **Joint distribtion** - specifies a real number assignment over a set of random var, ex: P(X1 = x1, X2 = x2 ...) or as P(x1, x2)\n* **Probabilistic models** - joint distribution overe a set of random variables\n* **Event** - set of E outcomes, sum of probabilities in join distribution where E's conditions are true (usually has ORs and ANDs)\n* **Marginal distributions** - subtable of JD which eliminate variables that don't care about (summing out and collapsing rows)\n* **Conditional probabilities** - probability of something happening conditioned (or given) that something else has happened. can go from JD table to this\n* **Product rule** - P(Y) * P(X|Y) = P(X,Y) let's you get back big JD table from subtables (marginal * conditional)\n* **Chain rule** - generalizes product rule so can do more than 2 var\n* **Bayes' rule** - P(X|Y) = P(Y|X) / P(Y) * P(X), build one conditional from reverse, super important\n* **** - \n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \nBaye's net is a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n  - directed acyclic graph\n  - A conditional distribution for each node\n    - A collection of distributions over X, one for each combination of parents’ values\n    - CPT: conditional probability table\n\nX and Y are indepedent if  P(x,y) = P(x)P(y), these random variables occurring don't influence each other's probability. pretty rare in real world and not that useful.\n\nconditional independence, independent if some variable Z occurs, otherwise they wouldn't be independent. important for reasoning about unobserved variables and the probability of them.\n\nP(xi | x1...xi-1) = P(xi|parents(Xi)) -> graphically encoded like this to get conditional independece assumptions\n  - often additional conditional independences that aren't as explicit but can still be enumerated from graph via an algo\n  - Baye's net allows us to model world with assumptions that we believe\n\nD-separation alg:\n  - alg for answering whether things are indepedent of each other\n  - Causal Chains: x causes y causes z.\n    - ex: low pressure causes rain which causes traffic, P(x,y,z) = P(x)P(y|x)P(z|y). Note no guranteed independece of x and z because of causal relation.\n    - Prove x independent of Z given y. P(z|x,y) = P(x,y,z) / P(x,y) = P(x)P(y|x)P(z|y) / P(x)P(y|x) = P(z|y). \n      - Because evidence along the chain \"blocks\" influence. Y's influence on Z makes X's irrelevent.\n  - Common Cause: x and z both caused by Y\n    - X: forums busy, Z: office hours fulls, Y: project due. No guranteed independece of x and z because of common cause once again (look at conditional prob tables).\n    - x independent of Z given y once again. Y can similarly block chain.\n  - Common Effect: two causes (X and Y) lead to Z\n    - are X and Y independent: Yes ex: X: raining, Y: ballgame, Z: traffic\n    - are X and Y independent gievn Z: NO since seeing Z (traffic) puts the rain and ballgame in competition\n      - backwards from other 2 cases, observing an effect activates influence between possible causes\n\nGeneral Q: in a given BN, are two variables independent?\nSolution: Analyze the graph and any complex examples can be broken into repetitions of of the three canoncial cases.\n\nHow to break down:\n - reachibility: find path between two variables (if it exists) and see if its blocked by some evidence...if so influence is blocked between them and conditinally independent\n    - one exception: third cases where there's a v structure\n\nActive/Inactive paths:\n  - Question: are X and Y conditionally indepdendent given evidence of variables {z}\n      - yes if X and Y \"d-separated\" by Z (consider all undirected paths from X to Y)\n      - NO active paths = independence\n  -Path is active if EACH triple is active in the path:\n    - causal chain A -> B -> C where B is unobserved (doesn't block influence)\n    - common cause A <- B -> C where B is unobserved\n    - common effect (v-structure): A -> B <- C where B or one of its descendenants is observed\n    - takes a single inactive segment to BLOCK a path\n\nD-separation:\n  - check for all undirected paths between Xi and Xj with query: Xi _|_ Xj | {Xk1,...Xkn} where {Xk1,...Xkn} are observed\n  - look at all triples and if one or more path is active, then independence not guranteed\n\nInference: calculate some useful quantity from a joint probability distribution\n  - what's probability of each variable assignment to query but also which is most likely explanantion\n\ninference by enumeration:\n  - Evidence vars (what we have), Query vars(what we want), hidden variables (what we have but don't care about)\n  - want: P(Q | e1...ek)\n  - Step 1: select entries consistent with evidence\n  - Step 2: sum out H to get join of Query and Evidence\n  - Step 3: normalize by 1/z\n\nBayes Net with Infer by Enumer Ex with alarm, burrglary, earthquake, mary calling, john calling (diagram on notes)\n  - P(B | +j, +m) \n  - start with summing over hidden variables (earthquake and alarm) which means probabilities with/without earthquake and alarm combos\n    - this operation is not very efficient especially when you # of hidden variables increase\n    - use variable elimination to speed up operation\n\n \n\n## Module 11 Definitions\n* **Baye's net** - probabilistic model -- graphical model where the nodes represent variables and the arcs represent the relationship between them\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Naive Bayes learns a set of probabilities while perceptrons have a weight associated with each feature and update weights accordingly (if current weight casuses misclassification) \n\nmachine learning will give us a mechanism for acquiring the data/experiences that we need to use a model from data\n  - learnring parameters(eg probabilities)\n  - learning structure and predicting them(eg BN graphs)\n  - learring hidden concepts(eg clustering, don't have data to learn)\n\nNaive Bayes -> makes independence assumptions in order to achieve classification\n  - input for system may be some kind of feature vector\n  - output : classification: choose frm a small/finite set of a classes, regresssion: assign and determine a real number\n  - ML Steps:\n      - have a set/collection of training data labeled with their class\n      - with that collection, learn a function that will take in new data and predict a class for it\n      - for each data point, transform it into a vector of features. Ex: for email, features could be the word \"viagra\" appeearing or \"free\" appearing\n\nModel-Based Classification:\n  - build a model (eg Bayes' net) where both the llabels and features are random variables\n  - instantiate any observed features\n  - query model in same way..what class is this?\nNaive Bayes:\n  - assume all features are independent effects of the label (of each other)\n    - have probaulities set up as P(Feature | Class)\n    - digit ocr example:\n      - have each coordinate <i,j> be feature Fij which is either off or on\n      - Naive Bayes model query would say: P(Class_Y, F00..F01...F1515) ie probability that it's class X given this feature list = P(Y)*product of each of P(Fi|Y) where P(Y) is prior probability of class Y\n      - have Y labels, then n * F * Y parameters whereas a full joint distrib would have Y * F^n...n is number of vals f can have.\n      - this model is simiplisitc and doesn't perfectly capture reality since total number of parameters is linear in number of features\n  - inference method in NB\n    - step 1: get joint probability of a label and evidence for each label, P(Y,f1...fn)\n    - step 2: sum to get probability of evidence -> P(f1..fn)\n    - step 3: normalize by dividing step 1 by step 2 to get P(Y|f1...fn)\n  - estimates of local conditional probability tables\n    - P(Y) - prior prob of labels\n    - P(Fi | Y) - for each feature (evidence variable)\n    - these probabilities are collectively the \"parameters\" of the model and denoted by theta which we'll get from training\n\n3 types of data:\n  - training data (estimate model params like probabilities)\n  - test data (use it this to test and compute accuracy)\n  - held out set (used for fine tuning hyperparamters)\n\noverfitting: when you too closely model training data that don't generalize to other test data\n  - should never (or sparingly) assign a probability of 0 to a feature since we compute by calculating a product, especially if it's just a unseen event\n  - to generalize better: smooth or regularize the estimates\n\nParamter Estimation:\n  - elicitation (ask human/expert)\n  - empirically: use training data to learn, and look at empirical rate of any value.\n    - choose the estimate that meximizes likelihood of the datat (via liklihood function)\n    - add all occurences and divide by total samples: count(x)/# samples\n\nLaplace Smoothing:\n  - pretend you saw every outcome once more than you actually did (prevent 0's)\n  - instead of maximizes likelihood, (count(x) + 1) / (# things in samples + |X|) where |X| is # unique things in sample\n  - instead of doiing by 1, can do by some constant k so : P_lap,k(x) = (count(x) + k) / (# things in samples + k|X|)\n  - add to and smooth condittiional probabilities: P_lap,k(x|y) = (count(x,y) + k) / (count(y) + k|X|)\n  - not greate for conditionals when |X| or |Y| is large\n\nLinear Interpolation: another technique to remove 0's and help generalize\n  - hyperparam is alpha: P_lin(x|y) = alpha*P(x|y) + (1-alpha)*P(x), so how much you want to weigh prior probability of class label over conditional (maximum likelihood calc)\n\nTuning models:\n  - in general learn probabiities with training set and tune hyperparams with held out/dev set\n  - potentially changing features\n\nBaseline:\n  - simplee \"straw man\" procedures to determine how hard the task is and what a \"good\" accuracy is\n  - for real researrch use prervious work as a (strong) baseline\n  - weak baseline could be skewed, eex: most freq label classifier is only one in test data\n\nPerceptron: a decision making device by weighing inputs\n  - have a bunch of inputs, each of which is associated with a weight\n  - take the weighted sum and the activation function will compare it to some threshold to determine the output, ex: 0 (spam) if <= thresh else 1 (ham)\n  - w is weight vector and x is input/feature vector\n  - can call bias, b, - threshold. so say 0 if w * x + b <= 0 and 1 if w * x + b > 0\n  - separating hyperplane is orthogonal to weight vector so (if < 90 degrees than take on positive classification, > 90 degrees takes on negative)\n    - bias term allows you to move decision boundary towards or away a classification\n\nLearning (binary classification so spam or not): \n  - Uses error driven learning to adjust weights\n  - initially start with weights = 0\n  - for each training instance:\n    - classifiy with current weights. if correct, no change, if wrong adjust weight vector by adding or subtracting and repeat this.\n    - if the guess was negativee classification, subtract as this adjusts hyperplane boundary by shifting weight vector\n\nMulticlass Decision Rule\n  - weight vector for every class\n  - score (activation) of every class so that y = argmax_y w_y * f(x) and highest dot product wins\n Learning (Multiclass classification): \n  - initially start with weights = 0\n  - for each training instance:\n    - classifiy with current weights. if correct, no change, if wrong adjust the two relevent weight vectors. \n    - subtract from the one that was incorrectly chosen as label (w_y = w_y - f(x)) and increase weights it should have predicted\n\nProperties of Perceptrons:\n  - for binary cases\n  - if data is linearly separable (So can separate data into two classes) than you CAN converge on set of weights that classify\n  - if not linearly separable, you have to come up with mistake bound, maximum number of mistakes related to the margin or degree of seeparabiliity\n    - mistakes < k / margin ^ 2\n\nProblems with perceptron:\n  - if non-separable than weights might thrash (go back and forth between weights)\n    - can address this by averaging weight vectors over time\n  - which hyperplane to pick as best?\n  - overtraining: type of overfitting\n    - training accuracy goes up but it's too fit to this data, too much training\n    - can use held-out development set so that if performance starts to decrease for this, then stop training\n\nFixing perceptron:\nMIRA: margin infused relaxed algo\n  - instead of updating weights by big amount, just a little to fix current mistake\n  - instead of w_y = w'_y - f(x) scaled it down with constant tau so w_y = w'_y - tau*f(x) (one that was wrongly predicted) and w_y* = w'_y* + tau*f(x) (one that should've been predicted)\n  - tau = (*w'y - w'y*) * f + 1)/ 2f * f .. + 1 helps to generalize\n  - sometimes do tau* = min (tau, C) where C is a capped max that you want to adjust by\n  - this can help converge faster, and is better when you may not have enough features, and better on noisy data and non-separable data\n\nLinear Separators:\n  - which separator to use?\n  - SVM or support vector machine find separator with max margin\n  - essentiallly MIRA but you optimize over all examples at once\nNon-Linear Separators:\n  - add another dimension, ex: value squared, then you can now linearly separate\n  - essentially just transforms your inputs\n  \nperceptrons are generally more accurate then Navie Bayes, makes less assumptions about data, and require multiple pass throughs the data (NB just does once)\n\n  \n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier Components:\n  - feature representation of the input, has become less important over time\n  - classification function that computes the estimated class y_hat (highest probability class) via p(y|x)\n  - an objective/loss function for learning that shows performance, usually involving minimizing error on training examples.\n  - an algo for optimizing the obj function (stochastic gradient descent) and updating the params\n\nLogistic Regression: another classifier like Perceptron (sentiment analysis ex):\n  - solves estimating P(y = 1 | x) by learning from a training set, a vector of weights and a bias term so z = w * x + b\n  - LR changes range of outputs, rather than set classes, it is a range of number values like -inf to inf\n    - the z value is squished via a sigmoid function : y = 1/ (1 + e^-z) (vals range from 0 to 1)\n    - to have proper probability distribution, all of the possible label values have to sum up to 1\n    - For binary: P(y = 1) = sigmoid(W * x + b) so P(y = 0) = 1 - sigmoid... with threshold of .5\n  - need to consider extracting features (ex: count of positive llexicon words, does ! appear, how many \"no\" occured)\n  - associate weights with these (can be positive or negative)\n\nLearning with LR using loss function:\n  - obj or loss function tells us distance between system and gold output (even if picked correct class, want to see what percent it predicted)\n  - (L(y_hat, y)) = how much y_hat differs from true y)\n  - example is mean squarerd error Lmse = 1/2(y_hat - y)^2 (not great though)\n  - cross entropy loss function (negative log liklihood loss) -> maximize probability of true labels by minimizing negative probability (in log space)\n  - use sotachstic gradient descent to minimize the loss function\n\nCross Entropy loss function:\n  - maximize probability of true label y: p(y|x) = y_hat^y(1-y_hat)^(1-y)\n    - if we say correct label is y = 1, then plugging in y = 1 gives y_hat when you simplify (*want y_hat as close to 1 as possible)\n    - if we say correct labe is y = 0, then we get 1 - y_hat (*want y_hat to as close to 0 as possible)\n    - put log space by log both sides of equation to maximize log property and to finally minimize negative log, flip sign (eq on sheet)\n\nGradient Descent: find good settings for our weights and bias (both encompassed in theta) by minimizing loss function\n  - alg to find theta (optimal weights and bias) that results in minimium loss\n  - finds a minimum of a function by by finding which direction in the space of theta that the function's slope is rising the most steeply and moving in opposite direc by a step\n    - size of step taken is learning rate: eta (consider decreasing over time)\n    - slope is negative, moving in right direction and if it's positive, we passed the minimum\n    - *we want to apply this to a n-dimensional space so can do this for and update multiple weights\n  - for linear regression, the loss function is convenitently convex (there is only one minimum) so gradient descent always guranteed to find minimum\n\n-With loss functions/deriv of loss functions can figure out Cost(w,b) by summing over all features and dividing by number to get average.\n\nMini batch training: \n  - stochastic gradient desc chooses a single random example at a time and updates its weights on that example. updates can fluctuate\n  - alt: batch training, computees gradient over entire dataset which gives better estimate of whiich direction to move the weights BUT takes longer\n  - BETTER: mini batch -> train on a small batch (~512 or 1024), and loss is then accumalted\n\nRegularization:\n  - overfitting: poor generlaization...for LR if a feature only occurs in one class then it will get a high weight\n    - sometimes this feature is just a noisy factor and this can have too much weight\n  - regularization: way to penallize large weights, a regularizatin term is added to the loss function\n    - lasso regression uses L1 regul (linear func of weight vals)\n    - ridge reg L2 (quadratic function, easier to optimize)\n\nMultinomial logisitic regression:\n  - instead of binary class so we wantt to know prob of y for eaech class c : P(y=c | x)\n  - use a generalization of the sigmoid function (softmax func) so that having multiple classes still sums to 1\n\nNeural network:\n  - perceptron network\n  - multiplee inputs that all go to different hidden layer perceptrons that will then serve as inputs to another perceptron layer until reaching an output layer\n  - LR better than perceptron because sigmoid adds a gradual change/smoothness while small weight changes in perceptron can quickly flip 0 to 1\n    - smoothness important for derivatives\n  - NN uses activation function (ensure its differentiable)\n    - outputs an activation value, a = f(z), and applies a non-linaer function to z = w*x + b.\n    - output of NN is called y so if activation is the final output of a network then y = a\n    - f is generally a sigmoid func, tanh func, or rectified linear unit ReLU\n\nFeed-forward NN:\n  - simples kind of NN\n  - multilayer network, all units are usually fully-connected, and no cycles\n  - outputs frm each layer are passed to units in the next layer\n\nTraining NN:\n  - loss function (Cross entropy loss), optim alg (gradient descent), AND * a way of computing the gradient of the loss function (error propagation)\n  - gradient descent like before would only work for one layer. we need to look back through all the earlier layers in the network to compute gradient\n  - SOLTN: error back propagation (similar to backwatd differentiation):\n    - define computation graph and then figure out how much each element contributes -> loss function can than be a graph\n    - computation is broken down into separate operations where each op is a node in graph\n    - backward diff uses chain rules frm calculus to compute derivatives needed for the weight update\n    - with the graph on sheet, can pass deriv. backwards\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nClassifier Components:\n  - feature representation of the input, has become less important over time\n  - classification function that computes the estimated class y_hat (highest probability class) via p(y|x)\n  - an objective/loss function for learning that shows performance, usually involving minimizing error on training examples.\n  - an algo for optimizing the obj function (stochastic gradient descent) and updating the params\n\nLogistic Regression: another classifier like Perceptron (sentiment analysis ex):\n  - solves estimating P(y = 1 | x) by learning from a training set, a vector of weights and a bias term so z = w * x + b\n  - LR changes range of outputs, rather than set classes, it is a range of number values like -inf to inf\n    - the z value is squished via a sigmoid function : y = 1/ (1 + e^-z) (vals range from 0 to 1)\n    - to have proper probability distribution, all of the possible label values have to sum up to 1\n    - For binary: P(y = 1) = sigmoid(W * x + b) so P(y = 0) = 1 - sigmoid... with threshold of .5\n  - need to consider extracting features (ex: count of positive llexicon words, does ! appear, how many \"no\" occured)\n  - associate weights with these (can be positive or negative)\n\nLearning with LR using loss function:\n  - obj or loss function tells us distance between system and gold output (even if picked correct class, want to see what percent it predicted)\n  - (L(y_hat, y)) = how much y_hat differs from true y)\n  - example is mean squarerd error Lmse = 1/2(y_hat - y)^2 (not great though)\n  - cross entropy loss function (negative log liklihood loss) -> maximize probability of true labels by minimizing negative probability (in log space)\n  - use sotachstic gradient descent to minimize the loss function\n\nCross Entropy loss function:\n  - maximize probability of true label y: p(y|x) = y_hat^y(1-y_hat)^(1-y)\n    - if we say correct label is y = 1, then plugging in y = 1 gives y_hat when you simplify (*want y_hat as close to 1 as possible)\n    - if we say correct labe is y = 0, then we get 1 - y_hat (*want y_hat to as close to 0 as possible)\n    - put log space by log both sides of equation to maximize log property and to finally minimize negative log, flip sign (eq on sheet)\n\nGradient Descent: find good settings for our weights and bias (both encompassed in theta) by minimizing loss function\n  - alg to find theta (optimal weights and bias) that results in minimium loss\n  - finds a minimum of a function by by finding which direction in the space of theta that the function's slope is rising the most steeply and moving in opposite direc by a step\n    - size of step taken is learning rate: eta (consider decreasing over time)\n    - slope is negative, moving in right direction and if it's positive, we passed the minimum\n    - *we want to apply this to a n-dimensional space so can do this for and update multiple weights\n  - for linear regression, the loss function is convenitently convex (there is only one minimum) so gradient descent always guranteed to find minimum\n\n-With loss functions/deriv of loss functions can figure out Cost(w,b) by summing over all features and dividing by number to get average.\n\nMini batch training: \n  - stochastic gradient desc chooses a single random example at a time and updates its weights on that example. updates can fluctuate\n  - alt: batch training, computees gradient over entire dataset which gives better estimate of whiich direction to move the weights BUT takes longer\n  - BETTER: mini batch -> train on a small batch (~512 or 1024), and loss is then accumalted\n\nRegularization:\n  - overfitting: poor generlaization...for LR if a feature only occurs in one class then it will get a high weight\n    - sometimes this feature is just a noisy factor and this can have too much weight\n  - regularization: way to penallize large weights, a regularizatin term is added to the loss function\n    - lasso regression uses L1 regul (linear func of weight vals)\n    - ridge reg L2 (quadratic function, easier to optimize)\n\nMultinomial logisitic regression:\n  - instead of binary class so we wantt to know prob of y for eaech class c : P(y=c | x)\n  - use a generalization of the sigmoid function (softmax func) so that having multiple classes still sums to 1\n\nNeural network:\n  - perceptron network\n  - multiplee inputs that all go to different hidden layer perceptrons that will then serve as inputs to another perceptron layer until reaching an output layer\n  - LR better than perceptron because sigmoid adds a gradual change/smoothness while small weight changes in perceptron can quickly flip 0 to 1\n    - smoothness important for derivatives\n  - NN uses activation function (ensure its differentiable)\n    - outputs an activation value, a = f(z), and applies a non-linaer function to z = w*x + b.\n    - output of NN is called y so if activation is the final output of a network then y = a\n    - f is generally a sigmoid func, tanh func, or rectified linear unit ReLU\n\nFeed-forward NN:\n  - simples kind of NN\n  - multilayer network, all units are usually fully-connected, and no cycles\n  - outputs frm each layer are passed to units in the next layer\n\nTraining NN:\n  - loss function (Cross entropy loss), optim alg (gradient descent), AND * a way of computing the gradient of the loss function (error propagation)\n  - gradient descent like before would only work for one layer. we need to look back through all the earlier layers in the network to compute gradient\n  - SOLTN: error back propagation (similar to backwatd differentiation):\n    - define computation graph and then figure out how much each element contributes -> loss function can than be a graph\n    - computation is broken down into separate operations where each op is a node in graph\n    - backward diff uses chain rules frm calculus to compute derivatives needed for the weight update\n    - with the graph on sheet, can pass deriv. backwards\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}