{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5523f74e-32bb-4ccb-b767-3fdbb4db90e6"
      },
      "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": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0aae8d5f-2dda-4d81-ee40-51d172431324"
      },
      "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": 2,
      "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": 3,
      "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 = \"\"\" Decision-theoretic agents assign a continuous range of values to states which \\\n",
        "allows it to more easily choose a better state when there is no clear best state. While the MEU \\\n",
        "principle formalizes the notion of what an intelligent agent should do, it does not operationalize \\\n",
        "it. It only provides a basic mathematical framework that can be used to define the AI problem. If \\\n",
        "an agent acts to maximize a utility function and that utility function correctly reflects the performance \\\n",
        "measure for a given environmen then the aagent will achieve the highest possible score. Performance measures \\\n",
        "give a score over a history of actions/state while the utility function only applies to the next state to help \\\n",
        "guide decisions step by step. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Events in lotteries can be atomic states or lotteries themselves. Six axioms of utility theory: \\\n",
        "Orderability (a rational agent must prefer a lottery over another or be indifferent to them), Transitivity, Continuity \\\n",
        "(if an agent prefers B between A and C, then there exists some probability p where the agent is indifferent between B and \\\n",
        "the lottery where A occurs with probability p and C occurs with probability 1 - p), Substitutability, Monotonicity (if an \\\n",
        "agent prefers A over B then it should prefer lotteries that have a greater chance of A occurring), and Decomposability \\\n",
        "(compound lotteries can be simplified using laws of probability). Two properties of utility functions: if an agent follows \\\n",
        "the axioms then there exists a utility function $U$ where $U(A) > U(B) \\Leftrightarrow A \\succ B$ and $U(A) = U(B) \\Leftrightarrow A \\sim B$, \\\n",
        "the expected utility of a lottery is U(\\[p_1, S_1; \\dots ; p_n, S_n]) = \\sum_i p_i U(S_i).\"\"\"\n",
        "chapter16_3 =  \"\"\" The best action $a*$ is determined by maximizing expected utility. $a* = argmax_a EU(a)$. \\\n",
        "For MDPs we have a stochastic transition model. Markovian means we ignore all states we visited before when calculating \\\n",
        "our transitions, so we only care about the current state we are in. Environment history is all the states visited until a terminal state is hit. Can \\\n",
        "solve MDPs using expectimax search. Even if we have an optimal policy, each time we follow the policy the nondeterminism makes it so that our total reward \\\n",
        "at the end is not always the same. Therefore we need to compute the expected utility of all the possible paths generated by a policy. Discounting penalizes \\\n",
        "rewards in the future, making us want to get rewards earlier (rewards decay exponentially). We discount because sooner rewards probably do have higher \\\n",
        "utility than later rewards and it will help our algorithms converge.\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" A sequentail decision problem in a fully observable, stochastic environment with a Markovian transition \\\n",
        "model and additive rewards is called a Markovian Decision Process (MDP). An MDP has: a set of states, an initial state $s_0$, \\\n",
        "a set of actions ACTIONS(s) in each state, a transition model $P(s' | s, a)$ and a reward function $R(s, a, s')$. Solving an MDP \\\n",
        "usually involves dynamic programming. Since the environment is stochastic there is no one sequence we can use, so we use a policy that \\\n",
        "tells us what we should do in any given state. With a finite horizon an optimal action in a given state may depend on teh remaining \\\n",
        "time. Assuming the agent choose the optimal action, the utility of a state is the expected reward of the following transition summed \\\n",
        "with the discounted utility of the next state. The Bellman Equation: $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s' | s, a) [R(s, a, s') + \\gamma U(s')]$. \\\n",
        "Q-function (action-utility function) is the expected utility of doing a given action in a given state: $U(s) = max_a Q(s, a)$ and $\\pi^*(s) = argmax_a Q(s, a)$. \\\n",
        "$Q(s, a) = \\sum_s' P(s' | s, a) [R(s, a, s') + \\gamma max_{a'} Q(s', a')]$. \"\"\"\n",
        "chapter17_2 =  \"\"\" Value Iteration: start with arbitrary values for utilities, perform the Bellman update on all states simulataneously until convergence: \\\n",
        "$U_{i + 1}(s) \\gets max_{a \\in A(s)} \\sum_{s'} P(s' | s, a) [R(s, a, s') + \\gamma U_i(s')]$. Policy Iteration: lets us get an optimal policy with an inaccurate \\\n",
        "utility function. Alternates between two steps: Policy evaluation: for a given policy $\\pi_i$, calculate the utility of each state if $pi_i$ was done, $U_i = U^{\\pi_i}$ \\\n",
        "and Policy improvement: get a new MEU policy $pi_{i + 1} by looking one-step ahead based on U_i. The algorithm stops when the policy improvement \\\n",
        "step no longer changes utility values. Asynchronous policy iteration only updates the utilites of a subset of states. Linear programming is a general approach for\n",
        "constrained optimization problems and can solve MDPs in polynomial time with respect to the number of states and actions. Value iteration and policy are offline \\\n",
        "algorithms which means they generate an optimal solution for a problem that an agent can execute. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Stationary preferences is $[a_1, a_2, \\dots] \\succ [b_1, b_2, \\dots] \\Leftrightarrow \\\n",
        "[r, a_1, a_2, \\dots] \\succ [r, b_1, b_2, \\dots]$. This gives us additive utilities $U([r_0, r_1, r_2, \\dots]) = r_0 + r_1 + r_2$ and discounted utilities \\\n",
        "$U([r_0, r_1, r_2, \\dots]) = r_0 + \\gamma r_1 + \\gamma^2 r_2$. MDP search trees, triangles are states, circles are q-states (state, action), and these \\\n",
        "trees are basically expectimax trees except our transition model has probabilities and rewards at given at each state instead of just the terminal states. \\\n",
        "$V*(s)$ is the expected utility starting in s and acting optimally. $Q*(s, a)$ is the expected utility starting out having taken action a from state s and \\\n",
        "then acting optimally. Fundamental operation is computing the expectimax value of a state by getting the expected utility under optimal action, \\\n",
        "average the sume of (discounted) rewards. $V*(s) = max_a Q*(s, a)$, $Q*(s, a) = \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V*(s')]$, and \\\n",
        "$V*(s) = max_a \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V*(s')]$. Value Iteration $O(S^2A)$, guaranteed to converge to unique optimal values. \\\n",
        "For policy evaluation, we fix the policy and determine the utilities, following the equation but we don't need to take the max of all actions. \\\n",
        "WE can just turn recursive Bellman equations into updates and perform valu iteration which takes O(S^2) time per iteration or since there rae no \\\n",
        "maxes in the equations we can directly solve the Bellman equations as a linear system. Policy extraction is when we are given the optimal values and \\\n",
        "we try to determine the optimal policy, which is done by a mini-expectimax (one-step) $\\pi * (s) = argmax_a \\sum_{s'} T(s, a, s') [R(s, a, s') + \\\n",
        "\\gamma V* (s')]$. Given the optimal q-values, it is trivial to get the best policy as we just do $\\pi *(s) = argmax_a Q*(s, a)$. Actions are easier \\\n",
        "to select from q-values than values. Policy iteration combines policy evaluation and policy improvement. Value iteration has problems in that it is slow \\\n",
        "and the max at each state rarely changes and the policy often converges long before the values. Policy iteration is optimal and converges faster \\\n",
        "than value iteration usually. In value iteration every iteration updates both the values and (implicitly) the policy and we don't track the policy, but \\\n",
        "taking the max over actions implicitly recomputes it. In policy iteration we do several passes that update utilities with a fixed policy (quick since we \\\n",
        "fix the policy), after the policy is evaluated a new policy is chosen (slow like a value iteration pass) and then the new policy will be better or we're done.\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"U(s): assigns a number to a state to describe its desirability\",\n",
        "\"expected utility\" : r\"$EU(a) = \\sum_{s'} P(\\textnormal{RESULT}(a)=s')U(s')$\",\n",
        "\"maximum expected utility (MEU)\": r\"$action = \\textnormal{argmax}_a EU(a)$, a rational agent should do things to maximize its expected utility\",\n",
        "\"lottery\" : \"$L = [p_1, S_1; p_2, S_2; \\dots p_n, S_n]$, Lottery $L$ with outcomes $S_i$ that occur with probability $p_i$\",\n",
        "\"orderability\" : \"one of $(A \\succ B)$, $(B \\succ A)$, or $(A \\sim B)$ holds\",\n",
        "\"transitivity\" : \"$(A \\succ B) \\wedge (B \\succ C) \\implies (A \\succ C)$\",\n",
        "\"continuity\" : \"$A \\succ B \\succ C \\implies \\exists p [p, A; 1 - p, C] \\sim B$\",\n",
        "\"substitutability\" : \"$A \\sim B \\implies [p, A; 1 - p, C] \\sim [p, B; 1 - p, C]$\",\n",
        "\"monotonicity\" : \"$A \\succ B \\implies (p > q \\Leftrightarrow [p, A; 1 - p, B] \\succ [q, A; 1 - q, B])$\",\n",
        "\"decomposability\" : \"$p, A; 1 - p, [q, B; 1 - q, C]] \\sim [p, A; (1 - p)q, B; (1 - p)(1 - q), C]$\",\n",
        "\"markovian\" : \"the probability of getting to state s' is solely dependent on the current state s\",\n",
        "\"policy\" : \"a solution that specifies what an agent should do in any given state\",\n",
        "\"optimal policy\" : \"$\\pi^*$, policy with highest expected utility\",\n",
        "\"finite horizon\" : \"fixed time N that decides when the game is over\",\n",
        "\"nonstationary\" : \"policy that depends on time\",\n",
        "\"discount factor\" : \"[0, 1], the preference of current rewards over future rewards\",\n",
        "\"proper policy\" : \"policy that is guaranteed to reach a terminal state\",\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "74651aaa-740f-4479-de87-97a85395c728"
      },
      "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": 5,
      "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 Decision-theoretic agents assign a continuous range of values to states which allows it to more easily choose a better state when there is no clear best state. While the MEU principle formalizes the notion of what an intelligent agent should do, it does not operationalize it. It only provides a basic mathematical framework that can be used to define the AI problem. If an agent acts to maximize a utility function and that utility function correctly reflects the performance measure for a given environmen then the aagent will achieve the highest possible score. Performance measures give a score over a history of actions/state while the utility function only applies to the next state to help guide decisions step by step.  $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 Events in lotteries can be atomic states or lotteries themselves. Six axioms of utility theory: Orderability (a rational agent must prefer a lottery over another or be indifferent to them), Transitivity, Continuity (if an agent prefers B between A and C, then there exists some probability p where the agent is indifferent between B and the lottery where A occurs with probability p and C occurs with probability 1 - p), Substitutability, Monotonicity (if an agent prefers A over B then it should prefer lotteries that have a greater chance of A occurring), and Decomposability (compound lotteries can be simplified using laws of probability). Two properties of utility functions: if an agent follows the axioms then there exists a utility function $U$ where $U(A) > U(B) \\Leftrightarrow A \\succ B$ and $U(A) = U(B) \\Leftrightarrow A \\sim B$, the expected utility of a lottery is U(\\[p_1, S_1; \\dots ; p_n, S_n]) = \\sum_i p_i U(S_i).\n\n## AIMA Chapter 16.3 Utility Functions\n The best action $a*$ is determined by maximizing expected utility. $a* = argmax_a EU(a)$. For MDPs we have a stochastic transition model. Markovian means we ignore all states we visited before when calculating our transitions, so we only care about the current state we are in. Environment history is all the states visited until a terminal state is hit. Can solve MDPs using expectimax search. Even if we have an optimal policy, each time we follow the policy the nondeterminism makes it so that our total reward at the end is not always the same. Therefore we need to compute the expected utility of all the possible paths generated by a policy. Discounting penalizes rewards in the future, making us want to get rewards earlier (rewards decay exponentially). We discount because sooner rewards probably do have higher utility than later rewards and it will help our algorithms converge.\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n A sequentail decision problem in a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markovian Decision Process (MDP). An MDP has: a set of states, an initial state $s_0$, a set of actions ACTIONS(s) in each state, a transition model $P(s' | s, a)$ and a reward function $R(s, a, s')$. Solving an MDP usually involves dynamic programming. Since the environment is stochastic there is no one sequence we can use, so we use a policy that tells us what we should do in any given state. With a finite horizon an optimal action in a given state may depend on teh remaining time. Assuming the agent choose the optimal action, the utility of a state is the expected reward of the following transition summed with the discounted utility of the next state. The Bellman Equation: $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s' | s, a) [R(s, a, s') + \\gamma U(s')]$. Q-function (action-utility function) is the expected utility of doing a given action in a given state: $U(s) = max_a Q(s, a)$ and $\\pi^*(s) = argmax_a Q(s, a)$. $Q(s, a) = \\sum_s' P(s' | s, a) [R(s, a, s') + \\gamma max_{a'} Q(s', a')]$. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value Iteration: start with arbitrary values for utilities, perform the Bellman update on all states simulataneously until convergence: $U_{i + 1}(s) \\gets max_{a \\in A(s)} \\sum_{s'} P(s' | s, a) [R(s, a, s') + \\gamma U_i(s')]$. Policy Iteration: lets us get an optimal policy with an inaccurate utility function. Alternates between two steps: Policy evaluation: for a given policy $\\pi_i$, calculate the utility of each state if $pi_i$ was done, $U_i = U^{\\pi_i}$ and Policy improvement: get a new MEU policy $pi_{i + 1} by looking one-step ahead based on U_i. The algorithm stops when the policy improvement step no longer changes utility values. Asynchronous policy iteration only updates the utilites of a subset of states. Linear programming is a general approach for\nconstrained optimization problems and can solve MDPs in polynomial time with respect to the number of states and actions. Value iteration and policy are offline algorithms which means they generate an optimal solution for a problem that an agent can execute. \n\n## Module 8 Lecture Notes\n Stationary preferences is $[a_1, a_2, \\dots] \\succ [b_1, b_2, \\dots] \\Leftrightarrow [r, a_1, a_2, \\dots] \\succ [r, b_1, b_2, \\dots]$. This gives us additive utilities $U([r_0, r_1, r_2, \\dots]) = r_0 + r_1 + r_2$ and discounted utilities $U([r_0, r_1, r_2, \\dots]) = r_0 + \\gamma r_1 + \\gamma^2 r_2$. MDP search trees, triangles are states, circles are q-states (state, action), and these trees are basically expectimax trees except our transition model has probabilities and rewards at given at each state instead of just the terminal states. $V*(s)$ is the expected utility starting in s and acting optimally. $Q*(s, a)$ is the expected utility starting out having taken action a from state s and then acting optimally. Fundamental operation is computing the expectimax value of a state by getting the expected utility under optimal action, average the sume of (discounted) rewards. $V*(s) = max_a Q*(s, a)$, $Q*(s, a) = \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V*(s')]$, and $V*(s) = max_a \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V*(s')]$. Value Iteration $O(S^2A)$, guaranteed to converge to unique optimal values. For policy evaluation, we fix the policy and determine the utilities, following the equation but we don't need to take the max of all actions. WE can just turn recursive Bellman equations into updates and perform valu iteration which takes O(S^2) time per iteration or since there rae no maxes in the equations we can directly solve the Bellman equations as a linear system. Policy extraction is when we are given the optimal values and we try to determine the optimal policy, which is done by a mini-expectimax (one-step) $\\pi * (s) = argmax_a \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V* (s')]$. Given the optimal q-values, it is trivial to get the best policy as we just do $\\pi *(s) = argmax_a Q*(s, a)$. Actions are easier to select from q-values than values. Policy iteration combines policy evaluation and policy improvement. Value iteration has problems in that it is slow and the max at each state rarely changes and the policy often converges long before the values. Policy iteration is optimal and converges faster than value iteration usually. In value iteration every iteration updates both the values and (implicitly) the policy and we don't track the policy, but taking the max over actions implicitly recomputes it. In policy iteration we do several passes that update utilities with a fixed policy (quick since we fix the policy), after the policy is evaluated a new policy is chosen (slow like a value iteration pass) and then the new policy will be better or we're done.\n\n## Module 8 Definitions\n* **Utility function** - U(s): assigns a number to a state to describe its desirability\n* **Expected utility** - $EU(a) = \\sum_{s'} P(\\textnormal{RESULT}(a)=s')U(s')$\n* **Maximum expected utility (meu)** - $action = \\textnormal{argmax}_a EU(a)$, a rational agent should do things to maximize its expected utility\n* **Lottery** - $L = [p_1, S_1; p_2, S_2; \\dots p_n, S_n]$, Lottery $L$ with outcomes $S_i$ that occur with probability $p_i$\n* **Orderability** - one of $(A \\succ B)$, $(B \\succ A)$, or $(A \\sim B)$ holds\n* **Transitivity** - $(A \\succ B) \\wedge (B \\succ C) \\implies (A \\succ C)$\n* **Continuity** - $A \\succ B \\succ C \\implies \\exists p [p, A; 1 - p, C] \\sim B$\n* **Substitutability** - $A \\sim B \\implies [p, A; 1 - p, C] \\sim [p, B; 1 - p, C]$\n* **Monotonicity** - $A \\succ B \\implies (p > q \\Leftrightarrow [p, A; 1 - p, B] \\succ [q, A; 1 - q, B])$\n* **Decomposability** - $p, A; 1 - p, [q, B; 1 - q, C]] \\sim [p, A; (1 - p)q, B; (1 - p)(1 - q), C]$\n* **Markovian** - the probability of getting to state s' is solely dependent on the current state s\n* **Policy** - a solution that specifies what an agent should do in any given state\n* **Optimal policy** - $\\pi^*$, policy with highest expected utility\n* **Finite horizon** - fixed time N that decides when the game is over\n* **Nonstationary** - policy that depends on time\n* **Discount factor** - [0, 1], the preference of current rewards over future rewards\n* **Proper policy** - policy that is guaranteed to reach a terminal state\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 =  \"\"\" Each arm $M_i$ of a bandit problem is a Markov reward process (MRP) which is an MDP with only one possible \\\n",
        "action $a_i$. The problem has states $S_i$, transition model $P_i(s' | s, a_i)$, and reward $R_i(s, a_i, s')$. Each arm defines \\\n",
        "a distribution over reward sequences $R_{i, 0}, R_{i_1}, \\dots$, with each $R_{i, t}$ being a random variable. The bandit problem is an \\\n",
        "MDP where the state space is the Cartesian product $S = S_1 X \\dots X S_n$, actions $a_1, \\dots, a_n,$ and the transition \\\n",
        "model updates the state of whichever arm $M_i$ is selected and the other arms don't change, and there is the discount $\\gamma$. For \\\n",
        "bandit problems, a key property is that the arms are independent of each other and the agent only works on one arm at a time. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Similarly to MDPs, reinforcement learning's goal is to maximize the expected sum of rewards. The main difference \\\n",
        "is that the agent may need to learn the transition model and/or reward function on its own. Model-based reinforcement learning is \\\n",
        "where the agent uses a transiiton model to interpret rewards and figure out how to act. The model might not be known, in which case \\\n",
        "the agent must learn it from the consequences of its actions. Model-based reinforcement learning often learn a utility function in \\\n",
        "terms of the sum of rewards from state $s$ onwards. Model-free reinforcement learning is where the agent does not know the transition \\\n",
        "model and does not learn it. Instead it learns a direct representation of what to do through either: Action-utility learning (most \\\n",
        "common form is Q-learning where agent learns Q-function $Q(s, a)$ that denotes the sum of rewards from state $s$ if action $a$ \\\n",
        "is done. Using this Q-function an agent can perform the action with the highest Q-value to determine what to do in each state) and \\\n",
        "Policy search (agent learns a policy $\\pi (s)$ that maps states to actions.) \"\"\"\n",
        "chapter22_2 =  \"\"\" In passive reinforcement learning the passive learning agent is trying to learn $U^pi(s)$ which is the expected \\\n",
        "total discounted reward if policy $\\pi$ is executed beginning in state $s$. Passive learning is similar to policy evaluation except the \\\n",
        "agent does not know the transition model nor the reward function. Direct utility estimation's idea is that the utility of a state \\\n",
        "is the expected total reward from that state onward (reward-to-go) and each trial gives a sample of this for each state visited. \\\n",
        "The utility of a state is determined by the expected utility and reward of previous states. Converges very slowly. Adaptive dynamic \\\n",
        "programming (ADP) uses constraints of the utilites of states by learning the transition model connecting them and solving the MDP \\\n",
        "using dynamic programming. In temporal differnce learning (TD) we do $U^{\\pi} (S) \\leftarrow U^{\\pi} (s) + \\alpha [R(s, \\pi(s), s') + \\\n",
        "\\gamma U^{\\pi}(s') - U^{\\pi} (s) where \\alpha is the learning rate. TD methods adjust the utility estimates toward the ideal \\\n",
        "equilibrium that holds locally when utility estimates are correct. TD does not use a transition model in its updates. \"\"\"\n",
        "chapter22_3 =  \"\"\" None.\"\"\"\n",
        "chapter22_4 =  \"\"\" Reinforcement learning is taking actions, observing the results and the associated reward and then updating \\\n",
        "our expectations of how the world works. There is an underlying MDP but we can't solve it because we don't know the transitions. The basic \\\n",
        "idea of reinforcement learning is receiving feedback in the form of rewards, agent's utility is defined by the reward funciton, learn to \\\n",
        "act as to maximize expected rewards, and all learning is based on observed samples of outcomes. Offline (MDPs) vs. Online (RL), for MDPs \\\n",
        "we can just compute things in our head but in online learning we don't know what's bad so we have to perform actions. Model-based learning is\n",
        "to learn an approximate model based on our experiences and solve for values as if our learned model is correct. Step 1, learn empirical MDP \\\n",
        "model by counting the outcomes s' for each s, a, normalizing to give an estimate of the transition model T(s, a, s'), and then discover each \\\n",
        "R(s, a, s') reward when we experience (s, a, s'). Step 2, solve the learned MDP using an algorithm like value iteration. Model-free learning is \\\n",
        "when everytime we take an action we compare the results of what we thought was going to happen and what actually happened and whenever what happens \\\n",
        "deviates from our expectations we update our values up or down. We only track the values of being in certain states and we don't care about the \\\n",
        "transition model or reward function. \"\"\"\n",
        "chapter22_5 =  \"\"\"Passive reinforcement is when we are given a fixed policy and we try to learn the state values, like the \\\n",
        "learner is just along for the ride. Direct evaluation, goal is to compute values fo each state under $\\pi$, idea: average together the sample \\\n",
        "values by acting according to $\\pi$ and every time we visit a state we record the sum of discounted rewards and average the samples. Direct \\\n",
        "evaluation does not learn about state connections, each state must be learned separately, and takes a long time to learn. Temporal difference \\\n",
        "learning, learn from every experience! Update V(s) each time we experience a transition (s, a, s', r), meaning likely outcomes s' will contribute \\\n",
        "updates more often. Temporal difference learning of values, policy still fixed, still doing evaluation! Move values toward value of whenever \\\n",
        "surccessor occurs: running average. sample = $R(s, \\pi (s), s') + \\gamma V^{\\pi} (s')$ and $V^{\\pi}(s) + \\alpha (sample - V^{\\pi}(s))$ where \\\n",
        "$\\alpha$ is the learning rate. Exponential moving average, so observations in the past become less and less over time because our discount is \\\n",
        "being multiplied by itself so more recent samples are more important. TD value learning is model free way to do policy evaluation, but we only \\\n",
        "learn the values not the q-values or else we won't be able to get a new policy.  \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Active reinforcement learning is full reinforcement learning \\\n",
        "to find optimal policies (like value iteration) to learn the optimal policy/values. Q-Value Iteration starts with $Q_0(s, a) = 0$ and \\\n",
        "$Q_{k + 1} (s, a) \\leftarrow \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma max_{a'} Q_k(s', a')]$. Learn $Q(s, a)$ values as you go, receiving a \\\n",
        "sample (s, a, s', r), old estimate Q(s, a) and new estimate sample = $R(s, a, s') + \\gamma max_{a'} Q(s', a')$ incorporated into a running \\\n",
        "average by interpolating between the old estimate and new estimate. We convere to the optimal policy (off-policy learning) but you have to \\\n",
        "explore enough and eventually make the learning rate small enough without decreasing it too quickly. Trade off between exploration and \\\n",
        "exploitation. Simplest exploration: random actions (e-greedy), every time step flip a coin and with small probability e act randomly, otherwise \\\n",
        "act on current policy. Exploration functions, explore places that we do not know are bad yet but once we know they are bad we should not go there \\\n",
        "anymore. $f(u, n) = u + k / n$ where $u$ is a value estimate and $n$ is visit count. Instead of $\\gamma max_{a'} Q(s', a')$ we have \\\n",
        "$f(Q(s', a'), N(s', a'))$ to max over. Propagates the \"bonus\" back to states that lead to unknown states as well. Regret measures the total \\\n",
        "mistake cost (the difference between expected rewards and optimal expected rewards). Need to optimally learn to be optimal to minimize regret. \\\n",
        "Approximate q-learning: $Q(s, a) = w_1 f_1 (s,a) + w_2 f_2 (s,a_ + \\dots + w_n f_n (s, a)]$. Adjust weights of active features when bad things \\\n",
        "happen.\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"n-armed bandit\" : \"slot machine with n levers\",\n",
        "\"exploitation\" : \"using the current best action to get rewards\",\n",
        "\"exploration\" : \"go to unknown states and actions to gain information of potentially better rewards/policies\",\n",
        "\"supervised learning\" : \"agent learns through passive observation of example input/output pairs provided by a 'teacher'\",\n",
        "\"reinforcement learning (RL)\" : \"agent interacts with world and receives rewards that reflect its performance\",\n",
        "\"sparse rewards\" : \"not all states give an informative reward signal, making learning much harder\",\n",
        "\"passive reinforcement learning\" : \"agent has fixed policy and wants to learn utilities of states\",\n",
        "\"active reinforcement learning\" : \"agent figures out what to do using exploration\",\n",
        "\"evaluation function\" : \"measures of desirability for vast state spaces\",\n",
        "\"function approximation\" : \"approximation of true utility function or Q-function\",\n",
        "\"policy search\" : \"adjusting the policy to improve performance until it can no longer improve\",\n",
        "\"regret\" : \"even if you learn intelligently, you make mistakes\",\n",
        "\"sampling\" : \"because of chance, you have to try things repeatedly to understand them\",\n",
        "\"difficulty\" : \"learning can be much harder than solving a known MDP\",\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "5b067282-0e81-4fca-a6a7-a2471aaf9745"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Each arm $M_i$ of a bandit problem is a Markov reward process (MRP) which is an MDP with only one possible action $a_i$. The problem has states $S_i$, transition model $P_i(s' | s, a_i)$, and reward $R_i(s, a_i, s')$. Each arm defines a distribution over reward sequences $R_{i, 0}, R_{i_1}, \\dots$, with each $R_{i, t}$ being a random variable. The bandit problem is an MDP where the state space is the Cartesian product $S = S_1 X \\dots X S_n$, actions $a_1, \\dots, a_n,$ and the transition model updates the state of whichever arm $M_i$ is selected and the other arms don't change, and there is the discount $\\gamma$. For bandit problems, a key property is that the arms are independent of each other and the agent only works on one arm at a time. \n\n## AIMA Chapter 22.1 Learning from Rewards\n Similarly to MDPs, reinforcement learning's goal is to maximize the expected sum of rewards. The main difference is that the agent may need to learn the transition model and/or reward function on its own. Model-based reinforcement learning is where the agent uses a transiiton model to interpret rewards and figure out how to act. The model might not be known, in which case the agent must learn it from the consequences of its actions. Model-based reinforcement learning often learn a utility function in terms of the sum of rewards from state $s$ onwards. Model-free reinforcement learning is where the agent does not know the transition model and does not learn it. Instead it learns a direct representation of what to do through either: Action-utility learning (most common form is Q-learning where agent learns Q-function $Q(s, a)$ that denotes the sum of rewards from state $s$ if action $a$ is done. Using this Q-function an agent can perform the action with the highest Q-value to determine what to do in each state) and Policy search (agent learns a policy $\\pi (s)$ that maps states to actions.) \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n In passive reinforcement learning the passive learning agent is trying to learn $U^pi(s)$ which is the expected total discounted reward if policy $\\pi$ is executed beginning in state $s$. Passive learning is similar to policy evaluation except the agent does not know the transition model nor the reward function. Direct utility estimation's idea is that the utility of a state is the expected total reward from that state onward (reward-to-go) and each trial gives a sample of this for each state visited. The utility of a state is determined by the expected utility and reward of previous states. Converges very slowly. Adaptive dynamic programming (ADP) uses constraints of the utilites of states by learning the transition model connecting them and solving the MDP using dynamic programming. In temporal differnce learning (TD) we do $U^{\\pi} (S) \\leftarrow U^{\\pi} (s) + \u0007lpha [R(s, \\pi(s), s') + \\gamma U^{\\pi}(s') - U^{\\pi} (s) where \u0007lpha is the learning rate. TD methods adjust the utility estimates toward the ideal equilibrium that holds locally when utility estimates are correct. TD does not use a transition model in its updates. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n None.\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Reinforcement learning is taking actions, observing the results and the associated reward and then updating our expectations of how the world works. There is an underlying MDP but we can't solve it because we don't know the transitions. The basic idea of reinforcement learning is receiving feedback in the form of rewards, agent's utility is defined by the reward funciton, learn to act as to maximize expected rewards, and all learning is based on observed samples of outcomes. Offline (MDPs) vs. Online (RL), for MDPs we can just compute things in our head but in online learning we don't know what's bad so we have to perform actions. Model-based learning is\nto learn an approximate model based on our experiences and solve for values as if our learned model is correct. Step 1, learn empirical MDP model by counting the outcomes s' for each s, a, normalizing to give an estimate of the transition model T(s, a, s'), and then discover each R(s, a, s') reward when we experience (s, a, s'). Step 2, solve the learned MDP using an algorithm like value iteration. Model-free learning is when everytime we take an action we compare the results of what we thought was going to happen and what actually happened and whenever what happens deviates from our expectations we update our values up or down. We only track the values of being in certain states and we don't care about the transition model or reward function. \n\n## Module 9 Lecture Notes\n Active reinforcement learning is full reinforcement learning to find optimal policies (like value iteration) to learn the optimal policy/values. Q-Value Iteration starts with $Q_0(s, a) = 0$ and $Q_{k + 1} (s, a) \\leftarrow \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma max_{a'} Q_k(s', a')]$. Learn $Q(s, a)$ values as you go, receiving a sample (s, a, s', r), old estimate Q(s, a) and new estimate sample = $R(s, a, s') + \\gamma max_{a'} Q(s', a')$ incorporated into a running average by interpolating between the old estimate and new estimate. We convere to the optimal policy (off-policy learning) but you have to explore enough and eventually make the learning rate small enough without decreasing it too quickly. Trade off between exploration and exploitation. Simplest exploration: random actions (e-greedy), every time step flip a coin and with small probability e act randomly, otherwise act on current policy. Exploration functions, explore places that we do not know are bad yet but once we know they are bad we should not go there anymore. $f(u, n) = u + k / n$ where $u$ is a value estimate and $n$ is visit count. Instead of $\\gamma max_{a'} Q(s', a')$ we have $f(Q(s', a'), N(s', a'))$ to max over. Propagates the \"bonus\" back to states that lead to unknown states as well. Regret measures the total mistake cost (the difference between expected rewards and optimal expected rewards). Need to optimally learn to be optimal to minimize regret. Approximate q-learning: $Q(s, a) = w_1 f_1 (s,a) + w_2 f_2 (s,a_ + \\dots + w_n f_n (s, a)]$. Adjust weights of active features when bad things happen.\n\n## Module 9 Definitions\n* **N-armed bandit** - slot machine with n levers\n* **Exploitation** - using the current best action to get rewards\n* **Exploration** - go to unknown states and actions to gain information of potentially better rewards/policies\n* **Supervised learning** - agent learns through passive observation of example input/output pairs provided by a 'teacher'\n* **Reinforcement learning (rl)** - agent interacts with world and receives rewards that reflect its performance\n* **Sparse rewards** - not all states give an informative reward signal, making learning much harder\n* **Passive reinforcement learning** - agent has fixed policy and wants to learn utilities of states\n* **Active reinforcement learning** - agent figures out what to do using exploration\n* **Evaluation function** - measures of desirability for vast state spaces\n* **Function approximation** - approximation of true utility function or Q-function\n* **Policy search** - adjusting the policy to improve performance until it can no longer improve\n* **Regret** - even if you learn intelligently, you make mistakes\n* **Sampling** - because of chance, you have to try things repeatedly to understand them\n* **Difficulty** - learning can be much harder than solving a known MDP\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Uncertainty occurs because of both laziness and ignorance. It will always be in present in complex, \\\n",
        "nondeterministic, or partially observable environments. \"\"\"\n",
        "chapter12_2 = \"\"\" Probabilities show the the agent's inability to reach a definite decision for the truth of \\\n",
        "a sentence and also summarize what an agent believes relative to evidence.\"\"\"\n",
        "chapter12_3 = \"\"\" Decision theory combines an agent's beliefs and desires and defines the best action as the \\\n",
        "one that maximizes the agent's expected utility. Basic probability statements are things like prior or unconditional \\\n",
        "probabilities as well as posterior or conditional probabilities in simple and complex propositions.\"\"\"\n",
        "chapter12_4 = \"\"\" Axioms of probability constrain probability logic and agents that violate these axioms must \\\n",
        "act irrationally in some cases. Full joint probability distribution includes the probability for every assignment of \\\n",
        "values to random variables. This is often to large to compute but when it is available, probabilties can be calculaed by \\\n",
        "summing the entries.\"\"\"\n",
        "chapter12_5 = \"\"\" Bayes' rule lets us calculate unknown probabilities from known conditional probabilities. \"\"\"\n",
        "chapter12_6 = \"\"\" Conditional independence achieved through direct casual relationships allows the full joint \\\n",
        "distribution to be broken down into smaller conditional distributions. Naive Bayes assumes the conditional \\\n",
        "independence of all effect variables from a single cause variable. \"\"\"\n",
        "chapter12_7 = \"\"\" None \"\"\"\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 = \"\"\" None \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" None \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" None \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" None \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" None \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" None \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Probabilistic reasoning gives us a framework for managing our beliefs and knowledge. A fully specified \\\n",
        "probability model associates a proability P(w) with each possible world w. P(W) must be between 0 and 1 and the sum of all values in a \\\n",
        "distribution W must sum to 1. The size of a joint distribution of $n$ variables with domain sizes $d$ is $d^n$. A probabilistic model is a \\\n",
        "joint distribution over a set of random variables. Probabilistic models have random variables with domains, assignments are called outcomes. \\\n",
        "$P(a|b) = P(a, b) / P(b)$. Conditional distributions are probability distributions over some varaibles given fixed values of others. Inference \\\n",
        "by enumeration: evidence varaibles, query variables, hidden variables make up the variables of our model. We want P(query | evidence). Step 1: \\\n",
        "select the entries consistent with the evidence, Step 2: sum out hidden varaibles to get joint of query and evidence, Step 3: noramlize. \\\n",
        "The Product Rule $P(y)P(x|y) = P(x, y)$. The Chain Rule $P(x_1, x_2, \\dots, x_n) = \\prod_i P(x_i | x_1 \\dots x_{i - 1})$. \\\n",
        "Bayes' Rule: $P(x | y) = P(y | x) * P(x) / P(y)$. Bayes rule allows us to build one conditional from its reverse which is useful becase \\\n",
        "often one conditional is more tricky than the other. Probabilistic language modeling's goal is to compute the probability of a sentence. \\\n",
        "Maximum likelihood estimation (MLE) is done by counting up the number of occurences of a phrase/sentence and dividing it by the total count \\\n",
        "of a smaller part of that phrase/sentence, but this doesn't work because some sentences may never show up if they are too long. Therefore we use \\\n",
        "the Markov Assumption to simplify things by limiting our word history (only previous k words). \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"sample space\" : \"possible world where events occur\",\n",
        "\"random variable\" : \"some aspect of the world about which we may have uncertainty\",\n",
        "\"joint distribution\" : \"specifies a real number for each assignment, $P(X_1 = x_1, X_2 = x_2 \\dots )\",\n",
        "\"event\" : \"set of outcomes\",\n",
        "\"marginalization\" : \"summing out, combine collapsed rows by adding\",\n",
        "\"probabilistic inference\" : \"compute a desired probability from known probabilities (conditional to joint)\",\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d5ee0b23-d3d1-4742-e910-d936097304fb"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Uncertainty occurs because of both laziness and ignorance. It will always be in present in complex, nondeterministic, or partially observable environments. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Probabilities show the the agent's inability to reach a definite decision for the truth of a sentence and also summarize what an agent believes relative to evidence.\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Decision theory combines an agent's beliefs and desires and defines the best action as the one that maximizes the agent's expected utility. Basic probability statements are things like prior or unconditional probabilities as well as posterior or conditional probabilities in simple and complex propositions.\n\n## AIMA Chapter 12.4 Independence\n Axioms of probability constrain probability logic and agents that violate these axioms must act irrationally in some cases. Full joint probability distribution includes the probability for every assignment of values to random variables. This is often to large to compute but when it is available, probabilties can be calculaed by summing the entries.\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes' rule lets us calculate unknown probabilities from known conditional probabilities. \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Conditional independence achieved through direct casual relationships allows the full joint distribution to be broken down into smaller conditional distributions. Naive Bayes assumes the conditional independence of all effect variables from a single cause variable. \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n None \n\n## SLP Chapter 3.1 N-Grams\n None \n\n## SLP Chapter 3.2 Evaluating Language Models\n None \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n None \n\n## SLP Chapter 3.4 Generalization and Zeros\n None \n\n## SLP Chapter 3.5 Smoothing\n None \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n None \n\n## Module 10 Lecture Notes\n Probabilistic reasoning gives us a framework for managing our beliefs and knowledge. A fully specified probability model associates a proability P(w) with each possible world w. P(W) must be between 0 and 1 and the sum of all values in a distribution W must sum to 1. The size of a joint distribution of $n$ variables with domain sizes $d$ is $d^n$. A probabilistic model is a joint distribution over a set of random variables. Probabilistic models have random variables with domains, assignments are called outcomes. $P(a|b) = P(a, b) / P(b)$. Conditional distributions are probability distributions over some varaibles given fixed values of others. Inference by enumeration: evidence varaibles, query variables, hidden variables make up the variables of our model. We want P(query | evidence). Step 1: select the entries consistent with the evidence, Step 2: sum out hidden varaibles to get joint of query and evidence, Step 3: noramlize. The Product Rule $P(y)P(x|y) = P(x, y)$. The Chain Rule $P(x_1, x_2, \\dots, x_n) = \\prod_i P(x_i | x_1 \\dots x_{i - 1})$. Bayes' Rule: $P(x | y) = P(y | x) * P(x) / P(y)$. Bayes rule allows us to build one conditional from its reverse which is useful becase often one conditional is more tricky than the other. Probabilistic language modeling's goal is to compute the probability of a sentence. Maximum likelihood estimation (MLE) is done by counting up the number of occurences of a phrase/sentence and dividing it by the total count of a smaller part of that phrase/sentence, but this doesn't work because some sentences may never show up if they are too long. Therefore we use the Markov Assumption to simplify things by limiting our word history (only previous k words). \n\n## Module 10 Definitions\n* **Sample space** - possible world where events occur\n* **Random variable** - some aspect of the world about which we may have uncertainty\n* **Joint distribution** - specifies a real number for each assignment, $P(X_1 = x_1, X_2 = x_2 \\dots )\n* **Event** - set of outcomes\n* **Marginalization** - summing out, combine collapsed rows by adding\n* **Probabilistic inference** - compute a desired probability from known probabilities (conditional to joint)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Bayesian Networks are DAGs where the nodes are random varaibles and each node \\\n",
        "has a conditional distribution for the node given its parents. Bayesian networks allow us to represent \\\n",
        "conditional independence relations in the domain. \"\"\"\n",
        "chapter13_2 = \"\"\" Bayesian networks specify a joint probaiblity distribution over its varaibles. The \n",
        "probability for any assignment to all variables is the product of the corresponding entires in the local conditioanl distributions. \\\n",
        "A Bayesian network is usually smaller than an explicitly complete joint distribution. \"\"\"\n",
        "chapter13_3 = \"\"\" Many conditional distributions can be represented using canonical families of distributions. \\\n",
        "Hybrid Bayesian networks include both discrete and continuous variables and use a variety of canonical distributions.\n",
        "Inference in Bayesian networks involves computation of the probability distribution of a set of query variables, \\\n",
        "given a set of evidence variables. Exact inference algorithms (variable elimination) evaluate the sum of products \\\n",
        "of conditional probabilities in as efficient a manner as possible. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Conditional independence: X and Y are conditionally independent given Z iff \\\n",
        "$P(x, y | z) = P(x | z) P(y | z)$ for all x, y, z. Equivalently we can say $P(x|z, y) = P(x|z)$ for all x, y, z. \\\n",
        "Bayes Nets are a way for us to model how we think the world works, and we can encode some conditional independence \\\n",
        "assumptions. D-separation algorithm. Casual chain (low pressure -> rain -> traffic): $P(x, y, z) = P(x) P(y |x)P(z|y)$, \\\n",
        "guranteed X independence of Z given Y. Common Cause (project due -> piazza, OH): $P(x, y, z) = P(y)P(x|y)P(z|y)$, guranteed \\\n",
        "X independence of Z given Y (Observing the cause blocks influence between effects). Common effect: two causes of one effect \\\n",
        "(v-structure) (X and Y are independent but are not independent given Z, opposite of previous cases). A common question \\\n",
        "in a BN is whther two variables are conditionally independent. Any complex example can be broken into repetitions of \\\n",
        "three canonical cases. X and Y are conditionally independent given Z if they are d-separated by Z. We consider all undirected \\\n",
        "paths from X to Y and if there are no active paths then we have independence. A path is active if each triple is active:\n",
        "casual chain A->B->C where B is unobserved (either direction), common cause A <- B -> C where B is unobserved, common effect \\\n",
        "(aka v-structure) A -> B <- C where B or one of its descendants is observed (grey = observed). If one or more paths are active, \\\n",
        "then indepndence is not guranteed otherwise (all paths are inactive) independence is guaranteed. Inference by enumeration in Bayes' \\\n",
        "Nets: given infinite time can solve, but is expensive since we basically calculate the entire joint distribution.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"inference\" : \"calculatin some useful quantity from a joint probability distribution\",    \n",
        "}\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 687
        },
        "cellView": "form",
        "outputId": "d360a32c-3e81-40c4-a158-35a1c11ecbdb"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian Networks are DAGs where the nodes are random varaibles and each node has a conditional distribution for the node given its parents. Bayesian networks allow us to represent conditional independence relations in the domain. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Bayesian networks specify a joint probaiblity distribution over its varaibles. The \nprobability for any assignment to all variables is the product of the corresponding entires in the local conditioanl distributions. A Bayesian network is usually smaller than an explicitly complete joint distribution. \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Many conditional distributions can be represented using canonical families of distributions. Hybrid Bayesian networks include both discrete and continuous variables and use a variety of canonical distributions.\nInference in Bayesian networks involves computation of the probability distribution of a set of query variables, given a set of evidence variables. Exact inference algorithms (variable elimination) evaluate the sum of products of conditional probabilities in as efficient a manner as possible. \n\n## Module 11 Lecture Notes\n Conditional independence: X and Y are conditionally independent given Z iff $P(x, y | z) = P(x | z) P(y | z)$ for all x, y, z. Equivalently we can say $P(x|z, y) = P(x|z)$ for all x, y, z. Bayes Nets are a way for us to model how we think the world works, and we can encode some conditional independence assumptions. D-separation algorithm. Casual chain (low pressure -> rain -> traffic): $P(x, y, z) = P(x) P(y |x)P(z|y)$, guranteed X independence of Z given Y. Common Cause (project due -> piazza, OH): $P(x, y, z) = P(y)P(x|y)P(z|y)$, guranteed X independence of Z given Y (Observing the cause blocks influence between effects). Common effect: two causes of one effect (v-structure) (X and Y are independent but are not independent given Z, opposite of previous cases). A common question in a BN is whther two variables are conditionally independent. Any complex example can be broken into repetitions of three canonical cases. X and Y are conditionally independent given Z if they are d-separated by Z. We consider all undirected paths from X to Y and if there are no active paths then we have independence. A path is active if each triple is active:\ncasual chain A->B->C where B is unobserved (either direction), common cause A <- B -> C where B is unobserved, common effect (aka v-structure) A -> B <- C where B or one of its descendants is observed (grey = observed). If one or more paths are active, then indepndence is not guranteed otherwise (all paths are inactive) independence is guaranteed. Inference by enumeration in Bayes' Nets: given infinite time can solve, but is expensive since we basically calculate the entire joint distribution.\n\n## Module 11 Definitions\n* **Inference** - calculatin some useful quantity from a joint probability distribution\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 = \"\"\" If the available data gives the correct answer for test inputs then the problem is supervised learning. \\\n",
        "For supervised learning we want to learn a function $y = h(x)$. Regression is wehre we learn a function whose output \\\n",
        "is a continuous or ordered value (like weight) and classification is learning a function with a small number of ossible\n",
        "output categories. \"\"\"\n",
        "chapter19_2 = \"\"\" Need a function that agrees with current data and can also agree with future data. Need to balance \\\n",
        "agreement with the data against the simplicity of our assumptions and hypotheses. Decision trees are able to represent all Boolean \\\n",
        "functions. Information-gain heuristic is an efficient method for finding a simple, consistent decision tree.\"\"\"\n",
        "chapter19_3 = \"\"\" Learning algorithm performance is visualized with a learning curve that shows the prediction accuracy \\\n",
        "on the test set as a function of the size of the training set. With multiple models, model selection can pick good values \\\n",
        "for hyperparameters using cross-validation on validation data. Once hyperparameters are tuend we can build out optimal \\\n",
        "model using all of the training data. Loss functions tell us how bad each error is and therefore the goal is to minimize \\\n",
        "loss over a validation set.\"\"\"\n",
        "chapter19_4 = \"\"\" Computational learning theory analyzes sample complexity and computational complexity of inductive learning. \\\n",
        "There is a tradeoff made in the expressiveness of the hypothesis space and teh ease of the learning. \"\"\"\n",
        "chapter19_5 = \"\"\" Linear regression can find its optimal parameters using radient descent search which can e used for \\\n",
        "models that do not have a closed-form solution. A perceptron is a linear classifier with ahard threshold that can be trained by a very\n",
        "simple weight udate rule to fit data that is linearly separable. Logistic regression replaces the perceptron's hard \\\n",
        "cutoff with a soft cut-off defined by a logistic function. Gradient descent works well even if the data is noisy and \\\n",
        "it is not linearly separable. \"\"\"\n",
        "chapter19_6 = \"\"\" Nonparametric models use all data to make predictions instead of just using a few parameters. Nearest \\\n",
        "neighbors and locally weighted regresision are two examples. \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" None \"\"\"\n",
        "slp_chapter4_2 = \"\"\" None \"\"\"\n",
        "slp_chapter4_3 = \"\"\" None \"\"\"\n",
        "slp_chapter4_4 = \"\"\" None \"\"\"\n",
        "slp_chapter4_5 = \"\"\" None \"\"\"\n",
        "slp_chapter4_6 = \"\"\" None \"\"\"\n",
        "slp_chapter4_7 = \"\"\" None \"\"\"\n",
        "slp_chapter4_8 = \"\"\" None \"\"\"\n",
        "slp_chapter4_9 = \"\"\" None \"\"\"\n",
        "slp_chapter4_10 = \"\"\" None \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Machine learning involves learning parameters (probabilities), learning structure (BN graphs), \\\n",
        "and learning hidden concepts (clustering). Classification: given inputs x, predict labels y. Model-based approach: build a \\\n",
        "model (Bayes' net) where the label and features are random variables, instantiate any observed features, and query for the \\\n",
        "distribution of the label conditioned on the features. Naive Bayes: features are independent effects of the label. General naive \\\n",
        "Bayes model has $P(Y, F_1, \\dots, F_n) = P(Y) \\prod_i P(F_i | Y). To update the weights of a perceptron we subtract the feature vector.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"machine learning\" : \"how to acquire a model from data\",\n",
        "\"features\" : \"attributes used to make the classification decision\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ce3c3791-34ca-4f78-a67f-da2e9fe8e4a1"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n If the available data gives the correct answer for test inputs then the problem is supervised learning. For supervised learning we want to learn a function $y = h(x)$. Regression is wehre we learn a function whose output is a continuous or ordered value (like weight) and classification is learning a function with a small number of ossible\noutput categories. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Need a function that agrees with current data and can also agree with future data. Need to balance agreement with the data against the simplicity of our assumptions and hypotheses. Decision trees are able to represent all Boolean functions. Information-gain heuristic is an efficient method for finding a simple, consistent decision tree.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Learning algorithm performance is visualized with a learning curve that shows the prediction accuracy on the test set as a function of the size of the training set. With multiple models, model selection can pick good values for hyperparameters using cross-validation on validation data. Once hyperparameters are tuend we can build out optimal model using all of the training data. Loss functions tell us how bad each error is and therefore the goal is to minimize loss over a validation set.\n\n## AIMA Chapter 5.5 Stochastic Games\n Computational learning theory analyzes sample complexity and computational complexity of inductive learning. There is a tradeoff made in the expressiveness of the hypothesis space and teh ease of the learning. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Linear regression can find its optimal parameters using radient descent search which can e used for models that do not have a closed-form solution. A perceptron is a linear classifier with ahard threshold that can be trained by a very\nsimple weight udate rule to fit data that is linearly separable. Logistic regression replaces the perceptron's hard cutoff with a soft cut-off defined by a logistic function. Gradient descent works well even if the data is noisy and it is not linearly separable. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Nonparametric models use all data to make predictions instead of just using a few parameters. Nearest neighbors and locally weighted regresision are two examples. \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n None \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n None \n\n## SLP Chapter 4.3 Worked Example\n None \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n None \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n None \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n None \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n None \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n None \n\n## SLP Chapter 4.9 Statistical Significance Testing\n None \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n None \n\n## Module 12 Lecture Notes\n Machine learning involves learning parameters (probabilities), learning structure (BN graphs), and learning hidden concepts (clustering). Classification: given inputs x, predict labels y. Model-based approach: build a model (Bayes' net) where the label and features are random variables, instantiate any observed features, and query for the distribution of the label conditioned on the features. Naive Bayes: features are independent effects of the label. General naive Bayes model has $P(Y, F_1, \\dots, F_n) = P(Y) \\prod_i P(F_i | Y). To update the weights of a perceptron we subtract the feature vector.\n\n## Module 12 Definitions\n* **Machine learning** - how to acquire a model from data\n* **Features** - attributes used to make the classification decision\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 = \"\"\" Classifiers requires a corpus of M observations of input/output pairs $(x^{(i)}, y^{(i)})$ and \\\n",
        "include a feature representation (vector of features for each input observation), a classification function that estimates class \\\n",
        "y using p(y|x), an objective function for learning to minimize error on training examples, and an algorithm to optimize the objective \\\n",
        "function. $z = \\sum_i w_i x_i + b$ where w_i is weight for feature x_i + bias term b and z is thrown into a sigmoid after. To learn in \\\n",
        "logistic regression (in order to know weights and bias), we use loss function that tells us the distance between our system output \\\n",
        "and our goal output (cross-entropy loss, MSE) and an algorithm optimizing the objective function like stochastic gradient descent to minimize \\\n",
        "the loss function. $L_{CE} (y_{hat}, y) = -[log \\sigma (wx + b) + (1 - y)log(1 - \\sigma(wx + b))]$ where $y_hat = \\sigma(wx + b)$. \\\n",
        "We want the loss to be smaller  if the model's estimate is close to correct and bigger if it is far from correct. \"\"\"\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 = \"\"\" Logistic regression loss function is convex so there is one minimum so gradient descent can always find the minimum not \n",
        "matter where it starts. We weight the amount of the gradient descent with a learning rate parameter. Gradient of cross-entropy loss function is intuitive, \\\n",
        "the difference between the true y and our estimate for x times the input value $x_j$. Loss for a batch of data is the average loss over the samples. The \\\n",
        "gradient for multiple data points is the sum of the individual gradients. Regularization is a way to penalize large weights and is done \\\n",
        "by adding a regularization term to the loss function. Softmax function is a generalization of sigmoid function for multinomial logistic \\\n",
        "regression. Neural networks are layers of classifiers essentially. Since perceptrons either output 0 or 1, we use smoothness sigmoid functions \\\n",
        "to allow for small changes to not drastically alter the input. We also take the linear z output of our sigmoid neurons and apply a \\\n",
        "non-linear function to them like a sigmoid, tanh, or rectified linear unit ReLU funciton. Represent a layer of the neural network as \\\n",
        "a single weight matrix W that sums all $w_i$ for each unit $i$ and a single bias vector $b$ that sums all $b_i$. With the wieght matrix \\\n",
        "$W$, we can easily perform three steps of multiplying W by x, adding b, and then applying the activation function. for a FFNN with a single \\\n",
        "hidden layer we have $h = \\sigma(Wx + b), z = Uh,$ and $y$ = softmax($z$). Like before to train neural networks we need a loss function \\\n",
        "(cross-entropy loss), optimization algorithm (gradient descent) and a way to calculate the gradient of the loss function (erorr propagation). \\\n",
        "Backwards differentiation utilizes the chain rule from calculus to calculate the slopes of the inputs. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"gradient descent\" : \"finds the minimum of a function by determining direction that function's slope is most steep and moving opposite\", \n",
        "\"overfitting\" : \"poor generalization and poor performance on hidden test cases\",\n",
        "\"feed-forward neural network\" : \"multilayer network that is fully connected and no cycles, only goes forward\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6aa51679-a986-4b5c-f483-bf79a5d720bf"
      },
      "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": 15,
      "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 Classifiers requires a corpus of M observations of input/output pairs $(x^{(i)}, y^{(i)})$ and include a feature representation (vector of features for each input observation), a classification function that estimates class y using p(y|x), an objective function for learning to minimize error on training examples, and an algorithm to optimize the objective function. $z = \\sum_i w_i x_i + b$ where w_i is weight for feature x_i + bias term b and z is thrown into a sigmoid after. To learn in logistic regression (in order to know weights and bias), we use loss function that tells us the distance between our system output and our goal output (cross-entropy loss, MSE) and an algorithm optimizing the objective function like stochastic gradient descent to minimize the loss function. $L_{CE} (y_{hat}, y) = -[log \\sigma (wx + b) + (1 - y)log(1 - \\sigma(wx + b))]$ where $y_hat = \\sigma(wx + b)$. We want the loss to be smaller  if the model's estimate is close to correct and bigger if it is far from correct. \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 Logistic regression loss function is convex so there is one minimum so gradient descent can always find the minimum not \nmatter where it starts. We weight the amount of the gradient descent with a learning rate parameter. Gradient of cross-entropy loss function is intuitive, the difference between the true y and our estimate for x times the input value $x_j$. Loss for a batch of data is the average loss over the samples. The gradient for multiple data points is the sum of the individual gradients. Regularization is a way to penalize large weights and is done by adding a regularization term to the loss function. Softmax function is a generalization of sigmoid function for multinomial logistic regression. Neural networks are layers of classifiers essentially. Since perceptrons either output 0 or 1, we use smoothness sigmoid functions to allow for small changes to not drastically alter the input. We also take the linear z output of our sigmoid neurons and apply a non-linear function to them like a sigmoid, tanh, or rectified linear unit ReLU funciton. Represent a layer of the neural network as a single weight matrix W that sums all $w_i$ for each unit $i$ and a single bias vector $b$ that sums all $b_i$. With the wieght matrix $W$, we can easily perform three steps of multiplying W by x, adding b, and then applying the activation function. for a FFNN with a single hidden layer we have $h = \\sigma(Wx + b), z = Uh,$ and $y$ = softmax($z$). Like before to train neural networks we need a loss function (cross-entropy loss), optimization algorithm (gradient descent) and a way to calculate the gradient of the loss function (erorr propagation). Backwards differentiation utilizes the chain rule from calculus to calculate the slopes of the inputs. \n\n## Module 13 Definitions\n* **Gradient descent** - finds the minimum of a function by determining direction that function's slope is most steep and moving opposite\n* **Overfitting** - poor generalization and poor performance on hidden test cases\n* **Feed-forward neural network** - multilayer network that is fully connected and no cycles, only goes forward\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 = \"\"\" Neural language models have several advantages over n-gram LMs like they don't \\\n",
        "need smoothing, they can handle much longer histories, they can generalize over contexts of similar words, and \\\n",
        "neural LMs tend to have much higher predictive accuracy than n-grams LM. The input to the neural networkis \\\n",
        "a k-gram of words $w_{1:k}, the output is a probability distribution over the next word, the k context words \\\n",
        "are treated as a word window. Each word is associated with an embedding vector. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c794082b-3078-403a-c1a1-3f8293bbbb57"
      },
      "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": 19,
      "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 Logistic regression loss function is convex so there is one minimum so gradient descent can always find the minimum not \nmatter where it starts. We weight the amount of the gradient descent with a learning rate parameter. Gradient of cross-entropy loss function is intuitive, the difference between the true y and our estimate for x times the input value $x_j$. Loss for a batch of data is the average loss over the samples. The gradient for multiple data points is the sum of the individual gradients. Regularization is a way to penalize large weights and is done by adding a regularization term to the loss function. Softmax function is a generalization of sigmoid function for multinomial logistic regression. Neural networks are layers of classifiers essentially. Since perceptrons either output 0 or 1, we use smoothness sigmoid functions to allow for small changes to not drastically alter the input. We also take the linear z output of our sigmoid neurons and apply a non-linear function to them like a sigmoid, tanh, or rectified linear unit ReLU funciton. Represent a layer of the neural network as a single weight matrix W that sums all $w_i$ for each unit $i$ and a single bias vector $b$ that sums all $b_i$. With the wieght matrix $W$, we can easily perform three steps of multiplying W by x, adding b, and then applying the activation function. for a FFNN with a single hidden layer we have $h = \\sigma(Wx + b), z = Uh,$ and $y$ = softmax($z$). Like before to train neural networks we need a loss function (cross-entropy loss), optimization algorithm (gradient descent) and a way to calculate the gradient of the loss function (erorr propagation). Backwards differentiation utilizes the chain rule from calculus to calculate the slopes of the inputs. \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "12c77f00-a2d6-4d52-e0c7-e6824e4b044b"
      },
      "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": 18,
      "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 Decision-theoretic agents assign a continuous range of values to states which allows it to more easily choose a better state when there is no clear best state. While the MEU principle formalizes the notion of what an intelligent agent should do, it does not operationalize it. It only provides a basic mathematical framework that can be used to define the AI problem. If an agent acts to maximize a utility function and that utility function correctly reflects the performance measure for a given environmen then the aagent will achieve the highest possible score. Performance measures give a score over a history of actions/state while the utility function only applies to the next state to help guide decisions step by step.  $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 Events in lotteries can be atomic states or lotteries themselves. Six axioms of utility theory: Orderability (a rational agent must prefer a lottery over another or be indifferent to them), Transitivity, Continuity (if an agent prefers B between A and C, then there exists some probability p where the agent is indifferent between B and the lottery where A occurs with probability p and C occurs with probability 1 - p), Substitutability, Monotonicity (if an agent prefers A over B then it should prefer lotteries that have a greater chance of A occurring), and Decomposability (compound lotteries can be simplified using laws of probability). Two properties of utility functions: if an agent follows the axioms then there exists a utility function $U$ where $U(A) > U(B) \\Leftrightarrow A \\succ B$ and $U(A) = U(B) \\Leftrightarrow A \\sim B$, the expected utility of a lottery is U(\\[p_1, S_1; \\dots ; p_n, S_n]) = \\sum_i p_i U(S_i).\n\n## AIMA Chapter 16.3 Utility Functions\n The best action $a*$ is determined by maximizing expected utility. $a* = argmax_a EU(a)$. For MDPs we have a stochastic transition model. Markovian means we ignore all states we visited before when calculating our transitions, so we only care about the current state we are in. Environment history is all the states visited until a terminal state is hit. Can solve MDPs using expectimax search. Even if we have an optimal policy, each time we follow the policy the nondeterminism makes it so that our total reward at the end is not always the same. Therefore we need to compute the expected utility of all the possible paths generated by a policy. Discounting penalizes rewards in the future, making us want to get rewards earlier (rewards decay exponentially). We discount because sooner rewards probably do have higher utility than later rewards and it will help our algorithms converge.\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n A sequentail decision problem in a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markovian Decision Process (MDP). An MDP has: a set of states, an initial state $s_0$, a set of actions ACTIONS(s) in each state, a transition model $P(s' | s, a)$ and a reward function $R(s, a, s')$. Solving an MDP usually involves dynamic programming. Since the environment is stochastic there is no one sequence we can use, so we use a policy that tells us what we should do in any given state. With a finite horizon an optimal action in a given state may depend on teh remaining time. Assuming the agent choose the optimal action, the utility of a state is the expected reward of the following transition summed with the discounted utility of the next state. The Bellman Equation: $U(s) = max_{a \\in A(s)} \\sum_{s'} P(s' | s, a) [R(s, a, s') + \\gamma U(s')]$. Q-function (action-utility function) is the expected utility of doing a given action in a given state: $U(s) = max_a Q(s, a)$ and $\\pi^*(s) = argmax_a Q(s, a)$. $Q(s, a) = \\sum_s' P(s' | s, a) [R(s, a, s') + \\gamma max_{a'} Q(s', a')]$. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value Iteration: start with arbitrary values for utilities, perform the Bellman update on all states simulataneously until convergence: $U_{i + 1}(s) \\gets max_{a \\in A(s)} \\sum_{s'} P(s' | s, a) [R(s, a, s') + \\gamma U_i(s')]$. Policy Iteration: lets us get an optimal policy with an inaccurate utility function. Alternates between two steps: Policy evaluation: for a given policy $\\pi_i$, calculate the utility of each state if $pi_i$ was done, $U_i = U^{\\pi_i}$ and Policy improvement: get a new MEU policy $pi_{i + 1} by looking one-step ahead based on U_i. The algorithm stops when the policy improvement step no longer changes utility values. Asynchronous policy iteration only updates the utilites of a subset of states. Linear programming is a general approach for\nconstrained optimization problems and can solve MDPs in polynomial time with respect to the number of states and actions. Value iteration and policy are offline algorithms which means they generate an optimal solution for a problem that an agent can execute. \n\n## Module 8 Lecture Notes\n Stationary preferences is $[a_1, a_2, \\dots] \\succ [b_1, b_2, \\dots] \\Leftrightarrow [r, a_1, a_2, \\dots] \\succ [r, b_1, b_2, \\dots]$. This gives us additive utilities $U([r_0, r_1, r_2, \\dots]) = r_0 + r_1 + r_2$ and discounted utilities $U([r_0, r_1, r_2, \\dots]) = r_0 + \\gamma r_1 + \\gamma^2 r_2$. MDP search trees, triangles are states, circles are q-states (state, action), and these trees are basically expectimax trees except our transition model has probabilities and rewards at given at each state instead of just the terminal states. $V*(s)$ is the expected utility starting in s and acting optimally. $Q*(s, a)$ is the expected utility starting out having taken action a from state s and then acting optimally. Fundamental operation is computing the expectimax value of a state by getting the expected utility under optimal action, average the sume of (discounted) rewards. $V*(s) = max_a Q*(s, a)$, $Q*(s, a) = \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V*(s')]$, and $V*(s) = max_a \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V*(s')]$. Value Iteration $O(S^2A)$, guaranteed to converge to unique optimal values. For policy evaluation, we fix the policy and determine the utilities, following the equation but we don't need to take the max of all actions. WE can just turn recursive Bellman equations into updates and perform valu iteration which takes O(S^2) time per iteration or since there rae no maxes in the equations we can directly solve the Bellman equations as a linear system. Policy extraction is when we are given the optimal values and we try to determine the optimal policy, which is done by a mini-expectimax (one-step) $\\pi * (s) = argmax_a \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma V* (s')]$. Given the optimal q-values, it is trivial to get the best policy as we just do $\\pi *(s) = argmax_a Q*(s, a)$. Actions are easier to select from q-values than values. Policy iteration combines policy evaluation and policy improvement. Value iteration has problems in that it is slow and the max at each state rarely changes and the policy often converges long before the values. Policy iteration is optimal and converges faster than value iteration usually. In value iteration every iteration updates both the values and (implicitly) the policy and we don't track the policy, but taking the max over actions implicitly recomputes it. In policy iteration we do several passes that update utilities with a fixed policy (quick since we fix the policy), after the policy is evaluated a new policy is chosen (slow like a value iteration pass) and then the new policy will be better or we're done.\n\n## Module 8 Definitions\n* **Utility function** - U(s): assigns a number to a state to describe its desirability\n* **Expected utility** - $EU(a) = \\sum_{s'} P(\\textnormal{RESULT}(a)=s')U(s')$\n* **Maximum expected utility (meu)** - $action = \\textnormal{argmax}_a EU(a)$, a rational agent should do things to maximize its expected utility\n* **Lottery** - $L = [p_1, S_1; p_2, S_2; \\dots p_n, S_n]$, Lottery $L$ with outcomes $S_i$ that occur with probability $p_i$\n* **Orderability** - one of $(A \\succ B)$, $(B \\succ A)$, or $(A \\sim B)$ holds\n* **Transitivity** - $(A \\succ B) \\wedge (B \\succ C) \\implies (A \\succ C)$\n* **Continuity** - $A \\succ B \\succ C \\implies \\exists p [p, A; 1 - p, C] \\sim B$\n* **Substitutability** - $A \\sim B \\implies [p, A; 1 - p, C] \\sim [p, B; 1 - p, C]$\n* **Monotonicity** - $A \\succ B \\implies (p > q \\Leftrightarrow [p, A; 1 - p, B] \\succ [q, A; 1 - q, B])$\n* **Decomposability** - $p, A; 1 - p, [q, B; 1 - q, C]] \\sim [p, A; (1 - p)q, B; (1 - p)(1 - q), C]$\n* **Markovian** - the probability of getting to state s' is solely dependent on the current state s\n* **Policy** - a solution that specifies what an agent should do in any given state\n* **Optimal policy** - $\\pi^*$, policy with highest expected utility\n* **Finite horizon** - fixed time N that decides when the game is over\n* **Nonstationary** - policy that depends on time\n* **Discount factor** - [0, 1], the preference of current rewards over future rewards\n* **Proper policy** - policy that is guaranteed to reach a terminal state\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Each arm $M_i$ of a bandit problem is a Markov reward process (MRP) which is an MDP with only one possible action $a_i$. The problem has states $S_i$, transition model $P_i(s' | s, a_i)$, and reward $R_i(s, a_i, s')$. Each arm defines a distribution over reward sequences $R_{i, 0}, R_{i_1}, \\dots$, with each $R_{i, t}$ being a random variable. The bandit problem is an MDP where the state space is the Cartesian product $S = S_1 X \\dots X S_n$, actions $a_1, \\dots, a_n,$ and the transition model updates the state of whichever arm $M_i$ is selected and the other arms don't change, and there is the discount $\\gamma$. For bandit problems, a key property is that the arms are independent of each other and the agent only works on one arm at a time. \n\n## AIMA Chapter 22.1 Learning from Rewards\n Similarly to MDPs, reinforcement learning's goal is to maximize the expected sum of rewards. The main difference is that the agent may need to learn the transition model and/or reward function on its own. Model-based reinforcement learning is where the agent uses a transiiton model to interpret rewards and figure out how to act. The model might not be known, in which case the agent must learn it from the consequences of its actions. Model-based reinforcement learning often learn a utility function in terms of the sum of rewards from state $s$ onwards. Model-free reinforcement learning is where the agent does not know the transition model and does not learn it. Instead it learns a direct representation of what to do through either: Action-utility learning (most common form is Q-learning where agent learns Q-function $Q(s, a)$ that denotes the sum of rewards from state $s$ if action $a$ is done. Using this Q-function an agent can perform the action with the highest Q-value to determine what to do in each state) and Policy search (agent learns a policy $\\pi (s)$ that maps states to actions.) \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n In passive reinforcement learning the passive learning agent is trying to learn $U^pi(s)$ which is the expected total discounted reward if policy $\\pi$ is executed beginning in state $s$. Passive learning is similar to policy evaluation except the agent does not know the transition model nor the reward function. Direct utility estimation's idea is that the utility of a state is the expected total reward from that state onward (reward-to-go) and each trial gives a sample of this for each state visited. The utility of a state is determined by the expected utility and reward of previous states. Converges very slowly. Adaptive dynamic programming (ADP) uses constraints of the utilites of states by learning the transition model connecting them and solving the MDP using dynamic programming. In temporal differnce learning (TD) we do $U^{\\pi} (S) \\leftarrow U^{\\pi} (s) + \u0007lpha [R(s, \\pi(s), s') + \\gamma U^{\\pi}(s') - U^{\\pi} (s) where \u0007lpha is the learning rate. TD methods adjust the utility estimates toward the ideal equilibrium that holds locally when utility estimates are correct. TD does not use a transition model in its updates. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n None.\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Reinforcement learning is taking actions, observing the results and the associated reward and then updating our expectations of how the world works. There is an underlying MDP but we can't solve it because we don't know the transitions. The basic idea of reinforcement learning is receiving feedback in the form of rewards, agent's utility is defined by the reward funciton, learn to act as to maximize expected rewards, and all learning is based on observed samples of outcomes. Offline (MDPs) vs. Online (RL), for MDPs we can just compute things in our head but in online learning we don't know what's bad so we have to perform actions. Model-based learning is\nto learn an approximate model based on our experiences and solve for values as if our learned model is correct. Step 1, learn empirical MDP model by counting the outcomes s' for each s, a, normalizing to give an estimate of the transition model T(s, a, s'), and then discover each R(s, a, s') reward when we experience (s, a, s'). Step 2, solve the learned MDP using an algorithm like value iteration. Model-free learning is when everytime we take an action we compare the results of what we thought was going to happen and what actually happened and whenever what happens deviates from our expectations we update our values up or down. We only track the values of being in certain states and we don't care about the transition model or reward function. \n\n## Module 9 Lecture Notes\n Active reinforcement learning is full reinforcement learning to find optimal policies (like value iteration) to learn the optimal policy/values. Q-Value Iteration starts with $Q_0(s, a) = 0$ and $Q_{k + 1} (s, a) \\leftarrow \\sum_{s'} T(s, a, s') [R(s, a, s') + \\gamma max_{a'} Q_k(s', a')]$. Learn $Q(s, a)$ values as you go, receiving a sample (s, a, s', r), old estimate Q(s, a) and new estimate sample = $R(s, a, s') + \\gamma max_{a'} Q(s', a')$ incorporated into a running average by interpolating between the old estimate and new estimate. We convere to the optimal policy (off-policy learning) but you have to explore enough and eventually make the learning rate small enough without decreasing it too quickly. Trade off between exploration and exploitation. Simplest exploration: random actions (e-greedy), every time step flip a coin and with small probability e act randomly, otherwise act on current policy. Exploration functions, explore places that we do not know are bad yet but once we know they are bad we should not go there anymore. $f(u, n) = u + k / n$ where $u$ is a value estimate and $n$ is visit count. Instead of $\\gamma max_{a'} Q(s', a')$ we have $f(Q(s', a'), N(s', a'))$ to max over. Propagates the \"bonus\" back to states that lead to unknown states as well. Regret measures the total mistake cost (the difference between expected rewards and optimal expected rewards). Need to optimally learn to be optimal to minimize regret. Approximate q-learning: $Q(s, a) = w_1 f_1 (s,a) + w_2 f_2 (s,a_ + \\dots + w_n f_n (s, a)]$. Adjust weights of active features when bad things happen.\n\n## Module 9 Definitions\n* **N-armed bandit** - slot machine with n levers\n* **Exploitation** - using the current best action to get rewards\n* **Exploration** - go to unknown states and actions to gain information of potentially better rewards/policies\n* **Supervised learning** - agent learns through passive observation of example input/output pairs provided by a 'teacher'\n* **Reinforcement learning (rl)** - agent interacts with world and receives rewards that reflect its performance\n* **Sparse rewards** - not all states give an informative reward signal, making learning much harder\n* **Passive reinforcement learning** - agent has fixed policy and wants to learn utilities of states\n* **Active reinforcement learning** - agent figures out what to do using exploration\n* **Evaluation function** - measures of desirability for vast state spaces\n* **Function approximation** - approximation of true utility function or Q-function\n* **Policy search** - adjusting the policy to improve performance until it can no longer improve\n* **Regret** - even if you learn intelligently, you make mistakes\n* **Sampling** - because of chance, you have to try things repeatedly to understand them\n* **Difficulty** - learning can be much harder than solving a known MDP\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Uncertainty occurs because of both laziness and ignorance. It will always be in present in complex, nondeterministic, or partially observable environments. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Probabilities show the the agent's inability to reach a definite decision for the truth of a sentence and also summarize what an agent believes relative to evidence.\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Decision theory combines an agent's beliefs and desires and defines the best action as the one that maximizes the agent's expected utility. Basic probability statements are things like prior or unconditional probabilities as well as posterior or conditional probabilities in simple and complex propositions.\n\n## AIMA Chapter 12.4 Independence\n Axioms of probability constrain probability logic and agents that violate these axioms must act irrationally in some cases. Full joint probability distribution includes the probability for every assignment of values to random variables. This is often to large to compute but when it is available, probabilties can be calculaed by summing the entries.\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes' rule lets us calculate unknown probabilities from known conditional probabilities. \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Conditional independence achieved through direct casual relationships allows the full joint distribution to be broken down into smaller conditional distributions. Naive Bayes assumes the conditional independence of all effect variables from a single cause variable. \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n None \n\n## SLP Chapter 3.1 N-Grams\n None \n\n## SLP Chapter 3.2 Evaluating Language Models\n None \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n None \n\n## SLP Chapter 3.4 Generalization and Zeros\n None \n\n## SLP Chapter 3.5 Smoothing\n None \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n None \n\n## Module 10 Lecture Notes\n Probabilistic reasoning gives us a framework for managing our beliefs and knowledge. A fully specified probability model associates a proability P(w) with each possible world w. P(W) must be between 0 and 1 and the sum of all values in a distribution W must sum to 1. The size of a joint distribution of $n$ variables with domain sizes $d$ is $d^n$. A probabilistic model is a joint distribution over a set of random variables. Probabilistic models have random variables with domains, assignments are called outcomes. $P(a|b) = P(a, b) / P(b)$. Conditional distributions are probability distributions over some varaibles given fixed values of others. Inference by enumeration: evidence varaibles, query variables, hidden variables make up the variables of our model. We want P(query | evidence). Step 1: select the entries consistent with the evidence, Step 2: sum out hidden varaibles to get joint of query and evidence, Step 3: noramlize. The Product Rule $P(y)P(x|y) = P(x, y)$. The Chain Rule $P(x_1, x_2, \\dots, x_n) = \\prod_i P(x_i | x_1 \\dots x_{i - 1})$. Bayes' Rule: $P(x | y) = P(y | x) * P(x) / P(y)$. Bayes rule allows us to build one conditional from its reverse which is useful becase often one conditional is more tricky than the other. Probabilistic language modeling's goal is to compute the probability of a sentence. Maximum likelihood estimation (MLE) is done by counting up the number of occurences of a phrase/sentence and dividing it by the total count of a smaller part of that phrase/sentence, but this doesn't work because some sentences may never show up if they are too long. Therefore we use the Markov Assumption to simplify things by limiting our word history (only previous k words). \n\n## Module 10 Definitions\n* **Sample space** - possible world where events occur\n* **Random variable** - some aspect of the world about which we may have uncertainty\n* **Joint distribution** - specifies a real number for each assignment, $P(X_1 = x_1, X_2 = x_2 \\dots )\n* **Event** - set of outcomes\n* **Marginalization** - summing out, combine collapsed rows by adding\n* **Probabilistic inference** - compute a desired probability from known probabilities (conditional to joint)\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian Networks are DAGs where the nodes are random varaibles and each node has a conditional distribution for the node given its parents. Bayesian networks allow us to represent conditional independence relations in the domain. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Bayesian networks specify a joint probaiblity distribution over its varaibles. The \nprobability for any assignment to all variables is the product of the corresponding entires in the local conditioanl distributions. A Bayesian network is usually smaller than an explicitly complete joint distribution. \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Many conditional distributions can be represented using canonical families of distributions. Hybrid Bayesian networks include both discrete and continuous variables and use a variety of canonical distributions.\nInference in Bayesian networks involves computation of the probability distribution of a set of query variables, given a set of evidence variables. Exact inference algorithms (variable elimination) evaluate the sum of products of conditional probabilities in as efficient a manner as possible. \n\n## Module 11 Lecture Notes\n Conditional independence: X and Y are conditionally independent given Z iff $P(x, y | z) = P(x | z) P(y | z)$ for all x, y, z. Equivalently we can say $P(x|z, y) = P(x|z)$ for all x, y, z. Bayes Nets are a way for us to model how we think the world works, and we can encode some conditional independence assumptions. D-separation algorithm. Casual chain (low pressure -> rain -> traffic): $P(x, y, z) = P(x) P(y |x)P(z|y)$, guranteed X independence of Z given Y. Common Cause (project due -> piazza, OH): $P(x, y, z) = P(y)P(x|y)P(z|y)$, guranteed X independence of Z given Y (Observing the cause blocks influence between effects). Common effect: two causes of one effect (v-structure) (X and Y are independent but are not independent given Z, opposite of previous cases). A common question in a BN is whther two variables are conditionally independent. Any complex example can be broken into repetitions of three canonical cases. X and Y are conditionally independent given Z if they are d-separated by Z. We consider all undirected paths from X to Y and if there are no active paths then we have independence. A path is active if each triple is active:\ncasual chain A->B->C where B is unobserved (either direction), common cause A <- B -> C where B is unobserved, common effect (aka v-structure) A -> B <- C where B or one of its descendants is observed (grey = observed). If one or more paths are active, then indepndence is not guranteed otherwise (all paths are inactive) independence is guaranteed. Inference by enumeration in Bayes' Nets: given infinite time can solve, but is expensive since we basically calculate the entire joint distribution.\n\n## Module 11 Definitions\n* **Inference** - calculatin some useful quantity from a joint probability distribution\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n If the available data gives the correct answer for test inputs then the problem is supervised learning. For supervised learning we want to learn a function $y = h(x)$. Regression is wehre we learn a function whose output is a continuous or ordered value (like weight) and classification is learning a function with a small number of ossible\noutput categories. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Need a function that agrees with current data and can also agree with future data. Need to balance agreement with the data against the simplicity of our assumptions and hypotheses. Decision trees are able to represent all Boolean functions. Information-gain heuristic is an efficient method for finding a simple, consistent decision tree.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Learning algorithm performance is visualized with a learning curve that shows the prediction accuracy on the test set as a function of the size of the training set. With multiple models, model selection can pick good values for hyperparameters using cross-validation on validation data. Once hyperparameters are tuend we can build out optimal model using all of the training data. Loss functions tell us how bad each error is and therefore the goal is to minimize loss over a validation set.\n\n## AIMA Chapter 5.5 Stochastic Games\n Computational learning theory analyzes sample complexity and computational complexity of inductive learning. There is a tradeoff made in the expressiveness of the hypothesis space and teh ease of the learning. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Linear regression can find its optimal parameters using radient descent search which can e used for models that do not have a closed-form solution. A perceptron is a linear classifier with ahard threshold that can be trained by a very\nsimple weight udate rule to fit data that is linearly separable. Logistic regression replaces the perceptron's hard cutoff with a soft cut-off defined by a logistic function. Gradient descent works well even if the data is noisy and it is not linearly separable. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Nonparametric models use all data to make predictions instead of just using a few parameters. Nearest neighbors and locally weighted regresision are two examples. \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n None \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n None \n\n## SLP Chapter 4.3 Worked Example\n None \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n None \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n None \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n None \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n None \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n None \n\n## SLP Chapter 4.9 Statistical Significance Testing\n None \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n None \n\n## Module 12 Lecture Notes\n Machine learning involves learning parameters (probabilities), learning structure (BN graphs), and learning hidden concepts (clustering). Classification: given inputs x, predict labels y. Model-based approach: build a model (Bayes' net) where the label and features are random variables, instantiate any observed features, and query for the distribution of the label conditioned on the features. Naive Bayes: features are independent effects of the label. General naive Bayes model has $P(Y, F_1, \\dots, F_n) = P(Y) \\prod_i P(F_i | Y). To update the weights of a perceptron we subtract the feature vector.\n\n## Module 12 Definitions\n* **Machine learning** - how to acquire a model from data\n* **Features** - attributes used to make the classification decision\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 Classifiers requires a corpus of M observations of input/output pairs $(x^{(i)}, y^{(i)})$ and include a feature representation (vector of features for each input observation), a classification function that estimates class y using p(y|x), an objective function for learning to minimize error on training examples, and an algorithm to optimize the objective function. $z = \\sum_i w_i x_i + b$ where w_i is weight for feature x_i + bias term b and z is thrown into a sigmoid after. To learn in logistic regression (in order to know weights and bias), we use loss function that tells us the distance between our system output and our goal output (cross-entropy loss, MSE) and an algorithm optimizing the objective function like stochastic gradient descent to minimize the loss function. $L_{CE} (y_{hat}, y) = -[log \\sigma (wx + b) + (1 - y)log(1 - \\sigma(wx + b))]$ where $y_hat = \\sigma(wx + b)$. We want the loss to be smaller  if the model's estimate is close to correct and bigger if it is far from correct. \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 Logistic regression loss function is convex so there is one minimum so gradient descent can always find the minimum not \nmatter where it starts. We weight the amount of the gradient descent with a learning rate parameter. Gradient of cross-entropy loss function is intuitive, the difference between the true y and our estimate for x times the input value $x_j$. Loss for a batch of data is the average loss over the samples. The gradient for multiple data points is the sum of the individual gradients. Regularization is a way to penalize large weights and is done by adding a regularization term to the loss function. Softmax function is a generalization of sigmoid function for multinomial logistic regression. Neural networks are layers of classifiers essentially. Since perceptrons either output 0 or 1, we use smoothness sigmoid functions to allow for small changes to not drastically alter the input. We also take the linear z output of our sigmoid neurons and apply a non-linear function to them like a sigmoid, tanh, or rectified linear unit ReLU funciton. Represent a layer of the neural network as a single weight matrix W that sums all $w_i$ for each unit $i$ and a single bias vector $b$ that sums all $b_i$. With the wieght matrix $W$, we can easily perform three steps of multiplying W by x, adding b, and then applying the activation function. for a FFNN with a single hidden layer we have $h = \\sigma(Wx + b), z = Uh,$ and $y$ = softmax($z$). Like before to train neural networks we need a loss function (cross-entropy loss), optimization algorithm (gradient descent) and a way to calculate the gradient of the loss function (erorr propagation). Backwards differentiation utilizes the chain rule from calculus to calculate the slopes of the inputs. \n\n## Module 13 Definitions\n* **Gradient descent** - finds the minimum of a function by determining direction that function's slope is most steep and moving opposite\n* **Overfitting** - poor generalization and poor performance on hidden test cases\n* **Feed-forward neural network** - multilayer network that is fully connected and no cycles, only goes forward\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 Logistic regression loss function is convex so there is one minimum so gradient descent can always find the minimum not \nmatter where it starts. We weight the amount of the gradient descent with a learning rate parameter. Gradient of cross-entropy loss function is intuitive, the difference between the true y and our estimate for x times the input value $x_j$. Loss for a batch of data is the average loss over the samples. The gradient for multiple data points is the sum of the individual gradients. Regularization is a way to penalize large weights and is done by adding a regularization term to the loss function. Softmax function is a generalization of sigmoid function for multinomial logistic regression. Neural networks are layers of classifiers essentially. Since perceptrons either output 0 or 1, we use smoothness sigmoid functions to allow for small changes to not drastically alter the input. We also take the linear z output of our sigmoid neurons and apply a non-linear function to them like a sigmoid, tanh, or rectified linear unit ReLU funciton. Represent a layer of the neural network as a single weight matrix W that sums all $w_i$ for each unit $i$ and a single bias vector $b$ that sums all $b_i$. With the wieght matrix $W$, we can easily perform three steps of multiplying W by x, adding b, and then applying the activation function. for a FFNN with a single hidden layer we have $h = \\sigma(Wx + b), z = Uh,$ and $y$ = softmax($z$). Like before to train neural networks we need a loss function (cross-entropy loss), optimization algorithm (gradient descent) and a way to calculate the gradient of the loss function (erorr propagation). Backwards differentiation utilizes the chain rule from calculus to calculate the slopes of the inputs. \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}