{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "0ede4358-57bf-48a3-c9c4-abef1b41ec60"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "dac4c6dd-4a19-4699-d4e1-0b7ed3e808b6"
      },
      "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": 3,
      "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": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \\n\n",
        "utility function: express the desirability of a state.\\n\n",
        "Expected Utility equals to the sum of (value of the outcome(utility) * probability that the outcome occurs).\\n\n",
        "principle of decision theory: MEU. a rational agent should choose action that maximizes agents expected utility.\\n\n",
        "limitation:\\n \n",
        "1. there may be uncertainty about utility function. \\n\n",
        "2. not operationalize advice, agent needs many things \\n\n",
        "\n",
        "if agent acts to maximize the utility function that correctly reflects the performance measure, then the agent will \\n\n",
        "have a highest avg performance score.\\n\n",
        "\n",
        "Uitily Function - performance measure - doing the right things.\\n\n",
        "MEU  is not the only rational way!!!\\n\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" \n",
        "In many cases, we are uncertain about what exact states are being offered. For a action, it can produce many different outcomes.\\n\n",
        "In order to express these preference, we think of these outcomes as a lottery, which is a set of outcomes and probability.\\n\n",
        "L = [p1,s1; p2,s2; p3,s3; ... ;pn,sn].\\n\n",
        "six preference relation:\\n\n",
        "1. orderability: agent must has preference.\\n\n",
        "2. transitivity\\n\n",
        "3. continuity: A > B > C -> there exist p that [p,A; 1 - p,C]~B.\\n\n",
        "4. substitutability: [p,A;1 - p,C] ~ [p,B;1 - p, C].\\n\n",
        "5. monotonicity: A > B -> (p > q <-> [p,A;1-p,B]>[q,A;1-q,B]).\\n\n",
        "6. decomposability: [p,A; 1-p,[q,B;1-q,C]] ~ [p,A;(1-p)q,B]; (1-p)(1-q),C]. \\n\n",
        "\n",
        "Expected Utility of a Lottery: sum of prob * utility of that outcome.\\n\n",
        "\n",
        "the existence of a utility function does not necessarily mean that the agent is explicitly maximizing that utility function. \\n\n",
        "Rational behavior can be generated in any number of ways.\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "there is no absolute scale for utility, so we can set standard for utility.\\n\n",
        "we set a standard lottery[p,u(up);(1-p),u(down)], then the probability p is adjusted unitil agent is indifferent between S and standard lottery.\\n\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "MDP: 1.sequential decision problem.transitions are Markovian. 2. the environment is stochastic and fully observable.  \n",
        "\n",
        "the utility function is depend on a sequence of states and actions - environment history, which is sum of rewards received\n",
        "\n",
        "\n",
        "π(s) policy, π*(s) optimal policy (yields highest expected utility).\\n\n",
        "\n",
        "reward function. addictive reward & discounted reward\n",
        "we use  \n",
        "\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "\n",
        "value iteration:\n",
        "n states, n Bellman equations(n utilities of states).\n",
        "max is not a linear operation.\n",
        "the update is applied simultaneously to all the states at each iteration.\n",
        "contraction: one fixed point, the value get closer to the fixed point \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "policy iteration: \n",
        "\n",
        "\n",
        "A reward is sparse if The agents is given no informative reward signal in the vast majority of states.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 23,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "01410636-f971-4cb8-ecfb-990c3d761798"
      },
      "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": 24,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary. \n\nutility function: express the desirability of a state.\n\nExpected Utility equals to the sum of (value of the outcome(utility) * probability that the outcome occurs).\n\nprinciple of decision theory: MEU. a rational agent should choose action that maximizes agents expected utility.\n\nlimitation:\n \n1. there may be uncertainty about utility function. \n\n2. not operationalize advice, agent needs many things \n\n\nif agent acts to maximize the utility function that correctly reflects the performance measure, then the agent will \n\nhave a highest avg performance score.\n\n\nUitily Function - performance measure - doing the right things.\n\nMEU  is not the only rational way!!!\n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nIn many cases, we are uncertain about what exact states are being offered. For a action, it can produce many different outcomes.\n\nIn order to express these preference, we think of these outcomes as a lottery, which is a set of outcomes and probability.\n\nL = [p1,s1; p2,s2; p3,s3; ... ;pn,sn].\n\nsix preference relation:\n\n1. orderability: agent must has preference.\n\n2. transitivity\n\n3. continuity: A > B > C -> there exist p that [p,A; 1 - p,C]~B.\n\n4. substitutability: [p,A;1 - p,C] ~ [p,B;1 - p, C].\n\n5. monotonicity: A > B -> (p > q <-> [p,A;1-p,B]>[q,A;1-q,B]).\n\n6. decomposability: [p,A; 1-p,[q,B;1-q,C]] ~ [p,A;(1-p)q,B]; (1-p)(1-q),C]. \n\n\nExpected Utility of a Lottery: sum of prob * utility of that outcome.\n\n\nthe existence of a utility function does not necessarily mean that the agent is explicitly maximizing that utility function. \n\nRational behavior can be generated in any number of ways.\n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nthere is no absolute scale for utility, so we can set standard for utility.\n\nwe set a standard lottery[p,u(up);(1-p),u(down)], then the probability p is adjusted unitil agent is indifferent between S and standard lottery.\n\n\n\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nMDP: 1.sequential decision problem.transitions are Markovian. 2. the environment is stochastic and fully observable.  \n\nthe utility function is depend on a sequence of states and actions - environment history, which is sum of rewards received\n\n\nπ(s) policy, π*(s) optimal policy (yields highest expected utility).\n\n\nreward function. addictive reward & discounted reward\nwe use  \n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n\nvalue iteration:\nn states, n Bellman equations(n utilities of states).\nmax is not a linear operation.\nthe update is applied simultaneously to all the states at each iteration.\ncontraction: one fixed point, the value get closer to the fixed point \n\n\n\n\n\npolicy iteration: \n\n\nA reward is sparse if The agents is given no informative reward signal in the vast majority of states.\n\n\n\n \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" \n",
        "bandit problem is an MDP\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" \n",
        "model-free reinforcement learning : neither knows nor learns a transition model for the environmnt\\n\n",
        "1. Action-utility learning: example q-learning, the agent learns a q-function, Q(s,a),the sum of rewards from state s onward.\\n\n",
        "the agent choose the action with highest q-value.\\n\n",
        "\n",
        "2. policy search: the agent learns a policy that maps from states to actions\\n\n",
        "\n",
        "\n",
        "passive reinforcement learning:\\n\n",
        "direct utility estimation: the utility of a state is defined as the expected total reward from that state onward. we reduced reinforcement \\n\n",
        "learning to a standard supervised learning.  but it ignores a constraint: the utility of a state is determined by the reward and the expected\\n\n",
        "utility of the successor states. missing the chance to learn. this hypothesis space is very large so the speed is very slow.\\n\n",
        "\n",
        "adaptive dynamic programming(ADP):\\n\n",
        "the agent takes advantage of the constraints among the utilities of states by learning the transition model.\\n\n",
        "put the learned reward function and model probability into Bell function to calculate utility.\n",
        "or we can use modified policy iteration, since model usually change slightly, the previous utility estimates can be initial values.\\n\n",
        "1. temporal difference learning (TD) taking a moving average, every time we visit state s , we updaate our current beliefs about the world,\\n\n",
        "based on the single observation. exponential moving average. but we can not extract policy directly.\\n\n",
        "therefore we need learn q-value.\\n\n",
        "\n",
        "q learning :even if you act uboptimally, it will converge to optimal policy.\\n \n",
        "This is called off-policy learning.  \n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "MDP: offline planning\\n\n",
        "Reinforcement learning: online planning\\n\n",
        "compared to MDP problem, RL don't know model T(s,a,s') and reward function R(s,a,s').\\n\n",
        "Model-Based Learning: learn an approximate model based on experiences. Solve for values as if the learned model were correct.\\n\n",
        "1. learn empirical MDP model. count the number of s' for each s, a and then try to normalize to give an estimate T(s,a,s'). Discover \\n\n",
        "each reward function when we meet (s,a,s').\\n\n",
        "2. solve the learned MDP, using value iteration or policy iteration to solve problems.\\n\n",
        "\n",
        "Model-Free Learning\\n\n",
        "compare the real outcome with what we expect, and then update our expectation.\n",
        "1. passive reinforcement learning. input: fixed policy, goal: learn the state values. quite like policy iteration.\n",
        "act according to π, every time visit a state, calculate expected utility, average samples of each state's value.\n",
        "direct evaluation : update every state's average utility, but it wastes information of state connections and take a long time to learn.\n",
        "policy evaluation \n",
        "xn(update) = (1-a) * xn-1(this is estimate) + a * xn(this is what we explore get, using bellman equation), we can decrease alpha overtime\n",
        "\n",
        "how to explore?\\n\n",
        "explore randomly.\\n\n",
        "epsilon-greedy, with probability epsilon, act randomly. \\n\n",
        "with large probability 1 - epsilon, act on current policy.\\n \n",
        "lower epsilon over time.\\n\n",
        "\n",
        "exploration function:\\n\n",
        "take a value estimate u and visit count n and return an optimistic utility. f(u,n) = u + k/n\n",
        "\n",
        "regret: the difference between expected rewards including youthful suboptimality and optimal rewards.\\n\n",
        "random one have higher regret than exploration function.\n",
        "\n",
        "approximate q learning:\n",
        "if you have many states, you can use approximately. learn something general principle.\n",
        "use a intermediate weighted evaluation \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"exploration\" : \"try to act to get information\",\n",
        "\"exploitation\" : \"use the information you get\",\n",
        "\"regret\" : \"sometimes you might make mistakes when you are learning\",\n",
        "\"sampling\": \"you need to try to act repeatedly\",\n",
        "\n",
        "}"
      ],
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "fa64b538-902c-4a16-c55b-038965704063"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \nbandit problem is an MDP\n\n\n\n\n\n\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n \nmodel-free reinforcement learning : neither knows nor learns a transition model for the environmnt\n\n1. Action-utility learning: example q-learning, the agent learns a q-function, Q(s,a),the sum of rewards from state s onward.\n\nthe agent choose the action with highest q-value.\n\n\n2. policy search: the agent learns a policy that maps from states to actions\n\n\n\npassive reinforcement learning:\n\ndirect utility estimation: the utility of a state is defined as the expected total reward from that state onward. we reduced reinforcement \n\nlearning to a standard supervised learning.  but it ignores a constraint: the utility of a state is determined by the reward and the expected\n\nutility of the successor states. missing the chance to learn. this hypothesis space is very large so the speed is very slow.\n\n\nadaptive dynamic programming(ADP):\n\nthe agent takes advantage of the constraints among the utilities of states by learning the transition model.\n\nput the learned reward function and model probability into Bell function to calculate utility.\nor we can use modified policy iteration, since model usually change slightly, the previous utility estimates can be initial values.\n\n1. temporal difference learning (TD) taking a moving average, every time we visit state s , we updaate our current beliefs about the world,\n\nbased on the single observation. exponential moving average. but we can not extract policy directly.\n\ntherefore we need learn q-value.\n\n\nq learning :even if you act uboptimally, it will converge to optimal policy.\n \nThis is called off-policy learning.  \n\n\n\n\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n \nMDP: offline planning\n\nReinforcement learning: online planning\n\ncompared to MDP problem, RL don't know model T(s,a,s') and reward function R(s,a,s').\n\nModel-Based Learning: learn an approximate model based on experiences. Solve for values as if the learned model were correct.\n\n1. learn empirical MDP model. count the number of s' for each s, a and then try to normalize to give an estimate T(s,a,s'). Discover \n\neach reward function when we meet (s,a,s').\n\n2. solve the learned MDP, using value iteration or policy iteration to solve problems.\n\n\nModel-Free Learning\n\ncompare the real outcome with what we expect, and then update our expectation.\n1. passive reinforcement learning. input: fixed policy, goal: learn the state values. quite like policy iteration.\nact according to π, every time visit a state, calculate expected utility, average samples of each state's value.\ndirect evaluation : update every state's average utility, but it wastes information of state connections and take a long time to learn.\npolicy evaluation \nxn(update) = (1-a) * xn-1(this is estimate) + a * xn(this is what we explore get, using bellman equation), we can decrease alpha overtime\n\nhow to explore?\n\nexplore randomly.\n\nepsilon-greedy, with probability epsilon, act randomly. \n\nwith large probability 1 - epsilon, act on current policy.\n \nlower epsilon over time.\n\n\nexploration function:\n\ntake a value estimate u and visit count n and return an optimistic utility. f(u,n) = u + k/n\n\nregret: the difference between expected rewards including youthful suboptimality and optimal rewards.\n\nrandom one have higher regret than exploration function.\n\napproximate q learning:\nif you have many states, you can use approximately. learn something general principle.\nuse a intermediate weighted evaluation \n\n\n \n\n## Module 9 Definitions\n* **Exploration** - try to act to get information\n* **Exploitation** - use the information you get\n* **Regret** - sometimes you might make mistakes when you are learning\n* **Sampling** - you need to try to act repeatedly\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "probabilities are about possible worlds, probability quantify how likely a particular possible world is.\n",
        "In probabiliaty theory, the possible worlds are called sample space, which are mutually exclusive and exhaustive.\n",
        "P(w)\n",
        "\n",
        "\n",
        "\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": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "574795de-20dc-4a40-cb19-b42da8111d58"
      },
      "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": 27,
      "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 \nprobabilities are about possible worlds, probability quantify how likely a particular possible world is.\nIn probabiliaty theory, the possible worlds are called sample space, which are mutually exclusive and exhaustive.\nP(w)\n\n\n\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 = \"\"\" \n",
        "Bayesian network is to represent the dependencies among variables. Bayesian network networks can representessentially any full joint probability distribution and in many cases\\n\n",
        " can do so very concisely\\n\n",
        "Its node and link specifies the conditional independence relationship that hold in the domain.\\n\n",
        "The syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. The semantics defines how the syntax corresponds to a\n",
        "joint distribution over the variables of the network.\\n\n",
        "P(x1, . . . ,xn) =(nΠi=1)θ(xi|parents(Xi))\\n\n",
        "P(xi|parents(Xi))\\n\n",
        "CPT(conditional probability table)\\n\n",
        "Each row in a CPT contains the conditional probability of each node value for a conditioning case. A conditioning case is just a possible combination Conditioning case of values for the parent\\n\n",
        "nodes—a miniature possible world.\\n \n",
        "\n",
        "2^k * n vs 2^n, n is the number of variables, k is the most domains each variable is most influenced by k parent node.\\n\n",
        "we will get a compact Bayes net only if we choose the node ordering well. Better in the casual order.\\n\n",
        "\n",
        "any of the three networks can represent exactly the same joint distribution.\\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\" how to construct BN?\\n\n",
        "chain rule in BN: P(Xi|Xi−1,...,X1)=P(Xi|Parents(Xi))\\n\n",
        "A Bayes net is more compact than the full joint distribution, which is locally structured (sparse) system. linear rather exponential in complexity.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\"Exact Inference in Bayesian Networks:\\n\n",
        "1.enumeration:\\n\n",
        "P(X|e)=αP(X,e)=α(Σy)P(X,e,y).\\n\n",
        "Step 1: Select the entries consistent with the evidence\\n\n",
        "Step 2: Sum out H to get joint of Query and evidence\\n\n",
        "Step 3: Normalize\\n add all P(X,e1,e2...en). and use it as deliminator to normalize P(X|e1,e2,e3...en)\\n\n",
        "\n",
        "2.variable elimination algorithm.\\n\n",
        "improved enumeration method: eliminating repeated calculations-------dynamic programming.\\n\n",
        "pointwise product\\n\n",
        "\n",
        "The complexity of exact inference:\\n\n",
        "depends strongly on the structure of the network.\\n\n",
        "for multi-connected network, inference in Bayes nets is NP-hard\\n\n",
        "tree-width\\n\n",
        "weighted model counting (WMC).sums the total weight of those satisfying assignments. the weight is essentially the product of the conditional probabilities for\\n\n",
        "each variable assignment given its parents.\n",
        "3.Clustering algorithms(join tree)\\n\n",
        "compute posterior probabilities for all the variables.\\n\n",
        "The basic idea of clustering is to join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree/\\n\n",
        "The two Boolean nodes are replaced by a meganode that takes on four possible Meganode values:tt,tf,ft,and ff. quite like red-black tree?\n",
        "O(n) join tree algorithm.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "3624f7ad-94b0-4349-baa2-1afd490581e6"
      },
      "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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \nBayesian network is to represent the dependencies among variables. Bayesian network networks can representessentially any full joint probability distribution and in many cases\n\n can do so very concisely\n\nIts node and link specifies the conditional independence relationship that hold in the domain.\n\nThe syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. The semantics defines how the syntax corresponds to a\njoint distribution over the variables of the network.\n\nP(x1, . . . ,xn) =(nΠi=1)θ(xi|parents(Xi))\n\nP(xi|parents(Xi))\n\nCPT(conditional probability table)\n\nEach row in a CPT contains the conditional probability of each node value for a conditioning case. A conditioning case is just a possible combination Conditioning case of values for the parent\n\nnodes—a miniature possible world.\n \n\n2^k * n vs 2^n, n is the number of variables, k is the most domains each variable is most influenced by k parent node.\n\nwe will get a compact Bayes net only if we choose the node ordering well. Better in the casual order.\n\n\nany of the three networks can represent exactly the same joint distribution.\n\n\n\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n how to construct BN?\n\nchain rule in BN: P(Xi|Xi−1,...,X1)=P(Xi|Parents(Xi))\n\nA Bayes net is more compact than the full joint distribution, which is locally structured (sparse) system. linear rather exponential in complexity.\n\n\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\nExact Inference in Bayesian Networks:\n\n1.enumeration:\n\nP(X|e)=αP(X,e)=α(Σy)P(X,e,y).\n\nStep 1: Select the entries consistent with the evidence\n\nStep 2: Sum out H to get joint of Query and evidence\n\nStep 3: Normalize\n add all P(X,e1,e2...en). and use it as deliminator to normalize P(X|e1,e2,e3...en)\n\n\n2.variable elimination algorithm.\n\nimproved enumeration method: eliminating repeated calculations-------dynamic programming.\n\npointwise product\n\n\nThe complexity of exact inference:\n\ndepends strongly on the structure of the network.\n\nfor multi-connected network, inference in Bayes nets is NP-hard\n\ntree-width\n\nweighted model counting (WMC).sums the total weight of those satisfying assignments. the weight is essentially the product of the conditional probabilities for\n\neach variable assignment given its parents.\n3.Clustering algorithms(join tree)\n\ncompute posterior probabilities for all the variables.\n\nThe basic idea of clustering is to join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree/\n\nThe two Boolean nodes are replaced by a meganode that takes on four possible Meganode values:tt,tf,ft,and ff. quite like red-black tree?\nO(n) join tree algorithm.\n\n\n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" \n",
        "improvement:\\n\n",
        "1.Which component is to be improved.\\n\n",
        "2.What prior knowledge the agent has,which influences the model it builds.\\n\n",
        "3.What data and feedback on that data is available.\\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter19_2 = \"\"\" \n",
        "supervised learning:\\n\n",
        "hypothesis about the world\\n\n",
        "limited domain set: classification.\\n\n",
        "coninuous domain set: regression.\\n\n",
        "Ockham’s razor: choosing the simplest hypothesis that matches the data.\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter19_3 = \"\"\" Decision tree : cutting nodes to deal with overfitting, entropy\\n \"\"\"\n",
        "chapter19_4 = \"\"\" model selection and optimization.\\n\n",
        "\n",
        "stationary assumption:the future examples will be like the past.without it, all bets are off.\\n\n",
        "We assume that each example Ej has the same prior probability distribution.\\n\n",
        "\n",
        "for multi hypo function we can divide into three data set:\\n\n",
        "1. A training set to train candidate models.\\n \n",
        "2. A validation set, also known as a development set or dev set, to evaluate the candidate\\n\n",
        "models choose the best one.\\n\n",
        "3. A test set to do a final unbiased evaluation of the best model.\\n\n",
        "if do not have enough data, use k-fold cross-validation: each example as both training data and validation data.\\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\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 = \"\"\"  \n",
        "multinomial naive Bayes classifier.\n",
        "a bag-of-words: unordered set of words with their position ignored, keeping only their frequency in the document.\\n\n",
        "Naïve Bayes: Assume all features are independent effects of the label\\n\n",
        "\n",
        "\n",
        "two assumption:\\n\n",
        "1.position doesn’t matter.\\n\n",
        "2. naive Bayes assumption:   probabilities P(fi|c) are independent given the class c.\\n\n",
        "\n",
        "we consider features in log space, so it is a linear function of input features.\\n\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_2 = \"\"\" \n",
        "\n",
        "add-one (Laplace) smoothing, +1\\n\n",
        "for unknow words not in the training document, the solution is to ignore them - remove them from the test document.\\n\n",
        "\n",
        "ignore stop words, sorting by vocabulary frequency.\\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter4_3 = \"\"\" \n",
        "sentiment lexicons: General Inquirer, LIWC, MPQA.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter4_4 = \"\"\"  \"\"\"\n",
        "slp_chapter4_5 = \"\"\" predefine some phrases, character n- gram, feature selection..\\n \"\"\"\n",
        "slp_chapter4_6 = \"\"\" P(s|c) = Yi∈positions P(wi|c).\\n \"\"\"\n",
        "slp_chapter4_7 = \"\"\" human labels -> gold labels\n",
        "\n",
        "a confusion matrix: is a table for visualizing how an algorithm performs with respect to the human gold\\n\n",
        "labels, using two dimensions (system output and gold labels),and each cell labeling a set of possible outcomes. \\n\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_8 = \"\"\" \n",
        "In cross-validation, we choose a number k, and partition our data into k disjoint\\n\n",
        "subsets called folds. Now we choose one of those k folds as a test set, train our\\n\n",
        "classifier on the remaining k − 1 folds, and then compute the error rate on the test\\n\n",
        "set. Then we repeat with another fold as the test set, again training on the other k−1\\n\n",
        "folds. We do this sampling process k times and average the test set error rate from\\n\n",
        "these k runs to get an average error rate. If we choose k = 10, we would train 10\\n\n",
        "different models (each on 90% of our data), test the model 10 times, and average\\n\n",
        "these 10 values. This is called 10-fold cross-validation.\\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_9 = \"\"\" n non-parametric tests:approximate randomization, bootstrap test.\\n   \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "\n",
        "Naïve Bayes: Assume all features are independent effects of the label\\n\n",
        "\n",
        "bag of words model:\\n\n",
        "Ne each Wi is identically distributed\n",
        "Wi is the word at positon i\n",
        "All positions share the same conditional probs P(W|Y), insensitive to order or reordering\n",
        "\n",
        "smooth and regularize:\\n\n",
        "MLE: count/toal samples\n",
        "Laplace’s estimate(smoothing) : Pretend you saw every outcome k extra times, c(x) + 1.\n",
        "Linear Interpolation: use p(x|y) = a*p^(x|y) + (1-a)*p^(x) Make sure the estimate of P(X|Y) isn’t too different from the empirical P(X).\\n\n",
        "P(s|c) = Yi∈positions P(wi|c).\\n\n",
        "\n",
        "\n",
        "tuning on held-out data:\n",
        "Learn parameters from training data\\n\n",
        "Tune hyperparameters on different data\\n\n",
        "For each value of the hyperparameters, train and test on the held-out data \\n\n",
        "Choose the best value and do a final test on the test data \\n\n",
        "\n",
        "\n",
        "set a baseline. usally use previous work as a baseline.\n",
        "\n",
        "\n",
        "perceptron:\\n\n",
        "\n",
        "for bi classifier:\\n\n",
        "If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y(real outcome) is -1.\\n\n",
        "\n",
        "\n",
        "for multi classifier:\n",
        "update : lower score of wrong answer, raise score of right answer\\n\n",
        "wy = wy - f(x)(feature)\\n\n",
        "wy* = wy* + f(x)\\n\n",
        "\n",
        "Separability: true if some parameters get the training set perfectly correct\\n\n",
        "\n",
        "Convergence: if the training is separable, perceptron will eventually converge (binary case)\\n\n",
        "\n",
        "Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of\n",
        "separability.\\n\n",
        "\n",
        "\n",
        "if data is not separable, we can average weight vectors over time. \n",
        "overtraining is kind of overfitting.\\n\n",
        "\n",
        "we can use minimum correcting update, converge faster and works better on noisy data\\n\n",
        "\n",
        "SVM: find the separator with max margin.\\n\n",
        "\n",
        "if z = w*x+b<=0, predict 0,and vice versa this linear prediction.\\n\n",
        "instead of directly output this, neuron units apply non-linear function f to z.\\n\n",
        "sigmoid(0,0.5)domian(0,1), tanh(0,0)domain(-1,1), relu(0,0)(0,inf)\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6519ea86-0081-45b8-c006-7903d8821350"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n \nimprovement:\n\n1.Which component is to be improved.\n\n2.What prior knowledge the agent has,which influences the model it builds.\n\n3.What data and feedback on that data is available.\n\n\n\n\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nsupervised learning:\n\nhypothesis about the world\n\nlimited domain set: classification.\n\nconinuous domain set: regression.\n\nOckham’s razor: choosing the simplest hypothesis that matches the data.\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Decision tree : cutting nodes to deal with overfitting, entropy\n \n\n## AIMA Chapter 5.5 Stochastic Games\n model selection and optimization.\n\n\nstationary assumption:the future examples will be like the past.without it, all bets are off.\n\nWe assume that each example Ej has the same prior probability distribution.\n\n\nfor multi hypo function we can divide into three data set:\n\n1. A training set to train candidate models.\n \n2. A validation set, also known as a development set or dev set, to evaluate the candidate\n\nmodels choose the best one.\n\n3. A test set to do a final unbiased evaluation of the best model.\n\nif do not have enough data, use k-fold cross-validation: each example as both training data and validation data.\n\n\n\n\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  \nmultinomial naive Bayes classifier.\na bag-of-words: unordered set of words with their position ignored, keeping only their frequency in the document.\n\nNaïve Bayes: Assume all features are independent effects of the label\n\n\n\ntwo assumption:\n\n1.position doesn’t matter.\n\n2. naive Bayes assumption:   probabilities P(fi|c) are independent given the class c.\n\n\nwe consider features in log space, so it is a linear function of input features.\n\n\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \n\nadd-one (Laplace) smoothing, +1\n\nfor unknow words not in the training document, the solution is to ignore them - remove them from the test document.\n\n\nignore stop words, sorting by vocabulary frequency.\n\n\n\n\n\n## SLP Chapter 4.3 Worked Example\n \nsentiment lexicons: General Inquirer, LIWC, MPQA.\n\n\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n  \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n predefine some phrases, character n- gram, feature selection..\n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n P(s|c) = Yi∈positions P(wi|c).\n \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n human labels -> gold labels\n\na confusion matrix: is a table for visualizing how an algorithm performs with respect to the human gold\n\nlabels, using two dimensions (system output and gold labels),and each cell labeling a set of possible outcomes. \n\n\n \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n \nIn cross-validation, we choose a number k, and partition our data into k disjoint\n\nsubsets called folds. Now we choose one of those k folds as a test set, train our\n\nclassifier on the remaining k − 1 folds, and then compute the error rate on the test\n\nset. Then we repeat with another fold as the test set, again training on the other k−1\n\nfolds. We do this sampling process k times and average the test set error rate from\n\nthese k runs to get an average error rate. If we choose k = 10, we would train 10\n\ndifferent models (each on 90% of our data), test the model 10 times, and average\n\nthese 10 values. This is called 10-fold cross-validation.\n\n\n\n \n\n## SLP Chapter 4.9 Statistical Significance Testing\n n non-parametric tests:approximate randomization, bootstrap test.\n   \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n\nNaïve Bayes: Assume all features are independent effects of the label\n\n\nbag of words model:\n\nNe each Wi is identically distributed\nWi is the word at positon i\nAll positions share the same conditional probs P(W|Y), insensitive to order or reordering\n\nsmooth and regularize:\n\nMLE: count/toal samples\nLaplace’s estimate(smoothing) : Pretend you saw every outcome k extra times, c(x) + 1.\nLinear Interpolation: use p(x|y) = a*p^(x|y) + (1-a)*p^(x) Make sure the estimate of P(X|Y) isn’t too different from the empirical P(X).\n\nP(s|c) = Yi∈positions P(wi|c).\n\n\n\ntuning on held-out data:\nLearn parameters from training data\n\nTune hyperparameters on different data\n\nFor each value of the hyperparameters, train and test on the held-out data \n\nChoose the best value and do a final test on the test data \n\n\n\nset a baseline. usally use previous work as a baseline.\n\n\nperceptron:\n\n\nfor bi classifier:\n\nIf wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y(real outcome) is -1.\n\n\n\nfor multi classifier:\nupdate : lower score of wrong answer, raise score of right answer\n\nwy = wy - f(x)(feature)\n\nwy* = wy* + f(x)\n\n\nSeparability: true if some parameters get the training set perfectly correct\n\n\nConvergence: if the training is separable, perceptron will eventually converge (binary case)\n\n\nMistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of\nseparability.\n\n\n\nif data is not separable, we can average weight vectors over time. \novertraining is kind of overfitting.\n\n\nwe can use minimum correcting update, converge faster and works better on noisy data\n\n\nSVM: find the separator with max margin.\n\n\nif z = w*x+b<=0, predict 0,and vice versa this linear prediction.\n\ninstead of directly output this, neuron units apply non-linear function f to z.\n\nsigmoid(0,0.5)domian(0,1), tanh(0,0)domain(-1,1), relu(0,0)(0,inf)\n\n \n\n## Module 12 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "logistic regression:\\n\n",
        "extract features\\n\n",
        "how do we get the weights of the model? loss function: cross-entropy loss, then use stochastic \n",
        "gradient descent to minimize the loss function.\\n\n",
        "\n",
        "loss function:\\n \n",
        "most easy one: mean sequred error MSE\n",
        "cross entropy loss: -log p(y|x), prefers the correct class labels of the training example to be more likely.\\n\n",
        "conditional maximum likelihood estimation: choose w,b that maximize the probability of the true labels in the\n",
        "training data.\\n\n",
        "logistic regress's loss function is convex, only one local minimum so it is guaranteed to find the minimum.\\n\n",
        "\n",
        "The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η\\n\n",
        "\n",
        "mini-batch training: computes the gradient over the entire dataset,better estimate f direction to move compared to gradient descent.\\n\n",
        "\n",
        "softmax function for multinomial logistic regression. (normalized)\\n\n",
        "\n",
        "neural network:\\n\n",
        "input layer - hidden layer - output layer\\n\n",
        "compared to perceptron to directly output 1 or 0 by computing z = wx + b, which a small change can bring huge output change\\n\n",
        "we use sigmoid neuron sigma. y = f(z)\\n \n",
        "\n",
        "\n",
        "feed-forwad NN:\\n\n",
        "all units are fully-connected, no cycles, one directional.\\n\n",
        "\n",
        "\n",
        "backward differentiation: o compute the derivatives that we’ll need for the weight update.\\n\n",
        "chain rule from calculus. \\n\n",
        "Error back propagation to compute the gradient of the loss function\n",
        "\n",
        "\n",
        "neural language model:\n",
        "do not need smoothing. handel much longer histories, higher accuracy, generalize contexts of similar words.\\n\n",
        "1. Associate each word in the vocabulary with a vector-representation, thereby\n",
        "creating a notion of similarity between words.\\n\n",
        "2. Express the joint probability function of a word sequence in terms of the word\n",
        "vectors for the words in that sequence.\\n\n",
        "3. Simultaneously learn the word vectors and the parameters of the function\\n\n",
        "\n",
        "using NN to caluculate conditional probablity of the nextword given previous word.\\n\n",
        "input is k-gram of words, each word is with an embedding vector. \n",
        "\n",
        "\n",
        "compute word similarity. calculate the joint probability of the sentence.\\n\n",
        "\n",
        "1. Create a mapping function C from any word in V onto ℝM. Store this\n",
        "in a V-by-M matrix. Initialize it with singular value decomposition (SVD).\\n\n",
        "2. The neural architecture: a function g maps sequence of word vectors\n",
        "onto a probability distribution over the vocabulary V\\n\n",
        "\n",
        "reduce dimensional.\\n\n",
        "similar but not just synonyms\\n\n",
        "vector comparison: compare distance.\n",
        "vector normalization use L1, L2.\\n\n",
        "or use cosine Distance which automatically normalize\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        " \n",
        "}\n"
      ],
      "execution_count": 45,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "1560902b-6023-4cf1-adee-f6c30a543ace"
      },
      "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": 46,
      "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 \nlogistic regression:\n\nextract features\n\nhow do we get the weights of the model? loss function: cross-entropy loss, then use stochastic \ngradient descent to minimize the loss function.\n\n\nloss function:\n \nmost easy one: mean sequred error MSE\ncross entropy loss: -log p(y|x), prefers the correct class labels of the training example to be more likely.\n\nconditional maximum likelihood estimation: choose w,b that maximize the probability of the true labels in the\ntraining data.\n\nlogistic regress's loss function is convex, only one local minimum so it is guaranteed to find the minimum.\n\n\nThe magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η\n\n\nmini-batch training: computes the gradient over the entire dataset,better estimate f direction to move compared to gradient descent.\n\n\nsoftmax function for multinomial logistic regression. (normalized)\n\n\nneural network:\n\ninput layer - hidden layer - output layer\n\ncompared to perceptron to directly output 1 or 0 by computing z = wx + b, which a small change can bring huge output change\n\nwe use sigmoid neuron sigma. y = f(z)\n \n\n\nfeed-forwad NN:\n\nall units are fully-connected, no cycles, one directional.\n\n\n\nbackward differentiation: o compute the derivatives that we’ll need for the weight update.\n\nchain rule from calculus. \n\nError back propagation to compute the gradient of the loss function\n\n\nneural language model:\ndo not need smoothing. handel much longer histories, higher accuracy, generalize contexts of similar words.\n\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n\n3. Simultaneously learn the word vectors and the parameters of the function\n\n\nusing NN to caluculate conditional probablity of the nextword given previous word.\n\ninput is k-gram of words, each word is with an embedding vector. \n\n\ncompute word similarity. calculate the joint probability of the sentence.\n\n\n1. Create a mapping function C from any word in V onto ℝM. Store this\nin a V-by-M matrix. Initialize it with singular value decomposition (SVD).\n\n2. The neural architecture: a function g maps sequence of word vectors\nonto a probability distribution over the vocabulary V\n\n\nreduce dimensional.\n\nsimilar but not just synonyms\n\nvector comparison: compare distance.\nvector normalization use L1, L2.\n\nor use cosine Distance which automatically normalize\n\n\n \n\n## Module 13 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" \n",
        "\n",
        "\n",
        "neural language model:\n",
        "do not need smoothing. handel much longer histories, higher accuracy, generalize contexts of similar words.\\n\n",
        "1. Associate each word in the vocabulary with a vector-representation, thereby\n",
        "creating a notion of similarity between words.\\n\n",
        "2. Express the joint probability function of a word sequence in terms of the word\n",
        "vectors for the words in that sequence.\\n\n",
        "3. Simultaneously learn the word vectors and the parameters of the function\\n\n",
        "\n",
        "using NN to caluculate conditional probablity of the nextword given previous word.\\n\n",
        "input is k-gram of words, each word is with an embedding vector. \n",
        "\n",
        "\n",
        "compute word similarity. calculate the joint probability of the sentence.\\n\n",
        "\n",
        "1. Create a mapping function C from any word in V onto ℝM. Store this\n",
        "in a V-by-M matrix. Initialize it with singular value decomposition (SVD).\\n\n",
        "2. The neural architecture: a function g maps sequence of word vectors\n",
        "onto a probability distribution over the vocabulary V\\n\n",
        "\n",
        "reduce dimensional.\\n\n",
        "similar but not just synonyms\\n\n",
        "vector comparison: compare distance.\n",
        "vector normalization use L1, L2.\\n\n",
        "or use cosine Distance which automatically normalize\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 47,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9effba88-592d-481e-8a36-7a1af3f1fb04"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nlogistic regression:\n\nextract features\n\nhow do we get the weights of the model? loss function: cross-entropy loss, then use stochastic \ngradient descent to minimize the loss function.\n\n\nloss function:\n \nmost easy one: mean sequred error MSE\ncross entropy loss: -log p(y|x), prefers the correct class labels of the training example to be more likely.\n\nconditional maximum likelihood estimation: choose w,b that maximize the probability of the true labels in the\ntraining data.\n\nlogistic regress's loss function is convex, only one local minimum so it is guaranteed to find the minimum.\n\n\nThe magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η\n\n\nmini-batch training: computes the gradient over the entire dataset,better estimate f direction to move compared to gradient descent.\n\n\nsoftmax function for multinomial logistic regression. (normalized)\n\n\nneural network:\n\ninput layer - hidden layer - output layer\n\ncompared to perceptron to directly output 1 or 0 by computing z = wx + b, which a small change can bring huge output change\n\nwe use sigmoid neuron sigma. y = f(z)\n \n\n\nfeed-forwad NN:\n\nall units are fully-connected, no cycles, one directional.\n\n\n\nbackward differentiation: o compute the derivatives that we’ll need for the weight update.\n\nchain rule from calculus. \n\nError back propagation to compute the gradient of the loss function\n\n\nneural language model:\ndo not need smoothing. handel much longer histories, higher accuracy, generalize contexts of similar words.\n\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n\n3. Simultaneously learn the word vectors and the parameters of the function\n\n\nusing NN to caluculate conditional probablity of the nextword given previous word.\n\ninput is k-gram of words, each word is with an embedding vector. \n\n\ncompute word similarity. calculate the joint probability of the sentence.\n\n\n1. Create a mapping function C from any word in V onto ℝM. Store this\nin a V-by-M matrix. Initialize it with singular value decomposition (SVD).\n\n2. The neural architecture: a function g maps sequence of word vectors\nonto a probability distribution over the vocabulary V\n\n\nreduce dimensional.\n\nsimilar but not just synonyms\n\nvector comparison: compare distance.\nvector normalization use L1, L2.\n\nor use cosine Distance which automatically normalize\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "0a893117-b695-4fde-d70e-cd89d64c512b"
      },
      "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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary. \n\nutility function: express the desirability of a state.\n\nExpected Utility equals to the sum of (value of the outcome(utility) * probability that the outcome occurs).\n\nprinciple of decision theory: MEU. a rational agent should choose action that maximizes agents expected utility.\n\nlimitation:\n \n1. there may be uncertainty about utility function. \n\n2. not operationalize advice, agent needs many things \n\n\nif agent acts to maximize the utility function that correctly reflects the performance measure, then the agent will \n\nhave a highest avg performance score.\n\n\nUitily Function - performance measure - doing the right things.\n\nMEU  is not the only rational way!!!\n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nIn many cases, we are uncertain about what exact states are being offered. For a action, it can produce many different outcomes.\n\nIn order to express these preference, we think of these outcomes as a lottery, which is a set of outcomes and probability.\n\nL = [p1,s1; p2,s2; p3,s3; ... ;pn,sn].\n\nsix preference relation:\n\n1. orderability: agent must has preference.\n\n2. transitivity\n\n3. continuity: A > B > C -> there exist p that [p,A; 1 - p,C]~B.\n\n4. substitutability: [p,A;1 - p,C] ~ [p,B;1 - p, C].\n\n5. monotonicity: A > B -> (p > q <-> [p,A;1-p,B]>[q,A;1-q,B]).\n\n6. decomposability: [p,A; 1-p,[q,B;1-q,C]] ~ [p,A;(1-p)q,B]; (1-p)(1-q),C]. \n\n\nExpected Utility of a Lottery: sum of prob * utility of that outcome.\n\n\nthe existence of a utility function does not necessarily mean that the agent is explicitly maximizing that utility function. \n\nRational behavior can be generated in any number of ways.\n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nthere is no absolute scale for utility, so we can set standard for utility.\n\nwe set a standard lottery[p,u(up);(1-p),u(down)], then the probability p is adjusted unitil agent is indifferent between S and standard lottery.\n\n\n\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nMDP: 1.sequential decision problem.transitions are Markovian. 2. the environment is stochastic and fully observable.  \n\nthe utility function is depend on a sequence of states and actions - environment history, which is sum of rewards received\n\n\nπ(s) policy, π*(s) optimal policy (yields highest expected utility).\n\n\nreward function. addictive reward & discounted reward\nwe use  \n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n\nvalue iteration:\nn states, n Bellman equations(n utilities of states).\nmax is not a linear operation.\nthe update is applied simultaneously to all the states at each iteration.\ncontraction: one fixed point, the value get closer to the fixed point \n\n\n\n\n\npolicy iteration: \n\n\nA reward is sparse if The agents is given no informative reward signal in the vast majority of states.\n\n\n\n \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \nbandit problem is an MDP\n\n\n\n\n\n\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n \nmodel-free reinforcement learning : neither knows nor learns a transition model for the environmnt\n\n1. Action-utility learning: example q-learning, the agent learns a q-function, Q(s,a),the sum of rewards from state s onward.\n\nthe agent choose the action with highest q-value.\n\n\n2. policy search: the agent learns a policy that maps from states to actions\n\n\n\npassive reinforcement learning:\n\ndirect utility estimation: the utility of a state is defined as the expected total reward from that state onward. we reduced reinforcement \n\nlearning to a standard supervised learning.  but it ignores a constraint: the utility of a state is determined by the reward and the expected\n\nutility of the successor states. missing the chance to learn. this hypothesis space is very large so the speed is very slow.\n\n\nadaptive dynamic programming(ADP):\n\nthe agent takes advantage of the constraints among the utilities of states by learning the transition model.\n\nput the learned reward function and model probability into Bell function to calculate utility.\nor we can use modified policy iteration, since model usually change slightly, the previous utility estimates can be initial values.\n\n1. temporal difference learning (TD) taking a moving average, every time we visit state s , we updaate our current beliefs about the world,\n\nbased on the single observation. exponential moving average. but we can not extract policy directly.\n\ntherefore we need learn q-value.\n\n\nq learning :even if you act uboptimally, it will converge to optimal policy.\n \nThis is called off-policy learning.  \n\n\n\n\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n \nMDP: offline planning\n\nReinforcement learning: online planning\n\ncompared to MDP problem, RL don't know model T(s,a,s') and reward function R(s,a,s').\n\nModel-Based Learning: learn an approximate model based on experiences. Solve for values as if the learned model were correct.\n\n1. learn empirical MDP model. count the number of s' for each s, a and then try to normalize to give an estimate T(s,a,s'). Discover \n\neach reward function when we meet (s,a,s').\n\n2. solve the learned MDP, using value iteration or policy iteration to solve problems.\n\n\nModel-Free Learning\n\ncompare the real outcome with what we expect, and then update our expectation.\n1. passive reinforcement learning. input: fixed policy, goal: learn the state values. quite like policy iteration.\nact according to π, every time visit a state, calculate expected utility, average samples of each state's value.\ndirect evaluation : update every state's average utility, but it wastes information of state connections and take a long time to learn.\npolicy evaluation \nxn(update) = (1-a) * xn-1(this is estimate) + a * xn(this is what we explore get, using bellman equation), we can decrease alpha overtime\n\nhow to explore?\n\nexplore randomly.\n\nepsilon-greedy, with probability epsilon, act randomly. \n\nwith large probability 1 - epsilon, act on current policy.\n \nlower epsilon over time.\n\n\nexploration function:\n\ntake a value estimate u and visit count n and return an optimistic utility. f(u,n) = u + k/n\n\nregret: the difference between expected rewards including youthful suboptimality and optimal rewards.\n\nrandom one have higher regret than exploration function.\n\napproximate q learning:\nif you have many states, you can use approximately. learn something general principle.\nuse a intermediate weighted evaluation \n\n\n \n\n## Module 9 Definitions\n* **Exploration** - try to act to get information\n* **Exploitation** - use the information you get\n* **Regret** - sometimes you might make mistakes when you are learning\n* **Sampling** - you need to try to act repeatedly\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 \nprobabilities are about possible worlds, probability quantify how likely a particular possible world is.\nIn probabiliaty theory, the possible worlds are called sample space, which are mutually exclusive and exhaustive.\nP(w)\n\n\n\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \nBayesian network is to represent the dependencies among variables. Bayesian network networks can representessentially any full joint probability distribution and in many cases\n\n can do so very concisely\n\nIts node and link specifies the conditional independence relationship that hold in the domain.\n\nThe syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. The semantics defines how the syntax corresponds to a\njoint distribution over the variables of the network.\n\nP(x1, . . . ,xn) =(nΠi=1)θ(xi|parents(Xi))\n\nP(xi|parents(Xi))\n\nCPT(conditional probability table)\n\nEach row in a CPT contains the conditional probability of each node value for a conditioning case. A conditioning case is just a possible combination Conditioning case of values for the parent\n\nnodes—a miniature possible world.\n \n\n2^k * n vs 2^n, n is the number of variables, k is the most domains each variable is most influenced by k parent node.\n\nwe will get a compact Bayes net only if we choose the node ordering well. Better in the casual order.\n\n\nany of the three networks can represent exactly the same joint distribution.\n\n\n\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n how to construct BN?\n\nchain rule in BN: P(Xi|Xi−1,...,X1)=P(Xi|Parents(Xi))\n\nA Bayes net is more compact than the full joint distribution, which is locally structured (sparse) system. linear rather exponential in complexity.\n\n\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\nExact Inference in Bayesian Networks:\n\n1.enumeration:\n\nP(X|e)=αP(X,e)=α(Σy)P(X,e,y).\n\nStep 1: Select the entries consistent with the evidence\n\nStep 2: Sum out H to get joint of Query and evidence\n\nStep 3: Normalize\n add all P(X,e1,e2...en). and use it as deliminator to normalize P(X|e1,e2,e3...en)\n\n\n2.variable elimination algorithm.\n\nimproved enumeration method: eliminating repeated calculations-------dynamic programming.\n\npointwise product\n\n\nThe complexity of exact inference:\n\ndepends strongly on the structure of the network.\n\nfor multi-connected network, inference in Bayes nets is NP-hard\n\ntree-width\n\nweighted model counting (WMC).sums the total weight of those satisfying assignments. the weight is essentially the product of the conditional probabilities for\n\neach variable assignment given its parents.\n3.Clustering algorithms(join tree)\n\ncompute posterior probabilities for all the variables.\n\nThe basic idea of clustering is to join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree/\n\nThe two Boolean nodes are replaced by a meganode that takes on four possible Meganode values:tt,tf,ft,and ff. quite like red-black tree?\nO(n) join tree algorithm.\n\n\n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n \nimprovement:\n\n1.Which component is to be improved.\n\n2.What prior knowledge the agent has,which influences the model it builds.\n\n3.What data and feedback on that data is available.\n\n\n\n\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nsupervised learning:\n\nhypothesis about the world\n\nlimited domain set: classification.\n\nconinuous domain set: regression.\n\nOckham’s razor: choosing the simplest hypothesis that matches the data.\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Decision tree : cutting nodes to deal with overfitting, entropy\n \n\n## AIMA Chapter 5.5 Stochastic Games\n model selection and optimization.\n\n\nstationary assumption:the future examples will be like the past.without it, all bets are off.\n\nWe assume that each example Ej has the same prior probability distribution.\n\n\nfor multi hypo function we can divide into three data set:\n\n1. A training set to train candidate models.\n \n2. A validation set, also known as a development set or dev set, to evaluate the candidate\n\nmodels choose the best one.\n\n3. A test set to do a final unbiased evaluation of the best model.\n\nif do not have enough data, use k-fold cross-validation: each example as both training data and validation data.\n\n\n\n\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  \nmultinomial naive Bayes classifier.\na bag-of-words: unordered set of words with their position ignored, keeping only their frequency in the document.\n\nNaïve Bayes: Assume all features are independent effects of the label\n\n\n\ntwo assumption:\n\n1.position doesn’t matter.\n\n2. naive Bayes assumption:   probabilities P(fi|c) are independent given the class c.\n\n\nwe consider features in log space, so it is a linear function of input features.\n\n\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \n\nadd-one (Laplace) smoothing, +1\n\nfor unknow words not in the training document, the solution is to ignore them - remove them from the test document.\n\n\nignore stop words, sorting by vocabulary frequency.\n\n\n\n\n\n## SLP Chapter 4.3 Worked Example\n \nsentiment lexicons: General Inquirer, LIWC, MPQA.\n\n\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n  \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n predefine some phrases, character n- gram, feature selection..\n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n P(s|c) = Yi∈positions P(wi|c).\n \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n human labels -> gold labels\n\na confusion matrix: is a table for visualizing how an algorithm performs with respect to the human gold\n\nlabels, using two dimensions (system output and gold labels),and each cell labeling a set of possible outcomes. \n\n\n \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n \nIn cross-validation, we choose a number k, and partition our data into k disjoint\n\nsubsets called folds. Now we choose one of those k folds as a test set, train our\n\nclassifier on the remaining k − 1 folds, and then compute the error rate on the test\n\nset. Then we repeat with another fold as the test set, again training on the other k−1\n\nfolds. We do this sampling process k times and average the test set error rate from\n\nthese k runs to get an average error rate. If we choose k = 10, we would train 10\n\ndifferent models (each on 90% of our data), test the model 10 times, and average\n\nthese 10 values. This is called 10-fold cross-validation.\n\n\n\n \n\n## SLP Chapter 4.9 Statistical Significance Testing\n n non-parametric tests:approximate randomization, bootstrap test.\n   \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n\nNaïve Bayes: Assume all features are independent effects of the label\n\n\nbag of words model:\n\nNe each Wi is identically distributed\nWi is the word at positon i\nAll positions share the same conditional probs P(W|Y), insensitive to order or reordering\n\nsmooth and regularize:\n\nMLE: count/toal samples\nLaplace’s estimate(smoothing) : Pretend you saw every outcome k extra times, c(x) + 1.\nLinear Interpolation: use p(x|y) = a*p^(x|y) + (1-a)*p^(x) Make sure the estimate of P(X|Y) isn’t too different from the empirical P(X).\n\nP(s|c) = Yi∈positions P(wi|c).\n\n\n\ntuning on held-out data:\nLearn parameters from training data\n\nTune hyperparameters on different data\n\nFor each value of the hyperparameters, train and test on the held-out data \n\nChoose the best value and do a final test on the test data \n\n\n\nset a baseline. usally use previous work as a baseline.\n\n\nperceptron:\n\n\nfor bi classifier:\n\nIf wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y(real outcome) is -1.\n\n\n\nfor multi classifier:\nupdate : lower score of wrong answer, raise score of right answer\n\nwy = wy - f(x)(feature)\n\nwy* = wy* + f(x)\n\n\nSeparability: true if some parameters get the training set perfectly correct\n\n\nConvergence: if the training is separable, perceptron will eventually converge (binary case)\n\n\nMistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of\nseparability.\n\n\n\nif data is not separable, we can average weight vectors over time. \novertraining is kind of overfitting.\n\n\nwe can use minimum correcting update, converge faster and works better on noisy data\n\n\nSVM: find the separator with max margin.\n\n\nif z = w*x+b<=0, predict 0,and vice versa this linear prediction.\n\ninstead of directly output this, neuron units apply non-linear function f to z.\n\nsigmoid(0,0.5)domian(0,1), tanh(0,0)domain(-1,1), relu(0,0)(0,inf)\n\n \n\n## Module 12 Definitions\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 \nlogistic regression:\n\nextract features\n\nhow do we get the weights of the model? loss function: cross-entropy loss, then use stochastic \ngradient descent to minimize the loss function.\n\n\nloss function:\n \nmost easy one: mean sequred error MSE\ncross entropy loss: -log p(y|x), prefers the correct class labels of the training example to be more likely.\n\nconditional maximum likelihood estimation: choose w,b that maximize the probability of the true labels in the\ntraining data.\n\nlogistic regress's loss function is convex, only one local minimum so it is guaranteed to find the minimum.\n\n\nThe magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η\n\n\nmini-batch training: computes the gradient over the entire dataset,better estimate f direction to move compared to gradient descent.\n\n\nsoftmax function for multinomial logistic regression. (normalized)\n\n\nneural network:\n\ninput layer - hidden layer - output layer\n\ncompared to perceptron to directly output 1 or 0 by computing z = wx + b, which a small change can bring huge output change\n\nwe use sigmoid neuron sigma. y = f(z)\n \n\n\nfeed-forwad NN:\n\nall units are fully-connected, no cycles, one directional.\n\n\n\nbackward differentiation: o compute the derivatives that we’ll need for the weight update.\n\nchain rule from calculus. \n\nError back propagation to compute the gradient of the loss function\n\n\nneural language model:\ndo not need smoothing. handel much longer histories, higher accuracy, generalize contexts of similar words.\n\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n\n3. Simultaneously learn the word vectors and the parameters of the function\n\n\nusing NN to caluculate conditional probablity of the nextword given previous word.\n\ninput is k-gram of words, each word is with an embedding vector. \n\n\ncompute word similarity. calculate the joint probability of the sentence.\n\n\n1. Create a mapping function C from any word in V onto ℝM. Store this\nin a V-by-M matrix. Initialize it with singular value decomposition (SVD).\n\n2. The neural architecture: a function g maps sequence of word vectors\nonto a probability distribution over the vocabulary V\n\n\nreduce dimensional.\n\nsimilar but not just synonyms\n\nvector comparison: compare distance.\nvector normalization use L1, L2.\n\nor use cosine Distance which automatically normalize\n\n\n \n\n## Module 13 Definitions\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \nlogistic regression:\n\nextract features\n\nhow do we get the weights of the model? loss function: cross-entropy loss, then use stochastic \ngradient descent to minimize the loss function.\n\n\nloss function:\n \nmost easy one: mean sequred error MSE\ncross entropy loss: -log p(y|x), prefers the correct class labels of the training example to be more likely.\n\nconditional maximum likelihood estimation: choose w,b that maximize the probability of the true labels in the\ntraining data.\n\nlogistic regress's loss function is convex, only one local minimum so it is guaranteed to find the minimum.\n\n\nThe magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η\n\n\nmini-batch training: computes the gradient over the entire dataset,better estimate f direction to move compared to gradient descent.\n\n\nsoftmax function for multinomial logistic regression. (normalized)\n\n\nneural network:\n\ninput layer - hidden layer - output layer\n\ncompared to perceptron to directly output 1 or 0 by computing z = wx + b, which a small change can bring huge output change\n\nwe use sigmoid neuron sigma. y = f(z)\n \n\n\nfeed-forwad NN:\n\nall units are fully-connected, no cycles, one directional.\n\n\n\nbackward differentiation: o compute the derivatives that we’ll need for the weight update.\n\nchain rule from calculus. \n\nError back propagation to compute the gradient of the loss function\n\n\nneural language model:\ndo not need smoothing. handel much longer histories, higher accuracy, generalize contexts of similar words.\n\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n\n3. Simultaneously learn the word vectors and the parameters of the function\n\n\nusing NN to caluculate conditional probablity of the nextword given previous word.\n\ninput is k-gram of words, each word is with an embedding vector. \n\n\ncompute word similarity. calculate the joint probability of the sentence.\n\n\n1. Create a mapping function C from any word in V onto ℝM. Store this\nin a V-by-M matrix. Initialize it with singular value decomposition (SVD).\n\n2. The neural architecture: a function g maps sequence of word vectors\nonto a probability distribution over the vocabulary V\n\n\nreduce dimensional.\n\nsimilar but not just synonyms\n\nvector comparison: compare distance.\nvector normalization use L1, L2.\n\nor use cosine Distance which automatically normalize\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}