{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_2_notes_WRS.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "a735a292-4653-4098-a489-8e69af098abb"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "1e783f0c-48d8-4f08-bb68-85afc4f5204b"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "f44e0359-3b32-4d82-eff2-7b5863cc1d40"
      },
      "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 = \"\"\"\n",
        "BASIC PRINCIPLE OF DECISION THEORY: THE MAXIMATION OF EXPECTED UTILITY\n",
        "\n",
        "Start is an agent who needs to make a decision:\n",
        "\n",
        "- Current state may be uncertain\n",
        "\n",
        "- Assigns probability P(s) to each possible current state s\n",
        "\n",
        "- Action outcomes may be uncertain\n",
        "\n",
        "- Transition model is given by P(s’|s,a), which is the probability that action a in state s reaches s’\n",
        "\n",
        "- P(RESULT(a)=s’) = sum(s) P(s)P(s’|s,a), the probability of reaching s’ by doing a in any current state\n",
        "\n",
        "\n",
        "Decision theory aims to choose among actions based on how desirable their immediate outcomes are\n",
        "\n",
        "- Utility function U(s) captures preferences and assigns a single number to express desirability\n",
        "\n",
        "- EU(a) is the expected utility of an action given the evidence (average utility value of outcomes weighted by resp. probability, sum(s’) P(RESULT(a)=s’)U(s’) )\n",
        "\n",
        "- Maximum expected utility (MEU) principle describes that a rational agent should choose the action with maximized expected utility, action = argmax_a EU(a)\n",
        "\n",
        "- MEU principle can be seen as a prescription for intelligent behaviour and formalizes the general notion that intelligent agents should do the right thing. However, it doesn’t operationalize that advice\n",
        "\n",
        "\"\"\"  + sample_equation\n",
        "\n",
        "chapter16_2 =  \"\"\"\n",
        "MODELLING RATIONAL AGENT BEHAVIOUR BY MAXIMIZING A UTILITY FUNCTION\n",
        "\n",
        "16.2.1 Constraints on rational preferences:\n",
        "\n",
        "Notations to describe agent preferences:\n",
        "\n",
        "- A ≻ B: agent prefers A over B\n",
        "\n",
        "- A ~ B: agent is indifferent between A and B\n",
        "\n",
        "- A ≻~ B: agent prefers A over B or is indifferent between them\n",
        "\n",
        "Constraints that any reasonable preference relation is required to obey (known as the axioms of utility theory):\n",
        "\n",
        "- Orderability: Exactly one of (A≻B), (B≻A), or (A~B) holds\n",
        "\n",
        "- Transitivity: (A≻B) and (B≻C) => (A≻C)\n",
        "\n",
        "- Continuity: A≻B≻C => there exits p [p,A; 1-p,C] ~ B\n",
        "\n",
        "- Substitutability: A~B => [p,A; 1-p,C] ~ [p,B; 1-p,C]\n",
        "\n",
        "- Monotonicity: A ≻B => (p>q  [p,A; 1-p,B] ≻ [q,A; 1-q,B]\n",
        "\n",
        "- Decomposability: [p,a; 1-p,[q,B; 1-q,C]] ~ [p,A; (1-p)q,B; (1-p)(1-q),C]\n",
        "\n",
        "16.2.2 Rational preferences lead to utility\n",
        "\n",
        "Consequences can be derived from the axioms of utility\n",
        "\n",
        "- Existence of Utility Function: U(a) > U(B)  A ≻B   and     U(A)=U(B)  A~B\n",
        "\n",
        "- Expected Utility of a Lottery: U([p1,S1;…;pn,Sn]) = sum(i) piU(Si) (sum of probability of each outcome times utility of that outcome)\n",
        "\n",
        "A utility function exists for any rational agent, assuming the constraints on rational references.\n",
        "\n",
        "Positive affine transformation: Utility function U(S) can be transformed to U’(S)=aU(S)+b where a and b are constants and a>0 without changing the agent’s behaviour\n",
        "\n",
        "Value function / Ordinal Utility function: In a deterministic environment (as is game-playing), agents only needs preference ranking on states, specific numbers don’t matter\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\"\n",
        "NATURE OF UTILITY FUNCTIONS AND RELATION TO INDIVIDUAL QUANTITIES\n",
        "\n",
        "Utility functions map from lotteries to real numbers and must obey the axioms discussed in 16.2\n",
        "\n",
        "16.3.1: Utility assessment and utility scales\n",
        "\n",
        "- Preference elicitation (work out human’s utility function): Process involving presenting choices to humans and using the observed preferences to get the underlying utility function\n",
        "\n",
        "- Helpful to establish some scale on which utilities can be recorded and compared for any particular problem, even though there is no absolute scale for utilities as per 16.2\n",
        "\n",
        "- Normalized utilities use u⊥ = 0 and u⊤ = 1 for a scale. Given that, the utility of any particular prize S can be assessed by asking the agent to choose between S and a standard lottery [p, u⊤; (1-p), u⊥]\n",
        "\n",
        "16.3.2 The utility of money\n",
        "\n",
        "- Agents have a monotonic preference for more money\n",
        "\n",
        "- Agents want to maximize the expected monetary value (EMV)\n",
        "\n",
        "- Agents can be risk-averse, risk seeking or risk-neutral\n",
        "\n",
        "- The insurance premium is the difference between the EMV of a lottery and its certainty equivalent\n",
        "\n",
        "16.3.3 Expected utility and post-decision disappointment\n",
        "\n",
        "- Best action a* maximizes expected utility: a* = argmax_a EUR(a)\n",
        "\n",
        "- Models usually oversimplify because either information is missing or computation of the true expected utility is too difficult, so effectively working with estimates ÊU(a) of the true expected utility\n",
        "\n",
        "- General assumption for unbiased estimates, so zero expected value of the error, E(ÊU(a)-EU(a))=0\n",
        "\n",
        "- Even though estimate was unbiased real outcome usually significantly worse than the estimate because of tendancy for the estimated expected utility of the best choice to be too high (optimizer’s curse), afflicting even the most seasoned decision analysts and statisticans\n",
        "\n",
        "- Curse can be avoided with a Bayesian approach that uses an explicit probability model P(ÊU|EU) of the error in the utility estimates, therefore utility estimate is treated as evidence and posterior distribution for true utility is computed using Bayes’ rule\n",
        "\n",
        "16.3.4 Human judgment and irrationality\n",
        "\n",
        "- Decision theory is a normative theory, meaning that it describes how a rational agent should act\n",
        "\n",
        "- Literature gives evidence suggesting that humas are predictably irrational, being strongly attracted to gains that are certain\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "Chapter 17: Sequential decision problems: Agent’s utility depends on a sequence of decisions,  \\\n",
        "incorporating utilities, uncertainty, and sensing, and including search and planning problems as special cases\n",
        "\n",
        "DEFINITION OF SEQUENTIAL DECISION PROBLEMS\n",
        "\n",
        "- An agent begins in the start state and must choose an action at each time step\n",
        "\n",
        "- Transition model describes the outcome of each action in each state, P(s’|s,a), which is the probability that action a in state s reaches\n",
        "\n",
        "- Markovian transitions are assumed: probability of reaching s’ from s depends only on s and not on the history of earlier states\n",
        "\n",
        "- Environment history: utility function depending on a sequence of states and actions rather than on a single state\n",
        "\n",
        "- Reward R(s,a,s’) can be positive or negative (bounded by +-Rmax) and is receives for every transition from s to s’ via action a\n",
        "\n",
        "- Markos Decision Process (MDP): sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards.\n",
        "\n",
        "- MDP includes: set of states (initial state s0); set ACTIONS(s) of actions in each state: transition model P(s’|s,a); reward function R(s,a,s’)\n",
        "\n",
        "- Dynamic Programming: simplifying a problem by recursively breaking it into smaller pieces and remembering the optimal solutions to the pieces, usually involved in methods for solving MDPs\n",
        "\n",
        "- Policy π: solution specifying what the agent should do for any state that the agent might reach (no fixed action sequence). Π(s) is the action recommended by the policy π for state s\n",
        "\n",
        "- Optimal policy π*: yields the highest expected utility\n",
        "\n",
        "17.1.1 Utilities over time\n",
        "\n",
        "- Finite/infinite horizon: means that there is a fixed time N after which nothing maters, optimal action in a \\\n",
        "given state may depend on how much time is left (optimal policy is nonstationary)\n",
        "\n",
        "- With no time limit, optimal policy is stationary, depending only on the current state\n",
        "\n",
        "- Proper policy: policy that is guaranteed to reach a terminal state (γ=1 possible for proper policies)\n",
        "\n",
        "- Infinite sequences comparable in terms of average reward obtained per time step\n",
        "\n",
        "17.1.2 Optimal policies and the utilities of states\n",
        "\n",
        "- Policies can be compared by comparing the expected utilites obtained during execution\n",
        "\n",
        "- Expected utility obtained by executing π starting in s: U^π(s) = E [ sum(t=0->inf) γ^tR(St, π(St),S(t+1)]\n",
        "\n",
        "- π*s = argmax_ π U^π(s)  is a policy, so it recommends an action for every state\n",
        "\n",
        "- Utilities are higher for states closer to the +1 exit, because fewer steps are required to reach the exit (fewer discounting)\n",
        "\n",
        "- π*(s) = argmax_(a in A(s)) sum(s’) P(s’|s,a)[R(s,a,s’)+ γU(S’)]\n",
        "\n",
        "- Action-utility function (Q-function) Q(s,a): expected utility taking a given action in a given state\n",
        "\n",
        "- Relation Q-function to Utility function: U(s) = max_a Q(s,a)\n",
        " \n",
        "17.1.3 Reward Scales\n",
        "\n",
        "17.1.4 Representing MDPs\n",
        "\n",
        "- Simplest way to represent P(s’,s,a) and R(s,a,s’): bism three-dimensional tables of size |S|^2|A|. Tables far too big for larger Problems\n",
        "\"\"\"\n",
        "\n",
        "chapter17_2 =  \"\"\"\n",
        "Four different algorithms for solving MDP:\n",
        "\n",
        "- Exact offline solutions: value iteration, policy iteration, linear programming\n",
        "\n",
        "- Online approximate algorithms: Monte Carlo planning\n",
        "\n",
        "17.2.1 Value Iteration\n",
        "\n",
        "- Basis is the Bellman equation\n",
        "\n",
        "- For n possible states, there are n Bellman equations, one for each state, containing n unknowns, the utilities of the states\n",
        "\n",
        "- Equations are nonlinear, because the “max” operator is not a linear operator\n",
        "\n",
        "- Iterative approach: 1. Start with arbitrary initial values for the utilities; 2. Calculate right-hand side of the equation and plug into left-hand side; 3. Thereby update the utility of each state from the utilities of its neighbors; 4. Repeat until we reach equilibrium\n",
        "\n",
        "- Iteration step / Bellman update: Ui+1(s) = max_(a in A(s)) sum(s’) P(s’|s,a)[R(s,a,s’)+ γUi(S’)], update is assumed to be applied simultaneously to all the states at each iteration\n",
        "\n",
        "- Guaranteed to reach an equilibrium when Bellman update applied infinitely often\n",
        "\n",
        "17.2.2 Policy Iteration\n",
        "\n",
        "Policy iteration suggested from the fact that exact magnitude of the utilities involved need not be precise if one action is clearly better than all others.\n",
        "\n",
        "Policy iteration alternates two steps, beginning from some initial policy π0:\n",
        "\n",
        "- Policy evaluation: calculates Ui = U^πi the utility of each state if πi were to be executed, given a policy π\n",
        "\n",
        "- Policy improvement: Calculates new MEU policy πi+1 using one-step look-ahead based on Ui\n",
        "\n",
        "Terminates when policy improvement yields no changes in the utilities, so Ui fixed point of the Bellman update, so solution to the Bellman equations and therefore πi must be an optimal policy\n",
        "\n",
        "- Modified policy Iteration: useful for large state spaces, no exact policy evaluation but simplified value iteration steps to give a reasonably good approximation of the utilities\n",
        "\n",
        "- Asynchronous policy iteration: General algorithm updating all utility/policy for all states at once (like value and policy iteration)\n",
        "\n",
        "17.2.3 Linear programming\n",
        "\n",
        "- General approach for formulating constrained optimization problems\n",
        "\n",
        "- A Bellman equations involve lot of sums and maxes, solving MDP can be reduced to solving a suitably formulated linear program\n",
        "\n",
        "- Utilities U(s) are considered as variables in the LP, we seek to minimize U(s) for all s subject to the inequalities U(s) >= sum(s’) P(s’|s,a)[R(s,a,s’)+ )+γU(s’)] for every state s and every action a\n",
        "\n",
        "- creates connection from dynamic programming to linear programming\n",
        "\n",
        "17.2.4 Online algorithms for MDPs\n",
        "\n",
        "- Exact offline solutions not possible for sufficiently large MDPs (such as Tetris)\n",
        "\n",
        "- In online algorithms, agent does significant amount of computation at each decision point rather than operation primarily with precomputed information\n",
        "\n",
        "- Example for straightforward approach is simplification of expectiminimax algorithm for game trees with chance nodes\n",
        "\n",
        "- Real-time dynamic programming (RTDP)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "Summary MDP Algorithm:\n",
        "\n",
        "Use MDP if you want to:\n",
        "- Compute optimal values: iteration or policy iteration\n",
        "\n",
        "- Compute values for a particular policy: policy evaluation\n",
        "\n",
        "- Turn values into a policy: policy extraction (one-step lookahead)\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",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter17_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter17_1))\n",
        "\n"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 450\n",
            "The length in characters is 2985\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3311
        },
        "cellView": "form",
        "outputId": "82566588-c1c7-483d-b20d-fe03270d5c23"
      },
      "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": 4,
      "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\nBASIC PRINCIPLE OF DECISION THEORY: THE MAXIMATION OF EXPECTED UTILITY\n\nStart is an agent who needs to make a decision:\n\n- Current state may be uncertain\n\n- Assigns probability P(s) to each possible current state s\n\n- Action outcomes may be uncertain\n\n- Transition model is given by P(s’|s,a), which is the probability that action a in state s reaches s’\n\n- P(RESULT(a)=s’) = sum(s) P(s)P(s’|s,a), the probability of reaching s’ by doing a in any current state\n\n\nDecision theory aims to choose among actions based on how desirable their immediate outcomes are\n\n- Utility function U(s) captures preferences and assigns a single number to express desirability\n\n- EU(a) is the expected utility of an action given the evidence (average utility value of outcomes weighted by resp. probability, sum(s’) P(RESULT(a)=s’)U(s’) )\n\n- Maximum expected utility (MEU) principle describes that a rational agent should choose the action with maximized expected utility, action = argmax_a EU(a)\n\n- MEU principle can be seen as a prescription for intelligent behaviour and formalizes the general notion that intelligent agents should do the right thing. However, it doesn’t operationalize that advice\n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nMODELLING RATIONAL AGENT BEHAVIOUR BY MAXIMIZING A UTILITY FUNCTION\n\n16.2.1 Constraints on rational preferences:\n\nNotations to describe agent preferences:\n\n- A ≻ B: agent prefers A over B\n\n- A ~ B: agent is indifferent between A and B\n\n- A ≻~ B: agent prefers A over B or is indifferent between them\n\nConstraints that any reasonable preference relation is required to obey (known as the axioms of utility theory):\n\n- Orderability: Exactly one of (A≻B), (B≻A), or (A~B) holds\n\n- Transitivity: (A≻B) and (B≻C) => (A≻C)\n\n- Continuity: A≻B≻C => there exits p [p,A; 1-p,C] ~ B\n\n- Substitutability: A~B => [p,A; 1-p,C] ~ [p,B; 1-p,C]\n\n- Monotonicity: A ≻B => (p>q  [p,A; 1-p,B] ≻ [q,A; 1-q,B]\n\n- Decomposability: [p,a; 1-p,[q,B; 1-q,C]] ~ [p,A; (1-p)q,B; (1-p)(1-q),C]\n\n16.2.2 Rational preferences lead to utility\n\nConsequences can be derived from the axioms of utility\n\n- Existence of Utility Function: U(a) > U(B)  A ≻B   and     U(A)=U(B)  A~B\n\n- Expected Utility of a Lottery: U([p1,S1;…;pn,Sn]) = sum(i) piU(Si) (sum of probability of each outcome times utility of that outcome)\n\nA utility function exists for any rational agent, assuming the constraints on rational references.\n\nPositive affine transformation: Utility function U(S) can be transformed to U’(S)=aU(S)+b where a and b are constants and a>0 without changing the agent’s behaviour\n\nValue function / Ordinal Utility function: In a deterministic environment (as is game-playing), agents only needs preference ranking on states, specific numbers don’t matter\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nNATURE OF UTILITY FUNCTIONS AND RELATION TO INDIVIDUAL QUANTITIES\n\nUtility functions map from lotteries to real numbers and must obey the axioms discussed in 16.2\n\n16.3.1: Utility assessment and utility scales\n\n- Preference elicitation (work out human’s utility function): Process involving presenting choices to humans and using the observed preferences to get the underlying utility function\n\n- Helpful to establish some scale on which utilities can be recorded and compared for any particular problem, even though there is no absolute scale for utilities as per 16.2\n\n- Normalized utilities use u⊥ = 0 and u⊤ = 1 for a scale. Given that, the utility of any particular prize S can be assessed by asking the agent to choose between S and a standard lottery [p, u⊤; (1-p), u⊥]\n\n16.3.2 The utility of money\n\n- Agents have a monotonic preference for more money\n\n- Agents want to maximize the expected monetary value (EMV)\n\n- Agents can be risk-averse, risk seeking or risk-neutral\n\n- The insurance premium is the difference between the EMV of a lottery and its certainty equivalent\n\n16.3.3 Expected utility and post-decision disappointment\n\n- Best action a* maximizes expected utility: a* = argmax_a EUR(a)\n\n- Models usually oversimplify because either information is missing or computation of the true expected utility is too difficult, so effectively working with estimates ÊU(a) of the true expected utility\n\n- General assumption for unbiased estimates, so zero expected value of the error, E(ÊU(a)-EU(a))=0\n\n- Even though estimate was unbiased real outcome usually significantly worse than the estimate because of tendancy for the estimated expected utility of the best choice to be too high (optimizer’s curse), afflicting even the most seasoned decision analysts and statisticans\n\n- Curse can be avoided with a Bayesian approach that uses an explicit probability model P(ÊU|EU) of the error in the utility estimates, therefore utility estimate is treated as evidence and posterior distribution for true utility is computed using Bayes’ rule\n\n16.3.4 Human judgment and irrationality\n\n- Decision theory is a normative theory, meaning that it describes how a rational agent should act\n\n- Literature gives evidence suggesting that humas are predictably irrational, being strongly attracted to gains that are certain\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nChapter 17: Sequential decision problems: Agent’s utility depends on a sequence of decisions,  incorporating utilities, uncertainty, and sensing, and including search and planning problems as special cases\n\nDEFINITION OF SEQUENTIAL DECISION PROBLEMS\n\n- An agent begins in the start state and must choose an action at each time step\n\n- Transition model describes the outcome of each action in each state, P(s’|s,a), which is the probability that action a in state s reaches\n\n- Markovian transitions are assumed: probability of reaching s’ from s depends only on s and not on the history of earlier states\n\n- Environment history: utility function depending on a sequence of states and actions rather than on a single state\n\n- Reward R(s,a,s’) can be positive or negative (bounded by +-Rmax) and is receives for every transition from s to s’ via action a\n\n- Markos Decision Process (MDP): sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards.\n\n- MDP includes: set of states (initial state s0); set ACTIONS(s) of actions in each state: transition model P(s’|s,a); reward function R(s,a,s’)\n\n- Dynamic Programming: simplifying a problem by recursively breaking it into smaller pieces and remembering the optimal solutions to the pieces, usually involved in methods for solving MDPs\n\n- Policy π: solution specifying what the agent should do for any state that the agent might reach (no fixed action sequence). Π(s) is the action recommended by the policy π for state s\n\n- Optimal policy π*: yields the highest expected utility\n\n17.1.1 Utilities over time\n\n- Finite/infinite horizon: means that there is a fixed time N after which nothing maters, optimal action in a given state may depend on how much time is left (optimal policy is nonstationary)\n\n- With no time limit, optimal policy is stationary, depending only on the current state\n\n- Proper policy: policy that is guaranteed to reach a terminal state (γ=1 possible for proper policies)\n\n- Infinite sequences comparable in terms of average reward obtained per time step\n\n17.1.2 Optimal policies and the utilities of states\n\n- Policies can be compared by comparing the expected utilites obtained during execution\n\n- Expected utility obtained by executing π starting in s: U^π(s) = E [ sum(t=0->inf) γ^tR(St, π(St),S(t+1)]\n\n- π*s = argmax_ π U^π(s)  is a policy, so it recommends an action for every state\n\n- Utilities are higher for states closer to the +1 exit, because fewer steps are required to reach the exit (fewer discounting)\n\n- π*(s) = argmax_(a in A(s)) sum(s’) P(s’|s,a)[R(s,a,s’)+ γU(S’)]\n\n- Action-utility function (Q-function) Q(s,a): expected utility taking a given action in a given state\n\n- Relation Q-function to Utility function: U(s) = max_a Q(s,a)\n \n17.1.3 Reward Scales\n\n17.1.4 Representing MDPs\n\n- Simplest way to represent P(s’,s,a) and R(s,a,s’): bism three-dimensional tables of size |S|^2|A|. Tables far too big for larger Problems\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nFour different algorithms for solving MDP:\n\n- Exact offline solutions: value iteration, policy iteration, linear programming\n\n- Online approximate algorithms: Monte Carlo planning\n\n17.2.1 Value Iteration\n\n- Basis is the Bellman equation\n\n- For n possible states, there are n Bellman equations, one for each state, containing n unknowns, the utilities of the states\n\n- Equations are nonlinear, because the “max” operator is not a linear operator\n\n- Iterative approach: 1. Start with arbitrary initial values for the utilities; 2. Calculate right-hand side of the equation and plug into left-hand side; 3. Thereby update the utility of each state from the utilities of its neighbors; 4. Repeat until we reach equilibrium\n\n- Iteration step / Bellman update: Ui+1(s) = max_(a in A(s)) sum(s’) P(s’|s,a)[R(s,a,s’)+ γUi(S’)], update is assumed to be applied simultaneously to all the states at each iteration\n\n- Guaranteed to reach an equilibrium when Bellman update applied infinitely often\n\n17.2.2 Policy Iteration\n\nPolicy iteration suggested from the fact that exact magnitude of the utilities involved need not be precise if one action is clearly better than all others.\n\nPolicy iteration alternates two steps, beginning from some initial policy π0:\n\n- Policy evaluation: calculates Ui = U^πi the utility of each state if πi were to be executed, given a policy π\n\n- Policy improvement: Calculates new MEU policy πi+1 using one-step look-ahead based on Ui\n\nTerminates when policy improvement yields no changes in the utilities, so Ui fixed point of the Bellman update, so solution to the Bellman equations and therefore πi must be an optimal policy\n\n- Modified policy Iteration: useful for large state spaces, no exact policy evaluation but simplified value iteration steps to give a reasonably good approximation of the utilities\n\n- Asynchronous policy iteration: General algorithm updating all utility/policy for all states at once (like value and policy iteration)\n\n17.2.3 Linear programming\n\n- General approach for formulating constrained optimization problems\n\n- A Bellman equations involve lot of sums and maxes, solving MDP can be reduced to solving a suitably formulated linear program\n\n- Utilities U(s) are considered as variables in the LP, we seek to minimize U(s) for all s subject to the inequalities U(s) >= sum(s’) P(s’|s,a)[R(s,a,s’)+ )+γU(s’)] for every state s and every action a\n\n- creates connection from dynamic programming to linear programming\n\n17.2.4 Online algorithms for MDPs\n\n- Exact offline solutions not possible for sufficiently large MDPs (such as Tetris)\n\n- In online algorithms, agent does significant amount of computation at each decision point rather than operation primarily with precomputed information\n\n- Example for straightforward approach is simplification of expectiminimax algorithm for game trees with chance nodes\n\n- Real-time dynamic programming (RTDP)\n\n\n## Module 8 Lecture Notes\n\nSummary MDP Algorithm:\n\nUse MDP if you want to:\n- Compute optimal values: iteration or policy iteration\n\n- Compute values for a particular policy: policy evaluation\n\n- Turn values into a policy: policy extraction (one-step lookahead)\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\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",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "d00aafe5-907b-4f6c-bf5d-e09fa538f696"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "MULTI-ARMED BANDIT PROBLEMS: SPECIFIC CLASS OF SEQUENTIAL DECISION PROBLEMS\n",
        "\n",
        "N-armed bandit problem is formal model, deciding which of n possible choices to choose. \n",
        "\n",
        "Clean and most general bandit problem definition:\n",
        "\n",
        "- Each arm Mi is a Markov reward process or MRP (MDP with only one possible action ai). It has states \\\n",
        "Si, transition model and reward. The arm defines a distribution over sequences of rewards Ri,0 , Ri,1 , ...\n",
        "\n",
        "- Overall bandit problem is an MDP: state space given by the Cartesian product S = S1 x ... x Sn\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "REINFORCEMENT LEARNING (RL) is an alternative to the supervised learning from previous chapters:\n",
        "\n",
        "- Agent interacts with the world and periodically receives rewards/reinforcements reflecting the performance\n",
        "\n",
        "- Reinforcement differs from previous learning because it's not given the MDP but the agent is in the MDP, \\\n",
        "it may not know transition model or reward function, has to act to learn more\n",
        "\n",
        "- Little bit of experience can be very helpful for reinforcement learning, especially in simulated environments\n",
        "\n",
        "Different approaches for reinforcement learning:\n",
        "\n",
        "Model-based reinforcement learning: transition model given; model can be initially unknown, agent then learns model from \\\n",
        "observing the effects of its actions; transition model is useful for state estimation in partially observable \\\n",
        "environments; such systems often learn a utility function U(s) defined in terms of the sum of rewards from state s onward\n",
        "  \n",
        "Model-free reinforcement learning: \n",
        "\n",
        "- Action-utility learning with Q-learning as its most common form, where \\\n",
        "the agent learns a Q-function (quality-function) Q(s,a) denoting the sum of rewards from state s onward if action a is taken\n",
        "\n",
        "- Policy search: agent learns policy π(s) that maps directly from states to actions, also known as reflex agent\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "Passive reinforcement learning: agent's policy π(s) is fixed and task is to learn the utilities of states U^π(s)(or state-action pairs), \\\n",
        "which is the expected total discounted reward if policy π is executed beginning in state s\n",
        "\n",
        "Passive learning task similar to policy evaluation task, difference being that the passive learning agent \\\n",
        "doesn't know the transition model P(s'|s,a) nor the reward function R(s,a,s')\n",
        "\n",
        "Agent executes a set of trials in the environment using its policy π, for each starting in first state executing sequence \\ \n",
        "until terminal state is reached, perceiving both current state and reward for transition.\n",
        "\n",
        "22.2.1 Direct utility estimation:\n",
        "\n",
        "Utility of a state defined as expected total reward from that state onward (reward-to-go), algo updates utility of the states after \\\n",
        "each sequence according to observed reward-to-go as runnign average\n",
        "\n",
        "-> reinforcement learning reduced to standard supervised learning problem\n",
        "\n",
        "-> ignores constraint that utility of a state is determined by reward and expected utility of successor states, obeying /\n",
        "thje bellman equations for a fixed policy\n",
        "\n",
        "-> Misses opportunites for learning by ignoring connections between states\n",
        "\n",
        "22.2.2 Adaptive dynamic programming:\n",
        "\n",
        "- Takes advantage of constraints among utilities of states by learning the transition model that connects them. \\\n",
        "\n",
        "- Solves MDP using dynamic programming. \n",
        "\n",
        "- Means for PLAs plugging the learned transition model and observed rewards \\\n",
        "into Bellman equation to calculate utilities of the states\n",
        " \n",
        "- Modified policy iteration uses simplified value iteration process to update utility estimates\n",
        "\n",
        "22.2.3 Temporal-difference learning:\n",
        "\n",
        "- Utilities of the observed states are adjusted with observed transitions so that they agree with the constraint equations.\n",
        "\n",
        "- α is the learning rate parameter, following update is applied when transition from state s to s' with action π(s): \\\n",
        "U^π(s) ← U^π(s)+α[R(s,π(s),s′)+γU^π(s′)−U^π(s)]\n",
        "\n",
        "- Parameter α can be turned into funcction decreasing as the number of times state has been visited increases\n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "Active reinforcement learning: agent must also figure out which actions to take\n",
        "\n",
        "- agent needs to learn a complete transition model with outcome probabilities for all \\\n",
        "actions rather than only for the fixed policy\n",
        "\n",
        "- learns utilities defined by the optimal policy via the Bellman equation\n",
        "\n",
        "- Agent decides on action in each step by obtained utility function U by one-step look-ahead to maximize expected utility\n",
        "\n",
        "22.3.1 Exploration\n",
        "\n",
        "- Greedy agent: Agent who always following recommendation of the optimal policy, likely to not converge to the optimal policy \\\n",
        "because the learned model is not the same as the true environment\n",
        "\n",
        "- Agent should tradeoff b/w exploitation of current best action to maximize short-term reward and exploration of previously unknown states/\n",
        "to gain info that might change the policy\n",
        "\n",
        "- Exploration function f(u,n) determines how greed is traded off against curiosity and should increase with u and decrease \\\n",
        "with n (number of times action a was tried in state s)\n",
        "\n",
        "22.3.2 Safe exploration\n",
        "\n",
        "For environments where bad state need to be avoided, need to use policy that works reasonably well for the \\\n",
        "whole range of models that have a reasonable chance of being the true model, even if the policy is \\\n",
        "suboptimal for the maximum-likelyhood model. Three mathematical approaches:\n",
        "\n",
        "- Bayesian reinforcement learning: assumes prior probability P(h) over hypotheses h about the true model; posterior \\\n",
        "probability P(h|e) is obtained in the usual way by Bayes' rule given observations to date. If aget stops learning \\\n",
        "optimal policy is the one that gives highest expected utility\n",
        "\n",
        "- Robust control theory: allows set of possible models H without assigning probs to each, defining an optimal robust \\\n",
        "policy as one giving best outcome in the worst case over H. Can result in overly conservative behaviour \n",
        "\n",
        "22.3.3 Temporal-difference Q-learning\n",
        "\n",
        "- Q-learning method avoids need for a model by learning action-utility function Q(s,a) instead of utility function U(s)\n",
        "\n",
        "- Q(s,a) is expected total discounted reward if agent takes action a in s and acts optimally afterwards\n",
        "\n",
        "- No need for look-ahead based on a transtiton model, just choosing argmax_a Q(s,a)\n",
        "\n",
        "TO BE ADDED: Bellman equation for Q(s,a) and Q-learning TD update (p. 802)\n",
        "\n",
        "- SARSA (state, action, reward, state, action) closely related to Q-learning, but Q-learning more flexible\n",
        "\"\"\"\n",
        "\n",
        "chapter22_4 =  \"\"\"\n",
        "Evaluation function can be used as compact measure of desirability for potentially vast state spaces.\n",
        "It is an approximate utility functionn, so we denote the process of constructing a compact approximation of the true utility \\\n",
        "function or Q-function with the term function approximation\n",
        "\n",
        "- Utility function can be approx. with weighted linear comb. of features: Ûθ(s) = θ1f1(s)+θ2f2(s)+···+θnfn(s)\n",
        "\n",
        "- Approx. utility function can be combined with look-ahead search for more accurate decisions\n",
        "\n",
        "22.4.1 Approximating direct utility estimation\n",
        "\n",
        "- Makes sense for reinforcement learning to use an online learning algorithm updating parameters after each trial\n",
        "\n",
        "- Widrow-Hoff rule / delta rule for online least-squared for updates\n",
        "\n",
        "22.4.2 Approximating temporal-difference learning\n",
        "\n",
        "- Ideas can also be applied to temporal-difference learning, adjusting the parameters to try reduce the temporal \\\n",
        "difference b/w successive states.\n",
        "\n",
        "TO BE ADDED: new versions of TD and Q-learning equations\n",
        "\n",
        "- Experience replay can be a solution for catastrophic forgetting\n",
        "\n",
        "22.4.3 Deep reinforcement learning\n",
        "\n",
        "Two reasons why necessary to go beyond linear function approximators:\n",
        "\n",
        "- May be no good linear function coming close to approximating the utility function or Q-function\n",
        "\n",
        "- May not be able to invest the necessary features, particularly in new domains\n",
        "\n",
        "Deep network is a function parameterized by θ, except that the function is much more complicated\n",
        "\n",
        "22.4.4 Reward shaping\n",
        "\n",
        "Reward shaping involves supplying the agent with additional rewards (called pseudorewards) for making progress. \\\n",
        "Such rewards can speed up learning enormously\n",
        "\n",
        "22.4.5 Hierarchical reinforcement learning\n",
        "\n",
        "Hierarchical reinforcement learning (HRL) is an approach to break up very long action sequences into a few pieces, \\\n",
        "until the action sequences are short enough to make learning easy. \n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "\n",
        "- Idea of Policy Search is to keep twiddling the policy as long as its performance imrpvoes, then stop.\n",
        "\n",
        "- Interested primarily in parameterized representations of π that have far fewer parameters than states in the state space\n",
        "\n",
        "- Can represent π by collection of parameterized Q-functions (one for each action) and take the action with the highest /\n",
        "predicted value: π()s) = argmax_a ^Q_θ(s,a)\n",
        "\n",
        "- Problem with policy representations is that the policy is a discontinuous function of the parameters when actions are discrete, \\\n",
        "so there will be values of θ such that an inﬁnitesimal change in θ causes the policy to switch from one action to another, \\\n",
        "meaning that the value of the policy may also change discontinuosly, making gradient-based search difficult\n",
        "\n",
        "- Therefore Policy search methods often use a stochastic policy representation π_θ(s,a) specifying the progrability of selecting \\\n",
        "action a in state s\n",
        "\n",
        "- Improving the policy: deterministic vs non-deterministic environments\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "Important ideas in reinforcement learning:\n",
        "\n",
        "- Exploration: Unknown actions have to be tried to get information\n",
        "\n",
        "- Exploitation: have to use what is known\n",
        "\n",
        "- Regret: even if you learn intelligently you make mistakes\n",
        "\n",
        "- Sampling: because of chance, things have to be tried repeatedly\n",
        "\n",
        "- Difficulty: learning can be much harder than solving a known MDP\n",
        "\n",
        "Offline Solution (MDPs) vs Online Learning (Reinforcement Learning)\n",
        "\n",
        "Model-Based Learning: \n",
        "  \n",
        "- Step 1: Learn empirical MDP model\n",
        "\n",
        "- Step 2: Solve the learned MDP\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter22_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter22_2))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 289\n",
            "The length in characters is 2050\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2694
        },
        "cellView": "form",
        "outputId": "98167b04-10ba-469e-d5bc-9ff24f80d181"
      },
      "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",
        "  (\"AIMA Chapter 22.5 Policy Search\", chapter22_5),\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": 6,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nMULTI-ARMED BANDIT PROBLEMS: SPECIFIC CLASS OF SEQUENTIAL DECISION PROBLEMS\n\nN-armed bandit problem is formal model, deciding which of n possible choices to choose. \n\nClean and most general bandit problem definition:\n\n- Each arm Mi is a Markov reward process or MRP (MDP with only one possible action ai). It has states Si, transition model and reward. The arm defines a distribution over sequences of rewards Ri,0 , Ri,1 , ...\n\n- Overall bandit problem is an MDP: state space given by the Cartesian product S = S1 x ... x Sn\n\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nREINFORCEMENT LEARNING (RL) is an alternative to the supervised learning from previous chapters:\n\n- Agent interacts with the world and periodically receives rewards/reinforcements reflecting the performance\n\n- Reinforcement differs from previous learning because it's not given the MDP but the agent is in the MDP, it may not know transition model or reward function, has to act to learn more\n\n- Little bit of experience can be very helpful for reinforcement learning, especially in simulated environments\n\nDifferent approaches for reinforcement learning:\n\nModel-based reinforcement learning: transition model given; model can be initially unknown, agent then learns model from observing the effects of its actions; transition model is useful for state estimation in partially observable environments; such systems often learn a utility function U(s) defined in terms of the sum of rewards from state s onward\n  \nModel-free reinforcement learning: \n\n- Action-utility learning with Q-learning as its most common form, where the agent learns a Q-function (quality-function) Q(s,a) denoting the sum of rewards from state s onward if action a is taken\n\n- Policy search: agent learns policy π(s) that maps directly from states to actions, also known as reflex agent\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\nPassive reinforcement learning: agent's policy π(s) is fixed and task is to learn the utilities of states U^π(s)(or state-action pairs), which is the expected total discounted reward if policy π is executed beginning in state s\n\nPassive learning task similar to policy evaluation task, difference being that the passive learning agent doesn't know the transition model P(s'|s,a) nor the reward function R(s,a,s')\n\nAgent executes a set of trials in the environment using its policy π, for each starting in first state executing sequence \\ \nuntil terminal state is reached, perceiving both current state and reward for transition.\n\n22.2.1 Direct utility estimation:\n\nUtility of a state defined as expected total reward from that state onward (reward-to-go), algo updates utility of the states after each sequence according to observed reward-to-go as runnign average\n\n-> reinforcement learning reduced to standard supervised learning problem\n\n-> ignores constraint that utility of a state is determined by reward and expected utility of successor states, obeying /\nthje bellman equations for a fixed policy\n\n-> Misses opportunites for learning by ignoring connections between states\n\n22.2.2 Adaptive dynamic programming:\n\n- Takes advantage of constraints among utilities of states by learning the transition model that connects them. \n- Solves MDP using dynamic programming. \n\n- Means for PLAs plugging the learned transition model and observed rewards into Bellman equation to calculate utilities of the states\n \n- Modified policy iteration uses simplified value iteration process to update utility estimates\n\n22.2.3 Temporal-difference learning:\n\n- Utilities of the observed states are adjusted with observed transitions so that they agree with the constraint equations.\n\n- α is the learning rate parameter, following update is applied when transition from state s to s' with action π(s): U^π(s) ← U^π(s)+α[R(s,π(s),s′)+γU^π(s′)−U^π(s)]\n\n- Parameter α can be turned into funcction decreasing as the number of times state has been visited increases\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nActive reinforcement learning: agent must also figure out which actions to take\n\n- agent needs to learn a complete transition model with outcome probabilities for all actions rather than only for the fixed policy\n\n- learns utilities defined by the optimal policy via the Bellman equation\n\n- Agent decides on action in each step by obtained utility function U by one-step look-ahead to maximize expected utility\n\n22.3.1 Exploration\n\n- Greedy agent: Agent who always following recommendation of the optimal policy, likely to not converge to the optimal policy because the learned model is not the same as the true environment\n\n- Agent should tradeoff b/w exploitation of current best action to maximize short-term reward and exploration of previously unknown states/\nto gain info that might change the policy\n\n- Exploration function f(u,n) determines how greed is traded off against curiosity and should increase with u and decrease with n (number of times action a was tried in state s)\n\n22.3.2 Safe exploration\n\nFor environments where bad state need to be avoided, need to use policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, even if the policy is suboptimal for the maximum-likelyhood model. Three mathematical approaches:\n\n- Bayesian reinforcement learning: assumes prior probability P(h) over hypotheses h about the true model; posterior probability P(h|e) is obtained in the usual way by Bayes' rule given observations to date. If aget stops learning optimal policy is the one that gives highest expected utility\n\n- Robust control theory: allows set of possible models H without assigning probs to each, defining an optimal robust policy as one giving best outcome in the worst case over H. Can result in overly conservative behaviour \n\n22.3.3 Temporal-difference Q-learning\n\n- Q-learning method avoids need for a model by learning action-utility function Q(s,a) instead of utility function U(s)\n\n- Q(s,a) is expected total discounted reward if agent takes action a in s and acts optimally afterwards\n\n- No need for look-ahead based on a transtiton model, just choosing argmax_a Q(s,a)\n\nTO BE ADDED: Bellman equation for Q(s,a) and Q-learning TD update (p. 802)\n\n- SARSA (state, action, reward, state, action) closely related to Q-learning, but Q-learning more flexible\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\nEvaluation function can be used as compact measure of desirability for potentially vast state spaces.\nIt is an approximate utility functionn, so we denote the process of constructing a compact approximation of the true utility function or Q-function with the term function approximation\n\n- Utility function can be approx. with weighted linear comb. of features: Ûθ(s) = θ1f1(s)+θ2f2(s)+···+θnfn(s)\n\n- Approx. utility function can be combined with look-ahead search for more accurate decisions\n\n22.4.1 Approximating direct utility estimation\n\n- Makes sense for reinforcement learning to use an online learning algorithm updating parameters after each trial\n\n- Widrow-Hoff rule / delta rule for online least-squared for updates\n\n22.4.2 Approximating temporal-difference learning\n\n- Ideas can also be applied to temporal-difference learning, adjusting the parameters to try reduce the temporal difference b/w successive states.\n\nTO BE ADDED: new versions of TD and Q-learning equations\n\n- Experience replay can be a solution for catastrophic forgetting\n\n22.4.3 Deep reinforcement learning\n\nTwo reasons why necessary to go beyond linear function approximators:\n\n- May be no good linear function coming close to approximating the utility function or Q-function\n\n- May not be able to invest the necessary features, particularly in new domains\n\nDeep network is a function parameterized by θ, except that the function is much more complicated\n\n22.4.4 Reward shaping\n\nReward shaping involves supplying the agent with additional rewards (called pseudorewards) for making progress. Such rewards can speed up learning enormously\n\n22.4.5 Hierarchical reinforcement learning\n\nHierarchical reinforcement learning (HRL) is an approach to break up very long action sequences into a few pieces, until the action sequences are short enough to make learning easy. \n\n\n\n## AIMA Chapter 22.5 Policy Search\n\n\n- Idea of Policy Search is to keep twiddling the policy as long as its performance imrpvoes, then stop.\n\n- Interested primarily in parameterized representations of π that have far fewer parameters than states in the state space\n\n- Can represent π by collection of parameterized Q-functions (one for each action) and take the action with the highest /\npredicted value: π()s) = argmax_a ^Q_θ(s,a)\n\n- Problem with policy representations is that the policy is a discontinuous function of the parameters when actions are discrete, so there will be values of θ such that an inﬁnitesimal change in θ causes the policy to switch from one action to another, meaning that the value of the policy may also change discontinuosly, making gradient-based search difficult\n\n- Therefore Policy search methods often use a stochastic policy representation π_θ(s,a) specifying the progrability of selecting action a in state s\n\n- Improving the policy: deterministic vs non-deterministic environments\n\n\n\n## Module 9 Lecture Notes\n\nImportant ideas in reinforcement learning:\n\n- Exploration: Unknown actions have to be tried to get information\n\n- Exploitation: have to use what is known\n\n- Regret: even if you learn intelligently you make mistakes\n\n- Sampling: because of chance, things have to be tried repeatedly\n\n- Difficulty: learning can be much harder than solving a known MDP\n\nOffline Solution (MDPs) vs Online Learning (Reinforcement Learning)\n\nModel-Based Learning: \n  \n- Step 1: Learn empirical MDP model\n\n- Step 2: Solve the learned MDP\n\n\n## Module 9 Definitions\n* **Term** - your definition here\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",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "b459e90e-8976-415b-888b-e47bf1a80cdc"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"\n",
        "- Uncertainly that agents need to handle in the real world can be due to partial observability, nondeterminism or adversaries\n",
        "\n",
        "- Problem-solving and logical agents handle uncertaintly by keeping track of a belief state and generating a contingency \\\n",
        "plan handling every possible eventuality it may observe during execution. Drawbacks as agent need to consider every possible \\\n",
        "explanation for sensor observations, a correct contigent plan handlingevery eventuality can grow arbitrarily large and sometimes \\\n",
        "no plan is guaranteed to achieve the goal\n",
        "\n",
        "12.1.1 Summarizing uncertainty\n",
        "\n",
        "- Trying to use logic to cope with a domain mgith fail for three main reasons: Laziness, Theoretical ignorance, Practical ignorance\n",
        "\n",
        "- Agent's knowledge can at best provide only a egree of belief in the relevant sentences, and out main tooll for dealing with such \\\n",
        "degrees of belief is probability theory\n",
        "\n",
        "- Difference of epistemological commitments: logical agent believes only true/false/no_opinion for each sentence, while \\\n",
        "probabilistic agent have numerical degree of belief b/w 0 and 1\n",
        "\n",
        "- Probability theory provides a way of summarizing the uncertainty that comes from our laziness and ignorance, thereby solving the \\\n",
        "qualification problem\n",
        "\n",
        "Probability satements are made with respect to a knowledge state, not the real world\n",
        "\n",
        "12.1.2 Uncertainty and rational decions\n",
        "\n",
        "- Outcome is a completely specified state: to make choice, agent must have preferences among the different possible outcomes of various plans\n",
        "\n",
        "- Utility function can account for any set of preferences\n",
        "\n",
        "- Decision Theory = probability theory + utility theory (preferences)\n",
        "\n",
        "- Maximum expected utility (MEU): agent is rational if and only if it chooses the action that yields the highest \\\n",
        "expected utility, averaged over all the possible outcomes of the action\n",
        "\n",
        "- Decision-theoretic agent's belief state represents not just the possibilities for world states but also their probabilities\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "\n",
        "12.2.1 What probabilities are about\n",
        "\n",
        "- Sample space: set of all possible worlds which are mutually exclusive and exhaustive\n",
        "\n",
        "- Ω (uppercase omega) is used to refer to the sample space\n",
        "\n",
        "- ω (lowercase omega) refers to elements of the space, particularly possible worlds\n",
        "\n",
        "- Fully specified probability model associates a numerical probability P(ω) with each possible world (b/w 0 and 1)\n",
        "\n",
        "- Events: sets of possible worlds for specific event\n",
        "\n",
        "- Proposition: corresponds to a set of worlds containing just the possible worlds in which the proposition holds\n",
        "\n",
        "- Probability associated with a proposition is deﬁned to be the sum of the probabilities of the worlds in which it holds\n",
        "\n",
        "- Unconditional probabilities (P(x)) vs conditional/posterior probabilities given y (P(x|y))\n",
        "\n",
        "- Agent needs to condition on all the evidence it has observed to make decisions\n",
        "\n",
        "12.2.2 The language of propositions in probability assertions\n",
        "\n",
        "- Variables in probability theory called random variables, their names beginning with uppercase\n",
        "\n",
        "- Random variable is function mapping the domain of possible worlds Ω to some range (set of possible values), names for values being lowercase\n",
        "\n",
        "- Propositions of the form A=true are abbreviated simply as a, A=false is abbreviated as ¬a\n",
        "\n",
        "- Common in probability notation to use a comma for conjunction, e.g.  P(cavity | ¬toothache,teen)\n",
        "\n",
        "- P statement defines probability distribution for a random variable, e.g. P(Weather)= 〈 0.6,0.1,0.29,0.01 〉\n",
        "\n",
        "- P notation is also used for conditional distributions: P(X|Y) gives the values of P(X=xi|Y=yj) for each possible i, j pair\n",
        "\n",
        "- For continuos variables, probabuility density function used\n",
        "\n",
        "- P(x,y) denotes the probabilities of all combinations of the values of x and y; P(x,y) = P(x|y)*P(y)\n",
        "\n",
        "- Possible world is defined to be an assignment of values to all the random variables under consideration\n",
        "\n",
        "- Full joint probability distribution defines a probability model\n",
        "\n",
        "12.2.3 Probability axioms and their reasonableness\n",
        "\n",
        "- Relationship between the probability of a proposition and the probability of its negation: P(¬a) = 1 - P(a)\n",
        "\n",
        "- Inclusion-exclusion principle (probability of a disjunction): P(a∨b) = P(a)+P(b)−P(a∧b)\n",
        "\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "\n",
        "- Simple method for probabilistic inference: computation of posterior probabilities for query propositions given observed evidence. \\\n",
        "Use full joint distribution as knowledge base from which answers to all questions may be derived\n",
        "\n",
        "- Probabilities in the joint distribution sum to 1\n",
        "\n",
        "- Common task to extract distribution over some subset of variables or a single variable (marginal probability)\n",
        "\n",
        "- Marginalization (summing out): marginalization rule for any sets of variables Y and Z: P(Y) = ∑_s P(Y,Z=z)\n",
        "\n",
        "- Conditioning Rule: P(Y) = ∑_z P(Y|z)P(z)\n",
        "\n",
        "- Marginalization and conditioning useful rules for different derivations involving probability expressions\n",
        "\n",
        "- General inference procedure (single variable X, list of evidence variables E, list of observed values for them e, \\\n",
        "remaining unobserved variables Y): Query P(X|e) can be evaluated as P(X|e) = αP(X,e) = α ∑_y P(X,e,y)\n",
        "\n",
        "- X, E, Y form complete set of variables in the domain, so P(X,e,y) simply a subset of probabilites from the full joint distribution\n",
        "\"\"\"\n",
        "\n",
        "chapter12_4 = \"\"\"\n",
        "\n",
        "- Independence assertions usually based on knowledge of the domain\n",
        "\n",
        "- If available, independence assertions can help reduce the size of the domain representation and complexity of the inference problem\n",
        "\n",
        "- Separation of entire sets of variables by independence is rare, because whenever a connection (also very indirect) /\n",
        "exisits b/w two variables, the independence fails to hold\n",
        "\n",
        "\"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "\n",
        "- Bayes Rule: P(b|a) = (P(a|b)P(b))/P(a)\n",
        "\n",
        "- General case of Bayes' rule for multivalued variables: P(Y|X) = ((P(X|Y)P(Y))/P(X)\n",
        "\n",
        "- General version conditionalized on some background evidence e: P(Y|X,e) = ((P(X|Y,e)P(Y|e))/P(X|e)\n",
        "\n",
        "12.5.1 Applying Bayes' rule: the simple case\n",
        "\n",
        "- Rule allows us to compute the single term P(b|a) in terms of three terms: P(a|b), P(b), and P(a)\n",
        "\n",
        "- Cause effect relationship: P(cause|effect) = (P(effect|cause)P(cause))/P(effect)\n",
        "\n",
        "- Avoid asessing prior probability of the evidence (here, P(s)) by instead computing a posterior probability for each value \\\n",
        "of the query variable (here, m and ¬m) and then normalizing results can also be applied using Bayes' rule: P(M|s) = α〈P(s|m)P(m),P(s|¬m)P(¬m)〉 \\\n",
        "(P(s|¬m) to be estimated instead of P(s))\n",
        "\n",
        "- General Form of Bayes' rule with normalization: P(Y|X) = α P(X|Y)P(Y), α being normalization constant to make entries in P(Y|X) \\\n",
        "sum to 1\n",
        "\n",
        "12.5.2 Using Bayes' rule: Combining evidence\n",
        "\n",
        "- Conditional independence of two variables X and Y, given a third variable Z: P(X,Y|Z) = P(X|Z)P(Y|Z)\n",
        "\n",
        "- Representation size: n variables that are all conditionally independent given another variable, size of representation \\\n",
        "grows as O(n) instead of O(n^2)\n",
        "\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "\n",
        "- Full joint distribution can be written as P(Cause,Effect 1,...,Effect n) = P(Cause) ∏i P(Effect i| Cause) (12.20)\n",
        "\n",
        "- Probability distribution called naive Bayes model because often used in cases even if effect variables are not strictly independent /\n",
        "given the cause variable, however often works well in practice\n",
        "\n",
        "Use naive Bayes:\n",
        "\n",
        "- Apply 12.20 (see above) to obtain probability of the cause given some unobserved effects\n",
        "\n",
        "- Observed Effects E=e, while remaining effect variables Y are unobserved\n",
        "\n",
        "- Apply standard method for inference from the joint distribution: P(Cause|e) = α ∑y P(Cause,e,y)\n",
        "\n",
        "- Word interpretation of the equation: \"for each possible cause, multiply the prior probability of the cause by the product \\\n",
        "of the conditional probabilities of the observed effects given the cause; then normalize the result\"\n",
        "\n",
        "- Calculation run time is linear in the number of observed effects and does not depend on the number of unobserved effects\n",
        "\n",
        "12.6.1 Text classification with naive Bayes\n",
        "\n",
        "- Naive Bayes assumes that words occur independently in documents, with frequencies determined by the document category, so \\\n",
        "independence assumption is clearly violated in practice\n",
        "\n",
        "- Violation of independence usually meansfinal posterior probabilities will be much closer to 1 or 0 than they should be, so model is overconfident\n",
        "\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\"\n",
        "\n",
        "- Independence and conditional independence relationships can be used to simplify te required summations\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "- Symplifying Assumption = Markov Assumption: Probability depends on the previous k words, not the whole context\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter12_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter12_2))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 314\n",
            "The length in characters is 2181\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2720
        },
        "cellView": "form",
        "outputId": "643e1d8a-abb1-470b-d519-1f3c391232b7"
      },
      "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": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- Uncertainly that agents need to handle in the real world can be due to partial observability, nondeterminism or adversaries\n\n- Problem-solving and logical agents handle uncertaintly by keeping track of a belief state and generating a contingency plan handling every possible eventuality it may observe during execution. Drawbacks as agent need to consider every possible explanation for sensor observations, a correct contigent plan handlingevery eventuality can grow arbitrarily large and sometimes no plan is guaranteed to achieve the goal\n\n12.1.1 Summarizing uncertainty\n\n- Trying to use logic to cope with a domain mgith fail for three main reasons: Laziness, Theoretical ignorance, Practical ignorance\n\n- Agent's knowledge can at best provide only a egree of belief in the relevant sentences, and out main tooll for dealing with such degrees of belief is probability theory\n\n- Difference of epistemological commitments: logical agent believes only true/false/no_opinion for each sentence, while probabilistic agent have numerical degree of belief b/w 0 and 1\n\n- Probability theory provides a way of summarizing the uncertainty that comes from our laziness and ignorance, thereby solving the qualification problem\n\nProbability satements are made with respect to a knowledge state, not the real world\n\n12.1.2 Uncertainty and rational decions\n\n- Outcome is a completely specified state: to make choice, agent must have preferences among the different possible outcomes of various plans\n\n- Utility function can account for any set of preferences\n\n- Decision Theory = probability theory + utility theory (preferences)\n\n- Maximum expected utility (MEU): agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action\n\n- Decision-theoretic agent's belief state represents not just the possibilities for world states but also their probabilities\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n\n12.2.1 What probabilities are about\n\n- Sample space: set of all possible worlds which are mutually exclusive and exhaustive\n\n- Ω (uppercase omega) is used to refer to the sample space\n\n- ω (lowercase omega) refers to elements of the space, particularly possible worlds\n\n- Fully specified probability model associates a numerical probability P(ω) with each possible world (b/w 0 and 1)\n\n- Events: sets of possible worlds for specific event\n\n- Proposition: corresponds to a set of worlds containing just the possible worlds in which the proposition holds\n\n- Probability associated with a proposition is deﬁned to be the sum of the probabilities of the worlds in which it holds\n\n- Unconditional probabilities (P(x)) vs conditional/posterior probabilities given y (P(x|y))\n\n- Agent needs to condition on all the evidence it has observed to make decisions\n\n12.2.2 The language of propositions in probability assertions\n\n- Variables in probability theory called random variables, their names beginning with uppercase\n\n- Random variable is function mapping the domain of possible worlds Ω to some range (set of possible values), names for values being lowercase\n\n- Propositions of the form A=true are abbreviated simply as a, A=false is abbreviated as ¬a\n\n- Common in probability notation to use a comma for conjunction, e.g.  P(cavity | ¬toothache,teen)\n\n- P statement defines probability distribution for a random variable, e.g. P(Weather)= 〈 0.6,0.1,0.29,0.01 〉\n\n- P notation is also used for conditional distributions: P(X|Y) gives the values of P(X=xi|Y=yj) for each possible i, j pair\n\n- For continuos variables, probabuility density function used\n\n- P(x,y) denotes the probabilities of all combinations of the values of x and y; P(x,y) = P(x|y)*P(y)\n\n- Possible world is defined to be an assignment of values to all the random variables under consideration\n\n- Full joint probability distribution defines a probability model\n\n12.2.3 Probability axioms and their reasonableness\n\n- Relationship between the probability of a proposition and the probability of its negation: P(¬a) = 1 - P(a)\n\n- Inclusion-exclusion principle (probability of a disjunction): P(a∨b) = P(a)+P(b)−P(a∧b)\n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n\n- Simple method for probabilistic inference: computation of posterior probabilities for query propositions given observed evidence. Use full joint distribution as knowledge base from which answers to all questions may be derived\n\n- Probabilities in the joint distribution sum to 1\n\n- Common task to extract distribution over some subset of variables or a single variable (marginal probability)\n\n- Marginalization (summing out): marginalization rule for any sets of variables Y and Z: P(Y) = ∑_s P(Y,Z=z)\n\n- Conditioning Rule: P(Y) = ∑_z P(Y|z)P(z)\n\n- Marginalization and conditioning useful rules for different derivations involving probability expressions\n\n- General inference procedure (single variable X, list of evidence variables E, list of observed values for them e, remaining unobserved variables Y): Query P(X|e) can be evaluated as P(X|e) = αP(X,e) = α ∑_y P(X,e,y)\n\n- X, E, Y form complete set of variables in the domain, so P(X,e,y) simply a subset of probabilites from the full joint distribution\n\n\n## AIMA Chapter 12.4 Independence\n\n\n- Independence assertions usually based on knowledge of the domain\n\n- If available, independence assertions can help reduce the size of the domain representation and complexity of the inference problem\n\n- Separation of entire sets of variables by independence is rare, because whenever a connection (also very indirect) /\nexisits b/w two variables, the independence fails to hold\n\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n\n- Bayes Rule: P(b|a) = (P(a|b)P(b))/P(a)\n\n- General case of Bayes' rule for multivalued variables: P(Y|X) = ((P(X|Y)P(Y))/P(X)\n\n- General version conditionalized on some background evidence e: P(Y|X,e) = ((P(X|Y,e)P(Y|e))/P(X|e)\n\n12.5.1 Applying Bayes' rule: the simple case\n\n- Rule allows us to compute the single term P(b|a) in terms of three terms: P(a|b), P(b), and P(a)\n\n- Cause effect relationship: P(cause|effect) = (P(effect|cause)P(cause))/P(effect)\n\n- Avoid asessing prior probability of the evidence (here, P(s)) by instead computing a posterior probability for each value of the query variable (here, m and ¬m) and then normalizing results can also be applied using Bayes' rule: P(M|s) = α〈P(s|m)P(m),P(s|¬m)P(¬m)〉 (P(s|¬m) to be estimated instead of P(s))\n\n- General Form of Bayes' rule with normalization: P(Y|X) = α P(X|Y)P(Y), α being normalization constant to make entries in P(Y|X) sum to 1\n\n12.5.2 Using Bayes' rule: Combining evidence\n\n- Conditional independence of two variables X and Y, given a third variable Z: P(X,Y|Z) = P(X|Z)P(Y|Z)\n\n- Representation size: n variables that are all conditionally independent given another variable, size of representation grows as O(n) instead of O(n^2)\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n\n- Full joint distribution can be written as P(Cause,Effect 1,...,Effect n) = P(Cause) ∏i P(Effect i| Cause) (12.20)\n\n- Probability distribution called naive Bayes model because often used in cases even if effect variables are not strictly independent /\ngiven the cause variable, however often works well in practice\n\nUse naive Bayes:\n\n- Apply 12.20 (see above) to obtain probability of the cause given some unobserved effects\n\n- Observed Effects E=e, while remaining effect variables Y are unobserved\n\n- Apply standard method for inference from the joint distribution: P(Cause|e) = α ∑y P(Cause,e,y)\n\n- Word interpretation of the equation: \"for each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause; then normalize the result\"\n\n- Calculation run time is linear in the number of observed effects and does not depend on the number of unobserved effects\n\n12.6.1 Text classification with naive Bayes\n\n- Naive Bayes assumes that words occur independently in documents, with frequencies determined by the document category, so independence assumption is clearly violated in practice\n\n- Violation of independence usually meansfinal posterior probabilities will be much closer to 1 or 0 than they should be, so model is overconfident\n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n- Independence and conditional independence relationships can be used to simplify te required summations\n\n\n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n- Symplifying Assumption = Markov Assumption: Probability depends on the previous k words, not the whole context\n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "4f9abc2d-aee4-4830-fd3e-8d41cd1176dd"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "- Bayesian network represents the dependencies among variables and is a directed graph in which each node is annotated with quantitative probability information\n",
        "\n",
        "- Nodes correspond to random variables, directed_links/arrows connect pairs of nodes\n",
        "\n",
        "- Node Xi has associated probability information θ(Xi|Parents(Xi)) quantifying the effect of the parents on the node using a ﬁnite number of parameters\n",
        "\n",
        "- Network (set of nodes and links) specifies conditional independence relationsjips that hold in the domain\n",
        "\n",
        "- X->Y: X has a direct influence on Y, suggests that causes should be parrents of effects\n",
        "\n",
        "- Conditiaonal probability table (CPT): Local probability information to each node, each row contains cond. prob. of each node value for a conditioning case\n",
        "\n",
        "- False value often omitted as 1 - p, generally a table for a Boolean variable with k Boolean parents contains 2^k independently specifiable probabilites\n",
        "\"\"\"\n",
        "\n",
        "chapter13_2 = \"\"\"\n",
        "- Syntax of a Bayes net consists of a directed acylclic graph with some local probability information attached to each node\n",
        "\n",
        "- Semantics defines how the syntax corresponds to a joint distr. over the variables of the network\n",
        "\n",
        "- Semantics of Bayes nets defines each entry in the joint distr. as P(x 1,...,x n) = n∏i=1 θ(xi|parents(Xi)), \\\n",
        "parents(Xi) denoting the values of Parents(Xi) that appear in x1,...,xn\n",
        "\n",
        "- Each entry in the joint distr. is represented by the product of the approp. elements of the local conditional distr. in the Bayes net.\n",
        "\n",
        "- P(xi|parents(Xi)) = θ(xi|parents(Xi)) so we can rewrite P(x 1,...,x n) = n∏i=1 P(xi|parents(Xi)), meaning that when one estimates values for \\\n",
        "the local cond. distr., they need to be the actual conditional probabilities for the variables given its parents\n",
        "\n",
        "- Chain Rule: P(x1,...,xn) = n∏i=1 P(xi|xi−1,...,x1)\n",
        "\n",
        "- P(Xi|Xi−1 ,...,X1) = P(Xi|Parents(Xi)) provided that Parents(Xi) ⊆ {Xi−1,...,X1}, so Bayesian network is a correct repr. of the domain only if each \\\n",
        "node is cond. indep. of its other predecessors in the node ordering, given its parents\n",
        "\n",
        "- Compactness and node ordering: ayes net often fare more compact than full joint distribution, well chosen node ordering required for compact Bayes net\n",
        "\n",
        "13.2.1 Conditional independence relations in Bayesian networks\n",
        "\n",
        "- Each variable is conditionally independent of its non-descendants, given its parents\n",
        "\n",
        "- Non-descendants property combined with interpr. of the network parameters θ(Xi|Parents(Xi)) as cond. prob. P(X i| Parents(X i)) sufﬁces to reconstruct \\\n",
        "full joint distribution \n",
        "\n",
        "- Markov blanket property: variable cond. indep. of all other nodes in the network, given its parents, cildren and children's parents\n",
        "\n",
        "- Determination if Bayes net Z d-separates X and Y is important\n",
        "\n",
        "13.2.2 Efficient Representation of Cinditional Distributions\n",
        "\n",
        "- Filling in the CPT for a node requires up to O(2^k)\n",
        "\n",
        "- Relationships are describable by a canonical distribution that fits some standard pattern, simplest example provided by deterministic nodes, whose value is specified \\\n",
        "exactly by the values of its parents with no uncertainty.\n",
        "\n",
        "- Context-specific independence (CSI) is exhibited by conditional distribution if a variable is cond. indep. of some of its parents given certain values of others\n",
        "\n",
        "- Noisy-OR model allows for uncertainly about the ability of each parent to cause the child being true, making two assumptions: 1. all the possible causes are listed; 2. inhibition /\n",
        "of each parent is indep. of inhibition of any other parents\n",
        "\n",
        "13.2.3 Bayesoan nets with continuous variables\n",
        "\n",
        "- continuous variables can by handled with discretization or nonparametric representation\n",
        "\n",
        "- Hybrid Bayesian network contains both discrete and continuous variables\n",
        "\n",
        "- Linear-Gaussian conditional distribution most common choice\n",
        "\n",
        "13.2.4 Case study: Car insurance\n",
        "\n",
        "- Bayes net includes hidden variables that are neither input nor output variables but essential for structuring the network\n",
        "\"\"\"\n",
        "\n",
        "chapter13_3 = \"\"\"\n",
        "Basic task of any probabilistic inference system is computation of posterior probability distribution for a set of query variables given some obsered event (assignment \\\n",
        "of value to a set of evidence variables)\n",
        "\n",
        "13.3.1 Inference by enumeration\n",
        "\n",
        "- Any conditional probability can be computed by summing terms from the full joint distribution, so a query P(X|e) can be answered using P(X|e) = αP(X,e) = α ∑y P(X,e,y)\n",
        "\n",
        "- P(x,e,y) in the joint distribution can be written as products of cond. prob. from the netwotk, so a query can be answered using a Bayes net by computing sums of products \\\n",
        "of conditional probabilities from the network\n",
        "\n",
        "- Complexity (O(n2^n) in the worst case) can be reduced to O(2^n) taking advantage of the nested structure of the computation (moving summations inwards as far as possible)\n",
        "\n",
        "13.3.2 The variable elimination algorithm\n",
        "\n",
        "- Elimination of repeated calculations can improve the enumeration algorithm substantially\n",
        "\n",
        "- The elimination of variables works by evaluating expressions in right-to-left order \n",
        "\n",
        "- Operations on factors: Pointwise product of two factors f and g yields a new factor h whose variables are the union of the variables in f and g and whose elements are given \\\n",
        "by the product of the corresponding elements in the two factors\n",
        "\n",
        "- Time and space requirements of variable elimination dominated by size of the largest factor construxted during he operation of the algorithm, \\\n",
        "being determined by the order of elimination of variables and the structure of the network.\n",
        "\n",
        "- Determination of optimal ordering is intracable, but several good heuristics are available. \n",
        "\n",
        "13.3.3 The complexity of exact inference\n",
        "\n",
        "13.3.4 Clustering algorithms\n",
        "\n",
        "- Clustering Algorithms can be used to reduce the time to O(n), so those algorithms are widely used in commercial Bayes net tools.\n",
        "\n",
        "- Basic idea of clustering is to join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree\n",
        "\n",
        "- Two Boolean nodes are replaced by a meganode that takes on four possible values\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter13_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter13_2))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 429\n",
            "The length in characters is 2968\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1607
        },
        "cellView": "form",
        "outputId": "f30c05c0-fbc1-478d-83a6-79c2a9d24c42"
      },
      "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": 10,
      "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\n- Bayesian network represents the dependencies among variables and is a directed graph in which each node is annotated with quantitative probability information\n\n- Nodes correspond to random variables, directed_links/arrows connect pairs of nodes\n\n- Node Xi has associated probability information θ(Xi|Parents(Xi)) quantifying the effect of the parents on the node using a ﬁnite number of parameters\n\n- Network (set of nodes and links) specifies conditional independence relationsjips that hold in the domain\n\n- X->Y: X has a direct influence on Y, suggests that causes should be parrents of effects\n\n- Conditiaonal probability table (CPT): Local probability information to each node, each row contains cond. prob. of each node value for a conditioning case\n\n- False value often omitted as 1 - p, generally a table for a Boolean variable with k Boolean parents contains 2^k independently specifiable probabilites\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- Syntax of a Bayes net consists of a directed acylclic graph with some local probability information attached to each node\n\n- Semantics defines how the syntax corresponds to a joint distr. over the variables of the network\n\n- Semantics of Bayes nets defines each entry in the joint distr. as P(x 1,...,x n) = n∏i=1 θ(xi|parents(Xi)), parents(Xi) denoting the values of Parents(Xi) that appear in x1,...,xn\n\n- Each entry in the joint distr. is represented by the product of the approp. elements of the local conditional distr. in the Bayes net.\n\n- P(xi|parents(Xi)) = θ(xi|parents(Xi)) so we can rewrite P(x 1,...,x n) = n∏i=1 P(xi|parents(Xi)), meaning that when one estimates values for the local cond. distr., they need to be the actual conditional probabilities for the variables given its parents\n\n- Chain Rule: P(x1,...,xn) = n∏i=1 P(xi|xi−1,...,x1)\n\n- P(Xi|Xi−1 ,...,X1) = P(Xi|Parents(Xi)) provided that Parents(Xi) ⊆ {Xi−1,...,X1}, so Bayesian network is a correct repr. of the domain only if each node is cond. indep. of its other predecessors in the node ordering, given its parents\n\n- Compactness and node ordering: ayes net often fare more compact than full joint distribution, well chosen node ordering required for compact Bayes net\n\n13.2.1 Conditional independence relations in Bayesian networks\n\n- Each variable is conditionally independent of its non-descendants, given its parents\n\n- Non-descendants property combined with interpr. of the network parameters θ(Xi|Parents(Xi)) as cond. prob. P(X i| Parents(X i)) sufﬁces to reconstruct full joint distribution \n\n- Markov blanket property: variable cond. indep. of all other nodes in the network, given its parents, cildren and children's parents\n\n- Determination if Bayes net Z d-separates X and Y is important\n\n13.2.2 Efficient Representation of Cinditional Distributions\n\n- Filling in the CPT for a node requires up to O(2^k)\n\n- Relationships are describable by a canonical distribution that fits some standard pattern, simplest example provided by deterministic nodes, whose value is specified exactly by the values of its parents with no uncertainty.\n\n- Context-specific independence (CSI) is exhibited by conditional distribution if a variable is cond. indep. of some of its parents given certain values of others\n\n- Noisy-OR model allows for uncertainly about the ability of each parent to cause the child being true, making two assumptions: 1. all the possible causes are listed; 2. inhibition /\nof each parent is indep. of inhibition of any other parents\n\n13.2.3 Bayesoan nets with continuous variables\n\n- continuous variables can by handled with discretization or nonparametric representation\n\n- Hybrid Bayesian network contains both discrete and continuous variables\n\n- Linear-Gaussian conditional distribution most common choice\n\n13.2.4 Case study: Car insurance\n\n- Bayes net includes hidden variables that are neither input nor output variables but essential for structuring the network\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\nBasic task of any probabilistic inference system is computation of posterior probability distribution for a set of query variables given some obsered event (assignment of value to a set of evidence variables)\n\n13.3.1 Inference by enumeration\n\n- Any conditional probability can be computed by summing terms from the full joint distribution, so a query P(X|e) can be answered using P(X|e) = αP(X,e) = α ∑y P(X,e,y)\n\n- P(x,e,y) in the joint distribution can be written as products of cond. prob. from the netwotk, so a query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network\n\n- Complexity (O(n2^n) in the worst case) can be reduced to O(2^n) taking advantage of the nested structure of the computation (moving summations inwards as far as possible)\n\n13.3.2 The variable elimination algorithm\n\n- Elimination of repeated calculations can improve the enumeration algorithm substantially\n\n- The elimination of variables works by evaluating expressions in right-to-left order \n\n- Operations on factors: Pointwise product of two factors f and g yields a new factor h whose variables are the union of the variables in f and g and whose elements are given by the product of the corresponding elements in the two factors\n\n- Time and space requirements of variable elimination dominated by size of the largest factor construxted during he operation of the algorithm, being determined by the order of elimination of variables and the structure of the network.\n\n- Determination of optimal ordering is intracable, but several good heuristics are available. \n\n13.3.3 The complexity of exact inference\n\n13.3.4 Clustering algorithms\n\n- Clustering Algorithms can be used to reduce the time to O(n), so those algorithms are widely used in commercial Bayes net tools.\n\n- Basic idea of clustering is to join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree\n\n- Two Boolean nodes are replaced by a meganode that takes on four possible values\n\n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "b72e55fb-a167-4365-93cb-280eeb705289"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" \n",
        "Machine learning can improve any component of an agent program. Improvements and the techniques used to make them depend on \\\n",
        "three factors:\n",
        "\n",
        "- Which component is to be improved?\n",
        "\n",
        "- What prior knowledge has the agent and which influences the model it builds\n",
        "\n",
        "- What data and feedback on that data is available\n",
        "\n",
        "Agents include the following components, and each of them can be learned:\n",
        "\n",
        "- Direct mapping from conditions on the current state to actions\n",
        "\n",
        "- Means to infer relevant properties of the world from the percept sequence\n",
        "\n",
        "- Information about the way the world evolves and about the results of possible actions the agent can take\n",
        "\n",
        "- Utility information indicating the desirability of world states\n",
        "\n",
        "- Action-value information indicating the desirability of world states\n",
        "\n",
        "- Goals that describe the most desirable states\n",
        "\n",
        "- A problem generator, critic, and learning element that enable the system to improve\n",
        "\n",
        "Going from a specific set of obsercations to a general rule is called indcution, which differs from the deduction because the inductive \\\n",
        "conclusions may be incorrect, wheras deductive conclusions are guaranteed to be currect if the premises are correct\n",
        "\n",
        "Chapter 19 focuses pf problems where the input is a factored representation (a vector of attribute values). \n",
        "\n",
        "Classification vs Regression learning problems:\n",
        "\n",
        "- Classification: Outout is one of a finite set of values\n",
        "\n",
        "- Regression: Output is a number\n",
        "\n",
        "Three types of feedback accompanying the inputs, determining the three main types of learning:\n",
        "\n",
        "- Supervised learning: Agent observes input-output pairs and learns a function that maps from input to output. (Output called a label)\n",
        "\n",
        "- Unsupervised learning: Agent learns patterns in the input without any explicit feedback. Most common unsupervised learning task is clustering\n",
        "\n",
        "- Reinforcement learning: Agent learns form a series of reinforcements: rewards and punishments\n",
        "\"\"\"\n",
        "\n",
        "chapter19_2 = \"\"\"\n",
        "- Task of supervised learning: Given a training set of N example input-output pairs (x1,y1),(x2,y2),...(xN,yN), with each pair generated by an unknown \\\n",
        "function y=f(x), the function h that approximates the true function f is to be discovered\n",
        "\n",
        "- Function h is a hypothesis about the world, and it is drawn from a hypothesis space H of possible functions\n",
        "\n",
        "- Exploratory data analysis: Examining the data with statistical tests and visualization\n",
        "\n",
        "- Consistent hypothesis: h such that each xi in the training set has h(xi)=yi, but unrealistic for continuous-valued outputs, for this better best-fit function\n",
        "\n",
        "- Best-fit function: h(xi) is close to yi\n",
        "\n",
        "- Generalization: We can say that h generalizes well if it accurately predicts the outputs of the test set\n",
        "\n",
        "- Underfitting: A hypothesis is underfitting when it fails to find a pattern in the data\n",
        "\n",
        "- Variance is the amount of change in the hypothesis due to fluctuation in the training data\n",
        "\n",
        "- Overfitting: function is overfitting data when it pays too much attention to the particular data set it is trained on, causing it to perform pporly on unseen data\n",
        "\n",
        "- Bias-Varianve tradeoff: Choice between more complex, low-bias hypothesis that fit the training data well and simplier, low-variance \\\n",
        "hypotheses that may generalize better\n",
        "\n",
        "- There is a tradoff between the expressiveness of a hypothesis space and the computational complexity of funding a good hypothesis within that space\n",
        "\n",
        "- Expressiceness-complexity tradeoff: Expressive language makes it possible for a simple hypothesis to fit the data, whereas \\\n",
        "restricting the expressiveness of the language means that any consistent hypothesis must be complex\n",
        "\"\"\"\n",
        "\n",
        "chapter19_3 = \"\"\"\n",
        "- Decision tree: Representation of a function that maps a vector of attribute values to a single output value (decision), reaching its decision \\\n",
        "by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached\n",
        "\n",
        "19.3.1: Expressiveness of decision trees:\n",
        "\n",
        "- Boolean decision tree equivalent to a logical statement of the form Output ⇔ (Path1 ∨ Path2 ∨ ···)\n",
        "\n",
        "- Path i is a conjunction of the form (Am = vx ∧ An = vy ∧ ···) of attribute-value tests corresponding to a path from the root to a true leaf.\n",
        "\n",
        "- There is no kind of representation that is efficient for all kinds of functions\n",
        "\n",
        "19.3.2 Learning decision trees fropm examples\n",
        "\n",
        "- The LEARN-DECISION-TREE algorithm adopts a greedy divide-and-conquer strategy: always test the most imprortant attribute first, then \\\n",
        "recursively solve the smaller subproblems that are defined  by the possible results of the test\n",
        "\n",
        "- A tree consists of tests on attributes in the interior nodes, values of attributes on the branches, and output values on the leaf nodes\n",
        "\n",
        "- Performance of a learning algorithm can be evaluated with a learning curve\n",
        "\n",
        "19.3.3 Choosing attribute tests\n",
        "\n",
        "-  Attributes are chosen with the highest importance in the decision tree learning algorithm\n",
        "\n",
        "- Importance can be measured with the notion of information gain, which is defined in terms of entropy, the fundamental quantity in infortmation theory\n",
        "\n",
        "- Entropy is a measure of the uncertainty of a random variable: the more information, the less entropy\n",
        "\n",
        "- Generally, the entropy of a random variable V with values vk having probability P(vk) is defined as H(V) = ∑k P(vk) log2 1/P(vk) = −∑k P(vk) log2 P(vk)\n",
        "\n",
        "- Randomly chosen example from the training set has the kth value for the attribute, so the expected entropy remaining after testing attribute \\\n",
        "A is Remainder(A) = d∑k=1 (pk+nk)/(p+n) B(pk/(pk+nk))\n",
        "\n",
        "- Information gain from the attribute test on A is the expected reduction in entropy: Gain(A) = B(p/(p+n))−Remainder(A)\n",
        "\n",
        "- Gain(A) is what is needed to implement the IMPORTANCE function\n",
        "\n",
        "19.3.4 Generalization and overfitting\n",
        "\n",
        "- Overfitting becomes more likely as the number of attributes grows, and les likely as the number of training examples increases\n",
        "\n",
        "- Decision tree pruning: Technique comating overfitting, which works by eliminating nodes that are not clearly relevant\n",
        "\n",
        "19.3.5 Broadening the applicability of decision trees\n",
        "\n",
        "- Decision trees can be made more widely useful y handling the following complications: Missing Data, Continuous and multivalued input \\\n",
        "attributes, continuous-valued output attributes\n",
        "\n",
        "- Advantages of decision trees: ease of understanding, scalabilit to large data sets and versatility in handling discrete and contiuous input \\\n",
        "as well as classification and regression\n",
        "\"\"\"\n",
        "\n",
        "chapter19_4 = \"\"\"\n",
        "- Stationarity assumption: Future examples will be like the past. Assume each example Ej has the same prior probability distribution \\\n",
        "and is independent of the previous examples -> equations are independent and identically distributed (i.i.d.)\n",
        "\n",
        "- Optimal fit is the hypothesis that minimizes the error rate: proportion of times that h(x) =/ y for an (x,y) example\n",
        "\n",
        "-The error rate of a hypothesis can be estimated by giving it a tesT: performance on a test set of examples is measured, and training set and test set \\\n",
        "are splitted\n",
        "\n",
        "- \"Knobs\" / hyperparameters: parameters of the model class, not of the individual model\n",
        "\n",
        "- Three data sets required: Training set, validation set (also development set) and test set\n",
        "\n",
        "- leave-one-out cross-validation (LOOCV)\n",
        "\n",
        "- Finding a good hypothesis consists of two subtasks: Model selection chooses a good hypothesis space, and optimization (training) \\\n",
        "finds the best hypothesis within that space\n",
        "\n",
        "- Part of the model selection is qualitative and subjective, other part can be quantitative and empirical\n",
        "\n",
        "19.4.1 Model selection:\n",
        "\n",
        "- Model-Selection algorithm takes learning algorithm with one hyperparameter as argument. Model selection starts with the smallesst value of the \\\n",
        "hyperparameter, yielding a simple model, iterating through larger values of the hyperparameter, considering cmore complex models. At the end, \\\n",
        "model-selection selects the model that hsa the lowest average error rate on the held-out validation data\n",
        "\n",
        "- Complexity measured by the number of decision tree nodes and number of neural nework parameters\n",
        "\n",
        "- Error decreases for a while as model complexity increases, but reaches a point where it begins to overfit and validation error rises\n",
        "\n",
        "- Model classes start to overfit as the capacity approaches the point of interpolation (model exactly fits all the training data)\n",
        "\n",
        "19.4.2 From error rates to loss\n",
        "\n",
        "- Machine learning traditionally minimizes a loss function rather than maximizing a utility function\n",
        "\n",
        "- Loss function L(x,y,^y) defines as the amount of utility lost by predicting h(x)=^y when the correct answer is f(x)=y\n",
        "\n",
        "- Simplified version: L(y,^y) that is independent of x\n",
        "\n",
        "- L(y,y) is always zero as there is no loss when you guess exactly right\n",
        "\n",
        "- Generalization loss\n",
        "\n",
        "- Empirical los\n",
        "\n",
        "- Learning problem is realizable if the hypothesis space H actually contains the true function f\n",
        "\n",
        "- Variance means that a learning algorithm will return different hypotheses for different sets of examples\n",
        "\n",
        "- Computationally intractable to systematically seach all possibilities in a hypothesis space when H is a complicated function\n",
        "\n",
        "- Small-scale learning vs learge-scale learning, where generalization loss is dominated by limits of computation\n",
        "\n",
        "19.4.3: Regularization\n",
        "\n",
        "- Process of explicitly penalizing complex hypotheses\n",
        "\n",
        "19.4.4 Hyperparameter tuning\n",
        "\n",
        "- When there are multiple hyperparameeter or they have continuous values, it is more difficult to choose good values\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter19_5 = \"\"\" \n",
        "\n",
        "- Computational learning theory lies at the intersction of AI, statistics and theoretical computer scienve\n",
        "\n",
        "- Underlying principle is that any hypothesis that is seriously wrong will almost certainly be \"found out\" with high probability after a small \\\n",
        "number of examples as it will make an incorrect prediction\n",
        "\n",
        "- Hypothesis must be probabily approximately correct (PAC) to be consistent with a sifficiently large set of traini9ng examples\n",
        "\n",
        "- PAC-learning theorems are logical consequences of axioms\n",
        "\n",
        "- Hypothesis h is approximately correct if error(h) ≤ ǫ, where ǫ is a small constant.\n",
        "\n",
        "- Sample complexity is the number of required examples as a function of ǫ and δ\n",
        "\n",
        "19.5.1 PAC learning example: Learning decision lists \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter19_6 = \"\"\" \n",
        "\n",
        "19.6.1 Univariate linear regression\n",
        "\n",
        "- Many forms of learning involve adjusting weights to minimize a loss\n",
        "\n",
        "- The loss function is convex\n",
        "\n",
        "19.6.2 Gradient descent\n",
        "\n",
        "- Search through a continuous weight space by incrementally modifying the parameters to minimize loss\n",
        "\n",
        "- Starting point (e,g, (w0,w1)) is chosen in weight space, then computing an estimate of the gradient and moving a small amount in the steepest downhill \\\n",
        "direction, repeating until converged on a point in weight space with (local) minimum loss\n",
        "\n",
        "- Batch gradient descent and stochastic gradient descent\n",
        "\n",
        "19.6.3 Multivariable linear regression\n",
        "\n",
        "- Multivariable linear regression has n-element vectors, it's not much more complicated than the univariate case\n",
        "\n",
        "- Gradient descent will reach the (unique) minimum of the loss function, the update the equation for each weight wi\n",
        "\n",
        "19.6.4 Linear classifiers with a hard threshold\n",
        "\n",
        "- Linear functions can be used to do classification as well as regression\n",
        "\n",
        "- Decision boundary is a line that separates the two classe, linear decision bounardy called a linear separator\n",
        "\n",
        "19.6.5 Linear classification with logistic regression\n",
        "\n",
        "- Logistic regression: Process of fitting weights of this model to minimize loss on a data set\n",
        "\"\"\"\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 = \"\"\"\n",
        "- Naive Bayes: Assume all features are independent effects of the label\n",
        "\n",
        "- Avoid giving unseen events zero probability -> smooth or regulazire the estimates\n",
        "\n",
        "- Best fit for set of training data, the parameter settings that maximizes the likelihood of the data given those parameter settings\n",
        "\n",
        "- Perceptron -> Decision making device\n",
        "\n",
        "- Binary Perceptron Learning: Start with weights 0 and for each training instance, classify with current wights \\\n",
        "and if those are wrong, adjust the weight vector by adding or substracting the feature vector (subtract if y* is -1). w = w + y* x f\n",
        "\n",
        "- Multiclass Decision Rule: If we have multiple classes, we have a weight vector for each class\n",
        "\n",
        "- Properties of Perceptrons: Separability, Convergence, Mistake Bound\n",
        "\n",
        "- Separabiulity: true if some parameters get the training set perfectly correct\n",
        "\n",
        "- Convergence: if the training is separable, perceptron will eventually converge (binary case)\n",
        "\n",
        "- Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability\n",
        "\n",
        "- MIRA (Margin infused relaxed algorithm): Chossing an update size that fixed the current mistake\n",
        "\n",
        "- Support Vector maxhines (SVMs): Find linear separator that maximizes the margin\n",
        "\n",
        "Naive Bayes vs Perceptrons: Classification comparison:\n",
        "\n",
        "- Naive Bayer: Builds a model training data, gives prediction prob., strong assumptions about feature indep., one pass through data (counting)\n",
        "\n",
        "- Preceptrons / MIRA: Makes less assumptions about data, Mistake-driven learning, multiple passes through data (prediction), often more accurate\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter19_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter19_4))\n"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 421\n",
            "The length in characters is 2923\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 4083
        },
        "cellView": "form",
        "outputId": "fb865f87-6abb-4089-8fe6-dc94b368cdf1"
      },
      "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 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 The Threory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.6 Linear Regression and Classification\", 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": 12,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n \nMachine learning can improve any component of an agent program. Improvements and the techniques used to make them depend on three factors:\n\n- Which component is to be improved?\n\n- What prior knowledge has the agent and which influences the model it builds\n\n- What data and feedback on that data is available\n\nAgents include the following components, and each of them can be learned:\n\n- Direct mapping from conditions on the current state to actions\n\n- Means to infer relevant properties of the world from the percept sequence\n\n- Information about the way the world evolves and about the results of possible actions the agent can take\n\n- Utility information indicating the desirability of world states\n\n- Action-value information indicating the desirability of world states\n\n- Goals that describe the most desirable states\n\n- A problem generator, critic, and learning element that enable the system to improve\n\nGoing from a specific set of obsercations to a general rule is called indcution, which differs from the deduction because the inductive conclusions may be incorrect, wheras deductive conclusions are guaranteed to be currect if the premises are correct\n\nChapter 19 focuses pf problems where the input is a factored representation (a vector of attribute values). \n\nClassification vs Regression learning problems:\n\n- Classification: Outout is one of a finite set of values\n\n- Regression: Output is a number\n\nThree types of feedback accompanying the inputs, determining the three main types of learning:\n\n- Supervised learning: Agent observes input-output pairs and learns a function that maps from input to output. (Output called a label)\n\n- Unsupervised learning: Agent learns patterns in the input without any explicit feedback. Most common unsupervised learning task is clustering\n\n- Reinforcement learning: Agent learns form a series of reinforcements: rewards and punishments\n\n\n## AIMA Chapter 19.2 Supervised Learning\n\n- Task of supervised learning: Given a training set of N example input-output pairs (x1,y1),(x2,y2),...(xN,yN), with each pair generated by an unknown function y=f(x), the function h that approximates the true function f is to be discovered\n\n- Function h is a hypothesis about the world, and it is drawn from a hypothesis space H of possible functions\n\n- Exploratory data analysis: Examining the data with statistical tests and visualization\n\n- Consistent hypothesis: h such that each xi in the training set has h(xi)=yi, but unrealistic for continuous-valued outputs, for this better best-fit function\n\n- Best-fit function: h(xi) is close to yi\n\n- Generalization: We can say that h generalizes well if it accurately predicts the outputs of the test set\n\n- Underfitting: A hypothesis is underfitting when it fails to find a pattern in the data\n\n- Variance is the amount of change in the hypothesis due to fluctuation in the training data\n\n- Overfitting: function is overfitting data when it pays too much attention to the particular data set it is trained on, causing it to perform pporly on unseen data\n\n- Bias-Varianve tradeoff: Choice between more complex, low-bias hypothesis that fit the training data well and simplier, low-variance hypotheses that may generalize better\n\n- There is a tradoff between the expressiveness of a hypothesis space and the computational complexity of funding a good hypothesis within that space\n\n- Expressiceness-complexity tradeoff: Expressive language makes it possible for a simple hypothesis to fit the data, whereas restricting the expressiveness of the language means that any consistent hypothesis must be complex\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n\n- Decision tree: Representation of a function that maps a vector of attribute values to a single output value (decision), reaching its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached\n\n19.3.1: Expressiveness of decision trees:\n\n- Boolean decision tree equivalent to a logical statement of the form Output ⇔ (Path1 ∨ Path2 ∨ ···)\n\n- Path i is a conjunction of the form (Am = vx ∧ An = vy ∧ ···) of attribute-value tests corresponding to a path from the root to a true leaf.\n\n- There is no kind of representation that is efficient for all kinds of functions\n\n19.3.2 Learning decision trees fropm examples\n\n- The LEARN-DECISION-TREE algorithm adopts a greedy divide-and-conquer strategy: always test the most imprortant attribute first, then recursively solve the smaller subproblems that are defined  by the possible results of the test\n\n- A tree consists of tests on attributes in the interior nodes, values of attributes on the branches, and output values on the leaf nodes\n\n- Performance of a learning algorithm can be evaluated with a learning curve\n\n19.3.3 Choosing attribute tests\n\n-  Attributes are chosen with the highest importance in the decision tree learning algorithm\n\n- Importance can be measured with the notion of information gain, which is defined in terms of entropy, the fundamental quantity in infortmation theory\n\n- Entropy is a measure of the uncertainty of a random variable: the more information, the less entropy\n\n- Generally, the entropy of a random variable V with values vk having probability P(vk) is defined as H(V) = ∑k P(vk) log2 1/P(vk) = −∑k P(vk) log2 P(vk)\n\n- Randomly chosen example from the training set has the kth value for the attribute, so the expected entropy remaining after testing attribute A is Remainder(A) = d∑k=1 (pk+nk)/(p+n) B(pk/(pk+nk))\n\n- Information gain from the attribute test on A is the expected reduction in entropy: Gain(A) = B(p/(p+n))−Remainder(A)\n\n- Gain(A) is what is needed to implement the IMPORTANCE function\n\n19.3.4 Generalization and overfitting\n\n- Overfitting becomes more likely as the number of attributes grows, and les likely as the number of training examples increases\n\n- Decision tree pruning: Technique comating overfitting, which works by eliminating nodes that are not clearly relevant\n\n19.3.5 Broadening the applicability of decision trees\n\n- Decision trees can be made more widely useful y handling the following complications: Missing Data, Continuous and multivalued input attributes, continuous-valued output attributes\n\n- Advantages of decision trees: ease of understanding, scalabilit to large data sets and versatility in handling discrete and contiuous input as well as classification and regression\n\n\n## AIMA Chapter 19.4 Model Selection and Optimization\n\n- Stationarity assumption: Future examples will be like the past. Assume each example Ej has the same prior probability distribution and is independent of the previous examples -> equations are independent and identically distributed (i.i.d.)\n\n- Optimal fit is the hypothesis that minimizes the error rate: proportion of times that h(x) =/ y for an (x,y) example\n\n-The error rate of a hypothesis can be estimated by giving it a tesT: performance on a test set of examples is measured, and training set and test set are splitted\n\n- \"Knobs\" / hyperparameters: parameters of the model class, not of the individual model\n\n- Three data sets required: Training set, validation set (also development set) and test set\n\n- leave-one-out cross-validation (LOOCV)\n\n- Finding a good hypothesis consists of two subtasks: Model selection chooses a good hypothesis space, and optimization (training) finds the best hypothesis within that space\n\n- Part of the model selection is qualitative and subjective, other part can be quantitative and empirical\n\n19.4.1 Model selection:\n\n- Model-Selection algorithm takes learning algorithm with one hyperparameter as argument. Model selection starts with the smallesst value of the hyperparameter, yielding a simple model, iterating through larger values of the hyperparameter, considering cmore complex models. At the end, model-selection selects the model that hsa the lowest average error rate on the held-out validation data\n\n- Complexity measured by the number of decision tree nodes and number of neural nework parameters\n\n- Error decreases for a while as model complexity increases, but reaches a point where it begins to overfit and validation error rises\n\n- Model classes start to overfit as the capacity approaches the point of interpolation (model exactly fits all the training data)\n\n19.4.2 From error rates to loss\n\n- Machine learning traditionally minimizes a loss function rather than maximizing a utility function\n\n- Loss function L(x,y,^y) defines as the amount of utility lost by predicting h(x)=^y when the correct answer is f(x)=y\n\n- Simplified version: L(y,^y) that is independent of x\n\n- L(y,y) is always zero as there is no loss when you guess exactly right\n\n- Generalization loss\n\n- Empirical los\n\n- Learning problem is realizable if the hypothesis space H actually contains the true function f\n\n- Variance means that a learning algorithm will return different hypotheses for different sets of examples\n\n- Computationally intractable to systematically seach all possibilities in a hypothesis space when H is a complicated function\n\n- Small-scale learning vs learge-scale learning, where generalization loss is dominated by limits of computation\n\n19.4.3: Regularization\n\n- Process of explicitly penalizing complex hypotheses\n\n19.4.4 Hyperparameter tuning\n\n- When there are multiple hyperparameeter or they have continuous values, it is more difficult to choose good values\n\n\n\n## AIMA Chapter 19.5 The Threory of Learning\n \n\n- Computational learning theory lies at the intersction of AI, statistics and theoretical computer scienve\n\n- Underlying principle is that any hypothesis that is seriously wrong will almost certainly be \"found out\" with high probability after a small number of examples as it will make an incorrect prediction\n\n- Hypothesis must be probabily approximately correct (PAC) to be consistent with a sifficiently large set of traini9ng examples\n\n- PAC-learning theorems are logical consequences of axioms\n\n- Hypothesis h is approximately correct if error(h) ≤ ǫ, where ǫ is a small constant.\n\n- Sample complexity is the number of required examples as a function of ǫ and δ\n\n19.5.1 PAC learning example: Learning decision lists \n\n\n\n## AIMA Chapter 16.6 Linear Regression and Classification\n \n\n19.6.1 Univariate linear regression\n\n- Many forms of learning involve adjusting weights to minimize a loss\n\n- The loss function is convex\n\n19.6.2 Gradient descent\n\n- Search through a continuous weight space by incrementally modifying the parameters to minimize loss\n\n- Starting point (e,g, (w0,w1)) is chosen in weight space, then computing an estimate of the gradient and moving a small amount in the steepest downhill direction, repeating until converged on a point in weight space with (local) minimum loss\n\n- Batch gradient descent and stochastic gradient descent\n\n19.6.3 Multivariable linear regression\n\n- Multivariable linear regression has n-element vectors, it's not much more complicated than the univariate case\n\n- Gradient descent will reach the (unique) minimum of the loss function, the update the equation for each weight wi\n\n19.6.4 Linear classifiers with a hard threshold\n\n- Linear functions can be used to do classification as well as regression\n\n- Decision boundary is a line that separates the two classe, linear decision bounardy called a linear separator\n\n19.6.5 Linear classification with logistic regression\n\n- Logistic regression: Process of fitting weights of this model to minimize loss on a data set\n\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\n- Naive Bayes: Assume all features are independent effects of the label\n\n- Avoid giving unseen events zero probability -> smooth or regulazire the estimates\n\n- Best fit for set of training data, the parameter settings that maximizes the likelihood of the data given those parameter settings\n\n- Perceptron -> Decision making device\n\n- Binary Perceptron Learning: Start with weights 0 and for each training instance, classify with current wights and if those are wrong, adjust the weight vector by adding or substracting the feature vector (subtract if y* is -1). w = w + y* x f\n\n- Multiclass Decision Rule: If we have multiple classes, we have a weight vector for each class\n\n- Properties of Perceptrons: Separability, Convergence, Mistake Bound\n\n- Separabiulity: true if some parameters get the training set perfectly correct\n\n- Convergence: if the training is separable, perceptron will eventually converge (binary case)\n\n- Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability\n\n- MIRA (Margin infused relaxed algorithm): Chossing an update size that fixed the current mistake\n\n- Support Vector maxhines (SVMs): Find linear separator that maximizes the margin\n\nNaive Bayes vs Perceptrons: Classification comparison:\n\n- Naive Bayer: Builds a model training data, gives prediction prob., strong assumptions about feature indep., one pass through data (counting)\n\n- Preceptrons / MIRA: Makes less assumptions about data, Mistake-driven learning, multiple passes through data (prediction), often more accurate\n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "67d3bda6-e635-4a1a-a1fe-b603a3841ce7"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "Logistic Regression:\n",
        "\n",
        "- Loss functions for probabilistic classification:\n",
        "\n",
        "- Use a loss function prefering the correct class labels of the training example to be more likely\n",
        "\n",
        "- Cond. maximum likelihood estimation: Choose parameters w,b that maximize the (log) prob. of the true labels in the training data\n",
        "\n",
        "- Resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss\n",
        "\n",
        "Stochastic Gradient Descent\n",
        "\n",
        "- Theta: Trying to find a particular setting of Theta that's going to minimize the average loss across our training \\\n",
        "set using the cross entropy loss function\n",
        "\n",
        "- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the parameters Theta) the \\\n",
        "function's slope is rising the most steeply, and moving in the opposite direction\n",
        "\n",
        "- Global v. Local Minimums: For logistic regression, loss function is conveniently convex (only one minimum), so gradient \\\n",
        "guaranteed to find minimum from any starting point\n",
        "\n",
        "- Regularization: penalizes large weights (added to the loss function) to avoid overfitting\n",
        "\n",
        "- Multinomial logistic regression can have more than two classes\n",
        "\n",
        "- Softmax: Softmax function takes in an input vector z = [z1,z2,...,Zk] and outputs a vector of values normalized into probabilities\n",
        "\n",
        "Neural Networks:\n",
        "\n",
        "- Neural networks includes differrent layers: Input layer, hidden layers, output layer\n",
        "\n",
        "- Sigmoid neuron function much smoother than Perceptron (0 or 1)\n",
        "\n",
        "- Activation functions: non-linear functions f to z, output is called the activation value, represented by variable a. \\\n",
        "Commonly used non-linear functions used for f are the sigmoid function, tanh function and rectified linear unit (ReLu)\n",
        "\n",
        "- Feed-Forward Neural Network: Simplest kind of Neural Network, a multilayer network where all units are usually fully-connected and no cycles. \\\n",
        "Outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower levels\n",
        "\n",
        "- Error backpropagation algorithm: Instance of backward differentiation, defining computation graph and \\\n",
        "figuring out how much each element contributes to the total at the end.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(module13_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module13_lecture_notes))\n"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 314\n",
            "The length in characters is 2142\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1527
        },
        "cellView": "form",
        "outputId": "f3d90a64-ee2b-4c56-aa8b-f45d9958ce9c"
      },
      "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": 14,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\nLogistic Regression:\n\n- Loss functions for probabilistic classification:\n\n- Use a loss function prefering the correct class labels of the training example to be more likely\n\n- Cond. maximum likelihood estimation: Choose parameters w,b that maximize the (log) prob. of the true labels in the training data\n\n- Resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss\n\nStochastic Gradient Descent\n\n- Theta: Trying to find a particular setting of Theta that's going to minimize the average loss across our training set using the cross entropy loss function\n\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the parameters Theta) the function's slope is rising the most steeply, and moving in the opposite direction\n\n- Global v. Local Minimums: For logistic regression, loss function is conveniently convex (only one minimum), so gradient guaranteed to find minimum from any starting point\n\n- Regularization: penalizes large weights (added to the loss function) to avoid overfitting\n\n- Multinomial logistic regression can have more than two classes\n\n- Softmax: Softmax function takes in an input vector z = [z1,z2,...,Zk] and outputs a vector of values normalized into probabilities\n\nNeural Networks:\n\n- Neural networks includes differrent layers: Input layer, hidden layers, output layer\n\n- Sigmoid neuron function much smoother than Perceptron (0 or 1)\n\n- Activation functions: non-linear functions f to z, output is called the activation value, represented by variable a. Commonly used non-linear functions used for f are the sigmoid function, tanh function and rectified linear unit (ReLu)\n\n- Feed-Forward Neural Network: Simplest kind of Neural Network, a multilayer network where all units are usually fully-connected and no cycles. Outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower levels\n\n- Error backpropagation algorithm: Instance of backward differentiation, defining computation graph and figuring out how much each element contributes to the total at the end.\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "- Neural LMs: Input to the neural network is a k-gram of words W_1:k Output is a probability distribution over the next word ; \\\n",
        "k context words are treated as a word window, and each word is associated with an embedding vector.\n",
        "\n",
        "- Input x is fed into a neural network with 1 or more hidden layers\n",
        "\n",
        "- Output layer corresponds to size of the vocabulary\n",
        "\n",
        "- Word Meaning: We want a meaning representation to encode: Synonyms, Antonyms, Connotations, Semantic Roles, Support for entailment\n",
        "\n",
        "- Meaning of Word can be represented via a Vector Space Model\n",
        "\n",
        "- Term-Document Matrix shows how often a word occurs in a document, can be used to compare how similar documents are\n",
        "\n",
        "- Vector comparisons via the Euclidean distance\n",
        "\n",
        "- Term-Term Matrix (also Term-Context Matrix) represent how often a word appeared in a context window surronding another word\n",
        "\n",
        "- Context windows shows how far the short term apearences are checked\n",
        "\n",
        "- Dependency parcing: shows types of syntactic relationships\n",
        "\n",
        "- Syntax can be used to define a word's context\n",
        "\n",
        "- Raw counts can also be transformated ; TF-IDF: Term frequency * inverse document frequency\n",
        "\n",
        "- Sparse vs. Dense Vectors: Co-occurrence matrix (weighted by TF-IDF or mutual info.): Long (length 50k+ ; Sparse, most elements zeros) | \\\n",
        "Alternative are learn vectors that are short (length 200-1k) and Dense (most elements non-zero)\n",
        "\n",
        "- How to get dense vectors: 1. Treat target word and neighboring context words as positive examples. \\\n",
        "2. Randomly sample other words in the lexicon to get negative samples. 3. Use logistic regr. to train a classifier to distinguish those two cases. \\\n",
        "4. Use the weights as the embeddings\n",
        "\n",
        "- Embeddings capture relational meanings\n",
        "\n",
        "- \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "cdb36b79-35b8-400b-c697-111b41437a8e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", module14_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": 21,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n- Neural LMs: Input to the neural network is a k-gram of words W_1:k Output is a probability distribution over the next word ; k context words are treated as a word window, and each word is associated with an embedding vector.\n\n- Input x is fed into a neural network with 1 or more hidden layers\n\n- Output layer corresponds to size of the vocabulary\n\n- Word Meaning: We want a meaning representation to encode: Synonyms, Antonyms, Connotations, Semantic Roles, Support for entailment\n\n- Meaning of Word can be represented via a Vector Space Model\n\n- Term-Document Matrix shows how often a word occurs in a document, can be used to compare how similar documents are\n\n- Vector comparisons via the Euclidean distance\n\n- Term-Term Matrix (also Term-Context Matrix) represent how often a word appeared in a context window surronding another word\n\n- Context windows shows how far the short term apearences are checked\n\n- Dependency parcing: shows types of syntactic relationships\n\n- Syntax can be used to define a word's context\n\n- Raw counts can also be transformated ; TF-IDF: Term frequency * inverse document frequency\n\n- Sparse vs. Dense Vectors: Co-occurrence matrix (weighted by TF-IDF or mutual info.): Long (length 50k+ ; Sparse, most elements zeros) | Alternative are learn vectors that are short (length 200-1k) and Dense (most elements non-zero)\n\n- How to get dense vectors: 1. Treat target word and neighboring context words as positive examples. 2. Randomly sample other words in the lexicon to get negative samples. 3. Use logistic regr. to train a classifier to distinguish those two cases. 4. Use the weights as the embeddings\n\n- Embeddings capture relational meanings\n\n- \n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 17201
        },
        "id": "T3cm1WV542_a",
        "outputId": "d646cd17-8959-414f-bff5-14a5288b1dd2"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nBASIC PRINCIPLE OF DECISION THEORY: THE MAXIMATION OF EXPECTED UTILITY\n\nStart is an agent who needs to make a decision:\n\n- Current state may be uncertain\n\n- Assigns probability P(s) to each possible current state s\n\n- Action outcomes may be uncertain\n\n- Transition model is given by P(s’|s,a), which is the probability that action a in state s reaches s’\n\n- P(RESULT(a)=s’) = sum(s) P(s)P(s’|s,a), the probability of reaching s’ by doing a in any current state\n\n\nDecision theory aims to choose among actions based on how desirable their immediate outcomes are\n\n- Utility function U(s) captures preferences and assigns a single number to express desirability\n\n- EU(a) is the expected utility of an action given the evidence (average utility value of outcomes weighted by resp. probability, sum(s’) P(RESULT(a)=s’)U(s’) )\n\n- Maximum expected utility (MEU) principle describes that a rational agent should choose the action with maximized expected utility, action = argmax_a EU(a)\n\n- MEU principle can be seen as a prescription for intelligent behaviour and formalizes the general notion that intelligent agents should do the right thing. However, it doesn’t operationalize that advice\n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nMODELLING RATIONAL AGENT BEHAVIOUR BY MAXIMIZING A UTILITY FUNCTION\n\n16.2.1 Constraints on rational preferences:\n\nNotations to describe agent preferences:\n\n- A ≻ B: agent prefers A over B\n\n- A ~ B: agent is indifferent between A and B\n\n- A ≻~ B: agent prefers A over B or is indifferent between them\n\nConstraints that any reasonable preference relation is required to obey (known as the axioms of utility theory):\n\n- Orderability: Exactly one of (A≻B), (B≻A), or (A~B) holds\n\n- Transitivity: (A≻B) and (B≻C) => (A≻C)\n\n- Continuity: A≻B≻C => there exits p [p,A; 1-p,C] ~ B\n\n- Substitutability: A~B => [p,A; 1-p,C] ~ [p,B; 1-p,C]\n\n- Monotonicity: A ≻B => (p>q  [p,A; 1-p,B] ≻ [q,A; 1-q,B]\n\n- Decomposability: [p,a; 1-p,[q,B; 1-q,C]] ~ [p,A; (1-p)q,B; (1-p)(1-q),C]\n\n16.2.2 Rational preferences lead to utility\n\nConsequences can be derived from the axioms of utility\n\n- Existence of Utility Function: U(a) > U(B)  A ≻B   and     U(A)=U(B)  A~B\n\n- Expected Utility of a Lottery: U([p1,S1;…;pn,Sn]) = sum(i) piU(Si) (sum of probability of each outcome times utility of that outcome)\n\nA utility function exists for any rational agent, assuming the constraints on rational references.\n\nPositive affine transformation: Utility function U(S) can be transformed to U’(S)=aU(S)+b where a and b are constants and a>0 without changing the agent’s behaviour\n\nValue function / Ordinal Utility function: In a deterministic environment (as is game-playing), agents only needs preference ranking on states, specific numbers don’t matter\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nNATURE OF UTILITY FUNCTIONS AND RELATION TO INDIVIDUAL QUANTITIES\n\nUtility functions map from lotteries to real numbers and must obey the axioms discussed in 16.2\n\n16.3.1: Utility assessment and utility scales\n\n- Preference elicitation (work out human’s utility function): Process involving presenting choices to humans and using the observed preferences to get the underlying utility function\n\n- Helpful to establish some scale on which utilities can be recorded and compared for any particular problem, even though there is no absolute scale for utilities as per 16.2\n\n- Normalized utilities use u⊥ = 0 and u⊤ = 1 for a scale. Given that, the utility of any particular prize S can be assessed by asking the agent to choose between S and a standard lottery [p, u⊤; (1-p), u⊥]\n\n16.3.2 The utility of money\n\n- Agents have a monotonic preference for more money\n\n- Agents want to maximize the expected monetary value (EMV)\n\n- Agents can be risk-averse, risk seeking or risk-neutral\n\n- The insurance premium is the difference between the EMV of a lottery and its certainty equivalent\n\n16.3.3 Expected utility and post-decision disappointment\n\n- Best action a* maximizes expected utility: a* = argmax_a EUR(a)\n\n- Models usually oversimplify because either information is missing or computation of the true expected utility is too difficult, so effectively working with estimates ÊU(a) of the true expected utility\n\n- General assumption for unbiased estimates, so zero expected value of the error, E(ÊU(a)-EU(a))=0\n\n- Even though estimate was unbiased real outcome usually significantly worse than the estimate because of tendancy for the estimated expected utility of the best choice to be too high (optimizer’s curse), afflicting even the most seasoned decision analysts and statisticans\n\n- Curse can be avoided with a Bayesian approach that uses an explicit probability model P(ÊU|EU) of the error in the utility estimates, therefore utility estimate is treated as evidence and posterior distribution for true utility is computed using Bayes’ rule\n\n16.3.4 Human judgment and irrationality\n\n- Decision theory is a normative theory, meaning that it describes how a rational agent should act\n\n- Literature gives evidence suggesting that humas are predictably irrational, being strongly attracted to gains that are certain\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nChapter 17: Sequential decision problems: Agent’s utility depends on a sequence of decisions,  incorporating utilities, uncertainty, and sensing, and including search and planning problems as special cases\n\nDEFINITION OF SEQUENTIAL DECISION PROBLEMS\n\n- An agent begins in the start state and must choose an action at each time step\n\n- Transition model describes the outcome of each action in each state, P(s’|s,a), which is the probability that action a in state s reaches\n\n- Markovian transitions are assumed: probability of reaching s’ from s depends only on s and not on the history of earlier states\n\n- Environment history: utility function depending on a sequence of states and actions rather than on a single state\n\n- Reward R(s,a,s’) can be positive or negative (bounded by +-Rmax) and is receives for every transition from s to s’ via action a\n\n- Markos Decision Process (MDP): sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards.\n\n- MDP includes: set of states (initial state s0); set ACTIONS(s) of actions in each state: transition model P(s’|s,a); reward function R(s,a,s’)\n\n- Dynamic Programming: simplifying a problem by recursively breaking it into smaller pieces and remembering the optimal solutions to the pieces, usually involved in methods for solving MDPs\n\n- Policy π: solution specifying what the agent should do for any state that the agent might reach (no fixed action sequence). Π(s) is the action recommended by the policy π for state s\n\n- Optimal policy π*: yields the highest expected utility\n\n17.1.1 Utilities over time\n\n- Finite/infinite horizon: means that there is a fixed time N after which nothing maters, optimal action in a given state may depend on how much time is left (optimal policy is nonstationary)\n\n- With no time limit, optimal policy is stationary, depending only on the current state\n\n- Proper policy: policy that is guaranteed to reach a terminal state (γ=1 possible for proper policies)\n\n- Infinite sequences comparable in terms of average reward obtained per time step\n\n17.1.2 Optimal policies and the utilities of states\n\n- Policies can be compared by comparing the expected utilites obtained during execution\n\n- Expected utility obtained by executing π starting in s: U^π(s) = E [ sum(t=0->inf) γ^tR(St, π(St),S(t+1)]\n\n- π*s = argmax_ π U^π(s)  is a policy, so it recommends an action for every state\n\n- Utilities are higher for states closer to the +1 exit, because fewer steps are required to reach the exit (fewer discounting)\n\n- π*(s) = argmax_(a in A(s)) sum(s’) P(s’|s,a)[R(s,a,s’)+ γU(S’)]\n\n- Action-utility function (Q-function) Q(s,a): expected utility taking a given action in a given state\n\n- Relation Q-function to Utility function: U(s) = max_a Q(s,a)\n \n17.1.3 Reward Scales\n\n17.1.4 Representing MDPs\n\n- Simplest way to represent P(s’,s,a) and R(s,a,s’): bism three-dimensional tables of size |S|^2|A|. Tables far too big for larger Problems\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nFour different algorithms for solving MDP:\n\n- Exact offline solutions: value iteration, policy iteration, linear programming\n\n- Online approximate algorithms: Monte Carlo planning\n\n17.2.1 Value Iteration\n\n- Basis is the Bellman equation\n\n- For n possible states, there are n Bellman equations, one for each state, containing n unknowns, the utilities of the states\n\n- Equations are nonlinear, because the “max” operator is not a linear operator\n\n- Iterative approach: 1. Start with arbitrary initial values for the utilities; 2. Calculate right-hand side of the equation and plug into left-hand side; 3. Thereby update the utility of each state from the utilities of its neighbors; 4. Repeat until we reach equilibrium\n\n- Iteration step / Bellman update: Ui+1(s) = max_(a in A(s)) sum(s’) P(s’|s,a)[R(s,a,s’)+ γUi(S’)], update is assumed to be applied simultaneously to all the states at each iteration\n\n- Guaranteed to reach an equilibrium when Bellman update applied infinitely often\n\n17.2.2 Policy Iteration\n\nPolicy iteration suggested from the fact that exact magnitude of the utilities involved need not be precise if one action is clearly better than all others.\n\nPolicy iteration alternates two steps, beginning from some initial policy π0:\n\n- Policy evaluation: calculates Ui = U^πi the utility of each state if πi were to be executed, given a policy π\n\n- Policy improvement: Calculates new MEU policy πi+1 using one-step look-ahead based on Ui\n\nTerminates when policy improvement yields no changes in the utilities, so Ui fixed point of the Bellman update, so solution to the Bellman equations and therefore πi must be an optimal policy\n\n- Modified policy Iteration: useful for large state spaces, no exact policy evaluation but simplified value iteration steps to give a reasonably good approximation of the utilities\n\n- Asynchronous policy iteration: General algorithm updating all utility/policy for all states at once (like value and policy iteration)\n\n17.2.3 Linear programming\n\n- General approach for formulating constrained optimization problems\n\n- A Bellman equations involve lot of sums and maxes, solving MDP can be reduced to solving a suitably formulated linear program\n\n- Utilities U(s) are considered as variables in the LP, we seek to minimize U(s) for all s subject to the inequalities U(s) >= sum(s’) P(s’|s,a)[R(s,a,s’)+ )+γU(s’)] for every state s and every action a\n\n- creates connection from dynamic programming to linear programming\n\n17.2.4 Online algorithms for MDPs\n\n- Exact offline solutions not possible for sufficiently large MDPs (such as Tetris)\n\n- In online algorithms, agent does significant amount of computation at each decision point rather than operation primarily with precomputed information\n\n- Example for straightforward approach is simplification of expectiminimax algorithm for game trees with chance nodes\n\n- Real-time dynamic programming (RTDP)\n\n\n## Module 8 Lecture Notes\n\nSummary MDP Algorithm:\n\nUse MDP if you want to:\n- Compute optimal values: iteration or policy iteration\n\n- Compute values for a particular policy: policy evaluation\n\n- Turn values into a policy: policy extraction (one-step lookahead)\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nMULTI-ARMED BANDIT PROBLEMS: SPECIFIC CLASS OF SEQUENTIAL DECISION PROBLEMS\n\nN-armed bandit problem is formal model, deciding which of n possible choices to choose. \n\nClean and most general bandit problem definition:\n\n- Each arm Mi is a Markov reward process or MRP (MDP with only one possible action ai). It has states Si, transition model and reward. The arm defines a distribution over sequences of rewards Ri,0 , Ri,1 , ...\n\n- Overall bandit problem is an MDP: state space given by the Cartesian product S = S1 x ... x Sn\n\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nREINFORCEMENT LEARNING (RL) is an alternative to the supervised learning from previous chapters:\n\n- Agent interacts with the world and periodically receives rewards/reinforcements reflecting the performance\n\n- Reinforcement differs from previous learning because it's not given the MDP but the agent is in the MDP, it may not know transition model or reward function, has to act to learn more\n\n- Little bit of experience can be very helpful for reinforcement learning, especially in simulated environments\n\nDifferent approaches for reinforcement learning:\n\nModel-based reinforcement learning: transition model given; model can be initially unknown, agent then learns model from observing the effects of its actions; transition model is useful for state estimation in partially observable environments; such systems often learn a utility function U(s) defined in terms of the sum of rewards from state s onward\n  \nModel-free reinforcement learning: \n\n- Action-utility learning with Q-learning as its most common form, where the agent learns a Q-function (quality-function) Q(s,a) denoting the sum of rewards from state s onward if action a is taken\n\n- Policy search: agent learns policy π(s) that maps directly from states to actions, also known as reflex agent\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\nPassive reinforcement learning: agent's policy π(s) is fixed and task is to learn the utilities of states U^π(s)(or state-action pairs), which is the expected total discounted reward if policy π is executed beginning in state s\n\nPassive learning task similar to policy evaluation task, difference being that the passive learning agent doesn't know the transition model P(s'|s,a) nor the reward function R(s,a,s')\n\nAgent executes a set of trials in the environment using its policy π, for each starting in first state executing sequence \\ \nuntil terminal state is reached, perceiving both current state and reward for transition.\n\n22.2.1 Direct utility estimation:\n\nUtility of a state defined as expected total reward from that state onward (reward-to-go), algo updates utility of the states after each sequence according to observed reward-to-go as runnign average\n\n-> reinforcement learning reduced to standard supervised learning problem\n\n-> ignores constraint that utility of a state is determined by reward and expected utility of successor states, obeying /\nthje bellman equations for a fixed policy\n\n-> Misses opportunites for learning by ignoring connections between states\n\n22.2.2 Adaptive dynamic programming:\n\n- Takes advantage of constraints among utilities of states by learning the transition model that connects them. \n- Solves MDP using dynamic programming. \n\n- Means for PLAs plugging the learned transition model and observed rewards into Bellman equation to calculate utilities of the states\n \n- Modified policy iteration uses simplified value iteration process to update utility estimates\n\n22.2.3 Temporal-difference learning:\n\n- Utilities of the observed states are adjusted with observed transitions so that they agree with the constraint equations.\n\n- α is the learning rate parameter, following update is applied when transition from state s to s' with action π(s): U^π(s) ← U^π(s)+α[R(s,π(s),s′)+γU^π(s′)−U^π(s)]\n\n- Parameter α can be turned into funcction decreasing as the number of times state has been visited increases\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\nActive reinforcement learning: agent must also figure out which actions to take\n\n- agent needs to learn a complete transition model with outcome probabilities for all actions rather than only for the fixed policy\n\n- learns utilities defined by the optimal policy via the Bellman equation\n\n- Agent decides on action in each step by obtained utility function U by one-step look-ahead to maximize expected utility\n\n22.3.1 Exploration\n\n- Greedy agent: Agent who always following recommendation of the optimal policy, likely to not converge to the optimal policy because the learned model is not the same as the true environment\n\n- Agent should tradeoff b/w exploitation of current best action to maximize short-term reward and exploration of previously unknown states/\nto gain info that might change the policy\n\n- Exploration function f(u,n) determines how greed is traded off against curiosity and should increase with u and decrease with n (number of times action a was tried in state s)\n\n22.3.2 Safe exploration\n\nFor environments where bad state need to be avoided, need to use policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, even if the policy is suboptimal for the maximum-likelyhood model. Three mathematical approaches:\n\n- Bayesian reinforcement learning: assumes prior probability P(h) over hypotheses h about the true model; posterior probability P(h|e) is obtained in the usual way by Bayes' rule given observations to date. If aget stops learning optimal policy is the one that gives highest expected utility\n\n- Robust control theory: allows set of possible models H without assigning probs to each, defining an optimal robust policy as one giving best outcome in the worst case over H. Can result in overly conservative behaviour \n\n22.3.3 Temporal-difference Q-learning\n\n- Q-learning method avoids need for a model by learning action-utility function Q(s,a) instead of utility function U(s)\n\n- Q(s,a) is expected total discounted reward if agent takes action a in s and acts optimally afterwards\n\n- No need for look-ahead based on a transtiton model, just choosing argmax_a Q(s,a)\n\nTO BE ADDED: Bellman equation for Q(s,a) and Q-learning TD update (p. 802)\n\n- SARSA (state, action, reward, state, action) closely related to Q-learning, but Q-learning more flexible\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\nEvaluation function can be used as compact measure of desirability for potentially vast state spaces.\nIt is an approximate utility functionn, so we denote the process of constructing a compact approximation of the true utility function or Q-function with the term function approximation\n\n- Utility function can be approx. with weighted linear comb. of features: Ûθ(s) = θ1f1(s)+θ2f2(s)+···+θnfn(s)\n\n- Approx. utility function can be combined with look-ahead search for more accurate decisions\n\n22.4.1 Approximating direct utility estimation\n\n- Makes sense for reinforcement learning to use an online learning algorithm updating parameters after each trial\n\n- Widrow-Hoff rule / delta rule for online least-squared for updates\n\n22.4.2 Approximating temporal-difference learning\n\n- Ideas can also be applied to temporal-difference learning, adjusting the parameters to try reduce the temporal difference b/w successive states.\n\nTO BE ADDED: new versions of TD and Q-learning equations\n\n- Experience replay can be a solution for catastrophic forgetting\n\n22.4.3 Deep reinforcement learning\n\nTwo reasons why necessary to go beyond linear function approximators:\n\n- May be no good linear function coming close to approximating the utility function or Q-function\n\n- May not be able to invest the necessary features, particularly in new domains\n\nDeep network is a function parameterized by θ, except that the function is much more complicated\n\n22.4.4 Reward shaping\n\nReward shaping involves supplying the agent with additional rewards (called pseudorewards) for making progress. Such rewards can speed up learning enormously\n\n22.4.5 Hierarchical reinforcement learning\n\nHierarchical reinforcement learning (HRL) is an approach to break up very long action sequences into a few pieces, until the action sequences are short enough to make learning easy. \n\n\n\n## AIMA Chapter 22.5 Policy Search\n\n\n- Idea of Policy Search is to keep twiddling the policy as long as its performance imrpvoes, then stop.\n\n- Interested primarily in parameterized representations of π that have far fewer parameters than states in the state space\n\n- Can represent π by collection of parameterized Q-functions (one for each action) and take the action with the highest /\npredicted value: π()s) = argmax_a ^Q_θ(s,a)\n\n- Problem with policy representations is that the policy is a discontinuous function of the parameters when actions are discrete, so there will be values of θ such that an inﬁnitesimal change in θ causes the policy to switch from one action to another, meaning that the value of the policy may also change discontinuosly, making gradient-based search difficult\n\n- Therefore Policy search methods often use a stochastic policy representation π_θ(s,a) specifying the progrability of selecting action a in state s\n\n- Improving the policy: deterministic vs non-deterministic environments\n\n\n\n## Module 9 Lecture Notes\n\nImportant ideas in reinforcement learning:\n\n- Exploration: Unknown actions have to be tried to get information\n\n- Exploitation: have to use what is known\n\n- Regret: even if you learn intelligently you make mistakes\n\n- Sampling: because of chance, things have to be tried repeatedly\n\n- Difficulty: learning can be much harder than solving a known MDP\n\nOffline Solution (MDPs) vs Online Learning (Reinforcement Learning)\n\nModel-Based Learning: \n  \n- Step 1: Learn empirical MDP model\n\n- Step 2: Solve the learned MDP\n\n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- Uncertainly that agents need to handle in the real world can be due to partial observability, nondeterminism or adversaries\n\n- Problem-solving and logical agents handle uncertaintly by keeping track of a belief state and generating a contingency plan handling every possible eventuality it may observe during execution. Drawbacks as agent need to consider every possible explanation for sensor observations, a correct contigent plan handlingevery eventuality can grow arbitrarily large and sometimes no plan is guaranteed to achieve the goal\n\n12.1.1 Summarizing uncertainty\n\n- Trying to use logic to cope with a domain mgith fail for three main reasons: Laziness, Theoretical ignorance, Practical ignorance\n\n- Agent's knowledge can at best provide only a egree of belief in the relevant sentences, and out main tooll for dealing with such degrees of belief is probability theory\n\n- Difference of epistemological commitments: logical agent believes only true/false/no_opinion for each sentence, while probabilistic agent have numerical degree of belief b/w 0 and 1\n\n- Probability theory provides a way of summarizing the uncertainty that comes from our laziness and ignorance, thereby solving the qualification problem\n\nProbability satements are made with respect to a knowledge state, not the real world\n\n12.1.2 Uncertainty and rational decions\n\n- Outcome is a completely specified state: to make choice, agent must have preferences among the different possible outcomes of various plans\n\n- Utility function can account for any set of preferences\n\n- Decision Theory = probability theory + utility theory (preferences)\n\n- Maximum expected utility (MEU): agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action\n\n- Decision-theoretic agent's belief state represents not just the possibilities for world states but also their probabilities\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n\n12.2.1 What probabilities are about\n\n- Sample space: set of all possible worlds which are mutually exclusive and exhaustive\n\n- Ω (uppercase omega) is used to refer to the sample space\n\n- ω (lowercase omega) refers to elements of the space, particularly possible worlds\n\n- Fully specified probability model associates a numerical probability P(ω) with each possible world (b/w 0 and 1)\n\n- Events: sets of possible worlds for specific event\n\n- Proposition: corresponds to a set of worlds containing just the possible worlds in which the proposition holds\n\n- Probability associated with a proposition is deﬁned to be the sum of the probabilities of the worlds in which it holds\n\n- Unconditional probabilities (P(x)) vs conditional/posterior probabilities given y (P(x|y))\n\n- Agent needs to condition on all the evidence it has observed to make decisions\n\n12.2.2 The language of propositions in probability assertions\n\n- Variables in probability theory called random variables, their names beginning with uppercase\n\n- Random variable is function mapping the domain of possible worlds Ω to some range (set of possible values), names for values being lowercase\n\n- Propositions of the form A=true are abbreviated simply as a, A=false is abbreviated as ¬a\n\n- Common in probability notation to use a comma for conjunction, e.g.  P(cavity | ¬toothache,teen)\n\n- P statement defines probability distribution for a random variable, e.g. P(Weather)= 〈 0.6,0.1,0.29,0.01 〉\n\n- P notation is also used for conditional distributions: P(X|Y) gives the values of P(X=xi|Y=yj) for each possible i, j pair\n\n- For continuos variables, probabuility density function used\n\n- P(x,y) denotes the probabilities of all combinations of the values of x and y; P(x,y) = P(x|y)*P(y)\n\n- Possible world is defined to be an assignment of values to all the random variables under consideration\n\n- Full joint probability distribution defines a probability model\n\n12.2.3 Probability axioms and their reasonableness\n\n- Relationship between the probability of a proposition and the probability of its negation: P(¬a) = 1 - P(a)\n\n- Inclusion-exclusion principle (probability of a disjunction): P(a∨b) = P(a)+P(b)−P(a∧b)\n\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n\n- Simple method for probabilistic inference: computation of posterior probabilities for query propositions given observed evidence. Use full joint distribution as knowledge base from which answers to all questions may be derived\n\n- Probabilities in the joint distribution sum to 1\n\n- Common task to extract distribution over some subset of variables or a single variable (marginal probability)\n\n- Marginalization (summing out): marginalization rule for any sets of variables Y and Z: P(Y) = ∑_s P(Y,Z=z)\n\n- Conditioning Rule: P(Y) = ∑_z P(Y|z)P(z)\n\n- Marginalization and conditioning useful rules for different derivations involving probability expressions\n\n- General inference procedure (single variable X, list of evidence variables E, list of observed values for them e, remaining unobserved variables Y): Query P(X|e) can be evaluated as P(X|e) = αP(X,e) = α ∑_y P(X,e,y)\n\n- X, E, Y form complete set of variables in the domain, so P(X,e,y) simply a subset of probabilites from the full joint distribution\n\n\n## AIMA Chapter 12.4 Independence\n\n\n- Independence assertions usually based on knowledge of the domain\n\n- If available, independence assertions can help reduce the size of the domain representation and complexity of the inference problem\n\n- Separation of entire sets of variables by independence is rare, because whenever a connection (also very indirect) /\nexisits b/w two variables, the independence fails to hold\n\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n\n- Bayes Rule: P(b|a) = (P(a|b)P(b))/P(a)\n\n- General case of Bayes' rule for multivalued variables: P(Y|X) = ((P(X|Y)P(Y))/P(X)\n\n- General version conditionalized on some background evidence e: P(Y|X,e) = ((P(X|Y,e)P(Y|e))/P(X|e)\n\n12.5.1 Applying Bayes' rule: the simple case\n\n- Rule allows us to compute the single term P(b|a) in terms of three terms: P(a|b), P(b), and P(a)\n\n- Cause effect relationship: P(cause|effect) = (P(effect|cause)P(cause))/P(effect)\n\n- Avoid asessing prior probability of the evidence (here, P(s)) by instead computing a posterior probability for each value of the query variable (here, m and ¬m) and then normalizing results can also be applied using Bayes' rule: P(M|s) = α〈P(s|m)P(m),P(s|¬m)P(¬m)〉 (P(s|¬m) to be estimated instead of P(s))\n\n- General Form of Bayes' rule with normalization: P(Y|X) = α P(X|Y)P(Y), α being normalization constant to make entries in P(Y|X) sum to 1\n\n12.5.2 Using Bayes' rule: Combining evidence\n\n- Conditional independence of two variables X and Y, given a third variable Z: P(X,Y|Z) = P(X|Z)P(Y|Z)\n\n- Representation size: n variables that are all conditionally independent given another variable, size of representation grows as O(n) instead of O(n^2)\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n\n- Full joint distribution can be written as P(Cause,Effect 1,...,Effect n) = P(Cause) ∏i P(Effect i| Cause) (12.20)\n\n- Probability distribution called naive Bayes model because often used in cases even if effect variables are not strictly independent /\ngiven the cause variable, however often works well in practice\n\nUse naive Bayes:\n\n- Apply 12.20 (see above) to obtain probability of the cause given some unobserved effects\n\n- Observed Effects E=e, while remaining effect variables Y are unobserved\n\n- Apply standard method for inference from the joint distribution: P(Cause|e) = α ∑y P(Cause,e,y)\n\n- Word interpretation of the equation: \"for each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause; then normalize the result\"\n\n- Calculation run time is linear in the number of observed effects and does not depend on the number of unobserved effects\n\n12.6.1 Text classification with naive Bayes\n\n- Naive Bayes assumes that words occur independently in documents, with frequencies determined by the document category, so independence assumption is clearly violated in practice\n\n- Violation of independence usually meansfinal posterior probabilities will be much closer to 1 or 0 than they should be, so model is overconfident\n\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n- Independence and conditional independence relationships can be used to simplify te required summations\n\n\n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n- Symplifying Assumption = Markov Assumption: Probability depends on the previous k words, not the whole context\n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n- Bayesian network represents the dependencies among variables and is a directed graph in which each node is annotated with quantitative probability information\n\n- Nodes correspond to random variables, directed_links/arrows connect pairs of nodes\n\n- Node Xi has associated probability information θ(Xi|Parents(Xi)) quantifying the effect of the parents on the node using a ﬁnite number of parameters\n\n- Network (set of nodes and links) specifies conditional independence relationsjips that hold in the domain\n\n- X->Y: X has a direct influence on Y, suggests that causes should be parrents of effects\n\n- Conditiaonal probability table (CPT): Local probability information to each node, each row contains cond. prob. of each node value for a conditioning case\n\n- False value often omitted as 1 - p, generally a table for a Boolean variable with k Boolean parents contains 2^k independently specifiable probabilites\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- Syntax of a Bayes net consists of a directed acylclic graph with some local probability information attached to each node\n\n- Semantics defines how the syntax corresponds to a joint distr. over the variables of the network\n\n- Semantics of Bayes nets defines each entry in the joint distr. as P(x 1,...,x n) = n∏i=1 θ(xi|parents(Xi)), parents(Xi) denoting the values of Parents(Xi) that appear in x1,...,xn\n\n- Each entry in the joint distr. is represented by the product of the approp. elements of the local conditional distr. in the Bayes net.\n\n- P(xi|parents(Xi)) = θ(xi|parents(Xi)) so we can rewrite P(x 1,...,x n) = n∏i=1 P(xi|parents(Xi)), meaning that when one estimates values for the local cond. distr., they need to be the actual conditional probabilities for the variables given its parents\n\n- Chain Rule: P(x1,...,xn) = n∏i=1 P(xi|xi−1,...,x1)\n\n- P(Xi|Xi−1 ,...,X1) = P(Xi|Parents(Xi)) provided that Parents(Xi) ⊆ {Xi−1,...,X1}, so Bayesian network is a correct repr. of the domain only if each node is cond. indep. of its other predecessors in the node ordering, given its parents\n\n- Compactness and node ordering: ayes net often fare more compact than full joint distribution, well chosen node ordering required for compact Bayes net\n\n13.2.1 Conditional independence relations in Bayesian networks\n\n- Each variable is conditionally independent of its non-descendants, given its parents\n\n- Non-descendants property combined with interpr. of the network parameters θ(Xi|Parents(Xi)) as cond. prob. P(X i| Parents(X i)) sufﬁces to reconstruct full joint distribution \n\n- Markov blanket property: variable cond. indep. of all other nodes in the network, given its parents, cildren and children's parents\n\n- Determination if Bayes net Z d-separates X and Y is important\n\n13.2.2 Efficient Representation of Cinditional Distributions\n\n- Filling in the CPT for a node requires up to O(2^k)\n\n- Relationships are describable by a canonical distribution that fits some standard pattern, simplest example provided by deterministic nodes, whose value is specified exactly by the values of its parents with no uncertainty.\n\n- Context-specific independence (CSI) is exhibited by conditional distribution if a variable is cond. indep. of some of its parents given certain values of others\n\n- Noisy-OR model allows for uncertainly about the ability of each parent to cause the child being true, making two assumptions: 1. all the possible causes are listed; 2. inhibition /\nof each parent is indep. of inhibition of any other parents\n\n13.2.3 Bayesoan nets with continuous variables\n\n- continuous variables can by handled with discretization or nonparametric representation\n\n- Hybrid Bayesian network contains both discrete and continuous variables\n\n- Linear-Gaussian conditional distribution most common choice\n\n13.2.4 Case study: Car insurance\n\n- Bayes net includes hidden variables that are neither input nor output variables but essential for structuring the network\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\nBasic task of any probabilistic inference system is computation of posterior probability distribution for a set of query variables given some obsered event (assignment of value to a set of evidence variables)\n\n13.3.1 Inference by enumeration\n\n- Any conditional probability can be computed by summing terms from the full joint distribution, so a query P(X|e) can be answered using P(X|e) = αP(X,e) = α ∑y P(X,e,y)\n\n- P(x,e,y) in the joint distribution can be written as products of cond. prob. from the netwotk, so a query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network\n\n- Complexity (O(n2^n) in the worst case) can be reduced to O(2^n) taking advantage of the nested structure of the computation (moving summations inwards as far as possible)\n\n13.3.2 The variable elimination algorithm\n\n- Elimination of repeated calculations can improve the enumeration algorithm substantially\n\n- The elimination of variables works by evaluating expressions in right-to-left order \n\n- Operations on factors: Pointwise product of two factors f and g yields a new factor h whose variables are the union of the variables in f and g and whose elements are given by the product of the corresponding elements in the two factors\n\n- Time and space requirements of variable elimination dominated by size of the largest factor construxted during he operation of the algorithm, being determined by the order of elimination of variables and the structure of the network.\n\n- Determination of optimal ordering is intracable, but several good heuristics are available. \n\n13.3.3 The complexity of exact inference\n\n13.3.4 Clustering algorithms\n\n- Clustering Algorithms can be used to reduce the time to O(n), so those algorithms are widely used in commercial Bayes net tools.\n\n- Basic idea of clustering is to join individual nodes of the network to form cluster nodes in such a way that the resulting network is a polytree\n\n- Two Boolean nodes are replaced by a meganode that takes on four possible values\n\n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n \nMachine learning can improve any component of an agent program. Improvements and the techniques used to make them depend on three factors:\n\n- Which component is to be improved?\n\n- What prior knowledge has the agent and which influences the model it builds\n\n- What data and feedback on that data is available\n\nAgents include the following components, and each of them can be learned:\n\n- Direct mapping from conditions on the current state to actions\n\n- Means to infer relevant properties of the world from the percept sequence\n\n- Information about the way the world evolves and about the results of possible actions the agent can take\n\n- Utility information indicating the desirability of world states\n\n- Action-value information indicating the desirability of world states\n\n- Goals that describe the most desirable states\n\n- A problem generator, critic, and learning element that enable the system to improve\n\nGoing from a specific set of obsercations to a general rule is called indcution, which differs from the deduction because the inductive conclusions may be incorrect, wheras deductive conclusions are guaranteed to be currect if the premises are correct\n\nChapter 19 focuses pf problems where the input is a factored representation (a vector of attribute values). \n\nClassification vs Regression learning problems:\n\n- Classification: Outout is one of a finite set of values\n\n- Regression: Output is a number\n\nThree types of feedback accompanying the inputs, determining the three main types of learning:\n\n- Supervised learning: Agent observes input-output pairs and learns a function that maps from input to output. (Output called a label)\n\n- Unsupervised learning: Agent learns patterns in the input without any explicit feedback. Most common unsupervised learning task is clustering\n\n- Reinforcement learning: Agent learns form a series of reinforcements: rewards and punishments\n\n\n## AIMA Chapter 19.2 Supervised Learning\n\n- Task of supervised learning: Given a training set of N example input-output pairs (x1,y1),(x2,y2),...(xN,yN), with each pair generated by an unknown function y=f(x), the function h that approximates the true function f is to be discovered\n\n- Function h is a hypothesis about the world, and it is drawn from a hypothesis space H of possible functions\n\n- Exploratory data analysis: Examining the data with statistical tests and visualization\n\n- Consistent hypothesis: h such that each xi in the training set has h(xi)=yi, but unrealistic for continuous-valued outputs, for this better best-fit function\n\n- Best-fit function: h(xi) is close to yi\n\n- Generalization: We can say that h generalizes well if it accurately predicts the outputs of the test set\n\n- Underfitting: A hypothesis is underfitting when it fails to find a pattern in the data\n\n- Variance is the amount of change in the hypothesis due to fluctuation in the training data\n\n- Overfitting: function is overfitting data when it pays too much attention to the particular data set it is trained on, causing it to perform pporly on unseen data\n\n- Bias-Varianve tradeoff: Choice between more complex, low-bias hypothesis that fit the training data well and simplier, low-variance hypotheses that may generalize better\n\n- There is a tradoff between the expressiveness of a hypothesis space and the computational complexity of funding a good hypothesis within that space\n\n- Expressiceness-complexity tradeoff: Expressive language makes it possible for a simple hypothesis to fit the data, whereas restricting the expressiveness of the language means that any consistent hypothesis must be complex\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n\n- Decision tree: Representation of a function that maps a vector of attribute values to a single output value (decision), reaching its decision by performing a sequence of tests, starting at the root and following the appropriate branch until a leaf is reached\n\n19.3.1: Expressiveness of decision trees:\n\n- Boolean decision tree equivalent to a logical statement of the form Output ⇔ (Path1 ∨ Path2 ∨ ···)\n\n- Path i is a conjunction of the form (Am = vx ∧ An = vy ∧ ···) of attribute-value tests corresponding to a path from the root to a true leaf.\n\n- There is no kind of representation that is efficient for all kinds of functions\n\n19.3.2 Learning decision trees fropm examples\n\n- The LEARN-DECISION-TREE algorithm adopts a greedy divide-and-conquer strategy: always test the most imprortant attribute first, then recursively solve the smaller subproblems that are defined  by the possible results of the test\n\n- A tree consists of tests on attributes in the interior nodes, values of attributes on the branches, and output values on the leaf nodes\n\n- Performance of a learning algorithm can be evaluated with a learning curve\n\n19.3.3 Choosing attribute tests\n\n-  Attributes are chosen with the highest importance in the decision tree learning algorithm\n\n- Importance can be measured with the notion of information gain, which is defined in terms of entropy, the fundamental quantity in infortmation theory\n\n- Entropy is a measure of the uncertainty of a random variable: the more information, the less entropy\n\n- Generally, the entropy of a random variable V with values vk having probability P(vk) is defined as H(V) = ∑k P(vk) log2 1/P(vk) = −∑k P(vk) log2 P(vk)\n\n- Randomly chosen example from the training set has the kth value for the attribute, so the expected entropy remaining after testing attribute A is Remainder(A) = d∑k=1 (pk+nk)/(p+n) B(pk/(pk+nk))\n\n- Information gain from the attribute test on A is the expected reduction in entropy: Gain(A) = B(p/(p+n))−Remainder(A)\n\n- Gain(A) is what is needed to implement the IMPORTANCE function\n\n19.3.4 Generalization and overfitting\n\n- Overfitting becomes more likely as the number of attributes grows, and les likely as the number of training examples increases\n\n- Decision tree pruning: Technique comating overfitting, which works by eliminating nodes that are not clearly relevant\n\n19.3.5 Broadening the applicability of decision trees\n\n- Decision trees can be made more widely useful y handling the following complications: Missing Data, Continuous and multivalued input attributes, continuous-valued output attributes\n\n- Advantages of decision trees: ease of understanding, scalabilit to large data sets and versatility in handling discrete and contiuous input as well as classification and regression\n\n\n## AIMA Chapter 19.4 Model Selection and Optimization\n\n- Stationarity assumption: Future examples will be like the past. Assume each example Ej has the same prior probability distribution and is independent of the previous examples -> equations are independent and identically distributed (i.i.d.)\n\n- Optimal fit is the hypothesis that minimizes the error rate: proportion of times that h(x) =/ y for an (x,y) example\n\n-The error rate of a hypothesis can be estimated by giving it a tesT: performance on a test set of examples is measured, and training set and test set are splitted\n\n- \"Knobs\" / hyperparameters: parameters of the model class, not of the individual model\n\n- Three data sets required: Training set, validation set (also development set) and test set\n\n- leave-one-out cross-validation (LOOCV)\n\n- Finding a good hypothesis consists of two subtasks: Model selection chooses a good hypothesis space, and optimization (training) finds the best hypothesis within that space\n\n- Part of the model selection is qualitative and subjective, other part can be quantitative and empirical\n\n19.4.1 Model selection:\n\n- Model-Selection algorithm takes learning algorithm with one hyperparameter as argument. Model selection starts with the smallesst value of the hyperparameter, yielding a simple model, iterating through larger values of the hyperparameter, considering cmore complex models. At the end, model-selection selects the model that hsa the lowest average error rate on the held-out validation data\n\n- Complexity measured by the number of decision tree nodes and number of neural nework parameters\n\n- Error decreases for a while as model complexity increases, but reaches a point where it begins to overfit and validation error rises\n\n- Model classes start to overfit as the capacity approaches the point of interpolation (model exactly fits all the training data)\n\n19.4.2 From error rates to loss\n\n- Machine learning traditionally minimizes a loss function rather than maximizing a utility function\n\n- Loss function L(x,y,^y) defines as the amount of utility lost by predicting h(x)=^y when the correct answer is f(x)=y\n\n- Simplified version: L(y,^y) that is independent of x\n\n- L(y,y) is always zero as there is no loss when you guess exactly right\n\n- Generalization loss\n\n- Empirical los\n\n- Learning problem is realizable if the hypothesis space H actually contains the true function f\n\n- Variance means that a learning algorithm will return different hypotheses for different sets of examples\n\n- Computationally intractable to systematically seach all possibilities in a hypothesis space when H is a complicated function\n\n- Small-scale learning vs learge-scale learning, where generalization loss is dominated by limits of computation\n\n19.4.3: Regularization\n\n- Process of explicitly penalizing complex hypotheses\n\n19.4.4 Hyperparameter tuning\n\n- When there are multiple hyperparameeter or they have continuous values, it is more difficult to choose good values\n\n\n\n## AIMA Chapter 19.5 The Threory of Learning\n \n\n- Computational learning theory lies at the intersction of AI, statistics and theoretical computer scienve\n\n- Underlying principle is that any hypothesis that is seriously wrong will almost certainly be \"found out\" with high probability after a small number of examples as it will make an incorrect prediction\n\n- Hypothesis must be probabily approximately correct (PAC) to be consistent with a sifficiently large set of traini9ng examples\n\n- PAC-learning theorems are logical consequences of axioms\n\n- Hypothesis h is approximately correct if error(h) ≤ ǫ, where ǫ is a small constant.\n\n- Sample complexity is the number of required examples as a function of ǫ and δ\n\n19.5.1 PAC learning example: Learning decision lists \n\n\n\n## AIMA Chapter 16.6 Linear Regression and Classification\n \n\n19.6.1 Univariate linear regression\n\n- Many forms of learning involve adjusting weights to minimize a loss\n\n- The loss function is convex\n\n19.6.2 Gradient descent\n\n- Search through a continuous weight space by incrementally modifying the parameters to minimize loss\n\n- Starting point (e,g, (w0,w1)) is chosen in weight space, then computing an estimate of the gradient and moving a small amount in the steepest downhill direction, repeating until converged on a point in weight space with (local) minimum loss\n\n- Batch gradient descent and stochastic gradient descent\n\n19.6.3 Multivariable linear regression\n\n- Multivariable linear regression has n-element vectors, it's not much more complicated than the univariate case\n\n- Gradient descent will reach the (unique) minimum of the loss function, the update the equation for each weight wi\n\n19.6.4 Linear classifiers with a hard threshold\n\n- Linear functions can be used to do classification as well as regression\n\n- Decision boundary is a line that separates the two classe, linear decision bounardy called a linear separator\n\n19.6.5 Linear classification with logistic regression\n\n- Logistic regression: Process of fitting weights of this model to minimize loss on a data set\n\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\n- Naive Bayes: Assume all features are independent effects of the label\n\n- Avoid giving unseen events zero probability -> smooth or regulazire the estimates\n\n- Best fit for set of training data, the parameter settings that maximizes the likelihood of the data given those parameter settings\n\n- Perceptron -> Decision making device\n\n- Binary Perceptron Learning: Start with weights 0 and for each training instance, classify with current wights and if those are wrong, adjust the weight vector by adding or substracting the feature vector (subtract if y* is -1). w = w + y* x f\n\n- Multiclass Decision Rule: If we have multiple classes, we have a weight vector for each class\n\n- Properties of Perceptrons: Separability, Convergence, Mistake Bound\n\n- Separabiulity: true if some parameters get the training set perfectly correct\n\n- Convergence: if the training is separable, perceptron will eventually converge (binary case)\n\n- Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability\n\n- MIRA (Margin infused relaxed algorithm): Chossing an update size that fixed the current mistake\n\n- Support Vector maxhines (SVMs): Find linear separator that maximizes the margin\n\nNaive Bayes vs Perceptrons: Classification comparison:\n\n- Naive Bayer: Builds a model training data, gives prediction prob., strong assumptions about feature indep., one pass through data (counting)\n\n- Preceptrons / MIRA: Makes less assumptions about data, Mistake-driven learning, multiple passes through data (prediction), often more accurate\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\nLogistic Regression:\n\n- Loss functions for probabilistic classification:\n\n- Use a loss function prefering the correct class labels of the training example to be more likely\n\n- Cond. maximum likelihood estimation: Choose parameters w,b that maximize the (log) prob. of the true labels in the training data\n\n- Resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss\n\nStochastic Gradient Descent\n\n- Theta: Trying to find a particular setting of Theta that's going to minimize the average loss across our training set using the cross entropy loss function\n\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the parameters Theta) the function's slope is rising the most steeply, and moving in the opposite direction\n\n- Global v. Local Minimums: For logistic regression, loss function is conveniently convex (only one minimum), so gradient guaranteed to find minimum from any starting point\n\n- Regularization: penalizes large weights (added to the loss function) to avoid overfitting\n\n- Multinomial logistic regression can have more than two classes\n\n- Softmax: Softmax function takes in an input vector z = [z1,z2,...,Zk] and outputs a vector of values normalized into probabilities\n\nNeural Networks:\n\n- Neural networks includes differrent layers: Input layer, hidden layers, output layer\n\n- Sigmoid neuron function much smoother than Perceptron (0 or 1)\n\n- Activation functions: non-linear functions f to z, output is called the activation value, represented by variable a. Commonly used non-linear functions used for f are the sigmoid function, tanh function and rectified linear unit (ReLu)\n\n- Feed-Forward Neural Network: Simplest kind of Neural Network, a multilayer network where all units are usually fully-connected and no cycles. Outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower levels\n\n- Error backpropagation algorithm: Instance of backward differentiation, defining computation graph and figuring out how much each element contributes to the total at the end.\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n\nLogistic Regression:\n\n- Loss functions for probabilistic classification:\n\n- Use a loss function prefering the correct class labels of the training example to be more likely\n\n- Cond. maximum likelihood estimation: Choose parameters w,b that maximize the (log) prob. of the true labels in the training data\n\n- Resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss\n\nStochastic Gradient Descent\n\n- Theta: Trying to find a particular setting of Theta that's going to minimize the average loss across our training set using the cross entropy loss function\n\n- Gradient descent: method that finds a minimum of a function by figuring out in which direction (in the space of the parameters Theta) the function's slope is rising the most steeply, and moving in the opposite direction\n\n- Global v. Local Minimums: For logistic regression, loss function is conveniently convex (only one minimum), so gradient guaranteed to find minimum from any starting point\n\n- Regularization: penalizes large weights (added to the loss function) to avoid overfitting\n\n- Multinomial logistic regression can have more than two classes\n\n- Softmax: Softmax function takes in an input vector z = [z1,z2,...,Zk] and outputs a vector of values normalized into probabilities\n\nNeural Networks:\n\n- Neural networks includes differrent layers: Input layer, hidden layers, output layer\n\n- Sigmoid neuron function much smoother than Perceptron (0 or 1)\n\n- Activation functions: non-linear functions f to z, output is called the activation value, represented by variable a. Commonly used non-linear functions used for f are the sigmoid function, tanh function and rectified linear unit (ReLu)\n\n- Feed-Forward Neural Network: Simplest kind of Neural Network, a multilayer network where all units are usually fully-connected and no cycles. Outputs from each layer are passed to units in the next higher layer, and no outputs are passed back to lower levels\n\n- Error backpropagation algorithm: Instance of backward differentiation, defining computation graph and figuring out how much each element contributes to the total at the end.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}