{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Bharg_Mehta_CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "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": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "54580f1e-22eb-4657-8e14-104a615b6276"
      },
      "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": null,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "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": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "2cd4c8a2-805b-483a-8fae-409ce38e0560"
      },
      "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": null,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Decision theory assume the environmnt to be episodic and the actions are based on the desirability of the immediate outcomes. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Six constraints that we require an resonable preference relation to obey.\n",
        "1. Orderabiity\n",
        "2. Transitivity\n",
        "3. Continuity\n",
        "4. Substitutability\n",
        "5. Monotonicity\n",
        "6. Decomposability \"\"\"\n",
        "chapter16_3 =  \"\"\"Utility functions map lotteries to real numbers. Measurements of utility are: Utility of money: We say that the agent exhibits a monotonic preference for more money. \\\n",
        "This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money. \\n\n",
        "Decision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act. The value an agent \\\n",
        "will accept in lieu of a lottery is called the certainty equivalent of the lottery. The difference between the EMV of a lottery and its certainty equivalent is called insurance.  This tendency for the estimated \\\n",
        "expected utility of the best choice to be too high is called the optimizer’s curse. Can be avoided using Bayesian Priors.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" A remarkable consequence of using discounted utilities with infinite horizons is that the optimal policy is independent of the starting state. There is a direct \\\n",
        "relationship between the utility of a state and that of its neighbors i.e. the utility of a state is the expected reward for the next transition plus the discounted utility of \\\n",
        "the next state, assuming that the agent chooses the optimal action. This called Ballman equation. Shaping theorem staes that the following transformation leaves the optimal policy \\\n",
        "unchanged. $R′(s,a,s′) = R(s,a,s′) +γΦ(s′)−Φ(s)$. All policies are optimal with zero reward functin everywhere. \"\"\"\n",
        "chapter17_2 =  \"\"\"Four algorithms for solving MDPs are explained which are (1)Value iteration (2)Policy iteration (3)Linear Programming (4)Monte Carlo Planning. The first three \\\n",
        "genrate exact offline solutions whereas the fourth genrates approximate online solutions. Each step of iteration in Value iteration is called Bellman update. The convergence of \\\n",
        "value iteration is shown using contraction. Bellman update is a contraction by a factor $\\gamma$ in the space of utility vectors. Value iteration. \n",
        "Policy iteration alternates between two steps beginning from some initial policy, policy evaluation followed by policy improvement. Time complexity of policy iteration is $O(S^3)$. \\\n",
        "After certain steps of policy iteration, the bellman update equation can be modified to do simplified value iteration (simplified as since the policy is fixed, the transition model \\\n",
        "is only a probability now). This is called Modified policy iteration. \\n\n",
        "Linear Programming is solvable in polynomial time. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"The stochastic transition models are written as T(s,a,s') or as probability p(s'|s,a). The fact that we are ignoring the history of the steps taken indicates that we are in the Marovian part of the Markov model.\\\n",
        "MDPs are sequential decision problems in a fully observable environment with a stochastic transition with additive rewards and are non-deterministic search problems and solved using expectimax. \\\n",
        "Solution to MDPs require, a set of states, set of actions Transition function (probability model), Reward function, initial state and optionally terminal states. The solution to MDP is a POLICY, Policy takes in the current state \\\n",
        "and tels the agent what action to take. $\\pi(s) = a$ Best policy is denoted by $\\pi*$. Best policy depends on reward functions.Same policy executed multiple times may result in different sequence of states and actions. Reward function \\\n",
        "will determine the optimal policy. Utility function depends on the environment history. Infinite rewards avoids exits and leads to infite horizon game. Rewards now are preferred over rewards later and hence future rewards are \\\n",
        "discounted and also helps algorithm converge. Solution to infinite utilities: (1)Finite-horizon (2)Discounting (3)Absorbing-state. Optimal quantities - V*(s), Q*(s,a), $\\pi*(s)$. Recursive definition of values\\n\n",
        "$V^*(s) = \\max_a Q^*(s,a)$ \\n\n",
        "$Q^*(s,a) = \\sum_s T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ \\n\n",
        "Bellman equation: $V_k+1 (s) = \\max_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ -> Repeat until convergence and each step has time complexity $O(S^2 A)$ \\n\n",
        "Downsides of value iteration- it is slow as it repeats the bellman updates, the max at each state rarely changes (i.e. value changes but the policy converges way early)\n",
        "In policy evaluation actions are easier to choose from Q-values rather than values. Policy iteration has two steps (1)Policy Evaluation (2)Policy Improvement . Comparison between policy and value iteration. Value iteration updates \\\n",
        "both values and policy but we dont track is explicitly however taking a max computes it implicitly. In policy iterations, several passes are done that updates utilities with fixed policy. After each pass of evaluation, new policy is chosen. \\\n",
        "If new policy is better, it is chosen or else the optimal policy is found. So, to compute optimal values, either value iteration or policy iteration is used. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"Goal-based agent\": \"has binary distinction into bad(non-goal) and good(goal) states\",\n",
        "\"Decision-theoretic agent\":\"Chooses better state based on continuous range of values assigned to states\",    \n",
        "\"utility function\" : \"a value that indicates the desirability of the of a state\",\n",
        "\"expected utility\" : \"sum of utility value of the outcomes weighted by the probability that the outcomes occurs as a result of chosen action\",\n",
        "\"Maximum Expected utility (MEU)\":\" The principle states that the agent chooses an action that maximizes its expected utility\",\n",
        "\"Expected utility of a lottery\":\"Sum of the utility of each outcome weighted by the probability of that outcome\",\n",
        "\"Preference Elicitation\":\"Identifying the underlying utility function from the observed preferences based on the choices presented to human\",\n",
        "\"micromort\":\"one in a million chance of death\",\n",
        "\"$V^*(s)$\":\"expected utility by acting optimally and starting in s\",\n",
        "\"$Q^*(s,a)$\":\"expected utility starting out having taken action a from state s and acting optimally\",\n",
        "\"$\\pi*(s)$\":\"optimal action from state s\",\n",
        "\"Policy evaluation\":\"computes values for a chosen policy\",\n",
        "\"Policy Extraction\": \"Converts values into policy\",\n",
        "\"Non-stationary policy\":\"A policy that depends on the remaining time(finite horizon)\",\n",
        "\"Stationary policy\":\"A policy whose optimal action depends only on the current state and not time\",\n",
        "\"Proper policy\":\"policy guranteed to reach terminal state\",\n",
        "\"Policy evaluation\":\"calculating the policy of each state based on the policy to be executed\",\n",
        "\"Policy Improvement\":\"Calculate new MEU policy based on the utility calculated in policy evaluation with one-step look-ahead \",\n",
        "\"Asynchronous policy iteration\":\"Pick a subset of states and apply either (policy improvement or simplified value-iteration)to that subset\",\n",
        "\"Real-time Dynamic Programming(RTDP)\":\"\",\n",
        "\"Preference elicitation\": \"involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\",\n",
        "\"Expected monetary value\":\"summation of (probability*utility)\",\n",
        "\"\":\"\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 22,
      "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": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "28770ce0-f8e6-4147-dec3-45c6ec3d2b71"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision theory assume the environmnt to be episodic and the actions are based on the desirability of the immediate outcomes.  $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 Six constraints that we require an resonable preference relation to obey.\n1. Orderabiity\n2. Transitivity\n3. Continuity\n4. Substitutability\n5. Monotonicity\n6. Decomposability \n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions map lotteries to real numbers. Measurements of utility are: Utility of money: We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money. \n\nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act. The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. The difference between the EMV of a lottery and its certainty equivalent is called insurance.  This tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse. Can be avoided using Bayesian Priors.\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n A remarkable consequence of using discounted utilities with infinite horizons is that the optimal policy is independent of the starting state. There is a direct relationship between the utility of a state and that of its neighbors i.e. the utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action. This called Ballman equation. Shaping theorem staes that the following transformation leaves the optimal policy unchanged. $R′(s,a,s′) = R(s,a,s′) +γΦ(s′)−Φ(s)$. All policies are optimal with zero reward functin everywhere. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nFour algorithms for solving MDPs are explained which are (1)Value iteration (2)Policy iteration (3)Linear Programming (4)Monte Carlo Planning. The first three genrate exact offline solutions whereas the fourth genrates approximate online solutions. Each step of iteration in Value iteration is called Bellman update. The convergence of value iteration is shown using contraction. Bellman update is a contraction by a factor $\\gamma$ in the space of utility vectors. Value iteration. \nPolicy iteration alternates between two steps beginning from some initial policy, policy evaluation followed by policy improvement. Time complexity of policy iteration is $O(S^3)$. After certain steps of policy iteration, the bellman update equation can be modified to do simplified value iteration (simplified as since the policy is fixed, the transition model is only a probability now). This is called Modified policy iteration. \n\nLinear Programming is solvable in polynomial time. \n\n## Module 8 Lecture Notes\nThe stochastic transition models are written as T(s,a,s') or as probability p(s'|s,a). The fact that we are ignoring the history of the steps taken indicates that we are in the Marovian part of the Markov model.MDPs are sequential decision problems in a fully observable environment with a stochastic transition with additive rewards and are non-deterministic search problems and solved using expectimax. Solution to MDPs require, a set of states, set of actions Transition function (probability model), Reward function, initial state and optionally terminal states. The solution to MDP is a POLICY, Policy takes in the current state and tels the agent what action to take. $\\pi(s) = a$ Best policy is denoted by $\\pi*$. Best policy depends on reward functions.Same policy executed multiple times may result in different sequence of states and actions. Reward function will determine the optimal policy. Utility function depends on the environment history. Infinite rewards avoids exits and leads to infite horizon game. Rewards now are preferred over rewards later and hence future rewards are discounted and also helps algorithm converge. Solution to infinite utilities: (1)Finite-horizon (2)Discounting (3)Absorbing-state. Optimal quantities - V*(s), Q*(s,a), $\\pi*(s)$. Recursive definition of values\n\n$V^*(s) = \\max_a Q^*(s,a)$ \n\n$Q^*(s,a) = \\sum_s T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ \n\nBellman equation: $V_k+1 (s) = \\max_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ -> Repeat until convergence and each step has time complexity $O(S^2 A)$ \n\nDownsides of value iteration- it is slow as it repeats the bellman updates, the max at each state rarely changes (i.e. value changes but the policy converges way early)\nIn policy evaluation actions are easier to choose from Q-values rather than values. Policy iteration has two steps (1)Policy Evaluation (2)Policy Improvement . Comparison between policy and value iteration. Value iteration updates both values and policy but we dont track is explicitly however taking a max computes it implicitly. In policy iterations, several passes are done that updates utilities with fixed policy. After each pass of evaluation, new policy is chosen. If new policy is better, it is chosen or else the optimal policy is found. So, to compute optimal values, either value iteration or policy iteration is used. \n\n\n## Module 8 Definitions\n* **Goal-based agent** - has binary distinction into bad(non-goal) and good(goal) states\n* **Decision-theoretic agent** - Chooses better state based on continuous range of values assigned to states\n* **Utility function** - a value that indicates the desirability of the of a state\n* **Expected utility** - sum of utility value of the outcomes weighted by the probability that the outcomes occurs as a result of chosen action\n* **Maximum expected utility (meu)** -  The principle states that the agent chooses an action that maximizes its expected utility\n* **Expected utility of a lottery** - Sum of the utility of each outcome weighted by the probability of that outcome\n* **Preference elicitation** - Identifying the underlying utility function from the observed preferences based on the choices presented to human\n* **Micromort** - one in a million chance of death\n* **$v^*(s)$** - expected utility by acting optimally and starting in s\n* **$q^*(s,a)$** - expected utility starting out having taken action a from state s and acting optimally\n* **$\\pi*(s)$** - optimal action from state s\n* **Policy evaluation** - calculating the policy of each state based on the policy to be executed\n* **Policy extraction** - Converts values into policy\n* **Non-stationary policy** - A policy that depends on the remaining time(finite horizon)\n* **Stationary policy** - A policy whose optimal action depends only on the current state and not time\n* **Proper policy** - policy guranteed to reach terminal state\n* **Policy improvement** - Calculate new MEU policy based on the utility calculated in policy evaluation with one-step look-ahead \n* **Asynchronous policy iteration** - Pick a subset of states and apply either (policy improvement or simplified value-iteration)to that subset\n* **Real-time dynamic programming(rtdp)** - \n* **Preference elicitation** - involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n* **Expected monetary value** - summation of (probability*utility)\n* **** - \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 =  \"\"\"Definition of Bandit problems \\n\n",
        "Gittins index (in handwritten notes). It provides very simple optimal policy for bandit problem i.e. pull th earm that has the highest gittins index followed by updating the Gittins index. Optimal first iteration calculation \\\n",
        "time complexity $O(n)$ and following decisions in $O(1)$. Approximately optimal policies use two methods to select an arm. The first method is by using Upper Confidence Bonds (UCB). Thsi uses confidence interval i.e. a range \\\n",
        "within which the value can be estimated to lie with high confidence. Chose an arm that has the highest upper bound in the confidence interval where the The upper bound is the current mean value estimate $μ_i$ plus some multiple \\\n",
        "of the standard deviation of the uncertainty in the value The standard deviation is proportional to $\\sqrt{1/N_i}$, where $N_i$ is the number of times arm $M_i$ has been sampled. So we have an approximate index value for arm \\\n",
        "$M_i$ given by \\n\n",
        "$UCB(M_i) = μ_i + g(N)/\\sqrt{N_i}$ \\n\n",
        "where g(N) is an appropriately chosen function of N, the total number of samples drawn from all arms. A UCB policy simply picks the arm with the highest UCB value. \\n\n",
        "Second method is Thompson sampling which chooses the arm randomly based on the probability that the arm is optimal. Suppose that $P_i(μ_i)$ is the current probability distribution for the true value of arm $M_i$. Then \\\n",
        "a simple way to implement Thompson sampling is to generate one sample from each $P_i$ and then pick the best sample. This algorithm also has a regret that grows as $O(logN)$.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Two approaches of RL \\n\n",
        "(1) Model-based - Agent uses transition models of the environment to interpret the reward signals \\n\n",
        "(2) Model-free RLAgent has no info of transition model nor learns it. It learns  a more direct representation of how to behave. There are two varieties of model-fere RL \\n\n",
        "(a) Action-utility learning- Agent learns the Q-function. It is also called as Q-learning \\n\n",
        "(b) Policy search- A policy is learnt that maps actions t states\"\"\"\n",
        "chapter22_2 =  \"\"\"**Direct Utiliy Estimation's** idea is that the utility of a state is defined as the expected estimation Reward-to-go total reward from that state onward (called the expected reward-to-go), and that each \\\n",
        "trial provides a sample of this quantity for each state visited. This RL technique is reduced to a suprvised learning problem by it ignores an important constraint that The utility of a state is determined by the reward \\\n",
        "and the expected utility of the successor states. By ignoring the connections between states, DUE misses opportunity for learning and so often coverges slowly. \\n\n",
        "**Adaptive Dynamic Programming** takes advantages of the connections/constraints between states by learning transition model that connects them and solving the corresponding MDP i.e. calculating the utilities of the state \\\n",
        "from the learned transition model and reward function. \\n\n",
        "**temporal-difference learning** (basic explanation in summary)\n",
        "ADP and TD are closely related but as both try to make local adjustments t utility estimates in order to make each state agree with its successor. However, the difference is that \\\n",
        "TD adjusts to agree with its observed successor whereas ADP adjusts the state to agree with all of the successors. that might occur, weighted by their probabilities. Moreover, \\\n",
        "TD makes only one adjustment per transition, ADP makes as many as it needs to restore consistency between the utility estimates U and the transition model P. Although the observed \\\n",
        "transition makes only a local change in P, its effects might need to be propagated throughout U. Thus, TD can be viewed as a crude but efficient first approximation to ADP. \\n\n",
        "**Prioritized sweeping heuristic** prefers prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates\"\"\"\n",
        "chapter22_3 =  \"\"\"Active RL has to find out the policy along with the expected utilities. This can be done using the ADP wher the first step is to find out the utilities followed by choosing the optimal policy by finding \\\n",
        "path with max utility by one-step look ahead. \\n\n",
        "**Exploration** \\n\n",
        "A greedy agent after certain steps finds out  apositive reward and thus finds ou the optimal path based on the learned model of the environment but this might not be the optimal solution. This optimal policy leading to \\\n",
        "sub-optimal solution is due to the fact that the learned environment is not the true environment. And so the agent needs to perform exploration. So agent must not be greedy in terms of immediate next move but must be \\\n",
        "GLIE (Greedy in limit of Infinite Exploration). i.e. GLIE scheme must try each state unbounded number of times so as to avoid the chance of having optimal action being missed. Examples of GLIE schemes \\n\n",
        "(1)Choose a random action at time step t with probability $1/t$ and to follow greedy policy otherwise \\n\n",
        "(2)More weight given to actions visted less frequently  and less to actions that have low utility. This results in optimistic prior over the possible environments and causes the agent to behave initially as if there \\\n",
        "were wonderful rewards scattered all over the place.\n",
        "**Temporal-difference Q-Learning** \"\"\"\n",
        "chapter22_4 =  \"\"\"Catastrophic forgetting: the tendency of an artificial neural network to completely and abruptly forget previously learned information upon learning new information. One solution to this problem, \\\n",
        "called experience replay, forces the network to make the mistake so that it remembers.Reward Shaping: One common method, originally used in animal training, is called reward shaping. This involves supplying the agent \\\n",
        "with additional rewards, called pseudorewards, for “making progress.”\n",
        "Hierarchical reinforcement learning:\n",
        "Another way to cope with very long action sequences is to break them up into a few smaller pieces, and then break those into smaller pieces still, and so on until the action sequences are short enough to make learning easy.\n",
        "The hierarchical structure of behavior also provides a natural additive decomposition of the overall utility function.\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"Basic idea of RL - feedback perceived as reward, reward function defines agent's utility, actions must be driven by idea to maximize expected rewards and all \\\n",
        "all learning is based on observed samples of outcomes. RL still looks for a policy as solution($\\pi(s)$). RL is a type of MDP with known states($s$) and actions($a$) but unknown \\\n",
        "transition model(T) or reward function(R).  The lecture talked about two different types of learning for RL (1)Model-based Learning (2)Model-free learing. In passive RL, someone \\\n",
        "chooses policy for us and try to figure out how good is the policy and is thus similar to policy evaluation. So we have policy as input with a goal of learning the states and no \\\n",
        "information on transition model or rewards. Direct evaluation is the process whose goal is to computes the values for each state under policy. This is done by acting according \\\n",
        "to the policy adn noting down the sum of discounted rewards everytime a state is reached and then averaging those out. Pros of direct evaluation-easy to understand, no knowledge \\\n",
        "of R and T required, and computes correct average value of states. Cons- wastes info of connection between states, all states are to be learned separately and thus takes more time.\\\n",
        "Sampled based policy evaluation doesnt work in RL as there is no gurantee that we will land up in a state(s) n times if n samples are taken. Temporal Difference Learning idea is \\\n",
        "to keep learning from each experience i.e. to update V(s) every time a transition is experienced. It involves exponential moving average where it forgets about the distant past \\\n",
        "values which is justified as the initial estimates were way off. Decreasing learning rates can give converging solutions. Updated Bellman equation for TemporalDifferenceLearning is \\n\n",
        "$ V^{\\pi(s)} = (1 - a)*V^{\\pi(s)} + a[R(s,\\pi(s),s') + \\gamma V^{\\pi(s')}]$ \\n\n",
        "TD learning is model-free RL technique to do policy evaluation mimicking Bellman Updates with running sample averages. But to select a policy, we need Q-values and not the values \\\n",
        "of states. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Exploration\" : \"randomly tring out actions to get information\",\n",
        "\"Explotation\":\"exploiting the already available information to do what is considered to be the best policy\",\n",
        "\"Regret\":\"Mistakes made even on learning intelligently and leading to sub-optimal policy\",\n",
        "\"Sampling\":\"Performing actions multiple times due to chance(stochastic environment) associated with actions\",\n",
        "\"Difficulty\":\"Much harder than MDP as not all information is given\",\n",
        "\"Passive RL\":\"Agent's task is to learn the utilities of the state or a model of the environment where its policy is fixed\",\n",
        "\"Active RL\":\"Along with learning utilities of the states, it must also figure out policy\",\n",
        "\n",
        "}"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "ydOK__lwWgdp",
        "outputId": "c26e9822-b6d7-4531-9286-6476fc8235ab"
      },
      "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": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nDefinition of Bandit problems \n\nGittins index (in handwritten notes). It provides very simple optimal policy for bandit problem i.e. pull th earm that has the highest gittins index followed by updating the Gittins index. Optimal first iteration calculation time complexity $O(n)$ and following decisions in $O(1)$. Approximately optimal policies use two methods to select an arm. The first method is by using Upper Confidence Bonds (UCB). Thsi uses confidence interval i.e. a range within which the value can be estimated to lie with high confidence. Chose an arm that has the highest upper bound in the confidence interval where the The upper bound is the current mean value estimate $μ_i$ plus some multiple of the standard deviation of the uncertainty in the value The standard deviation is proportional to $\\sqrt{1/N_i}$, where $N_i$ is the number of times arm $M_i$ has been sampled. So we have an approximate index value for arm $M_i$ given by \n\n$UCB(M_i) = μ_i + g(N)/\\sqrt{N_i}$ \n\nwhere g(N) is an appropriately chosen function of N, the total number of samples drawn from all arms. A UCB policy simply picks the arm with the highest UCB value. \n\nSecond method is Thompson sampling which chooses the arm randomly based on the probability that the arm is optimal. Suppose that $P_i(μ_i)$ is the current probability distribution for the true value of arm $M_i$. Then a simple way to implement Thompson sampling is to generate one sample from each $P_i$ and then pick the best sample. This algorithm also has a regret that grows as $O(logN)$.\n\n## AIMA Chapter 22.1 Learning from Rewards\n Two approaches of RL \n\n(1) Model-based - Agent uses transition models of the environment to interpret the reward signals \n\n(2) Model-free RLAgent has no info of transition model nor learns it. It learns  a more direct representation of how to behave. There are two varieties of model-fere RL \n\n(a) Action-utility learning- Agent learns the Q-function. It is also called as Q-learning \n\n(b) Policy search- A policy is learnt that maps actions t states\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n**Direct Utiliy Estimation's** idea is that the utility of a state is defined as the expected estimation Reward-to-go total reward from that state onward (called the expected reward-to-go), and that each trial provides a sample of this quantity for each state visited. This RL technique is reduced to a suprvised learning problem by it ignores an important constraint that The utility of a state is determined by the reward and the expected utility of the successor states. By ignoring the connections between states, DUE misses opportunity for learning and so often coverges slowly. \n\n**Adaptive Dynamic Programming** takes advantages of the connections/constraints between states by learning transition model that connects them and solving the corresponding MDP i.e. calculating the utilities of the state from the learned transition model and reward function. \n\n**temporal-difference learning** (basic explanation in summary)\nADP and TD are closely related but as both try to make local adjustments t utility estimates in order to make each state agree with its successor. However, the difference is that TD adjusts to agree with its observed successor whereas ADP adjusts the state to agree with all of the successors. that might occur, weighted by their probabilities. Moreover, TD makes only one adjustment per transition, ADP makes as many as it needs to restore consistency between the utility estimates U and the transition model P. Although the observed transition makes only a local change in P, its effects might need to be propagated throughout U. Thus, TD can be viewed as a crude but efficient first approximation to ADP. \n\n**Prioritized sweeping heuristic** prefers prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nActive RL has to find out the policy along with the expected utilities. This can be done using the ADP wher the first step is to find out the utilities followed by choosing the optimal policy by finding path with max utility by one-step look ahead. \n\n**Exploration** \n\nA greedy agent after certain steps finds out  apositive reward and thus finds ou the optimal path based on the learned model of the environment but this might not be the optimal solution. This optimal policy leading to sub-optimal solution is due to the fact that the learned environment is not the true environment. And so the agent needs to perform exploration. So agent must not be greedy in terms of immediate next move but must be GLIE (Greedy in limit of Infinite Exploration). i.e. GLIE scheme must try each state unbounded number of times so as to avoid the chance of having optimal action being missed. Examples of GLIE schemes \n\n(1)Choose a random action at time step t with probability $1/t$ and to follow greedy policy otherwise \n\n(2)More weight given to actions visted less frequently  and less to actions that have low utility. This results in optimistic prior over the possible environments and causes the agent to behave initially as if there were wonderful rewards scattered all over the place.\n**Temporal-difference Q-Learning** \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nCatastrophic forgetting: the tendency of an artificial neural network to completely and abruptly forget previously learned information upon learning new information. One solution to this problem, called experience replay, forces the network to make the mistake so that it remembers.Reward Shaping: One common method, originally used in animal training, is called reward shaping. This involves supplying the agent with additional rewards, called pseudorewards, for “making progress.”\nHierarchical reinforcement learning:\nAnother way to cope with very long action sequences is to break them up into a few smaller pieces, and then break those into smaller pieces still, and so on until the action sequences are short enough to make learning easy.\nThe hierarchical structure of behavior also provides a natural additive decomposition of the overall utility function.\n\n\n## Module 9 Lecture Notes\nBasic idea of RL - feedback perceived as reward, reward function defines agent's utility, actions must be driven by idea to maximize expected rewards and all all learning is based on observed samples of outcomes. RL still looks for a policy as solution($\\pi(s)$). RL is a type of MDP with known states($s$) and actions($a$) but unknown transition model(T) or reward function(R).  The lecture talked about two different types of learning for RL (1)Model-based Learning (2)Model-free learing. In passive RL, someone chooses policy for us and try to figure out how good is the policy and is thus similar to policy evaluation. So we have policy as input with a goal of learning the states and no information on transition model or rewards. Direct evaluation is the process whose goal is to computes the values for each state under policy. This is done by acting according to the policy adn noting down the sum of discounted rewards everytime a state is reached and then averaging those out. Pros of direct evaluation-easy to understand, no knowledge of R and T required, and computes correct average value of states. Cons- wastes info of connection between states, all states are to be learned separately and thus takes more time.Sampled based policy evaluation doesnt work in RL as there is no gurantee that we will land up in a state(s) n times if n samples are taken. Temporal Difference Learning idea is to keep learning from each experience i.e. to update V(s) every time a transition is experienced. It involves exponential moving average where it forgets about the distant past values which is justified as the initial estimates were way off. Decreasing learning rates can give converging solutions. Updated Bellman equation for TemporalDifferenceLearning is \n\n$ V^{\\pi(s)} = (1 - a)*V^{\\pi(s)} + a[R(s,\\pi(s),s') + \\gamma V^{\\pi(s')}]$ \n\nTD learning is model-free RL technique to do policy evaluation mimicking Bellman Updates with running sample averages. But to select a policy, we need Q-values and not the values of states. \n\n\n\n## Module 9 Definitions\n* **Exploration** - randomly tring out actions to get information\n* **Explotation** - exploiting the already available information to do what is considered to be the best policy\n* **Regret** - Mistakes made even on learning intelligently and leading to sub-optimal policy\n* **Sampling** - Performing actions multiple times due to chance(stochastic environment) associated with actions\n* **Difficulty** - Much harder than MDP as not all information is given\n* **Passive rl** - Agent's task is to learn the utilities of the state or a model of the environment where its policy is fixed\n* **Active rl** - Along with learning utilities of the states, it must also figure out policy\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 = \"\"\"Belief state is a representation of all possible states that the agent might be in as well as all the contingency plan in case of eventuality. Drawbacks of belief state are \\n\n",
        "(1)Agent must consider all possible explanation of its perceptions thus generating large belief state with unlikely possibilities \\n\n",
        "(2)Correct contingency plan may grow very large \\n\n",
        "(3)Sometimes there maybe no plan to achievegoal. \\n\n",
        "$Decision theory = probability theory + utility theory$ - The decision theory states that an agent is rational only if it choses an action that yields the highest expected utility which are averaged over all \\\n",
        "possible outcomes that result from an action. Tis principal is called Maximum Expected Utility(MEU). \\n\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\"Unconditional probabilities are also called prior probabilities. Conditional probability is also called posterior probability.\\n\n",
        "**Categorical Distribution** Probability Distribution that is finite and discrete range. \\n\n",
        "**Probability density function** Probability distribution that has continuous and takes infinitely many values. \\n\n",
        "A possible world is defined to be an assignment of values to all of the random variables under consideration.\"\"\"\n",
        "chapter12_3 = \"\"\"probabilistic inference—that is, the computation of posterior probabilities for query propositions given observed evidence. We use the full joint distribution as the “knowledge base” \\\n",
        "from which answers to all questions may be derived\"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\"$P(cause | effect) = {P(effect | cause)P(cause)}/P(effect)$ \\n\n",
        "Causal direction - $P(effect|cause)$ and diagnostic direction - $P(cause|effect)$. Diagnostic knowledge is often more fragile than causal knowledge\"\"\"\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 = \"\"\" \"\"\"\n",
        "SLP_chapter3_2 = \"\"\"The best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation.\n",
        "An intrinsic evaluation metric is one that measures the quality of a model independent of any application. In practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. \\\n",
        "The perplexity (PP) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. (equation of perplexity in hand-written notes).\n",
        "Thus, minimizing perplexity is equivalent to maximizing the test set probability according to the language model.As we see above, the more information the n-gram gives us about the word sequence, the lower the perplexity. \\\n",
        "(perplexity is related inversely to the likelihood of the test sequence according to the model).\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\"One step is to be sure to use a training corpus that has a similar genre to whatever task we are trying to accomplish. It is equally important to get training data in the appropriate dialect or variety, \\\n",
        "especially when processing social media posts or spoken transcripts. Matching genres and dialects is still not sufficient. Our models may still be subject to the problem of sparsity. Following are the ways to deal with Out of \\\n",
        "Vocabulory problems: \\n\n",
        "(1)Choose a word list that is fixed in advance (2)Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step (3)Estimate the probabilities from its counts just \\\n",
        "like any other regular word in the training set\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"Laplace smoothing- Done to avoid 0 probability cases. K smoothing- modification to laplace so as to reduce the bias. adding k=0.5,0.05,.. \\\n",
        "interpolation, probability estimates from all the n-gram estimators are mixed, weighing and combining the trigram, bigram, and unigram counts. If higher order are not available then back-off helps use lower order n-gram.\\\n",
        "Katz Backoff: In order for a backoff model to give a correct probability distribution, we have to discount the higher-order n-grams to save some probability mass for the lower order n-grams.Katz backoff is often combined \\\n",
        "with a smoothing method called Good-Turing. The combined Good-Turing backoff algorithm involves quite detailed computation for estimating the Good-Turing smoothing and the P ∗ and α values\"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"Possible world based on the probabilities are called sample space. They are mutually exclusive and exhaustive. Axioms of probability (1)Probability of any possible world is between 0 and 1. \n",
        "(2) Total probability of set of all possible world is 1. Size of distribution of n random variables with domain size d is $d^n$. Following are key sub parts of probabilistic models: (1)Domains - Each random variable can take \n",
        "a set of values called as the domain of the random variable (2)Outcomes- Set of assignments of values to variables (3)Joint distribution- How likely a set of assignments are (4)Normalized - sum of probabilities is equal to 1 \n",
        "(5)Ideally not many variables interact with each other. \n",
        "Conditional Probability distributions are one of the most important distributions as it tells us information about things that we didn't observe. $P(a|b) = P(a,b)/P(b)$. \\n\n",
        "Inference by enumeration - Evidence variable (values known), Querry variables (variables we care about), Hidden variables. Three steps to follow \\n\n",
        "(1)Select entries consistent with evidence. \\n\n",
        "(2)Get joint distribution of query and evidence by summing out H $P(Q,e_1,e_2, ...e_k) = \\sum_h P(Q,h_1,...,h_r,e_1...e_k)$. \\n\n",
        "(3)Normalize $Z = \\sum_q P(Q,e_1...e_k)$ then, $P(Q|e_1...e_k) = (1/Z)*P(Q,e_1...e_k)$ \\n\n",
        "Produce Rule - $P(y)P(x|y) = P(x,y)$ \\n\n",
        "Chain Rule - $P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$ \\n\n",
        "Bayes' Rule - $P(y)P(x|y) = P(x,y) = P(x)P(y|x)$ so, $P(x|y) = P(y|x)P(x)/P(y)$ \\n\n",
        "Probabilistic Language models examples autocomplete for texting, machine translation, spelling correction, speech recognition and other NL generation tasks incude summarization, question-answering, dialog systems.\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Observed variables (evidence)\" : \"Information know to the agent about the world\",\n",
        "\"Unobserved variables (states)\": \"Reasoning about certain aspects needs to be done by the agent\",\n",
        "\"Model\":\"Information known by agent on how evidence is related to the state\",\n",
        "\"Probabilistic model\":\"Joint distribution over a set of random variables of the world\",\n",
        "\"Event\":\"It is a set of possible outcomes\",\n",
        "\"Joint probability distributions\":\"Probability distributions that are based on the combination of multiple variables\",\n",
        "\"Marginal Distributions\":\"Sub sets of joint distribution with eliminated variables that are not important\",\n",
        "\"Marginalization\":\"Summing out useless rows to form marginalized distribution from joint distribution\",\n",
        "\"Conditinal Probability Distribution\":\"Probability distributions of a random variable given fixed value of other random variable\",\n",
        "\"Probabilistic Inference\":\"Infer probability of a desired outcome from other known probabiliies\",\n",
        "\"Unigram\":\"no history\",\n",
        "\"Bigram\":\"1 word history\",\n",
        "\"Trigram\":\"2 word history\",\n",
        "\"n-gram\":\"N-1 word history\", \n",
        "\"Ontological commitments\":\"\",\n",
        "\"Epistemological commitments\":\"\",\n",
        "}"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "be332561-d435-47d9-db70-84e06a8feb7d"
      },
      "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\nBelief state is a representation of all possible states that the agent might be in as well as all the contingency plan in case of eventuality. Drawbacks of belief state are \n\n(1)Agent must consider all possible explanation of its perceptions thus generating large belief state with unlikely possibilities \n\n(2)Correct contingency plan may grow very large \n\n(3)Sometimes there maybe no plan to achievegoal. \n\n$Decision theory = probability theory + utility theory$ - The decision theory states that an agent is rational only if it choses an action that yields the highest expected utility which are averaged over all possible outcomes that result from an action. Tis principal is called Maximum Expected Utility(MEU). \n\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\nUnconditional probabilities are also called prior probabilities. Conditional probability is also called posterior probability.\n\n**Categorical Distribution** Probability Distribution that is finite and discrete range. \n\n**Probability density function** Probability distribution that has continuous and takes infinitely many values. \n\nA possible world is defined to be an assignment of values to all of the random variables under consideration.\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nprobabilistic inference—that is, the computation of posterior probabilities for query propositions given observed evidence. We use the full joint distribution as the “knowledge base” from which answers to all questions may be derived\n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n$P(cause | effect) = {P(effect | cause)P(cause)}/P(effect)$ \n\nCausal direction - $P(effect|cause)$ and diagnostic direction - $P(cause|effect)$. Diagnostic knowledge is often more fragile than causal knowledge\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 \n\n## SLP Chapter 3.2 Evaluating Language Models\nThe best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation.\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application. In practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (PP) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. (equation of perplexity in hand-written notes).\nThus, minimizing perplexity is equivalent to maximizing the test set probability according to the language model.As we see above, the more information the n-gram gives us about the word sequence, the lower the perplexity. (perplexity is related inversely to the likelihood of the test sequence according to the model).\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\nOne step is to be sure to use a training corpus that has a similar genre to whatever task we are trying to accomplish. It is equally important to get training data in the appropriate dialect or variety, especially when processing social media posts or spoken transcripts. Matching genres and dialects is still not sufficient. Our models may still be subject to the problem of sparsity. Following are the ways to deal with Out of Vocabulory problems: \n\n(1)Choose a word list that is fixed in advance (2)Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step (3)Estimate the probabilities from its counts just like any other regular word in the training set\n\n## SLP Chapter 3.5 Smoothing\nLaplace smoothing- Done to avoid 0 probability cases. K smoothing- modification to laplace so as to reduce the bias. adding k=0.5,0.05,.. interpolation, probability estimates from all the n-gram estimators are mixed, weighing and combining the trigram, bigram, and unigram counts. If higher order are not available then back-off helps use lower order n-gram.Katz Backoff: In order for a backoff model to give a correct probability distribution, we have to discount the higher-order n-grams to save some probability mass for the lower order n-grams.Katz backoff is often combined with a smoothing method called Good-Turing. The combined Good-Turing backoff algorithm involves quite detailed computation for estimating the Good-Turing smoothing and the P ∗ and α values\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\nPossible world based on the probabilities are called sample space. They are mutually exclusive and exhaustive. Axioms of probability (1)Probability of any possible world is between 0 and 1. \n(2) Total probability of set of all possible world is 1. Size of distribution of n random variables with domain size d is $d^n$. Following are key sub parts of probabilistic models: (1)Domains - Each random variable can take \na set of values called as the domain of the random variable (2)Outcomes- Set of assignments of values to variables (3)Joint distribution- How likely a set of assignments are (4)Normalized - sum of probabilities is equal to 1 \n(5)Ideally not many variables interact with each other. \nConditional Probability distributions are one of the most important distributions as it tells us information about things that we didn't observe. $P(a|b) = P(a,b)/P(b)$. \n\nInference by enumeration - Evidence variable (values known), Querry variables (variables we care about), Hidden variables. Three steps to follow \n\n(1)Select entries consistent with evidence. \n\n(2)Get joint distribution of query and evidence by summing out H $P(Q,e_1,e_2, ...e_k) = \\sum_h P(Q,h_1,...,h_r,e_1...e_k)$. \n\n(3)Normalize $Z = \\sum_q P(Q,e_1...e_k)$ then, $P(Q|e_1...e_k) = (1/Z)*P(Q,e_1...e_k)$ \n\nProduce Rule - $P(y)P(x|y) = P(x,y)$ \n\nChain Rule - $P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$ \n\nBayes' Rule - $P(y)P(x|y) = P(x,y) = P(x)P(y|x)$ so, $P(x|y) = P(y|x)P(x)/P(y)$ \n\nProbabilistic Language models examples autocomplete for texting, machine translation, spelling correction, speech recognition and other NL generation tasks incude summarization, question-answering, dialog systems.\n\n\n\n## Module 10 Definitions\n* **Observed variables (evidence)** - Information know to the agent about the world\n* **Unobserved variables (states)** - Reasoning about certain aspects needs to be done by the agent\n* **Model** - Information known by agent on how evidence is related to the state\n* **Probabilistic model** - Joint distribution over a set of random variables of the world\n* **Event** - It is a set of possible outcomes\n* **Joint probability distributions** - Probability distributions that are based on the combination of multiple variables\n* **Marginal distributions** - Sub sets of joint distribution with eliminated variables that are not important\n* **Marginalization** - Summing out useless rows to form marginalized distribution from joint distribution\n* **Conditinal probability distribution** - Probability distributions of a random variable given fixed value of other random variable\n* **Probabilistic inference** - Infer probability of a desired outcome from other known probabiliies\n* **Unigram** - no history\n* **Bigram** - 1 word history\n* **Trigram** - 2 word history\n* **N-gram** - N-1 word history\n* **Ontological commitments** - \n* **Epistemological commitments** - \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 = \"\"\" Specification of Bayesian Network: \\n\n",
        "(1)Each node indicates a discrete or continuous random variable \\n\n",
        "(2)Directed arrows connect pair of nodes and there are no cycle of directed arrows formed \\n\n",
        "(3)Each node has an associated probability information $P(X_i|Parents(X_i))$\"\"\"\n",
        "chapter13_2 = \"\"\"Bayes Nets is complete and non-redundant representation of the domain. It can be far more compact than full joint distribution. Compactness of BNs is an example of \\\n",
        "genral property of locally structured(sparse) systems. In locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless \\\n",
        "of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity. General non-descendants property states that \\\n",
        "Each variable is conditionally independent of its non-descendants given its parents. Non-descendants property combined with interpretation of the network parameters \\\n",
        "$θ(X_i|Parents(X_i))$ as conditional probabilities $P(X_i|Parents(X_i))$ suffices to reconstruct the full joint distribution. Also, a variable is conditionally independent of \\\n",
        "all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket.\"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"X and Y are independent -> $P(x,y) = P(x)P(y)$. X and Y are conditionally independent given Z $P(x,y|z) = P(x|z)P(y|z)$\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian network\" : \"A directed graph where quantitative probability information is annotated on each node\", \n",
        "\"Topological order\":\"Order consistent with directed graph structure\",   \n",
        "}\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 597
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "b2f04cb4-7037-4d75-e1a0-1ccfa55550c1"
      },
      "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 Specification of Bayesian Network: \n\n(1)Each node indicates a discrete or continuous random variable \n\n(2)Directed arrows connect pair of nodes and there are no cycle of directed arrows formed \n\n(3)Each node has an associated probability information $P(X_i|Parents(X_i))$\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nBayes Nets is complete and non-redundant representation of the domain. It can be far more compact than full joint distribution. Compactness of BNs is an example of genral property of locally structured(sparse) systems. In locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity. General non-descendants property states that Each variable is conditionally independent of its non-descendants given its parents. Non-descendants property combined with interpretation of the network parameters $θ(X_i|Parents(X_i))$ as conditional probabilities $P(X_i|Parents(X_i))$ suffices to reconstruct the full joint distribution. Also, a variable is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket.\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\nX and Y are independent -> $P(x,y) = P(x)P(y)$. X and Y are conditionally independent given Z $P(x,y|z) = P(x|z)P(y|z)$\n\n## Module 11 Definitions\n* **Bayesian network** - A directed graph where quantitative probability information is annotated on each node\n* **Topological order** - Order consistent with directed graph structure\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 = \"\"\"An agent is learning if it improves its performance after making observations about the world. Performance of a component of agent program can be improved based on the following factors (1) What component to improve \\\n",
        "(2)Evidence it has that influences the model (3)What data and feedback on data is available. \\n\n",
        "Inductive conclusions MAY be correct but deductive conclusions are GURARANTEED to be correct if the premises are correct. \\n\n",
        "Three types of feedback that classify learning problems: (1)Supervised learning that receives input-output pairs where the output is called as label (2)Unsupervised learning - Agent learnd a pattern without any explicit feedback \\\n",
        "Clustering is an example (3)Reinforcement Learning- Rewards and punishments help the  agent learn.\"\"\"\n",
        "chapter19_2 = \"\"\"A training model generates a hypothesis of the actual function . The hyposthesis is drawn from the hypothesis space. The hypothesis is also called model of the data and the hypothesis space is also called the model \\\n",
        "class or a function drawn from a function class. There is atrade-off between bias and variance. \"\"\"\n",
        "chapter19_3 = \"\"\"Decision tree in a representation of a function that gives a single output by mapping a vector of attribute values. \\n\n",
        "Decision tree pruning eliminates nodes that are not relevant and thus helps combat overfitting. Addressing following complications of decision trees can make it more useful (1)Missing data (2)Continuous and multivalued \\\n",
        "input attributes - This can be solved using split point test or equality test. (3) Continuous valued ouput attribute. \\n\n",
        "Decision trees are unstable and if the trees are very deep, then getting a prediction for a new example can be very expensive. It can also have sub-optial accuracy. Also, adding one new example can change the test at root.\"\"\"\n",
        "chapter19_4 = \"\"\"k-fold crossvalidation is used when the there isn't enough data to categorize into three classes, training set, validation set and test set. So we use some of the training data set as a validation data set. \\n\n",
        "Finding a good hypothesis can be divided into two sub-parts (1) Model selection that chooses a good hypothesis space and (2) Optimization that finds a good hypothesis in that space. \\n\n",
        "Reasons why best hypothesis may differ from true function: (1)Ralizable (2) Variance (3)original function maybe Non-deterministic or noisy (4)Computationally intractable \\n\n",
        "Approaches to tunning a hyperparameter (1)hand-tuning (2)Grid search if there are a small number of parameters with each parameters likely to take only a few possibe set of values (3) Random search. \\n\n",
        "Bayesian optimization considers the process of tuning the parameters as a machine learning problem in itsf. \\n\n",
        "Population-based training (PBT) is an alternative to bayesian optimization it combines random search and then for later generation uses hand-tuning or bayesian optimization.\"\"\"\n",
        "chapter19_5 = \"\"\"Any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC) \\n\n",
        "**Decision lists** resemble decision trees, but their overall structure is simpler: they branch only in one direction.\n",
        "On the other hand, if we restrict the size of each test to at most k literals, then it is possible for the learning algorithm to generalize successfully from a small number of examples. We use the notation k -DL for a decision list with up to k conjunctions\n",
        "\"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"Induction\" : \"Forming a genral rule based on specific set of observations\",\n",
        "\"Factored representation\":\"vector of attributes\",\n",
        "\"Classification\":\"Output is one option from a finite set of options\",\n",
        "\"Regression\":\"When output is a number value and can have infinite values its called regression\",\n",
        "\"Bias\":\"predictive hypothesis's tendency to deviate from the expected value when averaged over different training sets\",\n",
        "\"Variance\":\"Fluctuations in training data cause change in hypothesis. Variance is the amount of this change\",\n",
        "\"Learning curve\":\"Proportion correct on test set v/s training set size\",\n",
        "\"Stationarity assumption\":\"Future examples will be like past\", \n",
        "\"Toxicity detection\":\"task of detecting hate speech, abuse, harassment, or other kinds of toxic language.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "189e557c-ac74-43a7-b142-ae11da912af8"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nAn agent is learning if it improves its performance after making observations about the world. Performance of a component of agent program can be improved based on the following factors (1) What component to improve (2)Evidence it has that influences the model (3)What data and feedback on data is available. \n\nInductive conclusions MAY be correct but deductive conclusions are GURARANTEED to be correct if the premises are correct. \n\nThree types of feedback that classify learning problems: (1)Supervised learning that receives input-output pairs where the output is called as label (2)Unsupervised learning - Agent learnd a pattern without any explicit feedback Clustering is an example (3)Reinforcement Learning- Rewards and punishments help the  agent learn.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nA training model generates a hypothesis of the actual function . The hyposthesis is drawn from the hypothesis space. The hypothesis is also called model of the data and the hypothesis space is also called the model class or a function drawn from a function class. There is atrade-off between bias and variance. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nDecision tree in a representation of a function that gives a single output by mapping a vector of attribute values. \n\nDecision tree pruning eliminates nodes that are not relevant and thus helps combat overfitting. Addressing following complications of decision trees can make it more useful (1)Missing data (2)Continuous and multivalued input attributes - This can be solved using split point test or equality test. (3) Continuous valued ouput attribute. \n\nDecision trees are unstable and if the trees are very deep, then getting a prediction for a new example can be very expensive. It can also have sub-optial accuracy. Also, adding one new example can change the test at root.\n\n## AIMA Chapter 5.5 Stochastic Games\nk-fold crossvalidation is used when the there isn't enough data to categorize into three classes, training set, validation set and test set. So we use some of the training data set as a validation data set. \n\nFinding a good hypothesis can be divided into two sub-parts (1) Model selection that chooses a good hypothesis space and (2) Optimization that finds a good hypothesis in that space. \n\nReasons why best hypothesis may differ from true function: (1)Ralizable (2) Variance (3)original function maybe Non-deterministic or noisy (4)Computationally intractable \n\nApproaches to tunning a hyperparameter (1)hand-tuning (2)Grid search if there are a small number of parameters with each parameters likely to take only a few possibe set of values (3) Random search. \n\nBayesian optimization considers the process of tuning the parameters as a machine learning problem in itsf. \n\nPopulation-based training (PBT) is an alternative to bayesian optimization it combines random search and then for later generation uses hand-tuning or bayesian optimization.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nAny hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC) \n\n**Decision lists** resemble decision trees, but their overall structure is simpler: they branch only in one direction.\nOn the other hand, if we restrict the size of each test to at most k literals, then it is possible for the learning algorithm to generalize successfully from a small number of examples. We use the notation k -DL for a decision list with up to k conjunctions\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Induction** - Forming a genral rule based on specific set of observations\n* **Factored representation** - vector of attributes\n* **Classification** - Output is one option from a finite set of options\n* **Regression** - When output is a number value and can have infinite values its called regression\n* **Bias** - predictive hypothesis's tendency to deviate from the expected value when averaged over different training sets\n* **Variance** - Fluctuations in training data cause change in hypothesis. Variance is the amount of this change\n* **Learning curve** - Proportion correct on test set v/s training set size\n* **Stationarity assumption** - Future examples will be like past\n* **Toxicity detection** - task of detecting hate speech, abuse, harassment, or other kinds of toxic language.\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 = \"\"\" For logistic regression and naive Bayes the combination features or feature interactions have to be designed by hand. Feature templates are also used to create it automatically. Advantages of \\\n",
        "Logistic regression over naive bayes are (1)NB has overly strong consitional independance assumptions (2)Logistic regression is very robst to correlated features so LR wors better on larger datasets. But NB works very well \\\n",
        "n small datasets and very easy and fast to implement.\"\"\"\n",
        "slp_chapter5_2 = \"\"\"Cross entropy loss is used as the loss function.  \"\"\"\n",
        "slp_chapter5_3 = \"\"\"We choose a loss function that prefers the correct class labels of the training examples to be more likely. This is called conditional maximum likelihood \\\n",
        "estimation: we choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x. The resulting loss function is the negative log likelihood loss, generally \\\n",
        "called the cross-entropy loss.\"\"\"\n",
        "slp_chapter5_4 = \"\"\"Aim of gradient descent is to find to optimal weights averaged over all examples to minimize the loss function. (equation in hand-written sheet)\"\"\"\n",
        "slp_chapter5_5 = \"\"\"L2 regulariztion is euclidean distance and also called as ridge regression. L1 regularization is manhattan distance also called as lasso regression\"\"\"\n",
        "slp_chapter5_6 = \"\"\"Cases where more than two classes are required there multinomial logistic regression also called as softmax regression is used. In multinomial logistic regression the target y is a variable that ranges\\\n",
        "over more than two classes. The multinomial logistic classifier uses a generalization of the sigmoid, called softmax the softmax function, to compute the probability $p(y = c|x)$. Loss function in multinomial regression is \\\n",
        "(in hand-written notes)\"\"\"\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 = \"\"\"Most important difference between naive Bayes and logistic regression is that logistic regression is a discriminative classifier while naive Bayes is a generative classifier. Following are \\\n",
        "the components of a ML classifier: \\n\n",
        "(1) Feature Representation (2) Classification function- Sigmoid or Softmax (3)Objective function- Minimizing error (4) Optimization algorithm \\n\n",
        "Sigmoid function along with decision boundary helps in classifying the ouput. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Period disambiguation\" : \"deciding whether a period is the end of sentence or not\", \n",
        "\"Loss function or cost function\":\"Distance between the system output and the gold output\",   \n",
        "\"Feedforward network\":\"architecture in which the computation proceeds iteratively from one layer to the next\",\n",
        "\"Deep learning\":\"modern neural network with more depth\",\n",
        "}\n"
      ],
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "49ade0bc-d6eb-4c5f-c7e1-3f5afd9232d3"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n For logistic regression and naive Bayes the combination features or feature interactions have to be designed by hand. Feature templates are also used to create it automatically. Advantages of Logistic regression over naive bayes are (1)NB has overly strong consitional independance assumptions (2)Logistic regression is very robst to correlated features so LR wors better on larger datasets. But NB works very well n small datasets and very easy and fast to implement.\n\n## SLP Chapter 5.2 Learning in Logistic Regression\nCross entropy loss is used as the loss function.  \n\n## SLP Chapter 5.3 The cross-entropy loss function\nWe choose a loss function that prefers the correct class labels of the training examples to be more likely. This is called conditional maximum likelihood estimation: we choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x. The resulting loss function is the negative log likelihood loss, generally called the cross-entropy loss.\n\n## SLP Chapter 5.4 Gradient Descent\nAim of gradient descent is to find to optimal weights averaged over all examples to minimize the loss function. (equation in hand-written sheet)\n\n## SLP Chapter 5.5 Regularization\nL2 regulariztion is euclidean distance and also called as ridge regression. L1 regularization is manhattan distance also called as lasso regression\n\n## SLP Chapter 5.6 Multinomial logistic regression\nCases where more than two classes are required there multinomial logistic regression also called as softmax regression is used. In multinomial logistic regression the target y is a variable that rangesover more than two classes. The multinomial logistic classifier uses a generalization of the sigmoid, called softmax the softmax function, to compute the probability $p(y = c|x)$. Loss function in multinomial regression is (in hand-written notes)\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\nMost important difference between naive Bayes and logistic regression is that logistic regression is a discriminative classifier while naive Bayes is a generative classifier. Following are the components of a ML classifier: \n\n(1) Feature Representation (2) Classification function- Sigmoid or Softmax (3)Objective function- Minimizing error (4) Optimization algorithm \n\nSigmoid function along with decision boundary helps in classifying the ouput. \n\n## Module 13 Definitions\n* **Period disambiguation** - deciding whether a period is the end of sentence or not\n* **Loss function or cost function** - Distance between the system output and the gold output\n* **Feedforward network** - architecture in which the computation proceeds iteratively from one layer to the next\n* **Deep learning** - modern neural network with more depth\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 = \"\"\"Recurrent Neural networks (RNN) - any network with a cycle within its connections. \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Weight tying is a method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers. That is, E = V\"\"\"\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 = \"\"\"Words that occur in similar contexts tend to have similar meanings. Vector semantics instantiates this linguistic vector semantics embeddings hypothesis by learning representations of \\\n",
        "the meaning of words, called embeddings directly from their distributions in texts. These representations are used in every natural language processing application that makes use of meaning, and the static \\\n",
        "embeddings we introduce here underlie the more powerful dynamic or contextualized embeddings like BERT.\\n\n",
        "Two words have propositional meaning if they are synonymous and can replace each other without changing the truth conditions. \\n\n",
        "A semantic field is a set of words which cover a particular semantic domain and bear structured relations with each other. \\n\n",
        "Words have affective meanings or connotations. The word connotation has different meanings in different fields, but here we use it to mean the aspects of a word’s meaning that are related to a writer or \\\n",
        "reader’s emotions, sentiment, opinions, or evaluations. For example some words have positive connotations (happy) while others have negative connotations (sad).\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\"The idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of embeddings word neighbors. Vectors for \\\n",
        "representing words are called embeddings. word2vec model family for constructing short, dense vectors that have useful semantic properties\"\"\"\n",
        "slp_chapter6_3 = \"\"\"Term-term matrix is als called as word-word matrix or term-context matrix, in which the columns are labeled by words rather word-word matrix than documents. This matrix is thus of \\\n",
        "dimensionality |V|×|V| and each cell records the number of times the row (target) word and the column (context) word co-occur in some context in some training corpus. Majoirty of the numbers in the term-term matrix are zero and\\\n",
        " hence can be represented in dense form.\"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" word2vec is a much simpler model than the neural network language model in two ways: (1) Making it simple by convertiin git to a binary classification rather than word prediction (2)Simplifies architecture \\\n",
        "by making it a training a logistic regression classifier instead of a multi-layer neural network with hidden layers. Intuition of skip-gram is: (1)Treat the target word and neighboring context word as positive example \\\n",
        "(2)Randomly samle other words in lexicon to get negative samples (3)Use logostic regression to train classifier to distinguish two cases (4)Use learned weights as embeddings.\n",
        "Classifier: Window of context words +-2 words\"\"\"\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 = \"\"\"Smoothing using Laplacian smoothing. Advantages of Neural Language models over n-grams LMs \\n\n",
        "(1)They dont need smoothing \\n\n",
        "(2)They can handle much longer histories \\n\n",
        "(3)Generalize over context of similar words \\n\n",
        "(4)have much higher predictive accuracy \\n\n",
        "However, the only disadvantage it has is that it is slow to train. \\n\n",
        "The neural language models associate each word in the vocabulary with a vector-representation, thereby creating a notion of similarity between words. They also express the \\\n",
        "joint probability function of a word sequence in terms of the word vectors for the words in that sequence. Neural LMs simulatneously learn the word vectors as well as the \\\n",
        "parameters of the function. The word vectors are low-dimensional dense vectors and the probability function is expressed as the product of conditional probabilities of the \\\n",
        "next word given the previous word, using multi-layer, feed-forward neural network. \\n\n",
        "Inputs to Neural LMs- k-gram of words and the output is the probability distribution over the next word \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"Distributional hypothesis\" : \" link between similarity of distribution of words and similarity in its meaning\",\n",
        "\"Lexical Semantics\":\"linguistic study of word meaning \",\n",
        "\"Polysemuous\":\"having multiple senses or interpretations\",   \n",
        "\"Word sense disambiguation\":\"determing the sense in which the word is used\", \n",
        "\"Principal of contrast\":\"Difference in linguistic form is always associated with difference in meaning\",\n",
        "\"Co-occurence matrix\": \"Representation of how words occur\",\n",
        "\"Term-document matrix\":\"Row represents word in the vocabulary and column represents a document from some collection of documents\",\n",
        "\"Term-term matrix\":\"\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "50ed92f1-f6e8-4968-e78f-0d17ca24ec88"
      },
      "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": 44,
      "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\nRecurrent Neural networks (RNN) - any network with a cycle within its connections. \n\n## SLP Chapter 9.3 RNNs as Language Models\n Weight tying is a method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers. That is, E = V\n\n## SLP Chapter 6.1 Lexical Semantics\nWords that occur in similar contexts tend to have similar meanings. Vector semantics instantiates this linguistic vector semantics embeddings hypothesis by learning representations of the meaning of words, called embeddings directly from their distributions in texts. These representations are used in every natural language processing application that makes use of meaning, and the static embeddings we introduce here underlie the more powerful dynamic or contextualized embeddings like BERT.\n\nTwo words have propositional meaning if they are synonymous and can replace each other without changing the truth conditions. \n\nA semantic field is a set of words which cover a particular semantic domain and bear structured relations with each other. \n\nWords have affective meanings or connotations. The word connotation has different meanings in different fields, but here we use it to mean the aspects of a word’s meaning that are related to a writer or reader’s emotions, sentiment, opinions, or evaluations. For example some words have positive connotations (happy) while others have negative connotations (sad).\n\n\n## SLP Chapter 6.2 Vector Semantics\nThe idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of embeddings word neighbors. Vectors for representing words are called embeddings. word2vec model family for constructing short, dense vectors that have useful semantic properties\n\n## SLP Chapter 6.3 Words and Vectors\nTerm-term matrix is als called as word-word matrix or term-context matrix, in which the columns are labeled by words rather word-word matrix than documents. This matrix is thus of dimensionality |V|×|V| and each cell records the number of times the row (target) word and the column (context) word co-occur in some context in some training corpus. Majoirty of the numbers in the term-term matrix are zero and hence can be represented in dense form.\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\nMost important difference between naive Bayes and logistic regression is that logistic regression is a discriminative classifier while naive Bayes is a generative classifier. Following are the components of a ML classifier: \n\n(1) Feature Representation (2) Classification function- Sigmoid or Softmax (3)Objective function- Minimizing error (4) Optimization algorithm \n\nSigmoid function along with decision boundary helps in classifying the ouput. \n\n## Module 14 Definitions\n* **Distributional hypothesis** -  link between similarity of distribution of words and similarity in its meaning\n* **Lexical semantics** - linguistic study of word meaning \n* **Polysemuous** - having multiple senses or interpretations\n* **Word sense disambiguation** - determing the sense in which the word is used\n* **Principal of contrast** - Difference in linguistic form is always associated with difference in meaning\n* **Co-occurence matrix** - Representation of how words occur\n* **Term-document matrix** - Row represents word in the vocabulary and column represents a document from some collection of documents\n* **Term-term matrix** - \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": "33552e0d-3bbb-4723-8e9a-609db1c211f9"
      },
      "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": 45,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision theory assume the environmnt to be episodic and the actions are based on the desirability of the immediate outcomes.  $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 Six constraints that we require an resonable preference relation to obey.\n1. Orderabiity\n2. Transitivity\n3. Continuity\n4. Substitutability\n5. Monotonicity\n6. Decomposability \n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions map lotteries to real numbers. Measurements of utility are: Utility of money: We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money. \n\nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act. The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. The difference between the EMV of a lottery and its certainty equivalent is called insurance.  This tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse. Can be avoided using Bayesian Priors.\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n A remarkable consequence of using discounted utilities with infinite horizons is that the optimal policy is independent of the starting state. There is a direct relationship between the utility of a state and that of its neighbors i.e. the utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action. This called Ballman equation. Shaping theorem staes that the following transformation leaves the optimal policy unchanged. $R′(s,a,s′) = R(s,a,s′) +γΦ(s′)−Φ(s)$. All policies are optimal with zero reward functin everywhere. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nFour algorithms for solving MDPs are explained which are (1)Value iteration (2)Policy iteration (3)Linear Programming (4)Monte Carlo Planning. The first three genrate exact offline solutions whereas the fourth genrates approximate online solutions. Each step of iteration in Value iteration is called Bellman update. The convergence of value iteration is shown using contraction. Bellman update is a contraction by a factor $\\gamma$ in the space of utility vectors. Value iteration. \nPolicy iteration alternates between two steps beginning from some initial policy, policy evaluation followed by policy improvement. Time complexity of policy iteration is $O(S^3)$. After certain steps of policy iteration, the bellman update equation can be modified to do simplified value iteration (simplified as since the policy is fixed, the transition model is only a probability now). This is called Modified policy iteration. \n\nLinear Programming is solvable in polynomial time. \n\n## Module 8 Lecture Notes\nThe stochastic transition models are written as T(s,a,s') or as probability p(s'|s,a). The fact that we are ignoring the history of the steps taken indicates that we are in the Marovian part of the Markov model.MDPs are sequential decision problems in a fully observable environment with a stochastic transition with additive rewards and are non-deterministic search problems and solved using expectimax. Solution to MDPs require, a set of states, set of actions Transition function (probability model), Reward function, initial state and optionally terminal states. The solution to MDP is a POLICY, Policy takes in the current state and tels the agent what action to take. $\\pi(s) = a$ Best policy is denoted by $\\pi*$. Best policy depends on reward functions.Same policy executed multiple times may result in different sequence of states and actions. Reward function will determine the optimal policy. Utility function depends on the environment history. Infinite rewards avoids exits and leads to infite horizon game. Rewards now are preferred over rewards later and hence future rewards are discounted and also helps algorithm converge. Solution to infinite utilities: (1)Finite-horizon (2)Discounting (3)Absorbing-state. Optimal quantities - V*(s), Q*(s,a), $\\pi*(s)$. Recursive definition of values\n\n$V^*(s) = \\max_a Q^*(s,a)$ \n\n$Q^*(s,a) = \\sum_s T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ \n\nBellman equation: $V_k+1 (s) = \\max_a \\sum_s' T(s,a,s')[R(s,a,s') + \\gamma V^*(s')]$ -> Repeat until convergence and each step has time complexity $O(S^2 A)$ \n\nDownsides of value iteration- it is slow as it repeats the bellman updates, the max at each state rarely changes (i.e. value changes but the policy converges way early)\nIn policy evaluation actions are easier to choose from Q-values rather than values. Policy iteration has two steps (1)Policy Evaluation (2)Policy Improvement . Comparison between policy and value iteration. Value iteration updates both values and policy but we dont track is explicitly however taking a max computes it implicitly. In policy iterations, several passes are done that updates utilities with fixed policy. After each pass of evaluation, new policy is chosen. If new policy is better, it is chosen or else the optimal policy is found. So, to compute optimal values, either value iteration or policy iteration is used. \n\n\n## Module 8 Definitions\n* **Goal-based agent** - has binary distinction into bad(non-goal) and good(goal) states\n* **Decision-theoretic agent** - Chooses better state based on continuous range of values assigned to states\n* **Utility function** - a value that indicates the desirability of the of a state\n* **Expected utility** - sum of utility value of the outcomes weighted by the probability that the outcomes occurs as a result of chosen action\n* **Maximum expected utility (meu)** -  The principle states that the agent chooses an action that maximizes its expected utility\n* **Expected utility of a lottery** - Sum of the utility of each outcome weighted by the probability of that outcome\n* **Preference elicitation** - Identifying the underlying utility function from the observed preferences based on the choices presented to human\n* **Micromort** - one in a million chance of death\n* **$v^*(s)$** - expected utility by acting optimally and starting in s\n* **$q^*(s,a)$** - expected utility starting out having taken action a from state s and acting optimally\n* **$\\pi*(s)$** - optimal action from state s\n* **Policy evaluation** - calculating the policy of each state based on the policy to be executed\n* **Policy extraction** - Converts values into policy\n* **Non-stationary policy** - A policy that depends on the remaining time(finite horizon)\n* **Stationary policy** - A policy whose optimal action depends only on the current state and not time\n* **Proper policy** - policy guranteed to reach terminal state\n* **Policy improvement** - Calculate new MEU policy based on the utility calculated in policy evaluation with one-step look-ahead \n* **Asynchronous policy iteration** - Pick a subset of states and apply either (policy improvement or simplified value-iteration)to that subset\n* **Real-time dynamic programming(rtdp)** - \n* **Preference elicitation** - involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n* **Expected monetary value** - summation of (probability*utility)\n* **** - \n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nDefinition of Bandit problems \n\nGittins index (in handwritten notes). It provides very simple optimal policy for bandit problem i.e. pull th earm that has the highest gittins index followed by updating the Gittins index. Optimal first iteration calculation time complexity $O(n)$ and following decisions in $O(1)$. Approximately optimal policies use two methods to select an arm. The first method is by using Upper Confidence Bonds (UCB). Thsi uses confidence interval i.e. a range within which the value can be estimated to lie with high confidence. Chose an arm that has the highest upper bound in the confidence interval where the The upper bound is the current mean value estimate $μ_i$ plus some multiple of the standard deviation of the uncertainty in the value The standard deviation is proportional to $\\sqrt{1/N_i}$, where $N_i$ is the number of times arm $M_i$ has been sampled. So we have an approximate index value for arm $M_i$ given by \n\n$UCB(M_i) = μ_i + g(N)/\\sqrt{N_i}$ \n\nwhere g(N) is an appropriately chosen function of N, the total number of samples drawn from all arms. A UCB policy simply picks the arm with the highest UCB value. \n\nSecond method is Thompson sampling which chooses the arm randomly based on the probability that the arm is optimal. Suppose that $P_i(μ_i)$ is the current probability distribution for the true value of arm $M_i$. Then a simple way to implement Thompson sampling is to generate one sample from each $P_i$ and then pick the best sample. This algorithm also has a regret that grows as $O(logN)$.\n\n## AIMA Chapter 22.1 Learning from Rewards\n Two approaches of RL \n\n(1) Model-based - Agent uses transition models of the environment to interpret the reward signals \n\n(2) Model-free RLAgent has no info of transition model nor learns it. It learns  a more direct representation of how to behave. There are two varieties of model-fere RL \n\n(a) Action-utility learning- Agent learns the Q-function. It is also called as Q-learning \n\n(b) Policy search- A policy is learnt that maps actions t states\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n**Direct Utiliy Estimation's** idea is that the utility of a state is defined as the expected estimation Reward-to-go total reward from that state onward (called the expected reward-to-go), and that each trial provides a sample of this quantity for each state visited. This RL technique is reduced to a suprvised learning problem by it ignores an important constraint that The utility of a state is determined by the reward and the expected utility of the successor states. By ignoring the connections between states, DUE misses opportunity for learning and so often coverges slowly. \n\n**Adaptive Dynamic Programming** takes advantages of the connections/constraints between states by learning transition model that connects them and solving the corresponding MDP i.e. calculating the utilities of the state from the learned transition model and reward function. \n\n**temporal-difference learning** (basic explanation in summary)\nADP and TD are closely related but as both try to make local adjustments t utility estimates in order to make each state agree with its successor. However, the difference is that TD adjusts to agree with its observed successor whereas ADP adjusts the state to agree with all of the successors. that might occur, weighted by their probabilities. Moreover, TD makes only one adjustment per transition, ADP makes as many as it needs to restore consistency between the utility estimates U and the transition model P. Although the observed transition makes only a local change in P, its effects might need to be propagated throughout U. Thus, TD can be viewed as a crude but efficient first approximation to ADP. \n\n**Prioritized sweeping heuristic** prefers prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nActive RL has to find out the policy along with the expected utilities. This can be done using the ADP wher the first step is to find out the utilities followed by choosing the optimal policy by finding path with max utility by one-step look ahead. \n\n**Exploration** \n\nA greedy agent after certain steps finds out  apositive reward and thus finds ou the optimal path based on the learned model of the environment but this might not be the optimal solution. This optimal policy leading to sub-optimal solution is due to the fact that the learned environment is not the true environment. And so the agent needs to perform exploration. So agent must not be greedy in terms of immediate next move but must be GLIE (Greedy in limit of Infinite Exploration). i.e. GLIE scheme must try each state unbounded number of times so as to avoid the chance of having optimal action being missed. Examples of GLIE schemes \n\n(1)Choose a random action at time step t with probability $1/t$ and to follow greedy policy otherwise \n\n(2)More weight given to actions visted less frequently  and less to actions that have low utility. This results in optimistic prior over the possible environments and causes the agent to behave initially as if there were wonderful rewards scattered all over the place.\n**Temporal-difference Q-Learning** \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nCatastrophic forgetting: the tendency of an artificial neural network to completely and abruptly forget previously learned information upon learning new information. One solution to this problem, called experience replay, forces the network to make the mistake so that it remembers.Reward Shaping: One common method, originally used in animal training, is called reward shaping. This involves supplying the agent with additional rewards, called pseudorewards, for “making progress.”\nHierarchical reinforcement learning:\nAnother way to cope with very long action sequences is to break them up into a few smaller pieces, and then break those into smaller pieces still, and so on until the action sequences are short enough to make learning easy.\nThe hierarchical structure of behavior also provides a natural additive decomposition of the overall utility function.\n\n\n## Module 9 Lecture Notes\nBasic idea of RL - feedback perceived as reward, reward function defines agent's utility, actions must be driven by idea to maximize expected rewards and all all learning is based on observed samples of outcomes. RL still looks for a policy as solution($\\pi(s)$). RL is a type of MDP with known states($s$) and actions($a$) but unknown transition model(T) or reward function(R).  The lecture talked about two different types of learning for RL (1)Model-based Learning (2)Model-free learing. In passive RL, someone chooses policy for us and try to figure out how good is the policy and is thus similar to policy evaluation. So we have policy as input with a goal of learning the states and no information on transition model or rewards. Direct evaluation is the process whose goal is to computes the values for each state under policy. This is done by acting according to the policy adn noting down the sum of discounted rewards everytime a state is reached and then averaging those out. Pros of direct evaluation-easy to understand, no knowledge of R and T required, and computes correct average value of states. Cons- wastes info of connection between states, all states are to be learned separately and thus takes more time.Sampled based policy evaluation doesnt work in RL as there is no gurantee that we will land up in a state(s) n times if n samples are taken. Temporal Difference Learning idea is to keep learning from each experience i.e. to update V(s) every time a transition is experienced. It involves exponential moving average where it forgets about the distant past values which is justified as the initial estimates were way off. Decreasing learning rates can give converging solutions. Updated Bellman equation for TemporalDifferenceLearning is \n\n$ V^{\\pi(s)} = (1 - a)*V^{\\pi(s)} + a[R(s,\\pi(s),s') + \\gamma V^{\\pi(s')}]$ \n\nTD learning is model-free RL technique to do policy evaluation mimicking Bellman Updates with running sample averages. But to select a policy, we need Q-values and not the values of states. \n\n\n\n## Module 9 Definitions\n* **Exploration** - randomly tring out actions to get information\n* **Explotation** - exploiting the already available information to do what is considered to be the best policy\n* **Regret** - Mistakes made even on learning intelligently and leading to sub-optimal policy\n* **Sampling** - Performing actions multiple times due to chance(stochastic environment) associated with actions\n* **Difficulty** - Much harder than MDP as not all information is given\n* **Passive rl** - Agent's task is to learn the utilities of the state or a model of the environment where its policy is fixed\n* **Active rl** - Along with learning utilities of the states, it must also figure out policy\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nBelief state is a representation of all possible states that the agent might be in as well as all the contingency plan in case of eventuality. Drawbacks of belief state are \n\n(1)Agent must consider all possible explanation of its perceptions thus generating large belief state with unlikely possibilities \n\n(2)Correct contingency plan may grow very large \n\n(3)Sometimes there maybe no plan to achievegoal. \n\n$Decision theory = probability theory + utility theory$ - The decision theory states that an agent is rational only if it choses an action that yields the highest expected utility which are averaged over all possible outcomes that result from an action. Tis principal is called Maximum Expected Utility(MEU). \n\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\nUnconditional probabilities are also called prior probabilities. Conditional probability is also called posterior probability.\n\n**Categorical Distribution** Probability Distribution that is finite and discrete range. \n\n**Probability density function** Probability distribution that has continuous and takes infinitely many values. \n\nA possible world is defined to be an assignment of values to all of the random variables under consideration.\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nprobabilistic inference—that is, the computation of posterior probabilities for query propositions given observed evidence. We use the full joint distribution as the “knowledge base” from which answers to all questions may be derived\n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n$P(cause | effect) = {P(effect | cause)P(cause)}/P(effect)$ \n\nCausal direction - $P(effect|cause)$ and diagnostic direction - $P(cause|effect)$. Diagnostic knowledge is often more fragile than causal knowledge\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 \n\n## SLP Chapter 3.2 Evaluating Language Models\nThe best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation.\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application. In practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (PP) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. (equation of perplexity in hand-written notes).\nThus, minimizing perplexity is equivalent to maximizing the test set probability according to the language model.As we see above, the more information the n-gram gives us about the word sequence, the lower the perplexity. (perplexity is related inversely to the likelihood of the test sequence according to the model).\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\nOne step is to be sure to use a training corpus that has a similar genre to whatever task we are trying to accomplish. It is equally important to get training data in the appropriate dialect or variety, especially when processing social media posts or spoken transcripts. Matching genres and dialects is still not sufficient. Our models may still be subject to the problem of sparsity. Following are the ways to deal with Out of Vocabulory problems: \n\n(1)Choose a word list that is fixed in advance (2)Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step (3)Estimate the probabilities from its counts just like any other regular word in the training set\n\n## SLP Chapter 3.5 Smoothing\nLaplace smoothing- Done to avoid 0 probability cases. K smoothing- modification to laplace so as to reduce the bias. adding k=0.5,0.05,.. interpolation, probability estimates from all the n-gram estimators are mixed, weighing and combining the trigram, bigram, and unigram counts. If higher order are not available then back-off helps use lower order n-gram.Katz Backoff: In order for a backoff model to give a correct probability distribution, we have to discount the higher-order n-grams to save some probability mass for the lower order n-grams.Katz backoff is often combined with a smoothing method called Good-Turing. The combined Good-Turing backoff algorithm involves quite detailed computation for estimating the Good-Turing smoothing and the P ∗ and α values\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\nPossible world based on the probabilities are called sample space. They are mutually exclusive and exhaustive. Axioms of probability (1)Probability of any possible world is between 0 and 1. \n(2) Total probability of set of all possible world is 1. Size of distribution of n random variables with domain size d is $d^n$. Following are key sub parts of probabilistic models: (1)Domains - Each random variable can take \na set of values called as the domain of the random variable (2)Outcomes- Set of assignments of values to variables (3)Joint distribution- How likely a set of assignments are (4)Normalized - sum of probabilities is equal to 1 \n(5)Ideally not many variables interact with each other. \nConditional Probability distributions are one of the most important distributions as it tells us information about things that we didn't observe. $P(a|b) = P(a,b)/P(b)$. \n\nInference by enumeration - Evidence variable (values known), Querry variables (variables we care about), Hidden variables. Three steps to follow \n\n(1)Select entries consistent with evidence. \n\n(2)Get joint distribution of query and evidence by summing out H $P(Q,e_1,e_2, ...e_k) = \\sum_h P(Q,h_1,...,h_r,e_1...e_k)$. \n\n(3)Normalize $Z = \\sum_q P(Q,e_1...e_k)$ then, $P(Q|e_1...e_k) = (1/Z)*P(Q,e_1...e_k)$ \n\nProduce Rule - $P(y)P(x|y) = P(x,y)$ \n\nChain Rule - $P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$ \n\nBayes' Rule - $P(y)P(x|y) = P(x,y) = P(x)P(y|x)$ so, $P(x|y) = P(y|x)P(x)/P(y)$ \n\nProbabilistic Language models examples autocomplete for texting, machine translation, spelling correction, speech recognition and other NL generation tasks incude summarization, question-answering, dialog systems.\n\n\n\n## Module 10 Definitions\n* **Observed variables (evidence)** - Information know to the agent about the world\n* **Unobserved variables (states)** - Reasoning about certain aspects needs to be done by the agent\n* **Model** - Information known by agent on how evidence is related to the state\n* **Probabilistic model** - Joint distribution over a set of random variables of the world\n* **Event** - It is a set of possible outcomes\n* **Joint probability distributions** - Probability distributions that are based on the combination of multiple variables\n* **Marginal distributions** - Sub sets of joint distribution with eliminated variables that are not important\n* **Marginalization** - Summing out useless rows to form marginalized distribution from joint distribution\n* **Conditinal probability distribution** - Probability distributions of a random variable given fixed value of other random variable\n* **Probabilistic inference** - Infer probability of a desired outcome from other known probabiliies\n* **Unigram** - no history\n* **Bigram** - 1 word history\n* **Trigram** - 2 word history\n* **N-gram** - N-1 word history\n* **Ontological commitments** - \n* **Epistemological commitments** - \n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Specification of Bayesian Network: \n\n(1)Each node indicates a discrete or continuous random variable \n\n(2)Directed arrows connect pair of nodes and there are no cycle of directed arrows formed \n\n(3)Each node has an associated probability information $P(X_i|Parents(X_i))$\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nBayes Nets is complete and non-redundant representation of the domain. It can be far more compact than full joint distribution. Compactness of BNs is an example of genral property of locally structured(sparse) systems. In locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity. General non-descendants property states that Each variable is conditionally independent of its non-descendants given its parents. Non-descendants property combined with interpretation of the network parameters $θ(X_i|Parents(X_i))$ as conditional probabilities $P(X_i|Parents(X_i))$ suffices to reconstruct the full joint distribution. Also, a variable is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket.\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\nX and Y are independent -> $P(x,y) = P(x)P(y)$. X and Y are conditionally independent given Z $P(x,y|z) = P(x|z)P(y|z)$\n\n## Module 11 Definitions\n* **Bayesian network** - A directed graph where quantitative probability information is annotated on each node\n* **Topological order** - Order consistent with directed graph structure\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nAn agent is learning if it improves its performance after making observations about the world. Performance of a component of agent program can be improved based on the following factors (1) What component to improve (2)Evidence it has that influences the model (3)What data and feedback on data is available. \n\nInductive conclusions MAY be correct but deductive conclusions are GURARANTEED to be correct if the premises are correct. \n\nThree types of feedback that classify learning problems: (1)Supervised learning that receives input-output pairs where the output is called as label (2)Unsupervised learning - Agent learnd a pattern without any explicit feedback Clustering is an example (3)Reinforcement Learning- Rewards and punishments help the  agent learn.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nA training model generates a hypothesis of the actual function . The hyposthesis is drawn from the hypothesis space. The hypothesis is also called model of the data and the hypothesis space is also called the model class or a function drawn from a function class. There is atrade-off between bias and variance. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nDecision tree in a representation of a function that gives a single output by mapping a vector of attribute values. \n\nDecision tree pruning eliminates nodes that are not relevant and thus helps combat overfitting. Addressing following complications of decision trees can make it more useful (1)Missing data (2)Continuous and multivalued input attributes - This can be solved using split point test or equality test. (3) Continuous valued ouput attribute. \n\nDecision trees are unstable and if the trees are very deep, then getting a prediction for a new example can be very expensive. It can also have sub-optial accuracy. Also, adding one new example can change the test at root.\n\n## AIMA Chapter 5.5 Stochastic Games\nk-fold crossvalidation is used when the there isn't enough data to categorize into three classes, training set, validation set and test set. So we use some of the training data set as a validation data set. \n\nFinding a good hypothesis can be divided into two sub-parts (1) Model selection that chooses a good hypothesis space and (2) Optimization that finds a good hypothesis in that space. \n\nReasons why best hypothesis may differ from true function: (1)Ralizable (2) Variance (3)original function maybe Non-deterministic or noisy (4)Computationally intractable \n\nApproaches to tunning a hyperparameter (1)hand-tuning (2)Grid search if there are a small number of parameters with each parameters likely to take only a few possibe set of values (3) Random search. \n\nBayesian optimization considers the process of tuning the parameters as a machine learning problem in itsf. \n\nPopulation-based training (PBT) is an alternative to bayesian optimization it combines random search and then for later generation uses hand-tuning or bayesian optimization.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nAny hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC) \n\n**Decision lists** resemble decision trees, but their overall structure is simpler: they branch only in one direction.\nOn the other hand, if we restrict the size of each test to at most k literals, then it is possible for the learning algorithm to generalize successfully from a small number of examples. We use the notation k -DL for a decision list with up to k conjunctions\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Induction** - Forming a genral rule based on specific set of observations\n* **Factored representation** - vector of attributes\n* **Classification** - Output is one option from a finite set of options\n* **Regression** - When output is a number value and can have infinite values its called regression\n* **Bias** - predictive hypothesis's tendency to deviate from the expected value when averaged over different training sets\n* **Variance** - Fluctuations in training data cause change in hypothesis. Variance is the amount of this change\n* **Learning curve** - Proportion correct on test set v/s training set size\n* **Stationarity assumption** - Future examples will be like past\n* **Toxicity detection** - task of detecting hate speech, abuse, harassment, or other kinds of toxic language.\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n For logistic regression and naive Bayes the combination features or feature interactions have to be designed by hand. Feature templates are also used to create it automatically. Advantages of Logistic regression over naive bayes are (1)NB has overly strong consitional independance assumptions (2)Logistic regression is very robst to correlated features so LR wors better on larger datasets. But NB works very well n small datasets and very easy and fast to implement.\n\n## SLP Chapter 5.2 Learning in Logistic Regression\nCross entropy loss is used as the loss function.  \n\n## SLP Chapter 5.3 The cross-entropy loss function\nWe choose a loss function that prefers the correct class labels of the training examples to be more likely. This is called conditional maximum likelihood estimation: we choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x. The resulting loss function is the negative log likelihood loss, generally called the cross-entropy loss.\n\n## SLP Chapter 5.4 Gradient Descent\nAim of gradient descent is to find to optimal weights averaged over all examples to minimize the loss function. (equation in hand-written sheet)\n\n## SLP Chapter 5.5 Regularization\nL2 regulariztion is euclidean distance and also called as ridge regression. L1 regularization is manhattan distance also called as lasso regression\n\n## SLP Chapter 5.6 Multinomial logistic regression\nCases where more than two classes are required there multinomial logistic regression also called as softmax regression is used. In multinomial logistic regression the target y is a variable that rangesover more than two classes. The multinomial logistic classifier uses a generalization of the sigmoid, called softmax the softmax function, to compute the probability $p(y = c|x)$. Loss function in multinomial regression is (in hand-written notes)\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\nMost important difference between naive Bayes and logistic regression is that logistic regression is a discriminative classifier while naive Bayes is a generative classifier. Following are the components of a ML classifier: \n\n(1) Feature Representation (2) Classification function- Sigmoid or Softmax (3)Objective function- Minimizing error (4) Optimization algorithm \n\nSigmoid function along with decision boundary helps in classifying the ouput. \n\n## Module 13 Definitions\n* **Period disambiguation** - deciding whether a period is the end of sentence or not\n* **Loss function or cost function** - Distance between the system output and the gold output\n* **Feedforward network** - architecture in which the computation proceeds iteratively from one layer to the next\n* **Deep learning** - modern neural network with more depth\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\nRecurrent Neural networks (RNN) - any network with a cycle within its connections. \n\n## SLP Chapter 9.3 RNNs as Language Models\n Weight tying is a method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers. That is, E = V\n\n## SLP Chapter 6.1 Lexical Semantics\nWords that occur in similar contexts tend to have similar meanings. Vector semantics instantiates this linguistic vector semantics embeddings hypothesis by learning representations of the meaning of words, called embeddings directly from their distributions in texts. These representations are used in every natural language processing application that makes use of meaning, and the static embeddings we introduce here underlie the more powerful dynamic or contextualized embeddings like BERT.\n\nTwo words have propositional meaning if they are synonymous and can replace each other without changing the truth conditions. \n\nA semantic field is a set of words which cover a particular semantic domain and bear structured relations with each other. \n\nWords have affective meanings or connotations. The word connotation has different meanings in different fields, but here we use it to mean the aspects of a word’s meaning that are related to a writer or reader’s emotions, sentiment, opinions, or evaluations. For example some words have positive connotations (happy) while others have negative connotations (sad).\n\n\n## SLP Chapter 6.2 Vector Semantics\nThe idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of embeddings word neighbors. Vectors for representing words are called embeddings. word2vec model family for constructing short, dense vectors that have useful semantic properties\n\n## SLP Chapter 6.3 Words and Vectors\nTerm-term matrix is als called as word-word matrix or term-context matrix, in which the columns are labeled by words rather word-word matrix than documents. This matrix is thus of dimensionality |V|×|V| and each cell records the number of times the row (target) word and the column (context) word co-occur in some context in some training corpus. Majoirty of the numbers in the term-term matrix are zero and hence can be represented in dense form.\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\nMost important difference between naive Bayes and logistic regression is that logistic regression is a discriminative classifier while naive Bayes is a generative classifier. Following are the components of a ML classifier: \n\n(1) Feature Representation (2) Classification function- Sigmoid or Softmax (3)Objective function- Minimizing error (4) Optimization algorithm \n\nSigmoid function along with decision boundary helps in classifying the ouput. \n\n## Module 14 Definitions\n* **Distributional hypothesis** -  link between similarity of distribution of words and similarity in its meaning\n* **Lexical semantics** - linguistic study of word meaning \n* **Polysemuous** - having multiple senses or interpretations\n* **Word sense disambiguation** - determing the sense in which the word is used\n* **Principal of contrast** - Difference in linguistic form is always associated with difference in meaning\n* **Co-occurence matrix** - Representation of how words occur\n* **Term-document matrix** - Row represents word in the vocabulary and column represents a document from some collection of documents\n* **Term-term matrix** - \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}