{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "brNDGX-kvzds",
        "aPtM8g7R0Pds",
        "cw5IpDLCZa4W",
        "s3Uk9gQTevcj",
        "5yG3-YncJfTB",
        "GZZXyrV-xuAp"
      ]
    },
    "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": "3551011f-be0b-408b-fbca-ed2282b1695e"
      },
      "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": 113,
      "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": "a52adcb1-cfe6-4ac9-e051-10374151abdc"
      },
      "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": 114,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 115,
      "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",
        "$EU(a) = \\sum_{s'} P(RESULT(a)=s')U(s') $\n",
        "\n",
        "$action = argmax_a EU(a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" MEU(maximum expected utility) principle says a rational agent shall choose the action that maximizes the expected utility.  It is clearly related the performance measures.  As an agent will achieve the highest possible perfermance measures if the agent acts to maximize a utility function that correctly reflects the performance measure.\n",
        "\n",
        "The performance measures apply retrospectively, giving scores for history, while the utility function applies to the very next state, used to guide actions for each step.\n",
        "\n",
        " \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" six constraints: Oderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability.  Known as axioms of utility theory.\n",
        "\n",
        "The axiom of utility theory can derive: a) Existence of Utility Function;  b) Expected Utility as the sum of the probability of each outcome times the utility of that outcome.\n",
        "\n",
        "In a deterministic environment an agent needs only a preference ranking on states.  This is called a value function or ordinal utility function. \"\"\"\n",
        "chapter16_3 =  \"\"\" The utility of money curve: the slope of the positive part of the curve decreases, agents with such shape of curves are risk-adverse.  On the other hand, it is called risk seek for behavior prefers smaller gains vs larger losses.\n",
        "\n",
        "The difference between EMV(expected monetary value) of a lottery and its certainty equivalent is call the insurance premium.\n",
        "\n",
        "Risk neutural is an agent havinga linear curve (Utility of monetary value curve). \n",
        "\n",
        "The computation of true expected utility tends to be too difficult in reality.  Usually working with estimates of the true expected utility: $\\hat {EU}(a)$ rather than $EU(a)$.\n",
        "We will assume the estimates are unbiased: $E(\\hat {EU}(a) -EU(a)) = 0.  Since we select highest utility estimate, we favor the overly optimistic estimates (even though there are as many pessimistic as optimistic estimates), that is the source of teh bias.\n",
        "This tendency for the estimated expected utility of the best choice to be too high is called the optimizer's curse.  It crops up everywhere because of widely adopted utility-maximizing selection process. Hence, take the utility estimates at face value is a bad idea.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Sequential decision problems are problems in which the agent's utility depends on a sequence of decisions.\n",
        "\n",
        "Markovian transitions: the probability of reaching $s'$ from $s$ depends only a $s$ and not on the history of earlier states.\n",
        "\n",
        "Markov decision process (MDP) is a sequential decision problem for a fully observable, stochastic environment with a Markavian transition model and additive rewards. consists of a set of states, including a initial state), a set of actions for each state, a transition model $P(s'|s,a)$ and a reward function $R(s,a,s')$.\n",
        "\n",
        "A solution can not be a fixed action sequence because the agent may end up in a state other than the goal state.  Hence, a solution must specify the agent's action for any state that the agent might reach.  Such solution is called a policy.\n",
        "\n",
        "When time horizon is infinite, there is no reason to behave differently in the same state at different times.  An optimal action depends on ly on the current state and the optimal polity is stationary.  But in a finite horizon, an optimal action in a given state may depend on how much time is left.  Hence, the policy is nonstationary.\n",
        "\n",
        "Optimal policy is independent of the starting state, in  infinite horizon.\n",
        "\n",
        "Bellman equation: $$ U(s) = max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma U(s')]$$  ($T(s,a,s') is another format for P(s'|s,a)$)\n",
        "\n",
        "Action utility function or Q-function: Q(s,a) is the expected utility of taking a given action in a given state.  Hence, $U(s) = max_a Q(s, a)$  and the optimal policy can be extracted from teh Q-function as:  $\\pi^*(s) = argmax_a Q(s, a)$\n",
        "\n",
        "Bellman equation for Q-function: $$ Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma U(s')] = \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma max_{a'}Q(s',a')] $$\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\" The Bellman equation for utility of a state above is the basis of the Value Iteration.  Bellman update : $U_{i+1}(s) \\leftarrow max_{a\\inA(s)} \\sum_{s'} P(s'|a,s)[R(s,a,s')+ \\gamma U_i(s')]$\n",
        "\n",
        "Iterative approach is because the max operator is not linear.  Staring with arbitrary initial values for the utilities, updating the utility of each state from the utilities of its neighbors by computing the right hand side of the equation and plug ging it into the left-hand side.  Repeat until reaching equilibrium.\n",
        "\n",
        "Policy iteration includes two steps: 1) policy evaluation, calculate the utility of each state if the given policy $\\pi_i$ is execued . $U_i = U^{\\pi_i}$.  2) policy improvement, compute a new MEU policy $\\pi_{i+1}$, using one-step look-ahead based on $U_i$.\n",
        "\n",
        "The implementation of policy iteration is simpler than value iteration because teh action in each state is fixed by the policy.  \n",
        "\n",
        "Value iteration and policy iteration are offline algorithm that generate an optimal solution for the problem, which can be executed by an agent.  For large problem, this is impossible.  Hence, online algorithms are needed.  One approach is a simplified ExpectMinMax algorithm for game trees with chance nodes.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "Value iteration runtime is $O(S^2 A)$ per iteration, slow among all algorithm. Policy converges way earlier than values converge.\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\" : \"a function to capture the agent's preference by assigns a single number to express the desirability of a state\",\n",
        "\"expected utility\" : \"the average utility value of the outcomes of an action, weighted by the probability of the outcomes\",\n",
        "\"maximum expected utility (MEU)\" : \" a rational agent should choose the action that maximizes the agent's expectd utility.\",\n",
        "\"proper policy\": \"a policy that is guaranteed to reach a terminal state.\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 116,
      "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": 0
        },
        "outputId": "350fa7dd-fc8b-4ac0-d925-79931478c281"
      },
      "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": 117,
      "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 MEU(maximum expected utility) principle says a rational agent shall choose the action that maximizes the expected utility.  It is clearly related the performance measures.  As an agent will achieve the highest possible perfermance measures if the agent acts to maximize a utility function that correctly reflects the performance measure.\n\nThe performance measures apply retrospectively, giving scores for history, while the utility function applies to the very next state, used to guide actions for each step.\n\n  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\n\n$EU(a) = \\sum_{s'} P(RESULT(a)=s')U(s') $\n\n$action = argmax_a EU(a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n six constraints: Oderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability.  Known as axioms of utility theory.\n\nThe axiom of utility theory can derive: a) Existence of Utility Function;  b) Expected Utility as the sum of the probability of each outcome times the utility of that outcome.\n\nIn a deterministic environment an agent needs only a preference ranking on states.  This is called a value function or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\n The utility of money curve: the slope of the positive part of the curve decreases, agents with such shape of curves are risk-adverse.  On the other hand, it is called risk seek for behavior prefers smaller gains vs larger losses.\n\nThe difference between EMV(expected monetary value) of a lottery and its certainty equivalent is call the insurance premium.\n\nRisk neutural is an agent havinga linear curve (Utility of monetary value curve). \n\nThe computation of true expected utility tends to be too difficult in reality.  Usually working with estimates of the true expected utility: $\\hat {EU}(a)$ rather than $EU(a)$.\nWe will assume the estimates are unbiased: $E(\\hat {EU}(a) -EU(a)) = 0.  Since we select highest utility estimate, we favor the overly optimistic estimates (even though there are as many pessimistic as optimistic estimates), that is the source of teh bias.\nThis tendency for the estimated expected utility of the best choice to be too high is called the optimizer's curse.  It crops up everywhere because of widely adopted utility-maximizing selection process. Hence, take the utility estimates at face value is a bad idea.\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Sequential decision problems are problems in which the agent's utility depends on a sequence of decisions.\n\nMarkovian transitions: the probability of reaching $s'$ from $s$ depends only a $s$ and not on the history of earlier states.\n\nMarkov decision process (MDP) is a sequential decision problem for a fully observable, stochastic environment with a Markavian transition model and additive rewards. consists of a set of states, including a initial state), a set of actions for each state, a transition model $P(s'|s,a)$ and a reward function $R(s,a,s')$.\n\nA solution can not be a fixed action sequence because the agent may end up in a state other than the goal state.  Hence, a solution must specify the agent's action for any state that the agent might reach.  Such solution is called a policy.\n\nWhen time horizon is infinite, there is no reason to behave differently in the same state at different times.  An optimal action depends on ly on the current state and the optimal polity is stationary.  But in a finite horizon, an optimal action in a given state may depend on how much time is left.  Hence, the policy is nonstationary.\n\nOptimal policy is independent of the starting state, in  infinite horizon.\n\nBellman equation: $$ U(s) = max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma U(s')]$$  ($T(s,a,s') is another format for P(s'|s,a)$)\n\nAction utility function or Q-function: Q(s,a) is the expected utility of taking a given action in a given state.  Hence, $U(s) = max_a Q(s, a)$  and the optimal policy can be extracted from teh Q-function as:  $\\pi^*(s) = argmax_a Q(s, a)$\n\nBellman equation for Q-function: $$ Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma U(s')] = \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma max_{a'}Q(s',a')] $$\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n The Bellman equation for utility of a state above is the basis of the Value Iteration.  Bellman update : $U_{i+1}(s) \\leftarrow max_{a\\inA(s)} \\sum_{s'} P(s'|a,s)[R(s,a,s')+ \\gamma U_i(s')]$\n\nIterative approach is because the max operator is not linear.  Staring with arbitrary initial values for the utilities, updating the utility of each state from the utilities of its neighbors by computing the right hand side of the equation and plug ging it into the left-hand side.  Repeat until reaching equilibrium.\n\nPolicy iteration includes two steps: 1) policy evaluation, calculate the utility of each state if the given policy $\\pi_i$ is execued . $U_i = U^{\\pi_i}$.  2) policy improvement, compute a new MEU policy $\\pi_{i+1}$, using one-step look-ahead based on $U_i$.\n\nThe implementation of policy iteration is simpler than value iteration because teh action in each state is fixed by the policy.  \n\nValue iteration and policy iteration are offline algorithm that generate an optimal solution for the problem, which can be executed by an agent.  For large problem, this is impossible.  Hence, online algorithms are needed.  One approach is a simplified ExpectMinMax algorithm for game trees with chance nodes.\n\n\n\n\n## Module 8 Lecture Notes\n \nValue iteration runtime is $O(S^2 A)$ per iteration, slow among all algorithm. Policy converges way earlier than values converge.\n\n\n## Module 8 Definitions\n* **Utility function** - a function to capture the agent's preference by assigns a single number to express the desirability of a state\n* **Expected utility** - the average utility value of the outcomes of an action, weighted by the probability of the outcomes\n* **Maximum expected utility (meu)** -  a rational agent should choose the action that maximizes the agent's expectd utility.\n* **Proper policy** - a 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 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" In Reinforcement learning (RL), agent interacts with the world and receives rewards, or reinforcement in the terminology of psychology. \n",
        "\n",
        "RL differs from solving an MDP as the agent is not given an MDP problem to solve.  Instead, the agent has to act in order to learn since the transition model and the reward function are not given.\n",
        "\n",
        "Sparse rewards.  In chess or racing, the agent is given no informative reward signal in the vast majority of states.  Intermediate rewards make learning much easier.\n",
        "\n",
        "Model-based RL: agent uses a transition model which may be unkown initially.  Model-based RL usually learn a utility function (in addition to learing the transition model if it is unknown).\n",
        "\n",
        "Model-free RL:  agent learns a more direct representation of how to act, and it neither knows nor learns a transition model.  There are two varieties: Action-utility learning, of which the most common is Q-learning where the agent learns a Q-function $Q(s,a)$; policy search, that the agent learns a policy $\\pi(s)$ maps directly from states to actions.\n",
        "\n",
        "\n",
        "\n",
        "  \"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "The agent tries to learn the utility function $U^{\\pi}(s)$.  It is similar to the policy evalution step of the policy iteration algorithm.  The difference is that the agent in passive learning does not know the transition model and the reward function.  \n",
        "\n",
        "Direct utility estimation is based on the idea that the utility of a state is defined as the expected total reward from that state onward, and that each trial provides a sample of the is quantity for each state visited.  Howver, it ignores the connections between states and misses opportunities for learning.  It often converges slowly.\n",
        "\n",
        "Adaptive dynamic programming (ADP) takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding MDP.  For a passive learning agent, this means plugging the learned trasition model and the obsearved rewards into the Bellman equation for the utility with a fixed policy.\n",
        "\n",
        "Temporal-difference learning:  solving the underlying MDP is not the only way to bring the Bellman equations to help the learning problem.  Another way is to use the observed transitions to adjust the utilites of the observed states so that they agree with the constraint equations. \n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "An active learning agent decides what actions to take compared to a passive learning agent with a fixed policy that determins its behavior.  \n",
        "\n",
        "The tradeoff between exploitation of the current best action to maximize short-term reward and exploration of previously unknown states to gain information that can lead to a change in policy and possibly better reward in the future.\n",
        "\n",
        "GLIE - greedy in the limit of infinite exploration.  A GLIE scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed.  \n",
        "\n",
        "TD Q-learning avoids the need for a model by learingin an action-utility function $Q(s,a)$ instead of a utility function $U(s)$.  \n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\" function approximation.  the process of constructing a compact approximation of the true (utility) function (or Q-function).  For example, approximate the utility funciton using a weighted linear combination of features $f_1,...,f_n$.\n",
        "\n",
        "Function approximation makes it practical to represent utility (or Q) functions for very large state spaces since a RL algorithm can learn 20 values of parameters that make a good approximation to the true utility (or Q) function instead of learning $10^{20}$ state values.\n",
        " \"\"\"\n",
        "chapter22_5 =  \"\"\" Policy search finds a value of $\\theta$ that results in good performance.  It is very different from Q-learning, which finds a value of $\\theta$ such that $\\hat Q_{\\theta}$ is \"close\" to $Q^*$, the optimal Q-function.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Solving MDPs is offline planning. Reinforcement learning is an MDP that one can not solve it with computation but act to figure it out.\n",
        "\n",
        "MDP with a set of states $s\\in S$, a set of actions A per state, a model T(s,a,s'), a reward function R(s,a,s'). Looking for policy $\\pi(s)$.\n",
        "In reinforcement learning, T and R are unknown ahead of actions.\n",
        "\n",
        "Model-based learning: learn an approximate model based trials, then solve for values as if the learned model is correct. During learning, count outcomes s' for each (s,a), normalize to have an estimate of $\\hat T(s,a,s')$.\n",
        "Discover each $\\hat R(s,a,s')$.  Then solve the learned MDP via value iteration.\n",
        "\n",
        "Model free learning: passive reinforcement learning.  Policy evaluation with input of a fixed policy and learn the state values.\n",
        "-Direct evaluation: act according to $\\pi$, record the sum of discounted rewards turned out to be, average the samples. Pros: easy, requries no knowledge of T and R, eventually computes the correct average values. Cons: wastes information about state connections, each state must be learned separately, takes long time to learn.\n",
        "\n",
        "We need to know $T(s,\\pi(s),s')$ and $R(s, \\pi(s), s')$ to use policy evaluation. $V_{k+1}^{\\pi}(s)$ $\\leftarrow$ $\\sum_{s'}$ $T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V_k^{\\pi}(s')])$.\n",
        "\n",
        "Temporal difference learning: fixed policy $\\pi$.  sample = $R(s,\\pi(s),s')+\\gamma V_k^{\\pi}(s')$, update to V(s): $V^{\\pi}(s)$ $\\leftarrow$ (1-alpha) $V^{\\pi}(s)$ + alpha $\\cdot$ sample; rewrite: $V^{\\pi}(s)$ $\\leftarrow$ $V^{\\pi}(s)$ + alpha(sample - $V^{\\pi}(s)$). \n",
        "\n",
        "Exponential moving average.  The running interpolation update is $\\hat V_n$ = $(1-\\\\alpha)\\hat V_{n-1}$ + $\\\\alpha \\cdot V_n$.  \n",
        "\n",
        "$$ \\hat V_n = \\\\frac{V_n + (1-\\\\alpha)V_{n-1} +(1-\\\\alpha)^2 V_{n-2} + ...}{1+(1-\\\\alpha)+(1-\\\\alpha)^2 + ...} $$  Hence, the weights of past observation goes down quickly.  Decreasing learning rate (alpha) can give converging averages.\n",
        "\n",
        "TD(temporal difference) value learning is a model-free way to do policy evaluation, minicking Bellman updates by running sample averages..  However, we can use the evaluation to choose a (new) policy.  For that, we need Q-values. $\\pi(s)$ = argmax$_a$ Q(s,a), Q(s,a) = $\\sum_{s'} T(s,a,s') [R(s,a,s')+ \\gamma V(s')]$.\n",
        "\n",
        "Q-values are more useful, hence, instead of value iteration, compute Q-values:  \n",
        "$$ Q_{k+1} (s,a) \\leftarrow \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma max_{a'}Q_k(s',a')] $$)\n",
        "\n",
        "Q-learning: after receiving a sample (s,a,s'r), consider old estimate Q(s,a) with new sample estimate:  $ sample = R(s,a,s') + \\gamma max_{a'} Q(s', a') $, and incorporate the new estimate into a running average:  $Q(s,a) \\leftarrow (1-\\\\alpha) Q(s,a) + \\\\alpha \\cdot sample $\n",
        "\n",
        "Q-learning converges to optimal policy even though the agent acts suboptimally (off-policy learning).  However, the agent needs to explore enough, eventually make the learning rae small enough, but not decrease it too quickly, basically, in the limit, it doesn't matter how agent selects actions.\n",
        "\n",
        "Method to force exploration: \n",
        "\n",
        "1)random actions: with samll probability to act randomly, and with large probability to act on current policy.\n",
        "\n",
        "2)exploration functions: takes a value estimate u and a visit count n, and returns an optimistic utility $f(u,n) = u + k/n$.  update Q-value as : $ Q(s,a) \\leftarrow \\\\alpha R(s,a,s')+\\gamma max_{a'}f(Q(s',a'),n(s',a'))\n",
        "\n",
        "Approximate Q-learning.  \n",
        "\n",
        "Generalizing across states.  Basic Q-learning keeps a table of all q-values, which is not practical in realistic situations.  There are too many states to visit in training and too big a tale to store in memory.  Instea, we generalize the experience from learning about some small number of training states to new, similar situations.\n",
        "\n",
        "Using feature representation, for any state:  $Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a)+...+w_nf_n(s,a)$.\n",
        "\n",
        "Q-learning with linear Q-functions: adjust weights of active fatures.  receiving transition = (s,a,r,s'),  $difference =[r+\\gamma max_{a'} Q(s',a')] - Q(s,a) $,  $Q(s,a) \\leftarrow Q(s,a) + \\\\alpha \\cdot differnce $ and $w_i \\leftarrow w_i + \\\\alpha \\cdot difference$ .\n",
        "\n",
        "Rgret is a measure of the total mistake cost: the difference between expected rewards and optimal (expected) rewards. \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Exploration\": \"try unkown actions to get information\",\n",
        "\"Exploitation\" : \"use what the agent has learned to act\",\n",
        "\"Regret\": \"mistake agent makes\",\n",
        "\"Sampling\": \"Due to chance, need to try things repeatedly\",\n",
        "\"Difficulty\": \"learning can be much harder than solving a know MDP\"\n",
        "}"
      ],
      "execution_count": 118,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "3cc6fe5f-3a3b-4526-f57c-411a31dc9a28"
      },
      "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": 119,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n In Reinforcement learning (RL), agent interacts with the world and receives rewards, or reinforcement in the terminology of psychology. \n\nRL differs from solving an MDP as the agent is not given an MDP problem to solve.  Instead, the agent has to act in order to learn since the transition model and the reward function are not given.\n\nSparse rewards.  In chess or racing, the agent is given no informative reward signal in the vast majority of states.  Intermediate rewards make learning much easier.\n\nModel-based RL: agent uses a transition model which may be unkown initially.  Model-based RL usually learn a utility function (in addition to learing the transition model if it is unknown).\n\nModel-free RL:  agent learns a more direct representation of how to act, and it neither knows nor learns a transition model.  There are two varieties: Action-utility learning, of which the most common is Q-learning where the agent learns a Q-function $Q(s,a)$; policy search, that the agent learns a policy $\\pi(s)$ maps directly from states to actions.\n\n\n\n  \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nThe agent tries to learn the utility function $U^{\\pi}(s)$.  It is similar to the policy evalution step of the policy iteration algorithm.  The difference is that the agent in passive learning does not know the transition model and the reward function.  \n\nDirect utility estimation is based on the idea that the utility of a state is defined as the expected total reward from that state onward, and that each trial provides a sample of the is quantity for each state visited.  Howver, it ignores the connections between states and misses opportunities for learning.  It often converges slowly.\n\nAdaptive dynamic programming (ADP) takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding MDP.  For a passive learning agent, this means plugging the learned trasition model and the obsearved rewards into the Bellman equation for the utility with a fixed policy.\n\nTemporal-difference learning:  solving the underlying MDP is not the only way to bring the Bellman equations to help the learning problem.  Another way is to use the observed transitions to adjust the utilites of the observed states so that they agree with the constraint equations. \n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nAn active learning agent decides what actions to take compared to a passive learning agent with a fixed policy that determins its behavior.  \n\nThe tradeoff between exploitation of the current best action to maximize short-term reward and exploration of previously unknown states to gain information that can lead to a change in policy and possibly better reward in the future.\n\nGLIE - greedy in the limit of infinite exploration.  A GLIE scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed.  \n\nTD Q-learning avoids the need for a model by learingin an action-utility function $Q(s,a)$ instead of a utility function $U(s)$.  \n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n function approximation.  the process of constructing a compact approximation of the true (utility) function (or Q-function).  For example, approximate the utility funciton using a weighted linear combination of features $f_1,...,f_n$.\n\nFunction approximation makes it practical to represent utility (or Q) functions for very large state spaces since a RL algorithm can learn 20 values of parameters that make a good approximation to the true utility (or Q) function instead of learning $10^{20}$ state values.\n \n\n## Module 9 Lecture Notes\n Solving MDPs is offline planning. Reinforcement learning is an MDP that one can not solve it with computation but act to figure it out.\n\nMDP with a set of states $s\\in S$, a set of actions A per state, a model T(s,a,s'), a reward function R(s,a,s'). Looking for policy $\\pi(s)$.\nIn reinforcement learning, T and R are unknown ahead of actions.\n\nModel-based learning: learn an approximate model based trials, then solve for values as if the learned model is correct. During learning, count outcomes s' for each (s,a), normalize to have an estimate of $\\hat T(s,a,s')$.\nDiscover each $\\hat R(s,a,s')$.  Then solve the learned MDP via value iteration.\n\nModel free learning: passive reinforcement learning.  Policy evaluation with input of a fixed policy and learn the state values.\n-Direct evaluation: act according to $\\pi$, record the sum of discounted rewards turned out to be, average the samples. Pros: easy, requries no knowledge of T and R, eventually computes the correct average values. Cons: wastes information about state connections, each state must be learned separately, takes long time to learn.\n\nWe need to know $T(s,\\pi(s),s')$ and $R(s, \\pi(s), s')$ to use policy evaluation. $V_{k+1}^{\\pi}(s)$ $\\leftarrow$ $\\sum_{s'}$ $T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V_k^{\\pi}(s')])$.\n\nTemporal difference learning: fixed policy $\\pi$.  sample = $R(s,\\pi(s),s')+\\gamma V_k^{\\pi}(s')$, update to V(s): $V^{\\pi}(s)$ $\\leftarrow$ (1-alpha) $V^{\\pi}(s)$ + alpha $\\cdot$ sample; rewrite: $V^{\\pi}(s)$ $\\leftarrow$ $V^{\\pi}(s)$ + alpha(sample - $V^{\\pi}(s)$). \n\nExponential moving average.  The running interpolation update is $\\hat V_n$ = $(1-\\alpha)\\hat V_{n-1}$ + $\\alpha \\cdot V_n$.  \n\n$$ \\hat V_n = \\frac{V_n + (1-\\alpha)V_{n-1} +(1-\\alpha)^2 V_{n-2} + ...}{1+(1-\\alpha)+(1-\\alpha)^2 + ...} $$  Hence, the weights of past observation goes down quickly.  Decreasing learning rate (alpha) can give converging averages.\n\nTD(temporal difference) value learning is a model-free way to do policy evaluation, minicking Bellman updates by running sample averages..  However, we can use the evaluation to choose a (new) policy.  For that, we need Q-values. $\\pi(s)$ = argmax$_a$ Q(s,a), Q(s,a) = $\\sum_{s'} T(s,a,s') [R(s,a,s')+ \\gamma V(s')]$.\n\nQ-values are more useful, hence, instead of value iteration, compute Q-values:  \n$$ Q_{k+1} (s,a) \\leftarrow \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma max_{a'}Q_k(s',a')] $$)\n\nQ-learning: after receiving a sample (s,a,s'r), consider old estimate Q(s,a) with new sample estimate:  $ sample = R(s,a,s') + \\gamma max_{a'} Q(s', a') $, and incorporate the new estimate into a running average:  $Q(s,a) \\leftarrow (1-\\alpha) Q(s,a) + \\alpha \\cdot sample $\n\nQ-learning converges to optimal policy even though the agent acts suboptimally (off-policy learning).  However, the agent needs to explore enough, eventually make the learning rae small enough, but not decrease it too quickly, basically, in the limit, it doesn't matter how agent selects actions.\n\nMethod to force exploration: \n\n1)random actions: with samll probability to act randomly, and with large probability to act on current policy.\n\n2)exploration functions: takes a value estimate u and a visit count n, and returns an optimistic utility $f(u,n) = u + k/n$.  update Q-value as : $ Q(s,a) \\leftarrow \\alpha R(s,a,s')+\\gamma max_{a'}f(Q(s',a'),n(s',a'))\n\nApproximate Q-learning.  \n\nGeneralizing across states.  Basic Q-learning keeps a table of all q-values, which is not practical in realistic situations.  There are too many states to visit in training and too big a tale to store in memory.  Instea, we generalize the experience from learning about some small number of training states to new, similar situations.\n\nUsing feature representation, for any state:  $Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a)+...+w_nf_n(s,a)$.\n\nQ-learning with linear Q-functions: adjust weights of active fatures.  receiving transition = (s,a,r,s'),  $difference =[r+\\gamma max_{a'} Q(s',a')] - Q(s,a) $,  $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\cdot differnce $ and $w_i \\leftarrow w_i + \\alpha \\cdot difference$ .\n\nRgret is a measure of the total mistake cost: the difference between expected rewards and optimal (expected) rewards. \n\n## Module 9 Definitions\n* **Exploration** - try unkown actions to get information\n* **Exploitation** - use what the agent has learned to act\n* **Regret** - mistake agent makes\n* **Sampling** - Due to chance, need to try things repeatedly\n* **Difficulty** - learning can be much harder than solving a know MDP\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Probability inference: calculate a desired probability from other know probabilities.\n",
        "\n",
        "Product Rule:  $P(y)P(x|y) = P(x,y)$\n",
        "\n",
        "Chain Rule:  $P(x_1,x_2,...,x_n) = \\prod_i P(x_i|x_1...x_{i-1})$ \n",
        "\n",
        "Bayes rule:  $ P(x|y) = \\\\frac{P(y|x)}{P(y)} P(x)$\n",
        "\n",
        "Probabilistic Language modeling:  assign the probability of a sentence or sequence of words.\n",
        "$P(W) =P(w_1,w_2,...,w_n)$ or related task $P(w_5|w_1,w_2,w_3,w_4)$.\n",
        "\n",
        "How to estimate these probabilities:  Maximum likelihood estimate (MLE)  $P(w_3|w_1,w_2) = \\\\frac{count(w_1, w_2, w_3)}{count(w_1,w_2)}$ \n",
        "\n",
        "Markov assumption: the probability of a word only depends on the previous k words, not the whole context. n-gram, unigram using no history, bigram using previous 1 word as history, trigram using last 2 words as history.\n",
        "\n",
        "Bigram:  $P(w_i|w_1w_2...w_{i-1}) \\\\approx P(w_i|w_{i-1})$\n",
        "\n",
        "In general n-gram model is an insufficient model of language because language has long-distance dependencies.\n",
        "\n",
        "Problems for MLE, out of vocabulary items (words never encountered in training have 0 probability).\n",
        "\n",
        "Pracical issue: compute in log space to avoid underflow (also adding is faster than multiplying)  $\\log(p_1\\cdot p_2\\cdot...\\cdot p_n) = \\log p_1 + \\log p_2 +...+\\log p_n $\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 120,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "de14138e-8f00-4621-ffd4-70eac9dd093e"
      },
      "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": 121,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Probability inference: calculate a desired probability from other know probabilities.\n\nProduct Rule:  $P(y)P(x|y) = P(x,y)$\n\nChain Rule:  $P(x_1,x_2,...,x_n) = \\prod_i P(x_i|x_1...x_{i-1})$ \n\nBayes rule:  $ P(x|y) = \\frac{P(y|x)}{P(y)} P(x)$\n\nProbabilistic Language modeling:  assign the probability of a sentence or sequence of words.\n$P(W) =P(w_1,w_2,...,w_n)$ or related task $P(w_5|w_1,w_2,w_3,w_4)$.\n\nHow to estimate these probabilities:  Maximum likelihood estimate (MLE)  $P(w_3|w_1,w_2) = \\frac{count(w_1, w_2, w_3)}{count(w_1,w_2)}$ \n\nMarkov assumption: the probability of a word only depends on the previous k words, not the whole context. n-gram, unigram using no history, bigram using previous 1 word as history, trigram using last 2 words as history.\n\nBigram:  $P(w_i|w_1w_2...w_{i-1}) \\approx P(w_i|w_{i-1})$\n\nIn general n-gram model is an insufficient model of language because language has long-distance dependencies.\n\nProblems for MLE, out of vocabulary items (words never encountered in training have 0 probability).\n\nPracical issue: compute in log space to avoid underflow (also adding is faster than multiplying)  $\\log(p_1\\cdot p_2\\cdot...\\cdot p_n) = \\log p_1 + \\log p_2 +...+\\log p_n $\n\n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"Full joint probability distribution can answer any question about the domain, but can become too large to tract.  \n",
        "Indenpendence and conditional indenpendence relationship among variables can greatly reduce the number of probabilities required to define the full joint distribution. Intuitively, a directed edge from X to Y means X has a direct influence on Y.\n",
        "\n",
        "Bayesian network is a data structure represent the dependencies among variables.\n",
        "A DAG (no directed cycles) that: \n",
        "\n",
        "a.  each node corresponds to a random variable (discrete or coninuous); \n",
        "b. directed edge connecting paris of nodes, where an edge coming from the parent node X to the child node Y;  \n",
        "c. each node has associated probability information $\\Theta(X_i|Parents(X_i))$ that quantifies the effects of parents on the node by a finite number of parameters. \n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"The semantics of Bayesian network (Bayes net) defines each entry in the joint probability distribution as:\\ \n",
        "$P(X_1=x_1\\wedge...\\wedge X_n=x_n) =P(x_1,...,x_n)= \\prod_{i=1}^n \\Theta (x_i|parents(X_i))$ \n",
        "where $parents(X_i)$ are values of $parents(X_i)$ appearing in $x_1,...,x_n$\n",
        "\n",
        "It can prove that $P(x_i|parents(X_i)) = \\Theta (x_i|parents(X_i))$, $P(x_1,...,x_n)= \\prod_{i=1}^n P(x_i|parents(X_i))$\n",
        "\n",
        "Chain rule: $P(x_1,...,x_n) = P(x_n|x_{n-1},...,x_1)P(x_{n-1},...,x_1)) = \\prod_{i=1}^n P(x_i|x_{i-1},...,x_1)$.\n",
        "\n",
        "$P(x_i|x_{i-1},...,x_1)= P(x_i|parents(X_i))$ provided that $parents(X_i) \\subset\\{x_{i-1},...,x_1\\}$\n",
        "\n",
        "This last condition is satisfied by numbering the nodes in topological order (any order consistent with the directed graph sturecture).\n",
        "\n",
        "The equation says Bayesian network is a correct representation of the domain only if each node is conditionally independent from its other predecessors in the node ordering, given its parents.\n",
        "\n",
        "\n",
        "In a locally structured (sparse) system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components.  Usually associated wtih linear rather than exponential growth in complexity.\n",
        "The compactness of Bayesian network is an example of a general property of locally structured systems.\n",
        "\n",
        "It is reasonable to assume that in most domains each random variable is directly influenced by at most k others in a Bayes net.  To specify each conditional probability table will be at most $2^k$ numbers, if there are $n$ boolean variables.\n",
        "\n",
        "The complete network needs $2^k\\cdot n$ in contrast to the $2^n$ numbers required for the joint distribution. \n",
        "\n",
        "Even in locally structured domain, we can get a compact Bayes net only if choosing the nodes ordering well.  Using causal model, we typically end up with fewer numbers(conditional prob) to assign and the numbers tend to be easier to come up with.\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" The basic task of any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event - some assignment of values to a set of evident variables.\n",
        "\n",
        "Every variable that is not an ancestor of a query variable or evidence variable is irrelevant to the query.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" X and Y are independent if $\\forall x, y P(x,y) = P(x)P(y)$\n",
        "\n",
        "Conditionally independent:  X and Y are conditionally indenpendent given Z if : $\\forall x, y, z  P(x,y|z) = P(x|z)P(y|z)$  iif $\\forall x,y,z: P(x|z, y) = P(x|z)$\n",
        "\n",
        "Bayes net assumption:  $P(x_i|x_1...x_{i-1}) = P(x_i|parents(X_i))$\n",
        "\n",
        "\"common cause\": $P(x,y,z) = P(y)P(x|y)P(z|y)$ (common cause is Y).  X and Z are not indenpendent, but are independent given Y.\n",
        "\n",
        "\"common effect\" (v-structures): X and Y each can cause Z.  X and Y are independent, but are not indenpendent given Z.\n",
        "\n",
        "Analyzing if two variables are independent in a BN.  To answer if X and Y are conditionally independent given evidence variable Z, check if X and Y are \"d-separated\" by Z.  If there is no active path from X to Y after considering all (undirected) paths from X to Y, then they are conditionally independent.\n",
        "\n",
        "A path is active if each triple is active: 1) causal chain $A\\\\rightarrow B\\\\rightarrow C$ where B is unobserved\n",
        "2) common cause $A\\leftarrow B \\\\rightarrow C$ where B is unobserved;  3) common effect(v structure) $A \\\\rightarrow B \\leftarrow C$ where B or one of its descendents is observed.  (opposite to causal chain adn common cause)\n",
        "\n",
        "A single inactive segment is all it takes to block a path (becoming inactive).\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Conditional Probability Table (CPT)\" : \"The local probability information associated with a node in Bayesian network. CPTs are only for discrete variables. Each row in CPT contains the conditional probability of the node value for a conditioning case.\", \n",
        "\"Conditioning case\" : \"possible combination of values for the parent nodes.\"}\n"
      ],
      "execution_count": 122,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "dba65fb1-e017-4ca2-e427-028ec76413eb"
      },
      "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": 123,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Conditional Probability Table (CPT)' is too long!\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\nFull joint probability distribution can answer any question about the domain, but can become too large to tract.  \nIndenpendence and conditional indenpendence relationship among variables can greatly reduce the number of probabilities required to define the full joint distribution. Intuitively, a directed edge from X to Y means X has a direct influence on Y.\n\nBayesian network is a data structure represent the dependencies among variables.\nA DAG (no directed cycles) that: \n\na.  each node corresponds to a random variable (discrete or coninuous); \nb. directed edge connecting paris of nodes, where an edge coming from the parent node X to the child node Y;  \nc. each node has associated probability information $\\Theta(X_i|Parents(X_i))$ that quantifies the effects of parents on the node by a finite number of parameters. \n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nThe semantics of Bayesian network (Bayes net) defines each entry in the joint probability distribution as:\\ \n$P(X_1=x_1\\wedge...\\wedge X_n=x_n) =P(x_1,...,x_n)= \\prod_{i=1}^n \\Theta (x_i|parents(X_i))$ \nwhere $parents(X_i)$ are values of $parents(X_i)$ appearing in $x_1,...,x_n$\n\nIt can prove that $P(x_i|parents(X_i)) = \\Theta (x_i|parents(X_i))$, $P(x_1,...,x_n)= \\prod_{i=1}^n P(x_i|parents(X_i))$\n\nChain rule: $P(x_1,...,x_n) = P(x_n|x_{n-1},...,x_1)P(x_{n-1},...,x_1)) = \\prod_{i=1}^n P(x_i|x_{i-1},...,x_1)$.\n\n$P(x_i|x_{i-1},...,x_1)= P(x_i|parents(X_i))$ provided that $parents(X_i) \\subset\\{x_{i-1},...,x_1\\}$\n\nThis last condition is satisfied by numbering the nodes in topological order (any order consistent with the directed graph sturecture).\n\nThe equation says Bayesian network is a correct representation of the domain only if each node is conditionally independent from its other predecessors in the node ordering, given its parents.\n\n\nIn a locally structured (sparse) system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components.  Usually associated wtih linear rather than exponential growth in complexity.\nThe compactness of Bayesian network is an example of a general property of locally structured systems.\n\nIt is reasonable to assume that in most domains each random variable is directly influenced by at most k others in a Bayes net.  To specify each conditional probability table will be at most $2^k$ numbers, if there are $n$ boolean variables.\n\nThe complete network needs $2^k\\cdot n$ in contrast to the $2^n$ numbers required for the joint distribution. \n\nEven in locally structured domain, we can get a compact Bayes net only if choosing the nodes ordering well.  Using causal model, we typically end up with fewer numbers(conditional prob) to assign and the numbers tend to be easier to come up with.\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n The basic task of any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event - some assignment of values to a set of evident variables.\n\nEvery variable that is not an ancestor of a query variable or evidence variable is irrelevant to the query.\n\n \n\n## Module 11 Lecture Notes\n X and Y are independent if $\forall x, y P(x,y) = P(x)P(y)$\n\nConditionally independent:  X and Y are conditionally indenpendent given Z if : $\forall x, y, z  P(x,y|z) = P(x|z)P(y|z)$  iif $\forall x,y,z: P(x|z, y) = P(x|z)$\n\nBayes net assumption:  $P(x_i|x_1...x_{i-1}) = P(x_i|parents(X_i))$\n\n\"common cause\": $P(x,y,z) = P(y)P(x|y)P(z|y)$ (common cause is Y).  X and Z are not indenpendent, but are independent given Y.\n\n\"common effect\" (v-structures): X and Y each can cause Z.  X and Y are independent, but are not indenpendent given Z.\n\nAnalyzing if two variables are independent in a BN.  To answer if X and Y are conditionally independent given evidence variable Z, check if X and Y are \"d-separated\" by Z.  If there is no active path from X to Y after considering all (undirected) paths from X to Y, then they are conditionally independent.\n\nA path is active if each triple is active: 1) causal chain $A\\rightarrow B\\rightarrow C$ where B is unobserved\n2) common cause $A\\leftarrow B \\rightarrow C$ where B is unobserved;  3) common effect(v structure) $A \\rightarrow B \\leftarrow C$ where B or one of its descendents is observed.  (opposite to causal chain adn common cause)\n\nA single inactive segment is all it takes to block a path (becoming inactive).\n\n\n \n\n## Module 11 Definitions\n* **Conditional probability table (cpt)** - The local probability information associated with a node in Bayesian network. CPTs are only for discrete variables. Each row in CPT contains the conditional probability of the node value for a conditioning case.\n* **Conditioning case** - possible combination of values for the parent nodes.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Machine learning: how to acquirea model from data and experience: learning parameters (such as probabilities), structure (such as BN graphs), hidden concepts (such as clustering).\n",
        "Model based classification: with Naive Bayes; with Perceptrons.\n",
        "\n",
        "Model-based classification approach: build a model where both the label and features are random variables, instantiate any observed features, query for the distribution of the label conditioned on the features.\n",
        "\n",
        "Naive Bayes assume all features are independent effects of the label.\n",
        "\n",
        "Naive Bayes for Text.  Bag-of-words: featueres, $w_i$ is the word at postion i, assume features are conditionally independent given label, predict label conditioned on feature variables, each $w_i$ is identically distributed. \n",
        "\n",
        "$P(Y, W_1...W_n) = P(Y)\\prod_i P(W_i|Y)$  insensitive to order of words since assuming identical distribution for each position.\n",
        "\n",
        "Experimentation cycle: learn parameters eg. model probabilities on training set, (tune hyperparameteres on held-out set), compute accuracy of test set.\n",
        "Issues: overfitting and generalization.  Relative frequency parameteres will overfit the training data!  Need to smooth or regularize the estimates to generalize better.\n",
        "\n",
        "Laplace's estimate: pretend the agent saw every outcome once more than the actual occurance.  $P_{LAP}(x) = \\frac{c(x)+1}{\\sum_x[c(x)+1]}  = \\frac{c(x)+1}{N+|X|]}$\n",
        "extended Laplace's estimate: $P_{LAP}(x) = \\frac{c(x)+k}{N+k|X|]} $   For conditionals:  P_{LAP, k}(x|y) = \\frac{c(x,y)+k}{c(y)+k|X|} smooth each condition independently.\n",
        "\n",
        "Another option: linear ionterpolation  $P_{LIN}(x|y) = \\\\alpha \\hat P(x|y) + (1-\\\\alpha)\\hat P(x)$.  $k, \\\\alpha$ are hyperparameters to be tuned on hold-out dataset.\n",
        "\n",
        "Perceptron, linear classifiers:  $activation_w(x) = \\sum_i w_i\\cdot f_i(x) = w\\cdot f(x) $\n",
        "\n",
        "Perceptron/MIRA makes less assumptions about data, mistaken-driven learning, multiple passes through data, and often more accurate than Naive Bayes.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 124,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "d9571132-ca9c-4d3a-ee75-b2ff2fa0a602"
      },
      "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": 125,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Machine learning: how to acquirea model from data and experience: learning parameters (such as probabilities), structure (such as BN graphs), hidden concepts (such as clustering).\nModel based classification: with Naive Bayes; with Perceptrons.\n\nModel-based classification approach: build a model where both the label and features are random variables, instantiate any observed features, query for the distribution of the label conditioned on the features.\n\nNaive Bayes assume all features are independent effects of the label.\n\nNaive Bayes for Text.  Bag-of-words: featueres, $w_i$ is the word at postion i, assume features are conditionally independent given label, predict label conditioned on feature variables, each $w_i$ is identically distributed. \n\n$P(Y, W_1...W_n) = P(Y)\\prod_i P(W_i|Y)$  insensitive to order of words since assuming identical distribution for each position.\n\nExperimentation cycle: learn parameters eg. model probabilities on training set, (tune hyperparameteres on held-out set), compute accuracy of test set.\nIssues: overfitting and generalization.  Relative frequency parameteres will overfit the training data!  Need to smooth or regularize the estimates to generalize better.\n\nLaplace's estimate: pretend the agent saw every outcome once more than the actual occurance.  $P_{LAP}(x) = \frac{c(x)+1}{\\sum_x[c(x)+1]}  = \frac{c(x)+1}{N+|X|]}$\nextended Laplace's estimate: $P_{LAP}(x) = \frac{c(x)+k}{N+k|X|]} $   For conditionals:  P_{LAP, k}(x|y) = \frac{c(x,y)+k}{c(y)+k|X|} smooth each condition independently.\n\nAnother option: linear ionterpolation  $P_{LIN}(x|y) = \\alpha \\hat P(x|y) + (1-\\alpha)\\hat P(x)$.  $k, \\alpha$ are hyperparameters to be tuned on hold-out dataset.\n\nPerceptron, linear classifiers:  $activation_w(x) = \\sum_i w_i\\cdot f_i(x) = w\\cdot f(x) $\n\nPerceptron/MIRA makes less assumptions about data, mistaken-driven learning, multiple passes through data, and often more accurate than Naive Bayes.\n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Logistic Regression uses a vector of weights and a bias term:  $z = \\sum_i w_i x_i +b = w\\cdot x +b $\n",
        "\n",
        "Activation functions: instead of directly output z=wx+b, which is a linear function of x, neuron units appply a non-linear function f to z.  Commonly used activation functions include Sigmoid, tanh, rectified linear unit(ReLU).\n",
        "\n",
        "Feed-Foward Neural Network is the simplest kind of NN, which is a multilayer network with all units usually fully-connected and no cycles.  The outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers.\n",
        "\n",
        "Training NN: cross-entropy loss as a loss function, gradient descent as an optimization algorithm, erro propagation as a way of computing the gradient of the loss function.\n",
        "\n",
        "Cross-entropy loss:  $L_{CE}(\\hat y, y) = -log p(y|x) = -[y\\log\\hat y + (1-y)\\log(1-\\hat y)]$\n",
        "\n",
        "for multnomial classification $L_{CE}(\\hat y, y) = - \\sum_{i=1}^C y_i \\log\\hat y_i$.\n",
        "\n",
        "If there is only one correct answer, where the truth is $y_i=1$, then the formula simplifies to:  $L_{CE}(\\hat y, y) = - \\log\\hat y_i$, and in softmax:   $L_{CE}(\\hat y, y)$ = - $\\log (e^{Z_i}/\\sum_{j=1}^K e^{Z_j})$\n",
        "\n",
        "Backpropagation was invente for NN, and it is related to general procedure called backward differentiation, which depends on the notion of computation graphs.\n",
        "\n",
        "Regularization is a way to penalize large weights.  A regularization term is added to the loss function.  Lasso regression uses L1 regularization, Ridge regression uses L2.\n",
        "\n",
        "For multinomial logistic regression, use a generalization of the sigmoid function - softmax function, which takes in an input vector $Z=Z_1,Z_2,...,Z_n$ and output a vector of values normalized into probabilities.\n",
        "\n",
        "$$ softmax(z) = [e^{z_1}/\\sum_{i=1}^k e^{z_i}, e^{z_2}/\\sum_{i=1}^k e^{z_i}, ...]$$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 126,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "cellView": "form",
        "outputId": "a41d3ec0-48dc-4c2c-e1f2-df2c6d666136"
      },
      "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": 127,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Logistic Regression uses a vector of weights and a bias term:  $z = \\sum_i w_i x_i +b = w\\cdot x +b $\n\nActivation functions: instead of directly output z=wx+b, which is a linear function of x, neuron units appply a non-linear function f to z.  Commonly used activation functions include Sigmoid, tanh, rectified linear unit(ReLU).\n\nFeed-Foward Neural Network is the simplest kind of NN, which is a multilayer network with all units usually fully-connected and no cycles.  The outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers.\n\nTraining NN: cross-entropy loss as a loss function, gradient descent as an optimization algorithm, erro propagation as a way of computing the gradient of the loss function.\n\nCross-entropy loss:  $L_{CE}(\\hat y, y) = -log p(y|x) = -[y\\log\\hat y + (1-y)\\log(1-\\hat y)]$\n\nfor multnomial classification $L_{CE}(\\hat y, y) = - \\sum_{i=1}^C y_i \\log\\hat y_i$.\n\nIf there is only one correct answer, where the truth is $y_i=1$, then the formula simplifies to:  $L_{CE}(\\hat y, y) = - \\log\\hat y_i$, and in softmax:   $L_{CE}(\\hat y, y)$ = - $\\log (e^{Z_i}/\\sum_{j=1}^K e^{Z_j})$\n\nBackpropagation was invente for NN, and it is related to general procedure called backward differentiation, which depends on the notion of computation graphs.\n\nRegularization is a way to penalize large weights.  A regularization term is added to the loss function.  Lasso regression uses L1 regularization, Ridge regression uses L2.\n\nFor multinomial logistic regression, use a generalization of the sigmoid function - softmax function, which takes in an input vector $Z=Z_1,Z_2,...,Z_n$ and output a vector of values normalized into probabilities.\n\n$$ softmax(z) = [e^{z_1}/\\sum_{i=1}^k e^{z_i}, e^{z_2}/\\sum_{i=1}^k e^{z_i}, ...]$$\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" distributional hypothesis points to the link between similarity in how words are distributed and similarity in what they mean, such that words which are synonyms tended to occur in the same environment\n",
        "\n",
        "vector semantics, which instantiates this linguistic vector semantics embeddings hypothesis by learning representations of the meaning of words, called embeddings, directly from their distributions in texts. \n",
        "\n",
        "These representations are used in every natural language processing application that makes use of meaning.\n",
        "\n",
        "the static embeddings and the more powerful dynamic or contextualized embeddings like BERT.\n",
        "\n",
        "Polysemous - multiple meanings. Each aspect of the meaings of a word is called a word sense.\n",
        "Synonymy have the same proositional meaning.  Probably no two words are absolutely identical in meaning.  That is also principle of contrast which states a difference in linguistic form is always associated wtih some difference in meaning.\n",
        "\n",
        "Word similarity - relations between words (like similarity) is more usefual than relations between word senses (like synonymy).  Knowing how similar two wrods are can help in computing how similar the meaning of two phrases or sentences are.\n",
        "\n",
        "A semantic fram is a set of words that denote perspectives or participants in a particular type of event.\n",
        "\n",
        "Positive or negative evaluation language is called sentiment.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\" \n",
        "Vectors semantics is the standard way to represent word meaning in NLP.  The idea is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of word neighbors.  \n",
        "\n",
        "Vectors for representing words are called embeddings.\n",
        "\n",
        "if-idf model defines the meaning of a word by a simple function of the counts of nearby words.  This results in very long vectors that are sparse.\n",
        "\n",
        "Word2vec model constructs short, dense vectors having useful semantic properties.\n",
        "  \"\"\"\n",
        "slp_chapter6_3 = \"\"\" In a Term-Document matrix, each row represents a word in the vocabulary and each column represents a document.  Each cell in this matrix represents the number of times a particular word occurs in a particular document.\n",
        "\n",
        "First used in vector space model. \n",
        "\n",
        "Term-document matrices were originally defined as a means to find similar documents for the task of document information retrieval (IR). \n",
        "\n",
        "Vector semantics can also be used to represent the meaning of words by associating each word with a word vector (a row vector in the matrix).  Similar words have similar vectors because they tend to occur in similar documents.\n",
        "\n",
        "Term-term matrix, or word-word matrix, or term-context matrix, in which columns are labeled by words rather than documents. Each cell represents the number of times the row (target) word and the column (contecx) word co-occur in some context in some training corpus.\n",
        "\n",
        "More commonly, using a +/-4 words window around the target word.\n",
        " \"\"\"\n",
        "slp_chapter6_4 = \"\"\" The cosine, is the dot product of two target words' vectors, giving a measure of their similarity.  It will tend to be high if the two vectors have large values in the same dimensions.\n",
        "\n",
        "Normalized dot product to remove the effect that long vector produces higher dot product value.\n",
        "\n",
        "The cosine similarity metric between two vector v and w is : $cosine(v,w) = v\\cdot w /|v||w|$\n",
        "\n",
        "inverse document frequency (idf) = $N/df_t$, N is the total number of documents in teh collection, $df_t$ is the number of documents in which term $t$ occurs.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_8 = \"\"\" embeddings are short dense vectors. number of dimensions ranges from 50 to 1000.\n",
        "\n",
        "word2vec is a software package includes skip-gram with negative sample (SGNS).  Word2vec embeddings are static embeddings, that the method learns one fixed embedding for each word in the vocabulary.\n",
        "\n",
        "Instead of counting how often each word w occurs near a word v, word2vec trains a classifier on a binary prediction taks: is the word w likely to show up near v?  Then the learned classifier weights are used as the word embeddings.\n",
        "\n",
        "This method, called self-supervison, avoids the need for any sort of hand-labeled supervision signal.\n",
        "\"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Embeddings not only reflect the statistics of the inputs, but also amplify bias. \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Idealy, a meaning representation of a word shall encode: synonyms - words that have similar meanings, antonyms - words that have opposite meanings, connotations - words that are positive or negative, semantic roles - different parts of the same underlying event, eg buy, sell, pay to the purchasing event, support entailment.\n",
        "\n",
        "skip-gram, given a tuple (target t, contect c) return probability that c is real context word.  compute p(+|t,c), dot product, then apply signoid to turn it into probability.\n",
        "\n",
        "$$P(+|t,c) = \\frac{1}{1+e^{-t\\cdot c}},  P(-|t,c) = 1- P(+|t,c)$$\n",
        "\n",
        "For all the context words, assuming independent.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 128,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "31de985b-8fbb-425d-f4bb-a61b90ed74b1"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", 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": 129,
      "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 distributional hypothesis points to the link between similarity in how words are distributed and similarity in what they mean, such that words which are synonyms tended to occur in the same environment\n\nvector semantics, which instantiates this linguistic vector semantics embeddings hypothesis by learning representations of the meaning of words, called embeddings, directly from their distributions in texts. \n\nThese representations are used in every natural language processing application that makes use of meaning.\n\nthe static embeddings and the more powerful dynamic or contextualized embeddings like BERT.\n\nPolysemous - multiple meanings. Each aspect of the meaings of a word is called a word sense.\nSynonymy have the same proositional meaning.  Probably no two words are absolutely identical in meaning.  That is also principle of contrast which states a difference in linguistic form is always associated wtih some difference in meaning.\n\nWord similarity - relations between words (like similarity) is more usefual than relations between word senses (like synonymy).  Knowing how similar two wrods are can help in computing how similar the meaning of two phrases or sentences are.\n\nA semantic fram is a set of words that denote perspectives or participants in a particular type of event.\n\nPositive or negative evaluation language is called sentiment.\n\n\n\n\n## SLP Chapter 6.2 Vector Semantics\n \nVectors semantics is the standard way to represent word meaning in NLP.  The idea is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of word neighbors.  \n\nVectors for representing words are called embeddings.\n\nif-idf model defines the meaning of a word by a simple function of the counts of nearby words.  This results in very long vectors that are sparse.\n\nWord2vec model constructs short, dense vectors having useful semantic properties.\n  \n\n## SLP Chapter 6.3 Words and Vectors\n In a Term-Document matrix, each row represents a word in the vocabulary and each column represents a document.  Each cell in this matrix represents the number of times a particular word occurs in a particular document.\n\nFirst used in vector space model. \n\nTerm-document matrices were originally defined as a means to find similar documents for the task of document information retrieval (IR). \n\nVector semantics can also be used to represent the meaning of words by associating each word with a word vector (a row vector in the matrix).  Similar words have similar vectors because they tend to occur in similar documents.\n\nTerm-term matrix, or word-word matrix, or term-context matrix, in which columns are labeled by words rather than documents. Each cell represents the number of times the row (target) word and the column (contecx) word co-occur in some context in some training corpus.\n\nMore commonly, using a +/-4 words window around the target word.\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n The cosine, is the dot product of two target words' vectors, giving a measure of their similarity.  It will tend to be high if the two vectors have large values in the same dimensions.\n\nNormalized dot product to remove the effect that long vector produces higher dot product value.\n\nThe cosine similarity metric between two vector v and w is : $cosine(v,w) = v\\cdot w /|v||w|$\n\ninverse document frequency (idf) = $N/df_t$, N is the total number of documents in teh collection, $df_t$ is the number of documents in which term $t$ occurs.\n\n \n\n## SLP Chapter 6.8 Word2vec\n embeddings are short dense vectors. number of dimensions ranges from 50 to 1000.\n\nword2vec is a software package includes skip-gram with negative sample (SGNS).  Word2vec embeddings are static embeddings, that the method learns one fixed embedding for each word in the vocabulary.\n\nInstead of counting how often each word w occurs near a word v, word2vec trains a classifier on a binary prediction taks: is the word w likely to show up near v?  Then the learned classifier weights are used as the word embeddings.\n\nThis method, called self-supervison, avoids the need for any sort of hand-labeled supervision signal.\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Embeddings not only reflect the statistics of the inputs, but also amplify bias. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n Logistic Regression uses a vector of weights and a bias term:  $z = \\sum_i w_i x_i +b = w\\cdot x +b $\n\nActivation functions: instead of directly output z=wx+b, which is a linear function of x, neuron units appply a non-linear function f to z.  Commonly used activation functions include Sigmoid, tanh, rectified linear unit(ReLU).\n\nFeed-Foward Neural Network is the simplest kind of NN, which is a multilayer network with all units usually fully-connected and no cycles.  The outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers.\n\nTraining NN: cross-entropy loss as a loss function, gradient descent as an optimization algorithm, erro propagation as a way of computing the gradient of the loss function.\n\nCross-entropy loss:  $L_{CE}(\\hat y, y) = -log p(y|x) = -[y\\log\\hat y + (1-y)\\log(1-\\hat y)]$\n\nfor multnomial classification $L_{CE}(\\hat y, y) = - \\sum_{i=1}^C y_i \\log\\hat y_i$.\n\nIf there is only one correct answer, where the truth is $y_i=1$, then the formula simplifies to:  $L_{CE}(\\hat y, y) = - \\log\\hat y_i$, and in softmax:   $L_{CE}(\\hat y, y)$ = - $\\log (e^{Z_i}/\\sum_{j=1}^K e^{Z_j})$\n\nBackpropagation was invente for NN, and it is related to general procedure called backward differentiation, which depends on the notion of computation graphs.\n\nRegularization is a way to penalize large weights.  A regularization term is added to the loss function.  Lasso regression uses L1 regularization, Ridge regression uses L2.\n\nFor multinomial logistic regression, use a generalization of the sigmoid function - softmax function, which takes in an input vector $Z=Z_1,Z_2,...,Z_n$ and output a vector of values normalized into probabilities.\n\n$$ softmax(z) = [e^{z_1}/\\sum_{i=1}^k e^{z_i}, e^{z_2}/\\sum_{i=1}^k e^{z_i}, ...]$$\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "3b8e788f-d971-4b79-a980-22b2cafb1dee"
      },
      "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": 130,
      "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 MEU(maximum expected utility) principle says a rational agent shall choose the action that maximizes the expected utility.  It is clearly related the performance measures.  As an agent will achieve the highest possible perfermance measures if the agent acts to maximize a utility function that correctly reflects the performance measure.\n\nThe performance measures apply retrospectively, giving scores for history, while the utility function applies to the very next state, used to guide actions for each step.\n\n  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\n\n$EU(a) = \\sum_{s'} P(RESULT(a)=s')U(s') $\n\n$action = argmax_a EU(a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n six constraints: Oderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability.  Known as axioms of utility theory.\n\nThe axiom of utility theory can derive: a) Existence of Utility Function;  b) Expected Utility as the sum of the probability of each outcome times the utility of that outcome.\n\nIn a deterministic environment an agent needs only a preference ranking on states.  This is called a value function or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\n The utility of money curve: the slope of the positive part of the curve decreases, agents with such shape of curves are risk-adverse.  On the other hand, it is called risk seek for behavior prefers smaller gains vs larger losses.\n\nThe difference between EMV(expected monetary value) of a lottery and its certainty equivalent is call the insurance premium.\n\nRisk neutural is an agent havinga linear curve (Utility of monetary value curve). \n\nThe computation of true expected utility tends to be too difficult in reality.  Usually working with estimates of the true expected utility: $\\hat {EU}(a)$ rather than $EU(a)$.\nWe will assume the estimates are unbiased: $E(\\hat {EU}(a) -EU(a)) = 0.  Since we select highest utility estimate, we favor the overly optimistic estimates (even though there are as many pessimistic as optimistic estimates), that is the source of teh bias.\nThis tendency for the estimated expected utility of the best choice to be too high is called the optimizer's curse.  It crops up everywhere because of widely adopted utility-maximizing selection process. Hence, take the utility estimates at face value is a bad idea.\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Sequential decision problems are problems in which the agent's utility depends on a sequence of decisions.\n\nMarkovian transitions: the probability of reaching $s'$ from $s$ depends only a $s$ and not on the history of earlier states.\n\nMarkov decision process (MDP) is a sequential decision problem for a fully observable, stochastic environment with a Markavian transition model and additive rewards. consists of a set of states, including a initial state), a set of actions for each state, a transition model $P(s'|s,a)$ and a reward function $R(s,a,s')$.\n\nA solution can not be a fixed action sequence because the agent may end up in a state other than the goal state.  Hence, a solution must specify the agent's action for any state that the agent might reach.  Such solution is called a policy.\n\nWhen time horizon is infinite, there is no reason to behave differently in the same state at different times.  An optimal action depends on ly on the current state and the optimal polity is stationary.  But in a finite horizon, an optimal action in a given state may depend on how much time is left.  Hence, the policy is nonstationary.\n\nOptimal policy is independent of the starting state, in  infinite horizon.\n\nBellman equation: $$ U(s) = max_{a \\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma U(s')]$$  ($T(s,a,s') is another format for P(s'|s,a)$)\n\nAction utility function or Q-function: Q(s,a) is the expected utility of taking a given action in a given state.  Hence, $U(s) = max_a Q(s, a)$  and the optimal policy can be extracted from teh Q-function as:  $\\pi^*(s) = argmax_a Q(s, a)$\n\nBellman equation for Q-function: $$ Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s') + \\gamma U(s')] = \\sum_{s'} P(s'|s,a)[R(s,a,s') +\\gamma max_{a'}Q(s',a')] $$\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n The Bellman equation for utility of a state above is the basis of the Value Iteration.  Bellman update : $U_{i+1}(s) \\leftarrow max_{a\\inA(s)} \\sum_{s'} P(s'|a,s)[R(s,a,s')+ \\gamma U_i(s')]$\n\nIterative approach is because the max operator is not linear.  Staring with arbitrary initial values for the utilities, updating the utility of each state from the utilities of its neighbors by computing the right hand side of the equation and plug ging it into the left-hand side.  Repeat until reaching equilibrium.\n\nPolicy iteration includes two steps: 1) policy evaluation, calculate the utility of each state if the given policy $\\pi_i$ is execued . $U_i = U^{\\pi_i}$.  2) policy improvement, compute a new MEU policy $\\pi_{i+1}$, using one-step look-ahead based on $U_i$.\n\nThe implementation of policy iteration is simpler than value iteration because teh action in each state is fixed by the policy.  \n\nValue iteration and policy iteration are offline algorithm that generate an optimal solution for the problem, which can be executed by an agent.  For large problem, this is impossible.  Hence, online algorithms are needed.  One approach is a simplified ExpectMinMax algorithm for game trees with chance nodes.\n\n\n\n\n## Module 8 Lecture Notes\n \nValue iteration runtime is $O(S^2 A)$ per iteration, slow among all algorithm. Policy converges way earlier than values converge.\n\n\n## Module 8 Definitions\n* **Utility function** - a function to capture the agent's preference by assigns a single number to express the desirability of a state\n* **Expected utility** - the average utility value of the outcomes of an action, weighted by the probability of the outcomes\n* **Maximum expected utility (meu)** -  a rational agent should choose the action that maximizes the agent's expectd utility.\n* **Proper policy** - a policy that is guaranteed to reach a terminal state.\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n In Reinforcement learning (RL), agent interacts with the world and receives rewards, or reinforcement in the terminology of psychology. \n\nRL differs from solving an MDP as the agent is not given an MDP problem to solve.  Instead, the agent has to act in order to learn since the transition model and the reward function are not given.\n\nSparse rewards.  In chess or racing, the agent is given no informative reward signal in the vast majority of states.  Intermediate rewards make learning much easier.\n\nModel-based RL: agent uses a transition model which may be unkown initially.  Model-based RL usually learn a utility function (in addition to learing the transition model if it is unknown).\n\nModel-free RL:  agent learns a more direct representation of how to act, and it neither knows nor learns a transition model.  There are two varieties: Action-utility learning, of which the most common is Q-learning where the agent learns a Q-function $Q(s,a)$; policy search, that the agent learns a policy $\\pi(s)$ maps directly from states to actions.\n\n\n\n  \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nThe agent tries to learn the utility function $U^{\\pi}(s)$.  It is similar to the policy evalution step of the policy iteration algorithm.  The difference is that the agent in passive learning does not know the transition model and the reward function.  \n\nDirect utility estimation is based on the idea that the utility of a state is defined as the expected total reward from that state onward, and that each trial provides a sample of the is quantity for each state visited.  Howver, it ignores the connections between states and misses opportunities for learning.  It often converges slowly.\n\nAdaptive dynamic programming (ADP) takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding MDP.  For a passive learning agent, this means plugging the learned trasition model and the obsearved rewards into the Bellman equation for the utility with a fixed policy.\n\nTemporal-difference learning:  solving the underlying MDP is not the only way to bring the Bellman equations to help the learning problem.  Another way is to use the observed transitions to adjust the utilites of the observed states so that they agree with the constraint equations. \n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nAn active learning agent decides what actions to take compared to a passive learning agent with a fixed policy that determins its behavior.  \n\nThe tradeoff between exploitation of the current best action to maximize short-term reward and exploration of previously unknown states to gain information that can lead to a change in policy and possibly better reward in the future.\n\nGLIE - greedy in the limit of infinite exploration.  A GLIE scheme must try each action in each state an unbounded number of times to avoid having a finite probability that an optimal action is missed.  \n\nTD Q-learning avoids the need for a model by learingin an action-utility function $Q(s,a)$ instead of a utility function $U(s)$.  \n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n function approximation.  the process of constructing a compact approximation of the true (utility) function (or Q-function).  For example, approximate the utility funciton using a weighted linear combination of features $f_1,...,f_n$.\n\nFunction approximation makes it practical to represent utility (or Q) functions for very large state spaces since a RL algorithm can learn 20 values of parameters that make a good approximation to the true utility (or Q) function instead of learning $10^{20}$ state values.\n \n\n## Module 9 Lecture Notes\n Solving MDPs is offline planning. Reinforcement learning is an MDP that one can not solve it with computation but act to figure it out.\n\nMDP with a set of states $s\\in S$, a set of actions A per state, a model T(s,a,s'), a reward function R(s,a,s'). Looking for policy $\\pi(s)$.\nIn reinforcement learning, T and R are unknown ahead of actions.\n\nModel-based learning: learn an approximate model based trials, then solve for values as if the learned model is correct. During learning, count outcomes s' for each (s,a), normalize to have an estimate of $\\hat T(s,a,s')$.\nDiscover each $\\hat R(s,a,s')$.  Then solve the learned MDP via value iteration.\n\nModel free learning: passive reinforcement learning.  Policy evaluation with input of a fixed policy and learn the state values.\n-Direct evaluation: act according to $\\pi$, record the sum of discounted rewards turned out to be, average the samples. Pros: easy, requries no knowledge of T and R, eventually computes the correct average values. Cons: wastes information about state connections, each state must be learned separately, takes long time to learn.\n\nWe need to know $T(s,\\pi(s),s')$ and $R(s, \\pi(s), s')$ to use policy evaluation. $V_{k+1}^{\\pi}(s)$ $\\leftarrow$ $\\sum_{s'}$ $T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V_k^{\\pi}(s')])$.\n\nTemporal difference learning: fixed policy $\\pi$.  sample = $R(s,\\pi(s),s')+\\gamma V_k^{\\pi}(s')$, update to V(s): $V^{\\pi}(s)$ $\\leftarrow$ (1-alpha) $V^{\\pi}(s)$ + alpha $\\cdot$ sample; rewrite: $V^{\\pi}(s)$ $\\leftarrow$ $V^{\\pi}(s)$ + alpha(sample - $V^{\\pi}(s)$). \n\nExponential moving average.  The running interpolation update is $\\hat V_n$ = $(1-\\alpha)\\hat V_{n-1}$ + $\\alpha \\cdot V_n$.  \n\n$$ \\hat V_n = \\frac{V_n + (1-\\alpha)V_{n-1} +(1-\\alpha)^2 V_{n-2} + ...}{1+(1-\\alpha)+(1-\\alpha)^2 + ...} $$  Hence, the weights of past observation goes down quickly.  Decreasing learning rate (alpha) can give converging averages.\n\nTD(temporal difference) value learning is a model-free way to do policy evaluation, minicking Bellman updates by running sample averages..  However, we can use the evaluation to choose a (new) policy.  For that, we need Q-values. $\\pi(s)$ = argmax$_a$ Q(s,a), Q(s,a) = $\\sum_{s'} T(s,a,s') [R(s,a,s')+ \\gamma V(s')]$.\n\nQ-values are more useful, hence, instead of value iteration, compute Q-values:  \n$$ Q_{k+1} (s,a) \\leftarrow \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma max_{a'}Q_k(s',a')] $$)\n\nQ-learning: after receiving a sample (s,a,s'r), consider old estimate Q(s,a) with new sample estimate:  $ sample = R(s,a,s') + \\gamma max_{a'} Q(s', a') $, and incorporate the new estimate into a running average:  $Q(s,a) \\leftarrow (1-\\alpha) Q(s,a) + \\alpha \\cdot sample $\n\nQ-learning converges to optimal policy even though the agent acts suboptimally (off-policy learning).  However, the agent needs to explore enough, eventually make the learning rae small enough, but not decrease it too quickly, basically, in the limit, it doesn't matter how agent selects actions.\n\nMethod to force exploration: \n\n1)random actions: with samll probability to act randomly, and with large probability to act on current policy.\n\n2)exploration functions: takes a value estimate u and a visit count n, and returns an optimistic utility $f(u,n) = u + k/n$.  update Q-value as : $ Q(s,a) \\leftarrow \\alpha R(s,a,s')+\\gamma max_{a'}f(Q(s',a'),n(s',a'))\n\nApproximate Q-learning.  \n\nGeneralizing across states.  Basic Q-learning keeps a table of all q-values, which is not practical in realistic situations.  There are too many states to visit in training and too big a tale to store in memory.  Instea, we generalize the experience from learning about some small number of training states to new, similar situations.\n\nUsing feature representation, for any state:  $Q(s,a) = w_1f_1(s,a) + w_2f_2(s,a)+...+w_nf_n(s,a)$.\n\nQ-learning with linear Q-functions: adjust weights of active fatures.  receiving transition = (s,a,r,s'),  $difference =[r+\\gamma max_{a'} Q(s',a')] - Q(s,a) $,  $Q(s,a) \\leftarrow Q(s,a) + \\alpha \\cdot differnce $ and $w_i \\leftarrow w_i + \\alpha \\cdot difference$ .\n\nRgret is a measure of the total mistake cost: the difference between expected rewards and optimal (expected) rewards. \n\n## Module 9 Definitions\n* **Exploration** - try unkown actions to get information\n* **Exploitation** - use what the agent has learned to act\n* **Regret** - mistake agent makes\n* **Sampling** - Due to chance, need to try things repeatedly\n* **Difficulty** - learning can be much harder than solving a know MDP\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Probability inference: calculate a desired probability from other know probabilities.\n\nProduct Rule:  $P(y)P(x|y) = P(x,y)$\n\nChain Rule:  $P(x_1,x_2,...,x_n) = \\prod_i P(x_i|x_1...x_{i-1})$ \n\nBayes rule:  $ P(x|y) = \\frac{P(y|x)}{P(y)} P(x)$\n\nProbabilistic Language modeling:  assign the probability of a sentence or sequence of words.\n$P(W) =P(w_1,w_2,...,w_n)$ or related task $P(w_5|w_1,w_2,w_3,w_4)$.\n\nHow to estimate these probabilities:  Maximum likelihood estimate (MLE)  $P(w_3|w_1,w_2) = \\frac{count(w_1, w_2, w_3)}{count(w_1,w_2)}$ \n\nMarkov assumption: the probability of a word only depends on the previous k words, not the whole context. n-gram, unigram using no history, bigram using previous 1 word as history, trigram using last 2 words as history.\n\nBigram:  $P(w_i|w_1w_2...w_{i-1}) \\approx P(w_i|w_{i-1})$\n\nIn general n-gram model is an insufficient model of language because language has long-distance dependencies.\n\nProblems for MLE, out of vocabulary items (words never encountered in training have 0 probability).\n\nPracical issue: compute in log space to avoid underflow (also adding is faster than multiplying)  $\\log(p_1\\cdot p_2\\cdot...\\cdot p_n) = \\log p_1 + \\log p_2 +...+\\log p_n $\n\n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n## WARNING: Your definition of 'Conditional Probability Table (CPT)' is too long!\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\nFull joint probability distribution can answer any question about the domain, but can become too large to tract.  \nIndenpendence and conditional indenpendence relationship among variables can greatly reduce the number of probabilities required to define the full joint distribution. Intuitively, a directed edge from X to Y means X has a direct influence on Y.\n\nBayesian network is a data structure represent the dependencies among variables.\nA DAG (no directed cycles) that: \n\na.  each node corresponds to a random variable (discrete or coninuous); \nb. directed edge connecting paris of nodes, where an edge coming from the parent node X to the child node Y;  \nc. each node has associated probability information $\\Theta(X_i|Parents(X_i))$ that quantifies the effects of parents on the node by a finite number of parameters. \n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nThe semantics of Bayesian network (Bayes net) defines each entry in the joint probability distribution as:\\ \n$P(X_1=x_1\\wedge...\\wedge X_n=x_n) =P(x_1,...,x_n)= \\prod_{i=1}^n \\Theta (x_i|parents(X_i))$ \nwhere $parents(X_i)$ are values of $parents(X_i)$ appearing in $x_1,...,x_n$\n\nIt can prove that $P(x_i|parents(X_i)) = \\Theta (x_i|parents(X_i))$, $P(x_1,...,x_n)= \\prod_{i=1}^n P(x_i|parents(X_i))$\n\nChain rule: $P(x_1,...,x_n) = P(x_n|x_{n-1},...,x_1)P(x_{n-1},...,x_1)) = \\prod_{i=1}^n P(x_i|x_{i-1},...,x_1)$.\n\n$P(x_i|x_{i-1},...,x_1)= P(x_i|parents(X_i))$ provided that $parents(X_i) \\subset\\{x_{i-1},...,x_1\\}$\n\nThis last condition is satisfied by numbering the nodes in topological order (any order consistent with the directed graph sturecture).\n\nThe equation says Bayesian network is a correct representation of the domain only if each node is conditionally independent from its other predecessors in the node ordering, given its parents.\n\n\nIn a locally structured (sparse) system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components.  Usually associated wtih linear rather than exponential growth in complexity.\nThe compactness of Bayesian network is an example of a general property of locally structured systems.\n\nIt is reasonable to assume that in most domains each random variable is directly influenced by at most k others in a Bayes net.  To specify each conditional probability table will be at most $2^k$ numbers, if there are $n$ boolean variables.\n\nThe complete network needs $2^k\\cdot n$ in contrast to the $2^n$ numbers required for the joint distribution. \n\nEven in locally structured domain, we can get a compact Bayes net only if choosing the nodes ordering well.  Using causal model, we typically end up with fewer numbers(conditional prob) to assign and the numbers tend to be easier to come up with.\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n The basic task of any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event - some assignment of values to a set of evident variables.\n\nEvery variable that is not an ancestor of a query variable or evidence variable is irrelevant to the query.\n\n \n\n## Module 11 Lecture Notes\n X and Y are independent if $\forall x, y P(x,y) = P(x)P(y)$\n\nConditionally independent:  X and Y are conditionally indenpendent given Z if : $\forall x, y, z  P(x,y|z) = P(x|z)P(y|z)$  iif $\forall x,y,z: P(x|z, y) = P(x|z)$\n\nBayes net assumption:  $P(x_i|x_1...x_{i-1}) = P(x_i|parents(X_i))$\n\n\"common cause\": $P(x,y,z) = P(y)P(x|y)P(z|y)$ (common cause is Y).  X and Z are not indenpendent, but are independent given Y.\n\n\"common effect\" (v-structures): X and Y each can cause Z.  X and Y are independent, but are not indenpendent given Z.\n\nAnalyzing if two variables are independent in a BN.  To answer if X and Y are conditionally independent given evidence variable Z, check if X and Y are \"d-separated\" by Z.  If there is no active path from X to Y after considering all (undirected) paths from X to Y, then they are conditionally independent.\n\nA path is active if each triple is active: 1) causal chain $A\\rightarrow B\\rightarrow C$ where B is unobserved\n2) common cause $A\\leftarrow B \\rightarrow C$ where B is unobserved;  3) common effect(v structure) $A \\rightarrow B \\leftarrow C$ where B or one of its descendents is observed.  (opposite to causal chain adn common cause)\n\nA single inactive segment is all it takes to block a path (becoming inactive).\n\n\n \n\n## Module 11 Definitions\n* **Conditional probability table (cpt)** - The local probability information associated with a node in Bayesian network. CPTs are only for discrete variables. Each row in CPT contains the conditional probability of the node value for a conditioning case.\n* **Conditioning case** - possible combination of values for the parent nodes.\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Machine learning: how to acquirea model from data and experience: learning parameters (such as probabilities), structure (such as BN graphs), hidden concepts (such as clustering).\nModel based classification: with Naive Bayes; with Perceptrons.\n\nModel-based classification approach: build a model where both the label and features are random variables, instantiate any observed features, query for the distribution of the label conditioned on the features.\n\nNaive Bayes assume all features are independent effects of the label.\n\nNaive Bayes for Text.  Bag-of-words: featueres, $w_i$ is the word at postion i, assume features are conditionally independent given label, predict label conditioned on feature variables, each $w_i$ is identically distributed. \n\n$P(Y, W_1...W_n) = P(Y)\\prod_i P(W_i|Y)$  insensitive to order of words since assuming identical distribution for each position.\n\nExperimentation cycle: learn parameters eg. model probabilities on training set, (tune hyperparameteres on held-out set), compute accuracy of test set.\nIssues: overfitting and generalization.  Relative frequency parameteres will overfit the training data!  Need to smooth or regularize the estimates to generalize better.\n\nLaplace's estimate: pretend the agent saw every outcome once more than the actual occurance.  $P_{LAP}(x) = \frac{c(x)+1}{\\sum_x[c(x)+1]}  = \frac{c(x)+1}{N+|X|]}$\nextended Laplace's estimate: $P_{LAP}(x) = \frac{c(x)+k}{N+k|X|]} $   For conditionals:  P_{LAP, k}(x|y) = \frac{c(x,y)+k}{c(y)+k|X|} smooth each condition independently.\n\nAnother option: linear ionterpolation  $P_{LIN}(x|y) = \\alpha \\hat P(x|y) + (1-\\alpha)\\hat P(x)$.  $k, \\alpha$ are hyperparameters to be tuned on hold-out dataset.\n\nPerceptron, linear classifiers:  $activation_w(x) = \\sum_i w_i\\cdot f_i(x) = w\\cdot f(x) $\n\nPerceptron/MIRA makes less assumptions about data, mistaken-driven learning, multiple passes through data, and often more accurate than Naive Bayes.\n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Logistic Regression uses a vector of weights and a bias term:  $z = \\sum_i w_i x_i +b = w\\cdot x +b $\n\nActivation functions: instead of directly output z=wx+b, which is a linear function of x, neuron units appply a non-linear function f to z.  Commonly used activation functions include Sigmoid, tanh, rectified linear unit(ReLU).\n\nFeed-Foward Neural Network is the simplest kind of NN, which is a multilayer network with all units usually fully-connected and no cycles.  The outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers.\n\nTraining NN: cross-entropy loss as a loss function, gradient descent as an optimization algorithm, erro propagation as a way of computing the gradient of the loss function.\n\nCross-entropy loss:  $L_{CE}(\\hat y, y) = -log p(y|x) = -[y\\log\\hat y + (1-y)\\log(1-\\hat y)]$\n\nfor multnomial classification $L_{CE}(\\hat y, y) = - \\sum_{i=1}^C y_i \\log\\hat y_i$.\n\nIf there is only one correct answer, where the truth is $y_i=1$, then the formula simplifies to:  $L_{CE}(\\hat y, y) = - \\log\\hat y_i$, and in softmax:   $L_{CE}(\\hat y, y)$ = - $\\log (e^{Z_i}/\\sum_{j=1}^K e^{Z_j})$\n\nBackpropagation was invente for NN, and it is related to general procedure called backward differentiation, which depends on the notion of computation graphs.\n\nRegularization is a way to penalize large weights.  A regularization term is added to the loss function.  Lasso regression uses L1 regularization, Ridge regression uses L2.\n\nFor multinomial logistic regression, use a generalization of the sigmoid function - softmax function, which takes in an input vector $Z=Z_1,Z_2,...,Z_n$ and output a vector of values normalized into probabilities.\n\n$$ softmax(z) = [e^{z_1}/\\sum_{i=1}^k e^{z_i}, e^{z_2}/\\sum_{i=1}^k e^{z_i}, ...]$$\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n distributional hypothesis points to the link between similarity in how words are distributed and similarity in what they mean, such that words which are synonyms tended to occur in the same environment\n\nvector semantics, which instantiates this linguistic vector semantics embeddings hypothesis by learning representations of the meaning of words, called embeddings, directly from their distributions in texts. \n\nThese representations are used in every natural language processing application that makes use of meaning.\n\nthe static embeddings and the more powerful dynamic or contextualized embeddings like BERT.\n\nPolysemous - multiple meanings. Each aspect of the meaings of a word is called a word sense.\nSynonymy have the same proositional meaning.  Probably no two words are absolutely identical in meaning.  That is also principle of contrast which states a difference in linguistic form is always associated wtih some difference in meaning.\n\nWord similarity - relations between words (like similarity) is more usefual than relations between word senses (like synonymy).  Knowing how similar two wrods are can help in computing how similar the meaning of two phrases or sentences are.\n\nA semantic fram is a set of words that denote perspectives or participants in a particular type of event.\n\nPositive or negative evaluation language is called sentiment.\n\n\n\n\n## SLP Chapter 6.2 Vector Semantics\n \nVectors semantics is the standard way to represent word meaning in NLP.  The idea is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of word neighbors.  \n\nVectors for representing words are called embeddings.\n\nif-idf model defines the meaning of a word by a simple function of the counts of nearby words.  This results in very long vectors that are sparse.\n\nWord2vec model constructs short, dense vectors having useful semantic properties.\n  \n\n## SLP Chapter 6.3 Words and Vectors\n In a Term-Document matrix, each row represents a word in the vocabulary and each column represents a document.  Each cell in this matrix represents the number of times a particular word occurs in a particular document.\n\nFirst used in vector space model. \n\nTerm-document matrices were originally defined as a means to find similar documents for the task of document information retrieval (IR). \n\nVector semantics can also be used to represent the meaning of words by associating each word with a word vector (a row vector in the matrix).  Similar words have similar vectors because they tend to occur in similar documents.\n\nTerm-term matrix, or word-word matrix, or term-context matrix, in which columns are labeled by words rather than documents. Each cell represents the number of times the row (target) word and the column (contecx) word co-occur in some context in some training corpus.\n\nMore commonly, using a +/-4 words window around the target word.\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n The cosine, is the dot product of two target words' vectors, giving a measure of their similarity.  It will tend to be high if the two vectors have large values in the same dimensions.\n\nNormalized dot product to remove the effect that long vector produces higher dot product value.\n\nThe cosine similarity metric between two vector v and w is : $cosine(v,w) = v\\cdot w /|v||w|$\n\ninverse document frequency (idf) = $N/df_t$, N is the total number of documents in teh collection, $df_t$ is the number of documents in which term $t$ occurs.\n\n \n\n## SLP Chapter 6.8 Word2vec\n embeddings are short dense vectors. number of dimensions ranges from 50 to 1000.\n\nword2vec is a software package includes skip-gram with negative sample (SGNS).  Word2vec embeddings are static embeddings, that the method learns one fixed embedding for each word in the vocabulary.\n\nInstead of counting how often each word w occurs near a word v, word2vec trains a classifier on a binary prediction taks: is the word w likely to show up near v?  Then the learned classifier weights are used as the word embeddings.\n\nThis method, called self-supervison, avoids the need for any sort of hand-labeled supervision signal.\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Embeddings not only reflect the statistics of the inputs, but also amplify bias. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n Logistic Regression uses a vector of weights and a bias term:  $z = \\sum_i w_i x_i +b = w\\cdot x +b $\n\nActivation functions: instead of directly output z=wx+b, which is a linear function of x, neuron units appply a non-linear function f to z.  Commonly used activation functions include Sigmoid, tanh, rectified linear unit(ReLU).\n\nFeed-Foward Neural Network is the simplest kind of NN, which is a multilayer network with all units usually fully-connected and no cycles.  The outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower layers.\n\nTraining NN: cross-entropy loss as a loss function, gradient descent as an optimization algorithm, erro propagation as a way of computing the gradient of the loss function.\n\nCross-entropy loss:  $L_{CE}(\\hat y, y) = -log p(y|x) = -[y\\log\\hat y + (1-y)\\log(1-\\hat y)]$\n\nfor multnomial classification $L_{CE}(\\hat y, y) = - \\sum_{i=1}^C y_i \\log\\hat y_i$.\n\nIf there is only one correct answer, where the truth is $y_i=1$, then the formula simplifies to:  $L_{CE}(\\hat y, y) = - \\log\\hat y_i$, and in softmax:   $L_{CE}(\\hat y, y)$ = - $\\log (e^{Z_i}/\\sum_{j=1}^K e^{Z_j})$\n\nBackpropagation was invente for NN, and it is related to general procedure called backward differentiation, which depends on the notion of computation graphs.\n\nRegularization is a way to penalize large weights.  A regularization term is added to the loss function.  Lasso regression uses L1 regularization, Ridge regression uses L2.\n\nFor multinomial logistic regression, use a generalization of the sigmoid function - softmax function, which takes in an input vector $Z=Z_1,Z_2,...,Z_n$ and output a vector of values normalized into probabilities.\n\n$$ softmax(z) = [e^{z_1}/\\sum_{i=1}^k e^{z_i}, e^{z_2}/\\sum_{i=1}^k e^{z_i}, ...]$$\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}