{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "384c6e94-9888-4136-b2ad-64ad38ee6733"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0ee040a2-a7e1-4477-a49f-a47fbcdaad26"
      },
      "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": 56,
      "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 = \"Xinwei Tang\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "- Agent has some available action a. There may be uncertainty about the current state, so we’ll assume that the agent assigns a probability P(s)\n",
        "\\to each possible current state s.\n",
        "- There may also be uncertainty about the action outcomes; the transition model is given by P(s'|s,a)\n",
        "- We are interested in outcome s', so probability of reaching s' by doing a in current state is P(Result(a)=s').\n",
        "- P(Result(a)=s') = summation of P(s)P(s'|s,a), this requires perception, learning, knowledge representation, and inference.\n",
        "- Computing this itself requires a causal model of world. Many actions to consider. computing the outcome utilities \n",
        "\\may itself require further searching or planning because an agent may not know how good a state is until it knows where it can get to from that state. \n",
        "\n",
        "### Decision theory\n",
        "- Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.\n",
        "- The agent’s preferences are captured by a utility function U(s),which assigns a single number to express the desirability of a state.\n",
        "- The expected utility of an action given the evidence, EU(a) is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n",
        "- It does provide the beginnings of a basic mathematical framework that is general enough to define the AI problem.\n",
        "### MEU\n",
        "- The MEU principle could be seen as a prescription for intelligent behavior, AI needs quantities, max U over actions, but AI problem is not solved.\n",
        "- The MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice.\n",
        "- The MEU principle has a clear relation to the idea of performance measures.\n",
        "- If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). \n",
        "- This is the central justification for the MEU principle itself. \n",
        "- The performance measure gives a score for a history—a sequence of states. Thus it is applied retrospectively after an agent completes a sequence of actions. The utility function applies to the very next state, so it can be used to guide actions step by step.\n",
        "\n",
        "\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" \n",
        "- MEU is not the only rational way to make decisions. \n",
        "- A&B can be states of world. \n",
        "\n",
        "### Constraints on rational preferences\n",
        "- Symbol in pic.\n",
        "- Think of the set of outcomes for each action as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1,...,Sn that occur with probabilities p1,...,pn is\n",
        "- L=[p1,S1;p2,S2;...;pn,Sn]\n",
        "- Each outcome  of a lottery can be either an atomic state or another lottery. \n",
        "1. Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding.\n",
        "2. TRANSITIVITY: If A prefers B, B prefers C, then A prefers C.\n",
        "3. Continuity: If lottery B between A and C in preference some probability p for which RA will be indifferent between getting B for sure and lottery that yields A with p and C with 1-p.\n",
        "4. Substitutability:  If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. Holds regardless of p and other outcomes in lotteries. \n",
        "5. Monotonicity: Two lotteries have the same two possible outcomes, A&B. If agent prefers A to B,then the agent must prefer the lottery that has a higher probability for A.\n",
        "6. Decomposability: Compound lotteries can be reduced to simpler ones using the laws of probability. \n",
        "- These constraints are known as the axioms of utility theory. Each axiom can be motivated by showing that an agent that violates it will exhibit patently irrational behavior in some situations. \n",
        "\n",
        "### Rational preferences lead to utility\n",
        "- Notice that the axioms of utility theory are really axioms about preferences—they say nothing about a utility function. \n",
        "1. Existence of utility function: If an agent’s preferences obey the axioms of utility, then there exists a function U such that U(A) > U(B) iff A is preferred to B, and U(A) = U(B) iff agent is indifferent between A and B.\n",
        "2. Expected utility of a lottery: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n",
        "- In other words, once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined. \n",
        "- The preceding theorems establish that (assuming the constraints on rational preferences) a utility function exists for any rational agent. The theorems do not establish that the utility function is unique. \n",
        "- It is important to remember that the existence of a utility function that describes an agent’s preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations. \n",
        "- By observing a rational agent’s behavior, an observer can learn about the utility function that represents what the agent is actually trying to achieve.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "\n",
        "## Utility Functions\n",
        "- Utility functions map from lotteries to real numbers.\n",
        "\n",
        "### Utility assessment and utility scales\n",
        "- A scale for utility can be established by fixing the utilities of any two particular outcomes, just as we fix a temperature scale by fixing the freezing point and boiling point of water.\n",
        "- Normalize utility, best = 1, worst = 0. Ask agent choose standard lottery [p, u1; (1-p),u2]. P is adjusted until agent is indifferent between S and the standard lottery. That will be utility of S.\n",
        "- Use micromort and QALY to value life. \n",
        "\n",
        "### Utility of money\n",
        "- Agents exhibits monotonic preference for money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n",
        "- Money lottery problem. To determine what to do, we need to assign utilities to the outcome states. Utility is not directly proportional to monetary value, because the utility for your first million is very high (or so they say), whereas the utility for an additional million is smaller. \n",
        "- In a pioneering study of actual utility functions, Grayson (1960) found that the utility of money was almost exactly proportional to the logarithm of the amount. \n",
        "- If we restrict our attention to the positive part of the curves, where the slope is decreasing, then for any lottery , the utility of being faced with that lottery is less than the utility of being handed the expected monetary value of the lottery as a sure thing.\n",
        "- That is, agents with curves of this shape are risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n",
        "- On the other hand, in the “desperate” region at large negative wealth in Figure 16.2(b), the behavior is risk-seeking. \n",
        "- For gambles with small sums, therefore, we expect risk neutrality.\n",
        "\n",
        "### Expected utility and post-decision disappointment\n",
        "- The rational way to choose the best action, a* , is to maximize expected utility.\n",
        "- If everything correct, on average, we will get the utility we expect if the whole process is repeated many times.\n",
        "- In reality, however, our model usually oversimplifies the real situation, either because we don’t know enough, or because the computation of the true expected utility is too difficult.\n",
        "- We assumed estimates are unbiased. In that case, it still seems reasonable to choose the action with the highest estimated utility and to expect to receive that utility, on average, when the action is executed.\n",
        "- Unfortunately, the real outcome will usually be significantly worse.\n",
        "- It is a straightforward matter to calculate the distribution of the maximum of the k estimates and hence quantify the extent of our disappointment.\n",
        "- When k gets larger, disappointment gets higher in terms of more std deviation.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "\n",
        "#### Certainty effect reasons\n",
        "1. First, people prefer to reduce computational burden; by choosing certain outcomes, they don’t have to compute with probabilities. But the effect persists even when the computations involved are very easy ones.\n",
        "2. Second, people may distrust the legitimacy of the stated probabilities. In the presence of distrust, it might be better to go for the sure thing. Distrust others flip coins.\n",
        "3. People may be accounting for their emotional state as well as their financial state. People know they would experience regret.\n",
        "- Yet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is framing effect. \n",
        "- People feel more comfortable making relative utility judgments rather than absolute ones.\n",
        "- If human informants insist on contradictory preference judgments, there is nothing that automated agents can do to be consistent with them. Fortunately, preference judgments made by humans are often open to revision in the light of further consideration.\n",
        "\n",
        "\n",
        "## Sequential Decision Problems\n",
        "- MDP more like real world. MDPs have been studied in several fields, including AI, operations research, economics, and control theory.\n",
        "#### Agent grids\n",
        "- The outcome is stochastic, so write as P(s'|s,a) for p reaching s' if a is done in state s.\n",
        "- We will assume that transitions are Markovian: the probability of reaching s' from s depends onl on s and not history of earlier states.\n",
        "- To complete the definition of the task environment, we must specify the utility function for the agent. Because the decision problem is sequential, the utility function will depend on a sequence of states and actions—an environment history—rather than on a single state.\n",
        "- Every transition from s to s' via a, agent receives reward R(s,a,s'), bounded by +- Rmax.\n",
        "- A sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process, or MDP, and consists of a set of states (initial state S0). A set of actions of actions in each state. A transition model P(s'|s,a), and a reward function R(s,a,s').\n",
        "- Methods for solving MDPs usually involve dynamic programming.\n",
        "\n",
        "#### Solution: Policy (pie)\n",
        "- No fixed action sequence can solve the problem, because the agent might end up in a state other than the goal.\n",
        "- Solution is policy. Therefore, a solution must specify what the agent should do for any state that the agent might reach.\n",
        "- Policy is symbol pie. pie(s) is action recommended by policy pie for state s.\n",
        "- No matter what the outcome of the action, the resulting state will be in the policy, and the agent will know what to do next.\n",
        "- The quality of a policy is therefore measured by the expected utility of the possible environment histories generated by that policy.\n",
        "- Represents the agent function explicitly. A description of a simple reflex agent, computed from the information used for a utility-based agent.\n",
        "- Often have multiple optimal policies.\n",
        "\n",
        "#### Utility over time\n",
        "- Finite or infinite horizon.\n",
        "- With a finite horizon, an optimal action in a given state may depend on how much time is left. So nonstationary policy used.\n",
        "- “Infinite horizon” does not necessarily mean that all state sequences are infinite; it just means that there is no fixed deadline.\n",
        "- If infinite, potential difficulty is if environment no terminal state/agent never reaches one, all environment histories are infinitely long and utilities with additive undiscounted rewards is finite.\n",
        "- Discount factory gamma between 0 and 1. \n",
        "- Discount make sense due to preference of early rewards, uncertainty about true rewards. \n",
        "- A discount factor of gamma is equivalent to adding a probability  of accidental termination at every time step, independent of the action taken.\n",
        "- Agent’s preferences between state sequences are stationary. Means if you prefer a future, preference same no matter when future starts.\n",
        "- If gamma < 1, rewards bounded by +- Rmax, utility is finite.\n",
        "- If environment contains terminal state and if proper policy, gamma can be 1.\n",
        "- Infinite sequences compred in terms of averge reward obtained per time step. But analysis is complex.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "\n",
        "#### Optimal policies and the utilities of states\n",
        "- Utility of a given history is the sum of discounted rewards\n",
        "- Compare policies thru expected utilities obtained when executing them.\n",
        "- A remarkable consequence of using discounted utilities with infinite horizons is that the optimal policy is independent of the starting state\n",
        "- Action sequence wont be independent. \n",
        "- True utility of a state is the expected sum of discounted rewards if the agent executes an optimal policy. Write as U(s).\n",
        "- The utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action. \n",
        "- Use bellman equation to calculate utilities of state.\n",
        "- Optimal policy extracted from Q-function by argmax(Q functions)\n",
        "\n",
        "\n",
        "#### Rewards scales\n",
        "- U(s) becomes U'(s)=mU(s) + b, m > 0. Repalce U(s) with reward function. \n",
        "- TWO MDPs have same optimal policies if only differ in reward functions.\n",
        "- The flexibility afforded by the shaping theorem means that we can actually help out the agent by making the immediate reward more directly reflect what the agent should do.\n",
        "\n",
        "#### Representing MDPs\n",
        "- Big 3 dimensional tables of size |S|^2 |A|. O(|S||A|)\n",
        "- Can represent MDPs by extending dynamic Bayesian networks with decision, reward, and utility nodes to create dynamic decision networks.\n",
        "- DNN has complexity advantage over atomic representations and can model quite substantial real-world problems.\n",
        "\n",
        "\n",
        "\n",
        "## Algorithms for MDPs\n",
        "#### Value Iteration\n",
        "- Propagating information through the state space by means of local updates\n",
        "- The Bellman equation is the basis of the value iteration algorithm for solving MDPs.\n",
        "- n possible states means n possible bellman equations, 1 for each state. \n",
        "- n equations conatins n unknowns, the state utilities. \n",
        "- Equations are non-linear due to max. So cannot solved by linear algebra.\n",
        "- We start with arbitrary initial values for the utilities, calculate the right-hand side of the equation, and plug it into the left-hand side—thereby updating the utility of each state from the utilities of its neighbors. We repeat this until we reach an equilibrium.\n",
        "- Ui(s) is utility value for state s at ith iteration. It is Bellman Update.\n",
        "- The update is assumed to be applied simultaneously to all the states at each iteration.\n",
        "- If applied infinitely, guaranteed to reach equilibrium. \n",
        "- Contraction. A contraction has only one fixed point; if there were two fixed points they would not get closer together when the function was applied, so it would not be a contraction. When the function is applied to any argument, the value must get closer to the fixed point, so repeated application reaches fixed point in the limit.\n",
        "- Measure distances between utility vectors by max norm.\n",
        "- Bellman update function beocmes Ui+1 = BUi with Bellman update operator B applied to all states.\n",
        "- Can use contraction property to analyze rate of convergence. \n",
        "- Terminal condition is |Ui+1 - U| < e\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "\n",
        "#### Policy iteration\n",
        "- Possible to get an optimal policy even when the utility function estimate is inaccurate.\n",
        "- If one action is clearly better than all others, then the exact magnitude of the utilities on the states involved need not be precise.\n",
        "- Done by policy evaluation and policy improvement. \n",
        "1. Policy evaluation: Given a policy piei, calculate Ui = U piei, the utility of each state if piei were to be executed.\n",
        "2. Policy improvement: Calculate a new MEU policy piei+1 using onestep lookahead based on Ui.\n",
        "- The algorithm terminates when the policy improvement step yields no change in the utilities.\n",
        "- O(n^3)\n",
        "-  Instead, we can perform some number of simplified value iteration steps (simplified because the policy is fixed) to give a reasonably good approximation of the utilities.\n",
        "- This is modified policy iteration. \n",
        "- Asynchronous policy iteration: Pick any subset of states and apply either kind of updating above.\n",
        "- The freedom to choose any states to work on means that we can design much more efficient heuristic algorithms\n",
        "\n",
        "\n",
        "#### Linear programming\n",
        "- General approach for formulating constrained optimization problems, and there are many industrial-strength LP solvers available.\n",
        "- The basic idea of the formulation is to consider as variables in the LP the utilities U(s) of each state s. In LP language, that means we seek to minimize U(s) for all s.\n",
        "- This creates a connection from dynamic programming to linear programming, for which algorithms and complexity issues have been studied in great depth.\n",
        "- LP solver seldom efficient as dp. \n",
        "- Polynomial time sounds  good, but number of states is large. \n",
        "\n",
        "#### Online algorithms for MDPs\n",
        "- Value iteration and policy iteration are offline algorithms. They generate an optimal solution for the problem, which can then be executed by a simple agent.\n",
        "- Offline not possible to solve large MDPs. \n",
        "- Simplification of the Expectiminimax algorithm for game trees with chance nodes.\n",
        "- Expectimax algorithm builds a tree of alternating max and chance nodes. An evaluation function can be applied to the nonterminal leaves of the tree, or they can be given a default value. A decision can be extracted from the search tree by backing up the utility values from the leaves, taking an average at the chance nodes and taking the maximum at the decision nodes.\n",
        "- e-horizon useful when discount factor not too close to 1. \n",
        "\n",
        "\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",
        "\"Transition model\" : \"P(s'|s,a), probability that action s in state s reaches state s'.\",\n",
        "\"principle of maximum expected utility (MEU)\" : \"a rational agent should choose the action that maximizes the agent’s expected utility\",\n",
        "\"value function\" : \"in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\",\n",
        "\"ordinal utility function\" : \"value function\",\n",
        "\"preference elicitation\" : \"involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\",\n",
        "\"Normalized utilities\" : \"see pic. Best u = 1, worst u = 0.\",\n",
        "\" micromort\" : \"a one in a million chance of death. Value of life.\",\n",
        "\"QALY\" : \"Quality-adjusted life year. Patients are willing to accept a shorter life expectancy to avoid a disability.\",\n",
        "\"monotonic preference\" : \"Prefer more to less, with other things equal.\",\n",
        "\"certainty equivalent \" : \"Value an agent will accept in lottery of that lottery. Like $400 confirm, not the expected value $500.\",\n",
        "\"insurance premium\" : \"Diff between EMV and certainty equivalent\",\n",
        "\" risk-neutral\" : \"agent with linear curve\",\n",
        "\"Unbiased\" : \"E(estimate of a - actual) = 0\",\n",
        "\"optimizer’s curse\" : \"This tendency for the estimated expected utility of the best choice to be too high\",\n",
        "\"normative theory\" : \"how a rational agent should act\",\n",
        "\"descriptive theory\" : \"describes how actual agents—for example, humans—really do act\",\n",
        "\"Allais paradox\" : \"Normative anlysis disagree. There is no utility function that is consistent with these choices\",\n",
        "\"certainty effect\" : \"Explain irrational preferences. people are strongly attracted to gains that are certain.\",\n",
        "\"ambiguity aversion\" : \"Most people elect the known probability rather than the unknown unknowns\",\n",
        "\"anchoring effect\" : \"$200 no one will buy, give $55 discount. \",\n",
        "\"framing effect\": \"Wording of problem gives different preference. Like 90% survival > 10% death.\",\n",
        "\"sequential decision problems\": \"the agent’s utility depends on a sequence of decisions\",\n",
        "\"Transition model\": \"describes the outcome of each action in each state.\",\n",
        "\"stochastic\": \"Outcome randomly determined\",\n",
        "\"Markovian\": \"Does not depend on history.\",\n",
        "\"Policy\": \"a solution must specify what the agent should do for any state that the agent might reach\",\n",
        "\"optimal policy\": \"policy that yields the highest expected utility. Pie*\",\n",
        "\"Finite horizon\": \"Fixed time N after which nothing matters, like game over.\",\n",
        "\"Nonstationary policy\": \"Policy that depends on the time\",\n",
        "\"Stationary policy\": \"Optimal action depends only on the current state\",\n",
        "\"Proper policy\": \"Guaranteed to reach terminal state. Can use gamma = 1.\",\n",
        "\"Q-function\": \"E(U) of taking a given action in a given state.\",\n",
        "\"Action-utility function\": \"Q-function\",\n",
        "\"Contraction\": \"MDP value iteration converges.\",\n",
        "\"Contraction function exp\": \"When applied to two different inputs in turn, produces two output values that are “closer together,\",\n",
        "\"Max norm\": \"measures the “length” of a vector by the absolute value of its biggest component\",\n",
        "\"Policy loss\": \"Most the agent can lose by executing piei than pie*\",\n",
        "\"Contraction\": \"MDP value iteration converges.\",\n",
        "\"Contraction\": \"MDP value iteration converges.\",\n",
        "\"Contraction\": \"MDP value iteration converges.\",\n",
        "\"Contraction\": \"MDP value iteration converges.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "37440bd4-6925-4eb6-c07a-240d737dfd24"
      },
      "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": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 17.1 Sequential Decision Problems' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Agent has some available action a. There may be uncertainty about the current state, so we’ll assume that the agent assigns a probability P(s)\n\to each possible current state s.\n- There may also be uncertainty about the action outcomes; the transition model is given by P(s'|s,a)\n- We are interested in outcome s', so probability of reaching s' by doing a in current state is P(Result(a)=s').\n- P(Result(a)=s') = summation of P(s)P(s'|s,a), this requires perception, learning, knowledge representation, and inference.\n- Computing this itself requires a causal model of world. Many actions to consider. computing the outcome utilities \n\\may itself require further searching or planning because an agent may not know how good a state is until it knows where it can get to from that state. \n\n### Decision theory\n- Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.\n- The agent’s preferences are captured by a utility function U(s),which assigns a single number to express the desirability of a state.\n- The expected utility of an action given the evidence, EU(a) is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n- It does provide the beginnings of a basic mathematical framework that is general enough to define the AI problem.\n### MEU\n- The MEU principle could be seen as a prescription for intelligent behavior, AI needs quantities, max U over actions, but AI problem is not solved.\n- The MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice.\n- The MEU principle has a clear relation to the idea of performance measures.\n- If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). \n- This is the central justification for the MEU principle itself. \n- The performance measure gives a score for a history—a sequence of states. Thus it is applied retrospectively after an agent completes a sequence of actions. The utility function applies to the very next state, so it can be used to guide actions step by step.\n\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 \n- MEU is not the only rational way to make decisions. \n- A&B can be states of world. \n\n### Constraints on rational preferences\n- Symbol in pic.\n- Think of the set of outcomes for each action as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1,...,Sn that occur with probabilities p1,...,pn is\n- L=[p1,S1;p2,S2;...;pn,Sn]\n- Each outcome  of a lottery can be either an atomic state or another lottery. \n1. Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding.\n2. TRANSITIVITY: If A prefers B, B prefers C, then A prefers C.\n3. Continuity: If lottery B between A and C in preference some probability p for which RA will be indifferent between getting B for sure and lottery that yields A with p and C with 1-p.\n4. Substitutability:  If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. Holds regardless of p and other outcomes in lotteries. \n5. Monotonicity: Two lotteries have the same two possible outcomes, A&B. If agent prefers A to B,then the agent must prefer the lottery that has a higher probability for A.\n6. Decomposability: Compound lotteries can be reduced to simpler ones using the laws of probability. \n- These constraints are known as the axioms of utility theory. Each axiom can be motivated by showing that an agent that violates it will exhibit patently irrational behavior in some situations. \n\n### Rational preferences lead to utility\n- Notice that the axioms of utility theory are really axioms about preferences—they say nothing about a utility function. \n1. Existence of utility function: If an agent’s preferences obey the axioms of utility, then there exists a function U such that U(A) > U(B) iff A is preferred to B, and U(A) = U(B) iff agent is indifferent between A and B.\n2. Expected utility of a lottery: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n- In other words, once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined. \n- The preceding theorems establish that (assuming the constraints on rational preferences) a utility function exists for any rational agent. The theorems do not establish that the utility function is unique. \n- It is important to remember that the existence of a utility function that describes an agent’s preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations. \n- By observing a rational agent’s behavior, an observer can learn about the utility function that represents what the agent is actually trying to achieve.\n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \n\n## Utility Functions\n- Utility functions map from lotteries to real numbers.\n\n### Utility assessment and utility scales\n- A scale for utility can be established by fixing the utilities of any two particular outcomes, just as we fix a temperature scale by fixing the freezing point and boiling point of water.\n- Normalize utility, best = 1, worst = 0. Ask agent choose standard lottery [p, u1; (1-p),u2]. P is adjusted until agent is indifferent between S and the standard lottery. That will be utility of S.\n- Use micromort and QALY to value life. \n\n### Utility of money\n- Agents exhibits monotonic preference for money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n- Money lottery problem. To determine what to do, we need to assign utilities to the outcome states. Utility is not directly proportional to monetary value, because the utility for your first million is very high (or so they say), whereas the utility for an additional million is smaller. \n- In a pioneering study of actual utility functions, Grayson (1960) found that the utility of money was almost exactly proportional to the logarithm of the amount. \n- If we restrict our attention to the positive part of the curves, where the slope is decreasing, then for any lottery , the utility of being faced with that lottery is less than the utility of being handed the expected monetary value of the lottery as a sure thing.\n- That is, agents with curves of this shape are risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n- On the other hand, in the “desperate” region at large negative wealth in Figure 16.2(b), the behavior is risk-seeking. \n- For gambles with small sums, therefore, we expect risk neutrality.\n\n### Expected utility and post-decision disappointment\n- The rational way to choose the best action, a* , is to maximize expected utility.\n- If everything correct, on average, we will get the utility we expect if the whole process is repeated many times.\n- In reality, however, our model usually oversimplifies the real situation, either because we don’t know enough, or because the computation of the true expected utility is too difficult.\n- We assumed estimates are unbiased. In that case, it still seems reasonable to choose the action with the highest estimated utility and to expect to receive that utility, on average, when the action is executed.\n- Unfortunately, the real outcome will usually be significantly worse.\n- It is a straightforward matter to calculate the distribution of the maximum of the k estimates and hence quantify the extent of our disappointment.\n- When k gets larger, disappointment gets higher in terms of more std deviation.\n\n\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \n\n#### Certainty effect reasons\n1. First, people prefer to reduce computational burden; by choosing certain outcomes, they don’t have to compute with probabilities. But the effect persists even when the computations involved are very easy ones.\n2. Second, people may distrust the legitimacy of the stated probabilities. In the presence of distrust, it might be better to go for the sure thing. Distrust others flip coins.\n3. People may be accounting for their emotional state as well as their financial state. People know they would experience regret.\n- Yet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is framing effect. \n- People feel more comfortable making relative utility judgments rather than absolute ones.\n- If human informants insist on contradictory preference judgments, there is nothing that automated agents can do to be consistent with them. Fortunately, preference judgments made by humans are often open to revision in the light of further consideration.\n\n\n## Sequential Decision Problems\n- MDP more like real world. MDPs have been studied in several fields, including AI, operations research, economics, and control theory.\n#### Agent grids\n- The outcome is stochastic, so write as P(s'|s,a) for p reaching s' if a is done in state s.\n- We will assume that transitions are Markovian: the probability of reaching s' from s depends onl on s and not history of earlier states.\n- To complete the definition of the task environment, we must specify the utility function for the agent. Because the decision problem is sequential, the utility function will depend on a sequence of states and actions—an environment history—rather than on a single state.\n- Every transition from s to s' via a, agent receives reward R(s,a,s'), bounded by +- Rmax.\n- A sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process, or MDP, and consists of a set of states (initial state S0). A set of actions of actions in each state. A transition model P(s'|s,a), and a reward function R(s,a,s').\n- Methods for solving MDPs usually involve dynamic programming.\n\n#### Solution: Policy (pie)\n- No fixed action sequence can solve the problem, because the agent might end up in a state other than the goal.\n- Solution is policy. Therefore, a solution must specify what the agent should do for any state that the agent might reach.\n- Policy is symbol pie. pie(s) is action recommended by policy pie for state s.\n- No matter what the outcome of the action, the resulting state will be in the policy, and the agent will know what to do next.\n- The quality of a policy is therefore measured by the expected utility of the possible environment histories generated by that policy.\n- Represents the agent function explicitly. A description of a simple reflex agent, computed from the information used for a utility-based agent.\n- Often have multiple optimal policies.\n\n#### Utility over time\n- Finite or infinite horizon.\n- With a finite horizon, an optimal action in a given state may depend on how much time is left. So nonstationary policy used.\n- “Infinite horizon” does not necessarily mean that all state sequences are infinite; it just means that there is no fixed deadline.\n- If infinite, potential difficulty is if environment no terminal state/agent never reaches one, all environment histories are infinitely long and utilities with additive undiscounted rewards is finite.\n- Discount factory gamma between 0 and 1. \n- Discount make sense due to preference of early rewards, uncertainty about true rewards. \n- A discount factor of gamma is equivalent to adding a probability  of accidental termination at every time step, independent of the action taken.\n- Agent’s preferences between state sequences are stationary. Means if you prefer a future, preference same no matter when future starts.\n- If gamma < 1, rewards bounded by +- Rmax, utility is finite.\n- If environment contains terminal state and if proper policy, gamma can be 1.\n- Infinite sequences compred in terms of averge reward obtained per time step. But analysis is complex.\n\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n\n#### Optimal policies and the utilities of states\n- Utility of a given history is the sum of discounted rewards\n- Compare policies thru expected utilities obtained when executing them.\n- A remarkable consequence of using discounted utilities with infinite horizons is that the optimal policy is independent of the starting state\n- Action sequence wont be independent. \n- True utility of a state is the expected sum of discounted rewards if the agent executes an optimal policy. Write as U(s).\n- The utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action. \n- Use bellman equation to calculate utilities of state.\n- Optimal policy extracted from Q-function by argmax(Q functions)\n\n\n#### Rewards scales\n- U(s) becomes U'(s)=mU(s) + b, m > 0. Repalce U(s) with reward function. \n- TWO MDPs have same optimal policies if only differ in reward functions.\n- The flexibility afforded by the shaping theorem means that we can actually help out the agent by making the immediate reward more directly reflect what the agent should do.\n\n#### Representing MDPs\n- Big 3 dimensional tables of size |S|^2 |A|. O(|S||A|)\n- Can represent MDPs by extending dynamic Bayesian networks with decision, reward, and utility nodes to create dynamic decision networks.\n- DNN has complexity advantage over atomic representations and can model quite substantial real-world problems.\n\n\n\n## Algorithms for MDPs\n#### Value Iteration\n- Propagating information through the state space by means of local updates\n- The Bellman equation is the basis of the value iteration algorithm for solving MDPs.\n- n possible states means n possible bellman equations, 1 for each state. \n- n equations conatins n unknowns, the state utilities. \n- Equations are non-linear due to max. So cannot solved by linear algebra.\n- We start with arbitrary initial values for the utilities, calculate the right-hand side of the equation, and plug it into the left-hand side—thereby updating the utility of each state from the utilities of its neighbors. We repeat this until we reach an equilibrium.\n- Ui(s) is utility value for state s at ith iteration. It is Bellman Update.\n- The update is assumed to be applied simultaneously to all the states at each iteration.\n- If applied infinitely, guaranteed to reach equilibrium. \n- Contraction. A contraction has only one fixed point; if there were two fixed points they would not get closer together when the function was applied, so it would not be a contraction. When the function is applied to any argument, the value must get closer to the fixed point, so repeated application reaches fixed point in the limit.\n- Measure distances between utility vectors by max norm.\n- Bellman update function beocmes Ui+1 = BUi with Bellman update operator B applied to all states.\n- Can use contraction property to analyze rate of convergence. \n- Terminal condition is |Ui+1 - U| < e\n\n\n \n\n## Module 8 Lecture Notes\n \n\n#### Policy iteration\n- Possible to get an optimal policy even when the utility function estimate is inaccurate.\n- If one action is clearly better than all others, then the exact magnitude of the utilities on the states involved need not be precise.\n- Done by policy evaluation and policy improvement. \n1. Policy evaluation: Given a policy piei, calculate Ui = U piei, the utility of each state if piei were to be executed.\n2. Policy improvement: Calculate a new MEU policy piei+1 using onestep lookahead based on Ui.\n- The algorithm terminates when the policy improvement step yields no change in the utilities.\n- O(n^3)\n-  Instead, we can perform some number of simplified value iteration steps (simplified because the policy is fixed) to give a reasonably good approximation of the utilities.\n- This is modified policy iteration. \n- Asynchronous policy iteration: Pick any subset of states and apply either kind of updating above.\n- The freedom to choose any states to work on means that we can design much more efficient heuristic algorithms\n\n\n#### Linear programming\n- General approach for formulating constrained optimization problems, and there are many industrial-strength LP solvers available.\n- The basic idea of the formulation is to consider as variables in the LP the utilities U(s) of each state s. In LP language, that means we seek to minimize U(s) for all s.\n- This creates a connection from dynamic programming to linear programming, for which algorithms and complexity issues have been studied in great depth.\n- LP solver seldom efficient as dp. \n- Polynomial time sounds  good, but number of states is large. \n\n#### Online algorithms for MDPs\n- Value iteration and policy iteration are offline algorithms. They generate an optimal solution for the problem, which can then be executed by a simple agent.\n- Offline not possible to solve large MDPs. \n- Simplification of the Expectiminimax algorithm for game trees with chance nodes.\n- Expectimax algorithm builds a tree of alternating max and chance nodes. An evaluation function can be applied to the nonterminal leaves of the tree, or they can be given a default value. A decision can be extracted from the search tree by backing up the utility values from the leaves, taking an average at the chance nodes and taking the maximum at the decision nodes.\n- e-horizon useful when discount factor not too close to 1. \n\n\n\n\n## Module 8 Definitions\n* **Transition model** - describes the outcome of each action in each state.\n* **Principle of maximum expected utility (meu)** - a rational agent should choose the action that maximizes the agent’s expected utility\n* **Value function** - in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\n* **Ordinal utility function** - value function\n* **Preference elicitation** - involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n* **Normalized utilities** - see pic. Best u = 1, worst u = 0.\n* ** micromort** - a one in a million chance of death. Value of life.\n* **Qaly** - Quality-adjusted life year. Patients are willing to accept a shorter life expectancy to avoid a disability.\n* **Monotonic preference** - Prefer more to less, with other things equal.\n* **Certainty equivalent ** - Value an agent will accept in lottery of that lottery. Like $400 confirm, not the expected value $500.\n* **Insurance premium** - Diff between EMV and certainty equivalent\n* ** risk-neutral** - agent with linear curve\n* **Unbiased** - E(estimate of a - actual) = 0\n* **Optimizer’s curse** - This tendency for the estimated expected utility of the best choice to be too high\n* **Normative theory** - how a rational agent should act\n* **Descriptive theory** - describes how actual agents—for example, humans—really do act\n* **Allais paradox** - Normative anlysis disagree. There is no utility function that is consistent with these choices\n* **Certainty effect** - Explain irrational preferences. people are strongly attracted to gains that are certain.\n* **Ambiguity aversion** - Most people elect the known probability rather than the unknown unknowns\n* **Anchoring effect** - $200 no one will buy, give $55 discount. \n* **Framing effect** - Wording of problem gives different preference. Like 90% survival > 10% death.\n* **Sequential decision problems** - the agent’s utility depends on a sequence of decisions\n* **Stochastic** - Outcome randomly determined\n* **Markovian** - Does not depend on history.\n* **Policy** - a solution must specify what the agent should do for any state that the agent might reach\n* **Optimal policy** - policy that yields the highest expected utility. Pie*\n* **Finite horizon** - Fixed time N after which nothing matters, like game over.\n* **Nonstationary policy** - Policy that depends on the time\n* **Stationary policy** - Optimal action depends only on the current state\n* **Proper policy** - Guaranteed to reach terminal state. Can use gamma = 1.\n* **Q-function** - E(U) of taking a given action in a given state.\n* **Action-utility function** - Q-function\n* **Contraction** - MDP value iteration converges.\n* **Contraction function exp** - When applied to two different inputs in turn, produces two output values that are “closer together,\n* **Max norm** - measures the “length” of a vector by the absolute value of its biggest component\n* **Policy loss** - Most the agent can lose by executing piei than pie*\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" \n",
        "### Bandit\n",
        "- An n-armed bandit has n levers. Behind each lever is a fixed but unknown probability distribution of winnings; each pull samples from that unknown distribution.\n",
        "- Ubiquitous tradeoff between exploitation of the current best action to obtain rewards and exploration of previously unknown states and actions to gain information.\n",
        "- Many definitions of bandit problem. \n",
        "1. Each arm is Markov reward process, an MDP with only one possible action. \n",
        "2. Overall bandit problem is an MDP.\n",
        "\n",
        "An important generalization of the bandit process is the bandit superprocess or BSP, in which each arm is a full Markov decision process in its own right, rather than being a Markov reward process with only one possible action. All other properties remain the same: the arms are independent, only one (or a bounded number) can be worked on at a time, and there is a single discount factor.\n",
        "\n",
        "### Learning from Rewards\n",
        "- An agent interacts with the world and periodically receives rewards that reflect how well it is doing.\n",
        "- Goal is maximize the expected sum of rewards, same as MDP.\n",
        "- Reinforcement learning differs from “just solving an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. It may not know the transition model or the reward function, and it has to act in order to learn more.\n",
        "- Reward function is concise ad easy to specify.\n",
        "- Can be general for simulated enviornments, as long as correct reward signals given.\n",
        "\n",
        "#### Model based reinforcement learning\n",
        "- The agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. The model may be initially unknown, in which case the agent learns the model from observing the effects of its actions, or it may already be known.\n",
        "- In partially observable environments, the transition model is also useful for state estimation\n",
        "- Model-based reinforcement learning systems often learn a utility function defined in terms of sum of rewards from state s onward.\n",
        "\n",
        "#### Model free reinforcement learning\n",
        "- The agent neither knows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave. This comes in one of two varieties:\n",
        "1. Action-utility learning: Q learning. Denote sum of rewards from s if a is taken. Agent choose action by finding highest Q value.\n",
        "2. Policy search: Agent learns a policy pie(s) that maps directl from states to actions. A reflex agent.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" \n",
        "\n",
        "\n",
        "### Passive reinforcement learning\n",
        "- The agent’s policy is fixed and the task is to learn the utilities of states (or of state–action pairs); this could also involve learning a model of the environment.\n",
        "- Fully observable environment with a small number of actions and states, in which an agent already has a fixed policy pie(s) that determines its actions. \n",
        "- The passive learning task is similar to the policy evaluation task.\n",
        "- The difference is that the passive learning agent does not know the transition model P(s'|s,a) and reward fucntion R(s,a,s').\n",
        "\n",
        "### Begin\n",
        "- The agent executes a set of trials in the environment using its policy pie.\n",
        "- In each trial, the agent starts in state (1,1) and experiences a sequence of state transitions until it reaches one of the terminal states.\n",
        "- Each transition is annotated with both the action taken and the reward received at the next state. The object is to use the information about rewards to learn the expected utility \n",
        " associated with each nonterminal state.\n",
        "- The utility is defined to be the expected sum of (discounted) rewards obtained if policy  is followed.\n",
        "\n",
        "#### Direct utility estimation\n",
        "- Reduce reinforcement learning to a standard supervised learning problem in which each example is a (state, reward-to-go) pair.\n",
        "- It ignores an important constraint: The utility of a state is determined by the reward and the expected utility of the successor states.\n",
        "- By ignoring the connections between states, direct utility estimation misses opportunities for learning.\n",
        "- Direct utility estimation as searching for  in a hypothesis space that is much larger than it needs to be.\n",
        "- Violates Bellman, so converges very slowly.\n",
        "\n",
        "#### Adaptive dynamic programming\n",
        "- Takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming.\n",
        "- For a passive learning agent, this means plugging the learned transition model and the observed rewards to calculate the utilities of the states.\n",
        "- The environment is fully observable, so learning transition model is easy. \n",
        "- Can use modified policy iteration, the model usually changes only slightly with each observation, the value iteration process can use the previous utility estimates as initial values and typically converge very quickly.\n",
        "- The ADP agent is limited only by its ability to learn the transition model. Hard to deal with large state spaces.\n",
        "- Provides standards against which to measure any other reinforcement learning algorithms.\n",
        "\n",
        " \"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "\n",
        "\n",
        "#### Temporal-difference learning\n",
        "- Use the observed transitions to adjust the utilities of the observed states so that they agree with the constraint equations.\n",
        "- Apply temporary update to utility score if too low or high. \n",
        "- Needs learning rate parameter alpha. Decreases as number of times a state has been visited increases, then will converge to correct value. \n",
        "- Because this update rule uses the difference in utilities between successive states (and thus successive times), it is often called the temporal-difference (TD) equation.\n",
        "- All temporal-difference methods work by adjusting the utility estimates toward the ideal equilibrium that holds locally when the utility estimates are correct. \n",
        "- First, notice that the update involves only the observed successor, whereas the actual equilibrium conditions involve all possible next states.\n",
        "- the average value of Upie(s) will converge to the correct quantity in the limit, even if the value itself continues to fluctuate.\n",
        "\n",
        "#### Difference between TD and ADP\n",
        "- Different with ADP. TD adjusts a state to agree with its observed successor, whereas ADP adjusts the state to agree with all of the successors that might occur, weighted by their probabilities.\n",
        "- This difference disappears when the effects of TD adjustments are averaged over a large number of transitions, because the frequency of each successor in the set of transitions is approximately proportional to its probability. A more important difference is that whereas TD makes a single adjustment per observed transition, ADP makes as many as it needs to restore consistency between the utility estimates U and the transition model .\n",
        "- Thus, TD can be viewed as a crude but efficient first approximation to ADP.\n",
        "- Each adjustment made by ADP could be seen, from the TD point of view, as a result of a pseudoexperience generated by simulating the current transition model. It is possible to extend the TD approach to use a transition model to generate several pseudoexperiences—transitions that the TD agent can imagine might happen, given its current model. For each observed transition, the TD agent can generate a large number of imaginary transitions.\n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "\n",
        "#### Generate efficient version of ADP with TD\n",
        "- One possible approach to generating reasonably good answers quickly is to bound the number of adjustments made after each observed transition. One can also use a heuristic to rank the possible adjustments so as to carry out only the most significant ones. \n",
        "- The prioritized sweeping heuristic prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n",
        "- Using heuristics like this, approximate ADP algorithms can learn roughly as fast as full ADP, in terms of the number of training sequences, but can be orders of magnitude more efficient in terms of total computation.\n",
        "- An approximation algorithm can use a minimum adjustment size that decreases as the transition model becomes more accurate. This eliminates the very long runs of value iteration that can occur early in learning due to large changes in the model.\n",
        "\n",
        "\n",
        "### Active Reinforcement Learning\n",
        "- An active learning agent gets to decide what actions to take.\n",
        "- Begin with ADP.\n",
        "- First, the agent will need to learn a complete transition model with outcome probabilities for all actions, rather than just the model for the fixed policy. The learning mechanism used by Passive-ADP-Agent will do just fine for this. \n",
        "- Next, we need to take into account the fact that the agent has a choice of actions. The utilities it needs to learn are those defined by the optimal policy; they obey the Bellman equations\n",
        "- These equations can be solved to obtain the utility function  using the value iteration or policy iteration algorithm.\n",
        "- Having obtained a utility function  that is optimal for the learned model, the agent can extract an optimal action by one-step look-ahead to maximize the expected utility.\n",
        "\n",
        "### GLIE\n",
        "- One simple way is to have the agent choose a random action at time step t with probability 1/t and to follow the greedy policy otherwise.\n",
        "- While this does eventually converge to an optimal policy, it can be slow.\n",
        "- A better approach would give some weight to actions that the agent has not tried very often, while tending to avoid actions that are believed to be of low utility.\n",
        "- This can be implemented by altering the constraint equation so that it assigns a higher utility estimate to relatively unexplored state–action pairs.\n",
        "- Has exploration function f. It determines how greed (preference for high values of utility u) is traded off against curiosity (preference for actions that have not been tried often and have a low count n).\n",
        "- f increases in u and decreases in n. \n",
        "- The fact that U+ rather than U appears on the right-hand side of Equation is very important. As exploration proceeds, the states and actions near the start state might well be tried a large number of times. \n",
        "\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "\n",
        "#### Approaches for safe exploration\n",
        "1. Bayesian reinforcement learning\n",
        "- assumes a prior probability P(h) over hypotheses h about what the true model is.\n",
        "- The posterior probability P(h|e) is obtained in the usual way by Bayes’ rule given the observations to date. \n",
        "- Then, if the agent has decided to stop learning, the optimal policy is the one that gives the highest expected utility.\n",
        "- Let Upieh be the expected utility, averaged over all possible start states, obtained by executing policy pie in model h.\n",
        "- When continue to learn in future, finding optimal policy is harder, because agent must consider effects of future observations on its beliefs about the transition model.\n",
        "- Problem becomes exploration POMDP. Should solve this before entering real world to get a complete strategy that tells the agent what to do next given any possible percept sequence.\n",
        "- Unable to prevent untimely death. \n",
        "2. Robust control theory\n",
        "- Allows for a set of possible models H without assigning probabilities to them, and defines an optimal robust policy as one that gives the best outcome in the worst case over H.\n",
        "- The robust control approach can be considered as a game between the agent and an adversary, where the adversary gets to pick the worst possible result for any action, and the policy we get is the minimax solution for the game.\n",
        "- Related to Bayesian approach, because set H will be the set of models that exceed some likelihood threshold on P(h|e).\n",
        "- The problem with the worst-case assumption is that it results in overly conservative behavior.\n",
        "- First way to improve is record series of actions by an experienced teacher, so that the system will act reasonably from the start, and can learn to improve from there.\n",
        "- A second way is for a human to write down constraints on what a system can do, and have a program outside of the reinforcement learning system enforce those constraints.\n",
        "\n",
        "\n",
        "### Temporal-difference Q-learning\n",
        "- The most obvious change is that the agent will have to learn a transition model so that it can choose an action based on U(s) via one-step look-ahead.\n",
        "- TD Q-learning agent does not need a transition model either for learning or for action selection.\n",
        "- Avoids the need for a model by learning an action-utility function Q(s,a) instead of a utility function U(s)\n",
        "- Knowing the Q-function enables the agent to act optimally simply by choosing argmaxa Q(s,a), with no need for look-ahead based on a transition model.\n",
        "- Model-free methods can be applied even in very complex domains because no model need be provided or learned.\n",
        "- No means to look into future, so it may have difficulty when rewards are sparse and long action sequences must be constructed to reach them.\n",
        "- Off-policy learning algorithm.\n",
        "- Answer the question “What would this action be worth in this state, assuming that I stop using whatever policy I am using now, and start acting according to a policy that chooses the best action (according to my estimates)?”\n",
        "\n",
        "\n",
        "### SARSA, similar to Q-learning\n",
        "- On-policy algo.\n",
        "- Answer the question “What would this action be worth in this state, assuming I stick with my policy?”\n",
        "- SARSA updates with the Q-value of the action a' that is actually taken.\n",
        "- State, action, reward, state, action.\n",
        "- SARSA is appropriate if the overall policy is even partly controlled by other agents or programs, in which case it is better to learn a Q-function for what will actually happen rather than what would happen if the agent got to pick estimated best actions. \n",
        "\n",
        "\n",
        "### Generalization in Reinforcement Learning\n",
        "- Backgammon is simpler than most real-world applications, yet it has about 10^20 states.\n",
        "- Reinforcement learnin algo learn like 20 vales that is a good approximation to the true utility function.\n",
        "- Sometimes this approximate utility function is combined with look-ahead search to produce more accurate decisions.\n",
        "- Adding look-ahead search means that effective behavior can be generated from a much simpler utility function approximator that is learnable from far fewer experiences.\n",
        "- Function approximation makes it practical to represent utility (or Q) functions for very large state spaces, but more importantly, it allows for inductive generalization: the agent can generalize from states it has visited to states it has not yet visited.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" \n",
        "### Approximating direct utility estimation\n",
        "- The method of direct utility estimation (Section 22.2) generates trajectories in the state space and extracts, for each state, the sum of rewards received from that state onward until termination.\n",
        "- The state and the sum of rewards received constitute a training example for a supervised learning algorithm.\n",
        "- Use standard linear regression to find best fit. \n",
        "- Online learning algorithm for reinforcement learning, updates paramaters after each trial.\n",
        "- The agent will learn faster if it uses a function approximator, provided that the hypothesis space is not too large and includes some functions that are a reasonably good fit to the true utility function.\n",
        "- We can choose the features to be arbitrary nonlinear functions of the state variables.\n",
        "\n",
        "\n",
        "\n",
        "### Approximating temporal-difference learning\n",
        "- Adjust the parameters to try to reduce the temporal difference between successive states.\n",
        "- When diverging to infinity, catastrophic forgetting occurs. \n",
        "- Solved by experience replay. \n",
        "- Experience replay: ensures that the car keeps reliving its youthful crashing behavior at regular intervals.\n",
        "- The learning algorithm can retain trajectories from the entire learning process and replay those trajectories to ensure that its value function is still accurate for parts of the state space it no longer visits.\n",
        "- For a partially observable environment, the learning problem is much more difficult because the next percept is no longer a label for the state prediction problem.\n",
        "\n",
        "\n",
        "### Deep reinforcement learning\n",
        "-  A reinforcement learning system that uses a deep network as a function approximator is called a deep reinforcement learning system.\n",
        "- Two reasons go to beyon linear function approximators:\n",
        "1. There may be no good linear function that comes close to approximating the utility function or the Q-function\n",
        "2. We may not be able to invent the necessary features, particularly in new domains.\n",
        "- The parameters are all the weights in all the layers of the network.\n",
        "- It is often difficult to get good performance and the trained system may behave very unpredictably if the environment differs even a little from the training data. \n",
        "\n",
        "### Reward shaping\n",
        "- Credit assignment problem. \n",
        "- This involves supplying the agent with additional rewards, called pseudorewards, for “making progress.”\n",
        "- Such rewards can speed up learning enormously and are simple to provide, but there is a risk that the agent will learn to maximize the pseudorewards rather than the true rewards.\n",
        "- Add potential functions to reward functions. \n",
        "- The potential fuction  can be constructed to reflect any desirable aspects of the state, such as achievement of subgoals or distance to a desired terminal state.\n",
        "\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "\n",
        "### Hierarchical reinforcement learning\n",
        "- Cope with very long action sequences. Break them up into a few smaller pieces, and then break those into smaller pieces still, and so on until the action sequences are short enough to make learning easy.\n",
        "- Begins with a partial program that outlines a hierarchical structure for the agent’s behavior.\n",
        "- The partial-programming language for agent programs extends any ordinary programming language by adding primitives for unspecified choices that must be filled in by learning.\n",
        "- The partial program can be arbitrarily complicated, as long as it terminates.\n",
        "- We simply provide the trivial partial program that allows the agent to keep choosing any action from A(s), the set of actions that can be executed in the current state s.\n",
        "- The learning process converts the partial agent program into a complete program by learning how each choice should be made.\n",
        "- Each of these choices invokes a subroutine that may itself make further choices, all the way down to primitive actions that can be executed directly. \n",
        "- The theoretical foundations of HRL are based on the concept of the joint state space, in which each state  is composed of a physical state  and a machine state .\n",
        "- The machine state is defined by the current internal state of the agent program: the program counter for each subroutine on the current call stack, the values of the arguments, and the values of all local and global variables.\n",
        "- Effective method for learning complex behaviors.\n",
        "\n",
        "\n",
        "### Policy search\n",
        "- The simplest of all the methods.\n",
        "- The idea is to keep twiddling the policy as long as its performance improves, then stop.\n",
        "- Policy pie is function that maps states to actions, we are interested primarily in parameterized representations of pie that have far fewer parameters than there are states in the state space.\n",
        "- We could represent pie by a collection of parameterized Q-functions, one for each action, and take the action with the highest predicted value\n",
        "- Each Q-function could be a linear function. Or a nonlinear function such as a deep neural network\n",
        "- Policy search will then adjust the parameters  to improve the policy.\n",
        "- But process not same as Q-learning. \n",
        "- It finds value of feature that results in good performance and not the optimal Q-function in Q-learning. Values found can be very different.\n",
        "- Problem: The policy is a discontinuous function of the parameters when the actions are discrete.\n",
        "- There will be values of  such that an infinitesimal change in feature causes the policy to switch from one action to another.\n",
        "- This means that the value of the policy may also change discontinuously, which makes gradient-based search difficult. For this reason, policy search methods often use a stochastic policy representation.\n",
        "- Can use softmax function. Normalize. \n",
        "- When the environment (or the policy) is nondeterministic, things get more difficult.\n",
        "\n",
        "### Unreliable result from undeterministic policy\n",
        "- The problem is that the total reward for each trial may vary widely, so estimates of the policy value from a small number of trials will be quite unreliable; trying to compare two such estimates will be even more unreliable.\n",
        "- One solution is simply to run lots of trials, measuring the sample variance and using it to determine that enough trials have been run to get a reliable indication of the direction of improvement.\n",
        "- Unfortunately, this is impractical for many real problems in which trials may be expensive, time-consuming, and perhaps even dangerous.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Stopping time\" : \"Pull first arm T times, T is stopping time. \",\n",
        "\"Gittins index\" : \"Reward achieved through a stochasitic process. \",\n",
        "\"Direct utility estimation\" : \"utility of state is expected total reward from that state onward and each trial provides a sample of this quantity for state visited.\",\n",
        "\"Temporal-difference equation\" : \"Temporal-difference learning's equation.\",\n",
        "\"Prioritized sweeping\" : \"Generate efficient version of ADP with TD section.\",\n",
        "\"greedy agent\" : \"takes the action that it currently believes to be optimal at each step.\",\n",
        "\"Absorbing state\" : \"No actions have any effect and no rewards are received\",\n",
        "\"exploration POMDP\" : \"belief states are distributions over models\",\n",
        "\"function approximation\" : \"process of constructing a compact approximation of the true utility function or Q-function\",\n",
        "\"catastrophic forgetting\" : \"see 22_4 ATDL\",\n",
        "}"
      ],
      "execution_count": 60,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f4c27760-0a57-445e-88a7-b393e448d7ac"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 61,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 22.4 Generalization in Reinforcement Learning' is too long!\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \n### Bandit\n- An n-armed bandit has n levers. Behind each lever is a fixed but unknown probability distribution of winnings; each pull samples from that unknown distribution.\n- Ubiquitous tradeoff between exploitation of the current best action to obtain rewards and exploration of previously unknown states and actions to gain information.\n- Many definitions of bandit problem. \n1. Each arm is Markov reward process, an MDP with only one possible action. \n2. Overall bandit problem is an MDP.\n\nAn important generalization of the bandit process is the bandit superprocess or BSP, in which each arm is a full Markov decision process in its own right, rather than being a Markov reward process with only one possible action. All other properties remain the same: the arms are independent, only one (or a bounded number) can be worked on at a time, and there is a single discount factor.\n\n### Learning from Rewards\n- An agent interacts with the world and periodically receives rewards that reflect how well it is doing.\n- Goal is maximize the expected sum of rewards, same as MDP.\n- Reinforcement learning differs from “just solving an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. It may not know the transition model or the reward function, and it has to act in order to learn more.\n- Reward function is concise ad easy to specify.\n- Can be general for simulated enviornments, as long as correct reward signals given.\n\n#### Model based reinforcement learning\n- The agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. The model may be initially unknown, in which case the agent learns the model from observing the effects of its actions, or it may already be known.\n- In partially observable environments, the transition model is also useful for state estimation\n- Model-based reinforcement learning systems often learn a utility function defined in terms of sum of rewards from state s onward.\n\n#### Model free reinforcement learning\n- The agent neither knows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave. This comes in one of two varieties:\n1. Action-utility learning: Q learning. Denote sum of rewards from s if a is taken. Agent choose action by finding highest Q value.\n2. Policy search: Agent learns a policy pie(s) that maps directl from states to actions. A reflex agent.\n\n\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n \n\n\n### Passive reinforcement learning\n- The agent’s policy is fixed and the task is to learn the utilities of states (or of state–action pairs); this could also involve learning a model of the environment.\n- Fully observable environment with a small number of actions and states, in which an agent already has a fixed policy pie(s) that determines its actions. \n- The passive learning task is similar to the policy evaluation task.\n- The difference is that the passive learning agent does not know the transition model P(s'|s,a) and reward fucntion R(s,a,s').\n\n### Begin\n- The agent executes a set of trials in the environment using its policy pie.\n- In each trial, the agent starts in state (1,1) and experiences a sequence of state transitions until it reaches one of the terminal states.\n- Each transition is annotated with both the action taken and the reward received at the next state. The object is to use the information about rewards to learn the expected utility \n associated with each nonterminal state.\n- The utility is defined to be the expected sum of (discounted) rewards obtained if policy  is followed.\n\n#### Direct utility estimation\n- Reduce reinforcement learning to a standard supervised learning problem in which each example is a (state, reward-to-go) pair.\n- It ignores an important constraint: The utility of a state is determined by the reward and the expected utility of the successor states.\n- By ignoring the connections between states, direct utility estimation misses opportunities for learning.\n- Direct utility estimation as searching for  in a hypothesis space that is much larger than it needs to be.\n- Violates Bellman, so converges very slowly.\n\n#### Adaptive dynamic programming\n- Takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming.\n- For a passive learning agent, this means plugging the learned transition model and the observed rewards to calculate the utilities of the states.\n- The environment is fully observable, so learning transition model is easy. \n- Can use modified policy iteration, the model usually changes only slightly with each observation, the value iteration process can use the previous utility estimates as initial values and typically converge very quickly.\n- The ADP agent is limited only by its ability to learn the transition model. Hard to deal with large state spaces.\n- Provides standards against which to measure any other reinforcement learning algorithms.\n\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n\n\n#### Temporal-difference learning\n- Use the observed transitions to adjust the utilities of the observed states so that they agree with the constraint equations.\n- Apply temporary update to utility score if too low or high. \n- Needs learning rate parameter alpha. Decreases as number of times a state has been visited increases, then will converge to correct value. \n- Because this update rule uses the difference in utilities between successive states (and thus successive times), it is often called the temporal-difference (TD) equation.\n- All temporal-difference methods work by adjusting the utility estimates toward the ideal equilibrium that holds locally when the utility estimates are correct. \n- First, notice that the update involves only the observed successor, whereas the actual equilibrium conditions involve all possible next states.\n- the average value of Upie(s) will converge to the correct quantity in the limit, even if the value itself continues to fluctuate.\n\n#### Difference between TD and ADP\n- Different with ADP. TD adjusts a state to agree with its observed successor, whereas ADP adjusts the state to agree with all of the successors that might occur, weighted by their probabilities.\n- This difference disappears when the effects of TD adjustments are averaged over a large number of transitions, because the frequency of each successor in the set of transitions is approximately proportional to its probability. A more important difference is that whereas TD makes a single adjustment per observed transition, ADP makes as many as it needs to restore consistency between the utility estimates U and the transition model .\n- Thus, TD can be viewed as a crude but efficient first approximation to ADP.\n- Each adjustment made by ADP could be seen, from the TD point of view, as a result of a pseudoexperience generated by simulating the current transition model. It is possible to extend the TD approach to use a transition model to generate several pseudoexperiences—transitions that the TD agent can imagine might happen, given its current model. For each observed transition, the TD agent can generate a large number of imaginary transitions.\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \n\n#### Generate efficient version of ADP with TD\n- One possible approach to generating reasonably good answers quickly is to bound the number of adjustments made after each observed transition. One can also use a heuristic to rank the possible adjustments so as to carry out only the most significant ones. \n- The prioritized sweeping heuristic prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n- Using heuristics like this, approximate ADP algorithms can learn roughly as fast as full ADP, in terms of the number of training sequences, but can be orders of magnitude more efficient in terms of total computation.\n- An approximation algorithm can use a minimum adjustment size that decreases as the transition model becomes more accurate. This eliminates the very long runs of value iteration that can occur early in learning due to large changes in the model.\n\n\n### Active Reinforcement Learning\n- An active learning agent gets to decide what actions to take.\n- Begin with ADP.\n- First, the agent will need to learn a complete transition model with outcome probabilities for all actions, rather than just the model for the fixed policy. The learning mechanism used by Passive-ADP-Agent will do just fine for this. \n- Next, we need to take into account the fact that the agent has a choice of actions. The utilities it needs to learn are those defined by the optimal policy; they obey the Bellman equations\n- These equations can be solved to obtain the utility function  using the value iteration or policy iteration algorithm.\n- Having obtained a utility function  that is optimal for the learned model, the agent can extract an optimal action by one-step look-ahead to maximize the expected utility.\n\n### GLIE\n- One simple way is to have the agent choose a random action at time step t with probability 1/t and to follow the greedy policy otherwise.\n- While this does eventually converge to an optimal policy, it can be slow.\n- A better approach would give some weight to actions that the agent has not tried very often, while tending to avoid actions that are believed to be of low utility.\n- This can be implemented by altering the constraint equation so that it assigns a higher utility estimate to relatively unexplored state–action pairs.\n- Has exploration function f. It determines how greed (preference for high values of utility u) is traded off against curiosity (preference for actions that have not been tried often and have a low count n).\n- f increases in u and decreases in n. \n- The fact that U+ rather than U appears on the right-hand side of Equation is very important. As exploration proceeds, the states and actions near the start state might well be tried a large number of times. \n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n\n#### Approaches for safe exploration\n1. Bayesian reinforcement learning\n- assumes a prior probability P(h) over hypotheses h about what the true model is.\n- The posterior probability P(h|e) is obtained in the usual way by Bayes’ rule given the observations to date. \n- Then, if the agent has decided to stop learning, the optimal policy is the one that gives the highest expected utility.\n- Let Upieh be the expected utility, averaged over all possible start states, obtained by executing policy pie in model h.\n- When continue to learn in future, finding optimal policy is harder, because agent must consider effects of future observations on its beliefs about the transition model.\n- Problem becomes exploration POMDP. Should solve this before entering real world to get a complete strategy that tells the agent what to do next given any possible percept sequence.\n- Unable to prevent untimely death. \n2. Robust control theory\n- Allows for a set of possible models H without assigning probabilities to them, and defines an optimal robust policy as one that gives the best outcome in the worst case over H.\n- The robust control approach can be considered as a game between the agent and an adversary, where the adversary gets to pick the worst possible result for any action, and the policy we get is the minimax solution for the game.\n- Related to Bayesian approach, because set H will be the set of models that exceed some likelihood threshold on P(h|e).\n- The problem with the worst-case assumption is that it results in overly conservative behavior.\n- First way to improve is record series of actions by an experienced teacher, so that the system will act reasonably from the start, and can learn to improve from there.\n- A second way is for a human to write down constraints on what a system can do, and have a program outside of the reinforcement learning system enforce those constraints.\n\n\n### Temporal-difference Q-learning\n- The most obvious change is that the agent will have to learn a transition model so that it can choose an action based on U(s) via one-step look-ahead.\n- TD Q-learning agent does not need a transition model either for learning or for action selection.\n- Avoids the need for a model by learning an action-utility function Q(s,a) instead of a utility function U(s)\n- Knowing the Q-function enables the agent to act optimally simply by choosing argmaxa Q(s,a), with no need for look-ahead based on a transition model.\n- Model-free methods can be applied even in very complex domains because no model need be provided or learned.\n- No means to look into future, so it may have difficulty when rewards are sparse and long action sequences must be constructed to reach them.\n- Off-policy learning algorithm.\n- Answer the question “What would this action be worth in this state, assuming that I stop using whatever policy I am using now, and start acting according to a policy that chooses the best action (according to my estimates)?”\n\n\n### SARSA, similar to Q-learning\n- On-policy algo.\n- Answer the question “What would this action be worth in this state, assuming I stick with my policy?”\n- SARSA updates with the Q-value of the action a' that is actually taken.\n- State, action, reward, state, action.\n- SARSA is appropriate if the overall policy is even partly controlled by other agents or programs, in which case it is better to learn a Q-function for what will actually happen rather than what would happen if the agent got to pick estimated best actions. \n\n\n### Generalization in Reinforcement Learning\n- Backgammon is simpler than most real-world applications, yet it has about 10^20 states.\n- Reinforcement learnin algo learn like 20 vales that is a good approximation to the true utility function.\n- Sometimes this approximate utility function is combined with look-ahead search to produce more accurate decisions.\n- Adding look-ahead search means that effective behavior can be generated from a much simpler utility function approximator that is learnable from far fewer experiences.\n- Function approximation makes it practical to represent utility (or Q) functions for very large state spaces, but more importantly, it allows for inductive generalization: the agent can generalize from states it has visited to states it has not yet visited.\n\n\n\n\n## Module 9 Lecture Notes\n \n\n### Hierarchical reinforcement learning\n- Cope with very long action sequences. Break them up into a few smaller pieces, and then break those into smaller pieces still, and so on until the action sequences are short enough to make learning easy.\n- Begins with a partial program that outlines a hierarchical structure for the agent’s behavior.\n- The partial-programming language for agent programs extends any ordinary programming language by adding primitives for unspecified choices that must be filled in by learning.\n- The partial program can be arbitrarily complicated, as long as it terminates.\n- We simply provide the trivial partial program that allows the agent to keep choosing any action from A(s), the set of actions that can be executed in the current state s.\n- The learning process converts the partial agent program into a complete program by learning how each choice should be made.\n- Each of these choices invokes a subroutine that may itself make further choices, all the way down to primitive actions that can be executed directly. \n- The theoretical foundations of HRL are based on the concept of the joint state space, in which each state  is composed of a physical state  and a machine state .\n- The machine state is defined by the current internal state of the agent program: the program counter for each subroutine on the current call stack, the values of the arguments, and the values of all local and global variables.\n- Effective method for learning complex behaviors.\n\n\n### Policy search\n- The simplest of all the methods.\n- The idea is to keep twiddling the policy as long as its performance improves, then stop.\n- Policy pie is function that maps states to actions, we are interested primarily in parameterized representations of pie that have far fewer parameters than there are states in the state space.\n- We could represent pie by a collection of parameterized Q-functions, one for each action, and take the action with the highest predicted value\n- Each Q-function could be a linear function. Or a nonlinear function such as a deep neural network\n- Policy search will then adjust the parameters  to improve the policy.\n- But process not same as Q-learning. \n- It finds value of feature that results in good performance and not the optimal Q-function in Q-learning. Values found can be very different.\n- Problem: The policy is a discontinuous function of the parameters when the actions are discrete.\n- There will be values of  such that an infinitesimal change in feature causes the policy to switch from one action to another.\n- This means that the value of the policy may also change discontinuously, which makes gradient-based search difficult. For this reason, policy search methods often use a stochastic policy representation.\n- Can use softmax function. Normalize. \n- When the environment (or the policy) is nondeterministic, things get more difficult.\n\n### Unreliable result from undeterministic policy\n- The problem is that the total reward for each trial may vary widely, so estimates of the policy value from a small number of trials will be quite unreliable; trying to compare two such estimates will be even more unreliable.\n- One solution is simply to run lots of trials, measuring the sample variance and using it to determine that enough trials have been run to get a reliable indication of the direction of improvement.\n- Unfortunately, this is impractical for many real problems in which trials may be expensive, time-consuming, and perhaps even dangerous.\n\n \n\n## Module 9 Definitions\n* **Stopping time** - Pull first arm T times, T is stopping time. \n* **Gittins index** - Reward achieved through a stochasitic process. \n* **Direct utility estimation** - utility of state is expected total reward from that state onward and each trial provides a sample of this quantity for state visited.\n* **Temporal-difference equation** - Temporal-difference learning's equation.\n* **Prioritized sweeping** - Generate efficient version of ADP with TD section.\n* **Greedy agent** - takes the action that it currently believes to be optimal at each step.\n* **Absorbing state** - No actions have any effect and no rewards are received\n* **Exploration pomdp** - belief states are distributions over models\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n* **Catastrophic forgetting** - see 22_4 ATDL\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \n",
        "### Acting under Uncertainty\n",
        "- Logical agents keep track of a belief state, and generating a contingency plan that handles every possible eventuality that its sensors may report during execution.\n",
        "- This works on simple problem, but has drawbacks:\n",
        "1. The agent must consider every possible explanation for its sensor observations, no matter how unlikely. This leads to a large belief-state full of unlikely possibilities\n",
        "2. A correct contingent plan that handles every eventuality can grow arbitrarily large and must consider arbitrarily unlikely contingencies.\n",
        "3. Sometimes there is no plan that is guaranteed to achieve the goal—yet the agent must act. It must have some way to compare the merits of plans that are not guaranteed.\n",
        "- Agent's knowledge cannot guarantee any of these outcomes to achieve, but can provide some degree of belief that they will be achieved.\n",
        "- A rational right decision: depends on both the relative importance of various goals and the likelihood that, and degree to which, they will be achieved.\n",
        "\n",
        "### Rule making\n",
        "- Make rules logically exhaustive. \n",
        "- Agent’s knowledge can at best provide only a degree of belief in the relevant sentences.\n",
        "- Logic to cope with domains like medical diagnosis fails due to:\n",
        "1. Laziness: It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n",
        "2. Theorectical ignorance: Medical science has no complete theory for the domain.\n",
        "3. Practical ignorance: Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n",
        "- Main dealing with degree of belief is probability theory.\n",
        "- A logical agent believes each sentence to be true or false or has no opinion, whereas a probabilistic agent may have a numerical degree of belief between 0 (for sentences that are certainly false) and 1 (certainly true).\n",
        "- So epistemological commitments are different. \n",
        "\n",
        "### Uncertainty and rational decisions\n",
        "- To make such choices, an agent must first have preferences among the different possible outcomes of the various plans.\n",
        "- We use utility theory to represent preferences and reason quantitatively with them.\n",
        "- The utility of a state is relative to an agent.\n",
        "- The fundamental idea of decision theory is that an 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",
        "- The above line is principle of maximum expected utility MEU. \n",
        "- Belief state includes possibilties and probabilities for world state. \n",
        "### \n",
        "\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\" \n",
        "### Basic probability Notation\n",
        "- The possible worlds are mutually exclusive and exhaustive.\n",
        "- Probabilities like P(Total = 11) are unconditional or prior probabilities.\n",
        "- Usually interested in conditional or posterior probability, situation with evidence. Rolling double given first dice is 5.\n",
        "- When making decisions, an agent needs to condition on all the evidence it has observed.\n",
        "- It is also important to understand the difference between conditioning and logical implication.\n",
        "- P(Cavity|toothache) = 0.6 means whenevr toothache is true and no other info, cavity is 60%.\n",
        "\n",
        "### The language of propositions in probability assertions\n",
        "- Range of Total for two dice is set {2,...,12}\n",
        "- Probability density functions (sometimes called pdfs) differ in meaning from discrete distributions.\n",
        "- PDFs uniform between 18C to 26C means 100% within this 8C and 50% 4C-wide region.\n",
        "- Comma used for distribution for multiple variables. Like P(Weather, Cavity), probability or weather AND cavity.\n",
        "\n",
        "### Probability axioms and their reasonableness\n",
        "- The basic axioms of probability imply certain relationships among the degrees of belief that can be accorded to logically related propositions.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "chapter12_3 = \"\"\" \n",
        "### Inference Using Full Joint Distributions\n",
        "- For probabilistic inference, we use full joint distribution as the knowledge base from which answers to all questions may be derived.\n",
        "- Unconfitional/Marginal probability is P(A)\n",
        "\n",
        "### full joint distribution\n",
        "- Does not scale well. \n",
        "- O(2^n)\n",
        "- Each of the probability has to be estimated separately, astronomical number.\n",
        "- Seldom a practical tool for building reasoning systems. \n",
        "- Should be viewed as the theoretical foundation on which more effective approaches may be built.\n",
        "\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        "### Independence\n",
        "- Independence assertions can help in reducing the size of the domain representation and the complexity of the inference problem.\n",
        "- Unfortunately, clean separation of entire sets of variables by independence is quite rare. \n",
        "\"\"\"\n",
        "chapter12_5 = \"\"\" \n",
        "### Bayes’ Rule and Its Use\n",
        "- Bayes' rule underlies most modern AI systems for probabilistic inference.\n",
        "- Diagnostic knowledge is often more fragile than causal knowledge.\n",
        "- O(2^n) possible combinations.\n",
        "- In general, for n symptoms that are all conditionally independent given Cavity, the size of the representation grows as O(n) instead of O(2^n).\n",
        "- That means that conditional independence assertions can allow probabilistic systems to scale up; moreover, they are much more commonly available than absolute independence assertions.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "### Naive Bayes Models\n",
        "- Often used (as a simplifying assumption) in cases where the “effect” variables are not strictly independent given the cause variable.\n",
        "- The naive Bayes model is sometimes called a Bayesian classifier, a somewhat careless usage that has prompted true Bayesians to call it the idiot Bayes model.\n",
        "- In practice, naive Bayes systems often work very well, even when the conditional independence assumption is not strictly true.\n",
        "- Naive Bayes models are widely used for language determination, document retrieval, spam filtering, and other classification tasks.\n",
        "- Not for medical diagnosis, where the actual values of the posterior probabilities really matter.\n",
        "\n",
        "### Naive equation steps (See pic)\n",
        "-  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. The run time of this calculation is linear in the number of observed effects and does not depend on the number of unobserved effects (which may be very large in domains such as medicine). We will see in the next chapter that this is a common phenomenon in probabilistic inference: evidence variables whose values are unobserved usually “disappear” from the computation altogether\n",
        "\n",
        "### Text classification with naive Bayes\n",
        "- given a text, decide which of a predefined set of classes or categories it belongs to.\n",
        "- The task is to classify each sentence into a Category. The major sections of newspaper.\n",
        "- naive Bayes consist of prior prbabilities P(Category) and conditional probabilities P(HasWordi|Category).\n",
        "- To categorize a new document, we check which key words appear in the document and then apply Equation to obtain the posterior probability distribution over categories.\n",
        "-  If we have to predict just one category, we take the one with the highest posterior probability\n",
        "- The naive Bayes model assumes that words occur independently in documents, with frequencies determined by the document category.\n",
        "- This independence assumption is clearly violated in practice.\n",
        "- The violation of independence usually means that the final posterior probabilities will be much closer to 1 or 0 than they should be; in other words, the model is overconfident in its predictions.\n",
        "- On the other hand, even with these errors, the ranking of the possible categories is often quite accurate.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "### Unigram model\n",
        "- Simplest case\n",
        "\n",
        "### Bigram model\n",
        "- Condition on the previous word\n",
        "\n",
        "### N-gram model\n",
        "- In general, insufficient model of language\n",
        "- Because language has long-distance dependencies\n",
        "- But can often get away with N-gram model\n",
        "\n",
        "### Problems for MLE\n",
        "- Test VS Train set not same. Train does not contain set. So assign 0.\n",
        "- Out of vocabulary items (OOV).\n",
        "- Fixed lexicon L of size V\n",
        "- Avoid zeroes with smoothing.\n",
        "\n",
        "### Practical issues\n",
        "- We do everything in log space to avoid underflow. Adding is also faster than multiplying. \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"belief state\" : \"a representation of the set of all possible world states that it might be in\",\n",
        "\"Laziness\" : \"Too much work required to do exhaustive search, or too hard, so cant do it. \",\n",
        "\"epistemological commitments\" : \"See 12_1 rule making.\",\n",
        "\"Theory of probability\" : \"Provides a way of summarizing the uncertainty that comes from our laziness and ignorance, and solves qualification problem.\",\n",
        "\"Utility theory\" : \"every state has a degree of usefulness/utility, to an agent and that the agent will prefer states with higher utility\",\n",
        "\"Decision theory\" : \"probability theory + utility theory\",\n",
        "\"probability model\" : \"Associates a numerical probability  with each possible world\",\n",
        "\"unconditional or prior probabilities\" : \"Refer to degrees of belief in propositions in the absence of any other information.\",\n",
        "\"Evidence\" : \"Some information that has already been revealed. Like first dice already showing 5.\",\n",
        "\"random variables\" : \"Names begin with an uppercase letter.function that maps from the domain of possible worlds  to some range\",\n",
        "\"probability density function\" : \"define the probability that a random variable takes on some value x as a paramaterized function of x\",\n",
        "\"probabilistic inference\" : \"the computation of posterior probabilities for query propositions given observed evidence\",\n",
        "\" Unconfitional/Marginal probability\" : \"P(A) alone.\",\n",
        "\"marginalization\" : \"Sum up probabilities for each possible value of the other variables, thereby taking them out of the equation.\",\n",
        "\"text classification\" : \"given a text, decide which of a predefined set of classes or categories it belongs to.\",\n",
        "\"posterior probability erm\" : \"conditional probability given the relevant evidence or background\",\n",
        "}"
      ],
      "execution_count": 62,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "78c9d892-71df-4d2b-dd6d-24552b1d4d5a"
      },
      "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": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n### Acting under Uncertainty\n- Logical agents keep track of a belief state, and generating a contingency plan that handles every possible eventuality that its sensors may report during execution.\n- This works on simple problem, but has drawbacks:\n1. The agent must consider every possible explanation for its sensor observations, no matter how unlikely. This leads to a large belief-state full of unlikely possibilities\n2. A correct contingent plan that handles every eventuality can grow arbitrarily large and must consider arbitrarily unlikely contingencies.\n3. Sometimes there is no plan that is guaranteed to achieve the goal—yet the agent must act. It must have some way to compare the merits of plans that are not guaranteed.\n- Agent's knowledge cannot guarantee any of these outcomes to achieve, but can provide some degree of belief that they will be achieved.\n- A rational right decision: depends on both the relative importance of various goals and the likelihood that, and degree to which, they will be achieved.\n\n### Rule making\n- Make rules logically exhaustive. \n- Agent’s knowledge can at best provide only a degree of belief in the relevant sentences.\n- Logic to cope with domains like medical diagnosis fails due to:\n1. Laziness: It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n2. Theorectical ignorance: Medical science has no complete theory for the domain.\n3. Practical ignorance: Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n- Main dealing with degree of belief is probability theory.\n- A logical agent believes each sentence to be true or false or has no opinion, whereas a probabilistic agent may have a numerical degree of belief between 0 (for sentences that are certainly false) and 1 (certainly true).\n- So epistemological commitments are different. \n\n### Uncertainty and rational decisions\n- To make such choices, an agent must first have preferences among the different possible outcomes of the various plans.\n- We use utility theory to represent preferences and reason quantitatively with them.\n- The utility of a state is relative to an agent.\n- The fundamental idea of decision theory is that an 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- The above line is principle of maximum expected utility MEU. \n- Belief state includes possibilties and probabilities for world state. \n### \n\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n### Basic probability Notation\n- The possible worlds are mutually exclusive and exhaustive.\n- Probabilities like P(Total = 11) are unconditional or prior probabilities.\n- Usually interested in conditional or posterior probability, situation with evidence. Rolling double given first dice is 5.\n- When making decisions, an agent needs to condition on all the evidence it has observed.\n- It is also important to understand the difference between conditioning and logical implication.\n- P(Cavity|toothache) = 0.6 means whenevr toothache is true and no other info, cavity is 60%.\n\n### The language of propositions in probability assertions\n- Range of Total for two dice is set {2,...,12}\n- Probability density functions (sometimes called pdfs) differ in meaning from discrete distributions.\n- PDFs uniform between 18C to 26C means 100% within this 8C and 50% 4C-wide region.\n- Comma used for distribution for multiple variables. Like P(Weather, Cavity), probability or weather AND cavity.\n\n### Probability axioms and their reasonableness\n- The basic axioms of probability imply certain relationships among the degrees of belief that can be accorded to logically related propositions.\n\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n### Inference Using Full Joint Distributions\n- For probabilistic inference, we use full joint distribution as the knowledge base from which answers to all questions may be derived.\n- Unconfitional/Marginal probability is P(A)\n\n### full joint distribution\n- Does not scale well. \n- O(2^n)\n- Each of the probability has to be estimated separately, astronomical number.\n- Seldom a practical tool for building reasoning systems. \n- Should be viewed as the theoretical foundation on which more effective approaches may be built.\n\n\n\n## AIMA Chapter 12.4 Independence\n \n### Independence\n- Independence assertions can help in reducing the size of the domain representation and the complexity of the inference problem.\n- Unfortunately, clean separation of entire sets of variables by independence is quite rare. \n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n### Bayes’ Rule and Its Use\n- Bayes' rule underlies most modern AI systems for probabilistic inference.\n- Diagnostic knowledge is often more fragile than causal knowledge.\n- O(2^n) possible combinations.\n- In general, for n symptoms that are all conditionally independent given Cavity, the size of the representation grows as O(n) instead of O(2^n).\n- That means that conditional independence assertions can allow probabilistic systems to scale up; moreover, they are much more commonly available than absolute independence assertions.\n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n### Naive Bayes Models\n- Often used (as a simplifying assumption) in cases where the “effect” variables are not strictly independent given the cause variable.\n- The naive Bayes model is sometimes called a Bayesian classifier, a somewhat careless usage that has prompted true Bayesians to call it the idiot Bayes model.\n- In practice, naive Bayes systems often work very well, even when the conditional independence assumption is not strictly true.\n- Naive Bayes models are widely used for language determination, document retrieval, spam filtering, and other classification tasks.\n- Not for medical diagnosis, where the actual values of the posterior probabilities really matter.\n\n### Naive equation steps (See pic)\n-  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. The run time of this calculation is linear in the number of observed effects and does not depend on the number of unobserved effects (which may be very large in domains such as medicine). We will see in the next chapter that this is a common phenomenon in probabilistic inference: evidence variables whose values are unobserved usually “disappear” from the computation altogether\n\n### Text classification with naive Bayes\n- given a text, decide which of a predefined set of classes or categories it belongs to.\n- The task is to classify each sentence into a Category. The major sections of newspaper.\n- naive Bayes consist of prior prbabilities P(Category) and conditional probabilities P(HasWordi|Category).\n- To categorize a new document, we check which key words appear in the document and then apply Equation to obtain the posterior probability distribution over categories.\n-  If we have to predict just one category, we take the one with the highest posterior probability\n- The naive Bayes model assumes that words occur independently in documents, with frequencies determined by the document category.\n- This independence assumption is clearly violated in practice.\n- The violation of independence usually means that the final posterior probabilities will be much closer to 1 or 0 than they should be; in other words, the model is overconfident in its predictions.\n- On the other hand, even with these errors, the ranking of the possible categories is often quite accurate.\n\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n### Unigram model\n- Simplest case\n\n### Bigram model\n- Condition on the previous word\n\n### N-gram model\n- In general, insufficient model of language\n- Because language has long-distance dependencies\n- But can often get away with N-gram model\n\n### Problems for MLE\n- Test VS Train set not same. Train does not contain set. So assign 0.\n- Out of vocabulary items (OOV).\n- Fixed lexicon L of size V\n- Avoid zeroes with smoothing.\n\n### Practical issues\n- We do everything in log space to avoid underflow. Adding is also faster than multiplying. \n\n \n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states that it might be in\n* **Laziness** - Too much work required to do exhaustive search, or too hard, so cant do it. \n* **Epistemological commitments** - See 12_1 rule making.\n* **Theory of probability** - Provides a way of summarizing the uncertainty that comes from our laziness and ignorance, and solves qualification problem.\n* **Utility theory** - every state has a degree of usefulness/utility, to an agent and that the agent will prefer states with higher utility\n* **Decision theory** - probability theory + utility theory\n* **Probability model** - Associates a numerical probability  with each possible world\n* **Unconditional or prior probabilities** - Refer to degrees of belief in propositions in the absence of any other information.\n* **Evidence** - Some information that has already been revealed. Like first dice already showing 5.\n* **Random variables** - Names begin with an uppercase letter.function that maps from the domain of possible worlds  to some range\n* **Probability density function** - define the probability that a random variable takes on some value x as a paramaterized function of x\n* **Probabilistic inference** - the computation of posterior probabilities for query propositions given observed evidence\n* ** unconfitional/marginal probability** - P(A) alone.\n* **Marginalization** - Sum up probabilities for each possible value of the other variables, thereby taking them out of the equation.\n* **Text classification** - given a text, decide which of a predefined set of classes or categories it belongs to.\n* **Posterior probability erm** - conditional probability given the relevant evidence or background\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" \n",
        "### Representing Knowledge in an Uncertain Domain\n",
        "#### Bayesian network\n",
        "- represent the dependencies among variables\n",
        "- Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely\n",
        "- A directed graph in which each node is annotated with quantitative probability information\n",
        "- Once the topology of the Bayes net is laid out, we need only specify the local probability information for each variable, in the form of a conditional distribution given its parents.\n",
        "- The full joint distribution for all the variables is defined by the topology and the local probability information.\n",
        "- The syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. \n",
        "\n",
        "#### Full specification of Bayesian network\n",
        "- Each node corresponds to a random variable, which may be discrete or continuous.\n",
        "- Directed links or arrows connect pairs of nodes. If there is an arrow from node X to node Y, x is said\n",
        "to be a parent of Y. he graph has no directed cycles and hence is a directed acyclic graph, or DAG.\n",
        "- Each node X, has associated probability information delta(Xi|Parents(Xi)), delta is feature, that quantifies the effect of the parents on the node using a finite number of parameters.\n",
        "\n",
        "#### conditional probability table\n",
        "- The local probability information attached to each node \n",
        "- Each row in a CPT contains the conditional probability of each node value for a conditioning case.\n",
        "- A conditioning case is just a possible combination of values for the parent nodes—a miniature possible world.\n",
        "- Each row must sum to 1, because the entries represent an exhaustive set of cases for the variable.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\" \n",
        "### Joint distribution semantics\n",
        "- Each entry in the joint distribution is represented by the product of the appropriate elements of the local conditional distributions in the Bayes net.\n",
        "- parents(Xi) denotes values of Parents(Xi) that appears in x1,...,xn.\n",
        "\n",
        "### A method for constructing Bayesian networks\n",
        "- First, we rewrite the entries in the joint distribution in terms of conditional probability, using the product rule.\n",
        "- Actually just chain rule.\n",
        "\n",
        "### Runtime\n",
        "- In general, noisy logical relationships in which a variable depends on k parents can be described\n",
        "using O(k) parameters instead of O(2^k)\n",
        "\n",
        "### Bayesian nets with continuous variables\n",
        "- Many real-world problems involve continuous quantities, such as height, mass, temperature, and money. By definition, continuous variables have an infinite number of possible values, so it is impossible to specify conditional probabilities explicitly for each value.\n",
        "- One way to handle is with discrtization. \n",
        "- Like temperature is below 0, 0 to 100, above 100.\n",
        "- Tradeoff between loss of accuracy and large CPTs which can lead to slow run times.\n",
        "- Another approach is to define a continuous variable using one of the standard families of probability density functions.\n",
        "\n",
        "### hybrid Bayesian network\n",
        "- To specify a hybrid network, we have to specify two new kinds of distributions\n",
        "- the conditional distribution for a continuous variable given discrete or continuous parents\n",
        "- and the conditional distribution for a discrete variable given continuous parents\n",
        "\n",
        "### linear–Gaussian conditional distribution\n",
        "- A network containing only continuous variables with linear–Gaussian distributions has a joint distribution that is a multivariate Gaussian distribution over all the variables.\n",
        "- Furthermore, the posterior distribution given any evidence also has this property.\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" \n",
        "### The variable elimination algorithm\n",
        "- The idea is simple: do the calculation once and save the results for later use. This is a form of dynamic programming. \n",
        "- Variable elimination works by evaluating expressions in right-to-left order or bottom up.\n",
        "- Intermediate results are stored, and summations over each variable are done only for those portions of the expression that depend on the variable.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "- Models are always simplifications, may not account for every variable and inetractions. \n",
        "- Two variables are independent if P(x,y) = P(x)P(y)\n",
        "- Bayes' net's joint distribution may have further conditional independence that is not detectable until you inspect its specific distribution.\n",
        "\n",
        "#### Bayes net semantics\n",
        "- A set of nodes, one per variable X\n",
        "- A directed, acyclic graph\n",
        "- A conditional distribution for each node. A colelction of distributions over X, one for each combination of parents' values. P(X|a1,...,an)\n",
        "- Topology + local conditional probabilities \n",
        "\n",
        "### Casuality\n",
        "- Bayes' nets reflect true casual patterns. Easy to think about.\n",
        "- BNs need not actually be casual. Sometimes no casual net exisst over domain. End up with arrows reflect correlation, not causation.\n",
        "- Arrow means topology may happen to encode casual structure or really encodes conditional independence.\n",
        "\n",
        "### Size\n",
        "- 2^n for joint distribution over N boolean variables\n",
        "- N-node net if nodes have up to k parents O(N* 2^{k+1})\n",
        "\n",
        "### Assumptions\n",
        "- P(Xi|x1... xi-1) = P(xi | parents(Xi))\n",
        "\n",
        "### Independence\n",
        "- D-separation gives precise conditional independence guarantees from graph alone\n",
        "- If one or more path is active, the independence not guaranteed.\n",
        "- If all paths are active, then independence is guaranteed.\n",
        "- A path is active if each triple is active. \n",
        "\n",
        "### Inference\n",
        "- Calculating some useufl quantity from a joint probability distribution.\n",
        "- To infer by enumeration given evidence e, query Q, hidden vriables H (all variables). Want P(Q|all evidences)\n",
        "1. Select entries consistent with evidence\n",
        "2. Sum out H(hidden variable) to get joint of query and evidence\n",
        "3. Normalize by multiplying 1/Z. Z = summation of P(Q, evidences) for all q.\n",
        "- Given unlimited time, inference in BNs is easy\n",
        "- Inference by enumeration slow because you join up whole joint distribution before you sum out hidden variables.\n",
        "- Advaced technique: Variable elimination. Interleave joining and marginalizing. Still NP-hard, but much faster.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "\"topology \" : \"the set of nodes and links—specifies the conditional independence relationships that hold in the domain,\",\n",
        "\"Arrow\" : \"X has direct influence on Y, causes should be parents of effects\",\n",
        "\"semantics \" : \"defines how the syntax corresponds to a joint distribution over the variables of the network\",\n",
        "\"conditionally independent\" : \"Each variable is conditionally independent of its non-descendants, given its parents.\",\n",
        "\"moral graph\" : \"Add links between any unlinked pair of nodes that share a common child;\",\n",
        "\" ancestral subgraph\" : \"XYZ and their ancestorys\",\n",
        "\"context-specific independence\" : \"if a variable is conditionally independent of some of its parents given certain values of others.\",\n",
        "\"discretization\" : \"dividing up the possible values into a fixed set of intervals\",\n",
        "\"hybrid Bayesian network\" : \"A network with both discrete and continuous variables\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "2e0a533d-9651-4ff3-d505-1c05b5f90405"
      },
      "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": 65,
      "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### Representing Knowledge in an Uncertain Domain\n#### Bayesian network\n- represent the dependencies among variables\n- Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely\n- A directed graph in which each node is annotated with quantitative probability information\n- Once the topology of the Bayes net is laid out, we need only specify the local probability information for each variable, in the form of a conditional distribution given its parents.\n- The full joint distribution for all the variables is defined by the topology and the local probability information.\n- The syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. \n\n#### Full specification of Bayesian network\n- Each node corresponds to a random variable, which may be discrete or continuous.\n- Directed links or arrows connect pairs of nodes. If there is an arrow from node X to node Y, x is said\nto be a parent of Y. he graph has no directed cycles and hence is a directed acyclic graph, or DAG.\n- Each node X, has associated probability information delta(Xi|Parents(Xi)), delta is feature, that quantifies the effect of the parents on the node using a finite number of parameters.\n\n#### conditional probability table\n- The local probability information attached to each node \n- Each row in a CPT contains the conditional probability of each node value for a conditioning case.\n- A conditioning case is just a possible combination of values for the parent nodes—a miniature possible world.\n- Each row must sum to 1, because the entries represent an exhaustive set of cases for the variable.\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n### Joint distribution semantics\n- Each entry in the joint distribution is represented by the product of the appropriate elements of the local conditional distributions in the Bayes net.\n- parents(Xi) denotes values of Parents(Xi) that appears in x1,...,xn.\n\n### A method for constructing Bayesian networks\n- First, we rewrite the entries in the joint distribution in terms of conditional probability, using the product rule.\n- Actually just chain rule.\n\n### Runtime\n- In general, noisy logical relationships in which a variable depends on k parents can be described\nusing O(k) parameters instead of O(2^k)\n\n### Bayesian nets with continuous variables\n- Many real-world problems involve continuous quantities, such as height, mass, temperature, and money. By definition, continuous variables have an infinite number of possible values, so it is impossible to specify conditional probabilities explicitly for each value.\n- One way to handle is with discrtization. \n- Like temperature is below 0, 0 to 100, above 100.\n- Tradeoff between loss of accuracy and large CPTs which can lead to slow run times.\n- Another approach is to define a continuous variable using one of the standard families of probability density functions.\n\n### hybrid Bayesian network\n- To specify a hybrid network, we have to specify two new kinds of distributions\n- the conditional distribution for a continuous variable given discrete or continuous parents\n- and the conditional distribution for a discrete variable given continuous parents\n\n### linear–Gaussian conditional distribution\n- A network containing only continuous variables with linear–Gaussian distributions has a joint distribution that is a multivariate Gaussian distribution over all the variables.\n- Furthermore, the posterior distribution given any evidence also has this property.\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n### The variable elimination algorithm\n- The idea is simple: do the calculation once and save the results for later use. This is a form of dynamic programming. \n- Variable elimination works by evaluating expressions in right-to-left order or bottom up.\n- Intermediate results are stored, and summations over each variable are done only for those portions of the expression that depend on the variable.\n\n \n\n## Module 11 Lecture Notes\n \n- Models are always simplifications, may not account for every variable and inetractions. \n- Two variables are independent if P(x,y) = P(x)P(y)\n- Bayes' net's joint distribution may have further conditional independence that is not detectable until you inspect its specific distribution.\n\n#### Bayes net semantics\n- A set of nodes, one per variable X\n- A directed, acyclic graph\n- A conditional distribution for each node. A colelction of distributions over X, one for each combination of parents' values. P(X|a1,...,an)\n- Topology + local conditional probabilities \n\n### Casuality\n- Bayes' nets reflect true casual patterns. Easy to think about.\n- BNs need not actually be casual. Sometimes no casual net exisst over domain. End up with arrows reflect correlation, not causation.\n- Arrow means topology may happen to encode casual structure or really encodes conditional independence.\n\n### Size\n- 2^n for joint distribution over N boolean variables\n- N-node net if nodes have up to k parents O(N* 2^{k+1})\n\n### Assumptions\n- P(Xi|x1... xi-1) = P(xi | parents(Xi))\n\n### Independence\n- D-separation gives precise conditional independence guarantees from graph alone\n- If one or more path is active, the independence not guaranteed.\n- If all paths are active, then independence is guaranteed.\n- A path is active if each triple is active. \n\n### Inference\n- Calculating some useufl quantity from a joint probability distribution.\n- To infer by enumeration given evidence e, query Q, hidden vriables H (all variables). Want P(Q|all evidences)\n1. Select entries consistent with evidence\n2. Sum out H(hidden variable) to get joint of query and evidence\n3. Normalize by multiplying 1/Z. Z = summation of P(Q, evidences) for all q.\n- Given unlimited time, inference in BNs is easy\n- Inference by enumeration slow because you join up whole joint distribution before you sum out hidden variables.\n- Advaced technique: Variable elimination. Interleave joining and marginalizing. Still NP-hard, but much faster.\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n* **Topology ** - the set of nodes and links—specifies the conditional independence relationships that hold in the domain,\n* **Arrow** - X has direct influence on Y, causes should be parents of effects\n* **Semantics ** - defines how the syntax corresponds to a joint distribution over the variables of the network\n* **Conditionally independent** - Each variable is conditionally independent of its non-descendants, given its parents.\n* **Moral graph** - Add links between any unlinked pair of nodes that share a common child;\n* ** ancestral subgraph** - XYZ and their ancestorys\n* **Context-specific independence** - if a variable is conditionally independent of some of its parents given certain values of others.\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Hybrid bayesian network** - A network with both discrete and continuous variables\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" \n",
        "#### Linear separators\n",
        "- Use support vector machine to find line of best linear fit\n",
        "- Mazimising the margin, good according to intuition, theory, practice\n",
        "- Only support vector matter, others ignorable\n",
        "- SVMs are MIRA where you optimize over all examples at once.\n",
        "\n",
        "#### Comparing NB and Perceptrons/MIRA\n",
        "- NB builds a model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data\n",
        "- Perceptrons/MIRA: Makes less assumptions about data, mistake-driven learning, multiple passes through data(prediction), often more accurate\n",
        "\n",
        "#### Perceptron\n",
        "- Many inputs each with a weight, goes to weighted sum, and then activation function with threshold to give output.\n",
        "- Output is 0 if sum of weight <= threshold. 1 if more than threshold.\n",
        "- Used for all kinds of classification problems\n",
        "- Inputs are features representing what we want to classify\n",
        "- Feature values for inputs are fixed, but we can choose different weight vectors.\n",
        "- A complex network of perceptrons could make quite subtle decisions\n",
        "\n",
        "#### Non-linear separators\n",
        "- Data that is linearly seprable works out great for linear decision rules.\n",
        "- General idea is that original feature space can always be mapped to some higher dimensional feature space where training set is separable.\n",
        "\n",
        "#### Activation functions\n",
        "- Non-linear function\n",
        "- y = a = f(z), y is output of neural network, a is activation function output\n",
        "- 3 commonly used non-linear functions for the f above are sigmoid function, tanh and rectified linear unit ReLU\n",
        "- Sigmoid: y = 1/(1+e^{-z})\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter4_10 = \"\"\" \n",
        "## Perceptrons\n",
        "#### linear classifiers\n",
        "- Inputs are feature values\n",
        "- Each feature has weight\n",
        "- Sum is activation\n",
        "- Activationw (x) = w * f(x) = sum of wi * fi(x)\n",
        "- If activation +ve, output+1, -ve output -1.\n",
        "\n",
        "#### Binary decision rule\n",
        "- In space of feature vectors, examples are points, any weght vector is hyperplane.\n",
        "- One side is y=+1 when w*f(x)>=0, other is y=-1 when w*f(x) < 0.\n",
        "- Start with weight = 0\n",
        "- For each training instance, classify current weights, if correct (y=y*), no change, if wrong, adjust weight vector.\n",
        "- w = w + y* X f. \n",
        "\n",
        "#### Multiclass decision rule\n",
        "- A weight vector for each class. wy\n",
        "- Score(activation) of a class y: wy * f(x)\n",
        "- Prediction highest score wins. y = argmaxy of wy*f(x)\n",
        "- Steps\n",
        "1. Start with all weights = 0\n",
        "2. Pick up training examples one by one\n",
        "3. Predict with current weights y = argmaxy of wy*f(x)\n",
        "4. If correct, no change. If Wrong, lower score of wrong answer, raise score of right answer.\n",
        "- wy = wy - f(x), wy* = wy* + f(x)\n",
        "\n",
        "#### Properties of perceptions\n",
        "- Separability\n",
        "- Convergence\n",
        "- Mistake bound\n",
        "\n",
        "#### Problems\n",
        "- Noise: if data isnt separable, weights might thrash. Averaging weight vectors over time can help.\n",
        "- Mediocre generlization: Finds a barely separating solution\n",
        "- Overtaining: test/held-out accuracy usually rises then falls. A kind of overfitting. \n",
        "\n",
        "#### Fix perceptron\n",
        "- Adjust weight update to mitigate effects\n",
        "- MIRA*: choose update size that fixes current mistake, minimize change to w\n",
        "- Minimum of t is not 0. It is where equality holds.\n",
        "\n",
        "#### Maximum step size\n",
        "- Bad to make too large updates\n",
        "- Example may be labeled incorrectly\n",
        "- May not have enough features\n",
        "- Solution is cap the maximum possible value of t with some constant C.\n",
        "- Corresponds to an optimization that assumes non-separable data\n",
        "- Usually converges faster than perceptron\n",
        "- Usually better on noisy data\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "### Spam classification\n",
        "- Setup with large collection of example emails, labeled smap or ham. \n",
        "- Attributes used to make the ham/spam decision.\n",
        "### Digit recognition\n",
        "- Input is image/pixel grids\n",
        "- Setup with large collection of example images, each labeled with a digit\n",
        "\n",
        "### Model based classification\n",
        "- Model based approach is to build a model like Bayes' net, where both label and features are random variable.\n",
        "- Instatiate any observed features\n",
        "- Query for distribution of label conditioned on features\n",
        "- Challenge is structure to use and how to learn param.\n",
        "\n",
        "### Naive Bayes for Digits\n",
        "- One feature variable Fij for each grid position i,j.\n",
        "- Feature values are on/off, based on whether intensity of more or less than 0.5 in underlying image.\n",
        "- Each input maps to a feature vector. Like F0,0 = 0, F0,1 = 1.\n",
        "\n",
        "### NB for text\n",
        "- Bag-of-wordsNB: Wi is word at position i is feature. Features conditionally independent given label. Insensitive to word order.\n",
        "- Each Wi is identically distributed. \n",
        "- Bestto do in homogenous cases like all features are words\n",
        "\n",
        "### General naive bayes\n",
        "- Total num of parameters is linear in number of features.\n",
        "- Simple\n",
        "- Specify how each feature depends on the class\n",
        "- We need inference method and estimate of local conditional probability tables..\n",
        "- Need P(Y), the prior over labels. P(Fi|Y) for each feature.\n",
        "\n",
        "### Inference for Naive Bayes\n",
        "- Get joint probability of label and evidence for each label\n",
        "- Sum to get probability of evidence\n",
        "- Normalize by dividing step 1 by step 2\n",
        "\n",
        "#### Training data\n",
        "- Labeled instances data like training/held out/test set\n",
        "- Features: Attribute-value pairs which characterize each x\n",
        "- Experiment cycle: Learn param on training set, tune hyperparameters on held-out set, compute accuracy test set\n",
        "#### Held-out data\n",
        "- Evaluation accuracy: fraction of instances predicted correctly\n",
        "#### Test data\n",
        "- Overfitting and generalization.\n",
        "- Need to smooth or regularize estimates\n",
        "\n",
        "### Parameter estimation\n",
        "- Estimate distribution of random variable thru elicitation or empirically\n",
        "- Laplace smoothing, k is length of prior\n",
        "- Laplace for conditionals (smooth each condition independently)\n",
        "- Linear interpolation\n",
        "\n",
        "### Do about errors\n",
        "- Need more features, add info source as new variables in NB model\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"Naive Bayes\" : \"Assume all features are independent effects of the label.\",    \n",
        "\"Overfitting\" : \"Fit training data very closely, but not generalizing well.\",    \n",
        "\"elicitation\" : \"Ask a human\",    \n",
        "\"empirically param estimation\" : \"count(x) / total samples is empiracal rate\",    \n",
        "\"Laplace smoothing\" : \"Pretend you saw every outcome once more than you actually did\",    \n",
        "\"Linear interpolation\" : \"Get empirical P(X) from data\",    \n",
        "\"Baseline\" : \"Help determine how hard the task is, how good accuracy is. For research, use strong baseline.\",    \n",
        "\"Confidence\" : \"Represent how sure the classififer is of the classification. Any probmodels have confidences. No guarantee correct.\",    \n",
        "\"Weak Calibration\" : \"Higher confidence higher accruacy. \",    \n",
        "\"Strong calibration\" : \"Confidence predicts accuracy. \",    \n",
        "\"Separability\" : \"True if some param get training set perfectly correct\",    \n",
        "\"Convergence\" : \"If training is separable, perceptron will eventually converge\",    \n",
        "\"Mistake Bound\" : \"Maximum num of mistakes (binary case) related to the margin or degree of separability. Mistake <k/d^2\",  \n",
        "\"tanh function\" : \"The tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\",    \n",
        "\"ReLU\" : \"ReLU activation function is an activation function defined as the positive part of its argument\",      \n",
        "\"ReLU2\" : \"A piecewise linear function that will output the input directly if it is positive, otherwise, it will output zero.\",     \n",
        "}\n",
        "\n"
      ],
      "execution_count": 66,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "30d6e52d-1a5d-4cb0-fedf-e5595518a81c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 67,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n \n#### Linear separators\n- Use support vector machine to find line of best linear fit\n- Mazimising the margin, good according to intuition, theory, practice\n- Only support vector matter, others ignorable\n- SVMs are MIRA where you optimize over all examples at once.\n\n#### Comparing NB and Perceptrons/MIRA\n- NB builds a model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data\n- Perceptrons/MIRA: Makes less assumptions about data, mistake-driven learning, multiple passes through data(prediction), often more accurate\n\n#### Perceptron\n- Many inputs each with a weight, goes to weighted sum, and then activation function with threshold to give output.\n- Output is 0 if sum of weight <= threshold. 1 if more than threshold.\n- Used for all kinds of classification problems\n- Inputs are features representing what we want to classify\n- Feature values for inputs are fixed, but we can choose different weight vectors.\n- A complex network of perceptrons could make quite subtle decisions\n\n#### Non-linear separators\n- Data that is linearly seprable works out great for linear decision rules.\n- General idea is that original feature space can always be mapped to some higher dimensional feature space where training set is separable.\n\n#### Activation functions\n- Non-linear function\n- y = a = f(z), y is output of neural network, a is activation function output\n- 3 commonly used non-linear functions for the f above are sigmoid function, tanh and rectified linear unit ReLU\n- Sigmoid: y = 1/(1+e^{-z})\n\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n \n## Perceptrons\n#### linear classifiers\n- Inputs are feature values\n- Each feature has weight\n- Sum is activation\n- Activationw (x) = w * f(x) = sum of wi * fi(x)\n- If activation +ve, output+1, -ve output -1.\n\n#### Binary decision rule\n- In space of feature vectors, examples are points, any weght vector is hyperplane.\n- One side is y=+1 when w*f(x)>=0, other is y=-1 when w*f(x) < 0.\n- Start with weight = 0\n- For each training instance, classify current weights, if correct (y=y*), no change, if wrong, adjust weight vector.\n- w = w + y* X f. \n\n#### Multiclass decision rule\n- A weight vector for each class. wy\n- Score(activation) of a class y: wy * f(x)\n- Prediction highest score wins. y = argmaxy of wy*f(x)\n- Steps\n1. Start with all weights = 0\n2. Pick up training examples one by one\n3. Predict with current weights y = argmaxy of wy*f(x)\n4. If correct, no change. If Wrong, lower score of wrong answer, raise score of right answer.\n- wy = wy - f(x), wy* = wy* + f(x)\n\n#### Properties of perceptions\n- Separability\n- Convergence\n- Mistake bound\n\n#### Problems\n- Noise: if data isnt separable, weights might thrash. Averaging weight vectors over time can help.\n- Mediocre generlization: Finds a barely separating solution\n- Overtaining: test/held-out accuracy usually rises then falls. A kind of overfitting. \n\n#### Fix perceptron\n- Adjust weight update to mitigate effects\n- MIRA*: choose update size that fixes current mistake, minimize change to w\n- Minimum of t is not 0. It is where equality holds.\n\n#### Maximum step size\n- Bad to make too large updates\n- Example may be labeled incorrectly\n- May not have enough features\n- Solution is cap the maximum possible value of t with some constant C.\n- Corresponds to an optimization that assumes non-separable data\n- Usually converges faster than perceptron\n- Usually better on noisy data\n\n\n \n\n## Module 12 Lecture Notes\n \n### Spam classification\n- Setup with large collection of example emails, labeled smap or ham. \n- Attributes used to make the ham/spam decision.\n### Digit recognition\n- Input is image/pixel grids\n- Setup with large collection of example images, each labeled with a digit\n\n### Model based classification\n- Model based approach is to build a model like Bayes' net, where both label and features are random variable.\n- Instatiate any observed features\n- Query for distribution of label conditioned on features\n- Challenge is structure to use and how to learn param.\n\n### Naive Bayes for Digits\n- One feature variable Fij for each grid position i,j.\n- Feature values are on/off, based on whether intensity of more or less than 0.5 in underlying image.\n- Each input maps to a feature vector. Like F0,0 = 0, F0,1 = 1.\n\n### NB for text\n- Bag-of-wordsNB: Wi is word at position i is feature. Features conditionally independent given label. Insensitive to word order.\n- Each Wi is identically distributed. \n- Bestto do in homogenous cases like all features are words\n\n### General naive bayes\n- Total num of parameters is linear in number of features.\n- Simple\n- Specify how each feature depends on the class\n- We need inference method and estimate of local conditional probability tables..\n- Need P(Y), the prior over labels. P(Fi|Y) for each feature.\n\n### Inference for Naive Bayes\n- Get joint probability of label and evidence for each label\n- Sum to get probability of evidence\n- Normalize by dividing step 1 by step 2\n\n#### Training data\n- Labeled instances data like training/held out/test set\n- Features: Attribute-value pairs which characterize each x\n- Experiment cycle: Learn param on training set, tune hyperparameters on held-out set, compute accuracy test set\n#### Held-out data\n- Evaluation accuracy: fraction of instances predicted correctly\n#### Test data\n- Overfitting and generalization.\n- Need to smooth or regularize estimates\n\n### Parameter estimation\n- Estimate distribution of random variable thru elicitation or empirically\n- Laplace smoothing, k is length of prior\n- Laplace for conditionals (smooth each condition independently)\n- Linear interpolation\n\n### Do about errors\n- Need more features, add info source as new variables in NB model\n\n\n\n\n \n\n## Module 12 Definitions\n* **Naive bayes** - Assume all features are independent effects of the label.\n* **Overfitting** - Fit training data very closely, but not generalizing well.\n* **Elicitation** - Ask a human\n* **Empirically param estimation** - count(x) / total samples is empiracal rate\n* **Laplace smoothing** - Pretend you saw every outcome once more than you actually did\n* **Linear interpolation** - Get empirical P(X) from data\n* **Baseline** - Help determine how hard the task is, how good accuracy is. For research, use strong baseline.\n* **Confidence** - Represent how sure the classififer is of the classification. Any probmodels have confidences. No guarantee correct.\n* **Weak calibration** - Higher confidence higher accruacy. \n* **Strong calibration** - Confidence predicts accuracy. \n* **Separability** - True if some param get training set perfectly correct\n* **Convergence** - If training is separable, perceptron will eventually converge\n* **Mistake bound** - Maximum num of mistakes (binary case) related to the margin or degree of separability. Mistake <k/d^2\n* **Tanh function** - The tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n* **Relu** - ReLU activation function is an activation function defined as the positive part of its argument\n* **Relu2** - A piecewise linear function that will output the input directly if it is positive, otherwise, it will output zero.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" \n",
        "\n",
        "### Logistic regression\n",
        "- Like the Perceptron, logistic regression uses a vector of weights and a bias term.\n",
        "- z = w*x + b\n",
        "- Instead of outputting z directly, logistic regression transforms it with the sigmoid\n",
        "function σ(z).\n",
        "\n",
        "### Sigmoid neurons\n",
        "- Problem: a small change in the weights or bias of any single perceptron in the network\n",
        "can causes the output to completely flip from 0 to 1.\n",
        "- This is solution.\n",
        "- output = sigma(w*x + b)\n",
        "- sigma(z) = 1/ (1+ e^-z)\n",
        "- Smoothness of sigma means that small changes in the weights wj and in the bias b will\n",
        "produce a small change the output from the neuron.\n",
        "- Δoutput is a linear function of the changes Δwj and Δb\n",
        "- This makes it easy to choose small changes in the weights and biases to achieve any\n",
        "desired small change in the output\n",
        "\n",
        "### Feed Forward Neural Network\n",
        "- The simplest kind of NN\n",
        "- Multilayer network, all units are usually fully-connected, and no cycles.\n",
        "- The outputs from each layer are passed to units in the next higher layer, and no\n",
        "outputs are passed back to lower layers.\n",
        "- A single hidden unit has parameters w (the weight vector) and b (the bias scalar).\n",
        "- We represent the parameters for the entire hidden layer by combining the weight\n",
        "vector wi and bias bi for each unit i into a single weight matrix W and a single bias\n",
        "vector b for the whole layer.\n",
        "- The advantage of using a single matrix W for the weights of the entire layer is the\n",
        "hidden layer computation can be done efficiently with simple matrix operations.\n",
        "- The computation has three steps:\n",
        "1. multiplying the weight matrix by the input vector x,\n",
        "2. adding the bias vector b, and\n",
        "3. applying the activation function g (such as Sigmoid)\n",
        "- The output of the hidden layer, the vector h, is thus the following, using the sigmoid\n",
        "function σ: h = σ(Wx+b)\n",
        "- Like the hidden layer, the output layer has a weight matrix U.\n",
        "Its weight matrix is multiplied by its input vector (h) to produce the intermediate output z. z = Uh\n",
        "- Here are the final equations for a feedforward network with a single hidden layer,\n",
        "which takes an input vector x, outputs a probability distribution y, and is parameterized\n",
        "by weight matrices W and U and a bias vector b:\n",
        "- h = σ(Wx+b)\n",
        "- z = Uh\n",
        "- y = softmax(z)\n",
        "- Like with logistic regression, softmax normalizes the output and turns it into a\n",
        "probability distribution.\n",
        "\n",
        "#### Training neural network\n",
        "- Need loss function, cross entropy loss.\n",
        "- An optimization algorithm, gradient descent.\n",
        "- A way of computing the gradient of loss function, error propagation.\n",
        "\n",
        "#### Computation graphs\n",
        "- Although backpropagation was invented for neural nets, it is related to general\n",
        "procedure called backward differentiation, which depends on the notion of\n",
        "computation graphs.\n",
        "- A computation graph represents the process of computing a mathematical expression.\n",
        "The computation is broken down into separate operations. Each operation is a node in\n",
        "a graph.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_7 = \"\"\" \n",
        "\n",
        "#### Mini-batch training\n",
        "- Stochastic gradient descent chooses a single random example at a time and updates\n",
        "its weights on that example. As a result the updates can fluctuate.\n",
        "- An alternate is batch training, which computes the gradient over the entire dataset.\n",
        "This gives a much better estimate of which direction to move the weights but takes a\n",
        "long time to compute.\n",
        "- A commonly used compromise is mini-batch training, where we train on a small\n",
        "batch. The batch size can be 512 or 1024, often selected based on computational\n",
        "resources, so that all examples in the mini-batch can be processed in parallel. The loss\n",
        "is then accumulated.\n",
        "\n",
        "#### Regularization\n",
        "- Regularization is a way to penalize large weights. A regularization term is added to\n",
        "the loss function.\n",
        "- Overfitting is a problem with many machine learning models. Overfitting results in\n",
        "poor generalization and poor performance on unseen test set.\n",
        "- In logistic regression, if a feature only occurs in one class then it will get a high weight.\n",
        "Sometimes we are just modelling noisy factors that just accidentally correlate with the\n",
        "class.\n",
        "- Lasso regression uses L1 regularization\n",
        "- Ridge regression uses L2 regularization\n",
        "\n",
        "#### Multinomial logistic regression\n",
        "- Instead of binary classification, we often want more than two classes. For sentiment\n",
        "classification we might extend the class labels to be positive, negative, and neutral.\n",
        "- We want to know the probability of y for each class c ∈ C, p(y = c|x).\n",
        "- To get a proper probability, we will use a generalization of the sigmoid function\n",
        "called the softmax function.\n",
        "\n",
        "#### Softmax function\n",
        "- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of\n",
        "values normalized into probabilities.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "### Classifier components\n",
        "- ML classifiers require a training corpus of M observations input/output pairs xi yi.\n",
        "1. A feature representation of the input. For each input observation xi, there will be vector of features x1..xn.\n",
        "2. A classification function that computes the estimated class y cap via p(y|x)\n",
        "3. An objective function for learning, usually involving minimizing error on training examples.\n",
        "4. An algorithm for optimizing the objective function.\n",
        "\n",
        "#### Sentiment classifier\n",
        "- Output positive 1 or negative 0\n",
        "- Estimate P(y=1 |x) give a vector of features x1,...,xn. \n",
        "- Logistic regression solves this task by learning from a training set, a vector of weights and bias term\n",
        "- z = w*x + b\n",
        "- z = sum of wixi + b\n",
        "- Each x has a weight, value * weight = product, sum all products to get final z.\n",
        "- Then use sigmoid function, sigmoid(z) to get final one.\n",
        "\n",
        "#### Learning in losgistic regression\n",
        "- Require 2 components to learn params (weights + bias) via learning. \n",
        "1. Loss function/objective function, tells us distance between the system output and the gold output. We use cross-entropy loss.\n",
        "2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function.\n",
        "\n",
        "#### Loss functions\n",
        "- Determine for some observation x how close the classifier output ycap = sigmoid(w*x + b) is to the correct output (y, which is 0 or 1)\n",
        "- L(ycap, y) = how much ycap differs from the true y\n",
        "- One example is mean squared error\n",
        "- We use loss function that prefers correct class labels of training example to be more likely.\n",
        "- Conditional maximum likelihood estimation: Choose parameters w, b that maximise log probabilities of true labels in training data.\n",
        "- The resulting loss function is negative log likelihood loss, more commonly called cross entropy loss.\n",
        "- We want loss to be smaller if model's estimate is close to correct, and we want the loss be bigger if it is confused.\n",
        "\n",
        "#### Gradient descent\n",
        "- Find good parameters. Find good settings for weights and bias by minimizing loss function. \n",
        "- Gradient descent is a method that finds minimum of a function by figuring out in which direction the function's slope is rising the most steeply, and moving in th opposite direction.\n",
        "- Can find minimum iteratively since convex.\n",
        "- The magnitude of amount to move in gradient descent is value of slope weighted by a learning rate n.\n",
        "- Higher/faster learning rate means we should move w more on each step.\n",
        "- The gradient is difference between true y and estimate for x, multiplied by corresponding input value xj.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Decision boundary\" : \"That 0.5 for >0.5 is 1, below 0.5 is 0.\",\n",
        "\"Convex\" : \"A convex function has 1 minimum, wont be stuck. In LR, loss function is convex.\",         \n",
        "}\n"
      ],
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "180c930b-285a-493f-ab86-6da7e13db6f0"
      },
      "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": 69,
      "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 \n\n### Logistic regression\n- Like the Perceptron, logistic regression uses a vector of weights and a bias term.\n- z = w*x + b\n- Instead of outputting z directly, logistic regression transforms it with the sigmoid\nfunction σ(z).\n\n### Sigmoid neurons\n- Problem: a small change in the weights or bias of any single perceptron in the network\ncan causes the output to completely flip from 0 to 1.\n- This is solution.\n- output = sigma(w*x + b)\n- sigma(z) = 1/ (1+ e^-z)\n- Smoothness of sigma means that small changes in the weights wj and in the bias b will\nproduce a small change the output from the neuron.\n- Δoutput is a linear function of the changes Δwj and Δb\n- This makes it easy to choose small changes in the weights and biases to achieve any\ndesired small change in the output\n\n### Feed Forward Neural Network\n- The simplest kind of NN\n- Multilayer network, all units are usually fully-connected, and no cycles.\n- The outputs from each layer are passed to units in the next higher layer, and no\noutputs are passed back to lower layers.\n- A single hidden unit has parameters w (the weight vector) and b (the bias scalar).\n- We represent the parameters for the entire hidden layer by combining the weight\nvector wi and bias bi for each unit i into a single weight matrix W and a single bias\nvector b for the whole layer.\n- The advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\n- The computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\n- The output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ: h = σ(Wx+b)\n- Like the hidden layer, the output layer has a weight matrix U.\nIts weight matrix is multiplied by its input vector (h) to produce the intermediate output z. z = Uh\n- Here are the final equations for a feedforward network with a single hidden layer,\nwhich takes an input vector x, outputs a probability distribution y, and is parameterized\nby weight matrices W and U and a bias vector b:\n- h = σ(Wx+b)\n- z = Uh\n- y = softmax(z)\n- Like with logistic regression, softmax normalizes the output and turns it into a\nprobability distribution.\n\n#### Training neural network\n- Need loss function, cross entropy loss.\n- An optimization algorithm, gradient descent.\n- A way of computing the gradient of loss function, error propagation.\n\n#### Computation graphs\n- Although backpropagation was invented for neural nets, it is related to general\nprocedure called backward differentiation, which depends on the notion of\ncomputation graphs.\n- A computation graph represents the process of computing a mathematical expression.\nThe computation is broken down into separate operations. Each operation is a node in\na graph.\n\n \n\n## SLP Chapter 7.7 Training the neural language model\n \n\n#### Mini-batch training\n- Stochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\n- An alternate is batch training, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\n- A commonly used compromise is mini-batch training, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n#### Regularization\n- Regularization is a way to penalize large weights. A regularization term is added to\nthe loss function.\n- Overfitting is a problem with many machine learning models. Overfitting results in\npoor generalization and poor performance on unseen test set.\n- In logistic regression, if a feature only occurs in one class then it will get a high weight.\nSometimes we are just modelling noisy factors that just accidentally correlate with the\nclass.\n- Lasso regression uses L1 regularization\n- Ridge regression uses L2 regularization\n\n#### Multinomial logistic regression\n- Instead of binary classification, we often want more than two classes. For sentiment\nclassification we might extend the class labels to be positive, negative, and neutral.\n- We want to know the probability of y for each class c ∈ C, p(y = c|x).\n- To get a proper probability, we will use a generalization of the sigmoid function\ncalled the softmax function.\n\n#### Softmax function\n- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of\nvalues normalized into probabilities.\n\n \n\n## Module 13 Lecture Notes\n \n### Classifier components\n- ML classifiers require a training corpus of M observations input/output pairs xi yi.\n1. A feature representation of the input. For each input observation xi, there will be vector of features x1..xn.\n2. A classification function that computes the estimated class y cap via p(y|x)\n3. An objective function for learning, usually involving minimizing error on training examples.\n4. An algorithm for optimizing the objective function.\n\n#### Sentiment classifier\n- Output positive 1 or negative 0\n- Estimate P(y=1 |x) give a vector of features x1,...,xn. \n- Logistic regression solves this task by learning from a training set, a vector of weights and bias term\n- z = w*x + b\n- z = sum of wixi + b\n- Each x has a weight, value * weight = product, sum all products to get final z.\n- Then use sigmoid function, sigmoid(z) to get final one.\n\n#### Learning in losgistic regression\n- Require 2 components to learn params (weights + bias) via learning. \n1. Loss function/objective function, tells us distance between the system output and the gold output. We use cross-entropy loss.\n2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function.\n\n#### Loss functions\n- Determine for some observation x how close the classifier output ycap = sigmoid(w*x + b) is to the correct output (y, which is 0 or 1)\n- L(ycap, y) = how much ycap differs from the true y\n- One example is mean squared error\n- We use loss function that prefers correct class labels of training example to be more likely.\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximise log probabilities of true labels in training data.\n- The resulting loss function is negative log likelihood loss, more commonly called cross entropy loss.\n- We want loss to be smaller if model's estimate is close to correct, and we want the loss be bigger if it is confused.\n\n#### Gradient descent\n- Find good parameters. Find good settings for weights and bias by minimizing loss function. \n- Gradient descent is a method that finds minimum of a function by figuring out in which direction the function's slope is rising the most steeply, and moving in th opposite direction.\n- Can find minimum iteratively since convex.\n- The magnitude of amount to move in gradient descent is value of slope weighted by a learning rate n.\n- Higher/faster learning rate means we should move w more on each step.\n- The gradient is difference between true y and estimate for x, multiplied by corresponding input value xj.\n\n\n\n\n \n\n## Module 13 Definitions\n* **Decision boundary** - That 0.5 for >0.5 is 1, below 0.5 is 0.\n* **Convex** - A convex function has 1 minimum, wont be stuck. In LR, loss function is convex.\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 = \"\"\" \n",
        "### Word meaning\n",
        "1. Synonyms – words that have similar meanings\n",
        "2. Antonyms – words that have opposite meanings\n",
        "3. Connotations – words that are positive or negative\n",
        "4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\n",
        "purchasing event\n",
        "5. Support for entailment\n",
        "\n",
        "### Term Document Matrix\n",
        "- Each column vector represents a document\n",
        "- Each row vector represents a term\n",
        "- Value in cell is based on how often that term occurred in that document\n",
        "- Length of document vectors is the size of the vocabulary\n",
        "- Measure how similar two documents are by comparing their column vectors\n",
        "- Compare row vector to know which one is more positive or negative. \n",
        "- Normalize word vectors to get more accurate representation of sentiment, divided by its L2 length. \n",
        "- Cosine does L2 normalization too. Cosine angle between vectors tell about similarity, larger the less similar. \n",
        "\n",
        "### Term term matrix / Term context matrix\n",
        "- Word X Word matrix\n",
        "- Length of vector is |V|\n",
        "- Value in cell indicates how often the X word appears in a context window surrounding Y word\n",
        "- Context window is w-2, w-2, targetword, w+1, w+2\n",
        " \"\"\"\n",
        "slp_chapter6_10 = \"\"\" \n",
        "\n",
        "\n",
        "### TF-IDF\n",
        "#### Term frequency\n",
        "- How often a word occurred in a document\n",
        "#### Inverse document frequency\n",
        "- 1 over the number of documents that it occurred in\n",
        "#### Space VS dense vectors\n",
        "- Co-occurrence matrix (weighted by TFIDF or mutual information)\n",
        "1. Long (length |V| = 50000+)\n",
        "2. Sparse (most elements are zeros)\n",
        "- Alternative: Learn vectors that are short (length 200~1000) and dense (most elements are non-zero)\n",
        "\n",
        "### Language modeling\n",
        "- Goal is to learn a function that returns the joint probability\n",
        "- Primary difficulty:\n",
        "1. There are too many parameters to accurately estimate. This is sometimes called the “curse of dimensionality”\n",
        "2. In n-gram-based models we fail to generalize to related words / word sequences that we have observed.\n",
        "- Deal with unseen sequences (new combination of n words) by back-off or smoothing/interpolation.  \n",
        "\n",
        "### Neural Language models\n",
        "- Neural Language models have several advantages over n-gram LMs:\n",
        "1. They don’t need smoothing\n",
        "2. They can handle much longer histories.\n",
        "3. They can generalize over contexts of similar words.\n",
        "4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
        "- Disadvantage: slower to train than traditional n-gram LMs\n",
        "- Steps:\n",
        "1. Associate each word in the vocabulary with a vector-representation, thereby\n",
        "creating a notion of similarity between words.\n",
        "2. Express the joint probability function of a word sequence in terms of the word\n",
        "vectors for the words in that sequence.\n",
        "3. Simultaneously learn the word vectors and the parameters of the function.\n",
        "- The word vectors are low-dimensional (d=30 to d=100) dense vectors, like we’ve seen\n",
        "before.\n",
        "- The probability function is expressed the product of conditional probabilities of the\n",
        "next word given the previous word, using a multi-layer, feed forward neural network.\n",
        "- Output layer, hidden layer, projection layer, input layer, input words.\n",
        "\n",
        "#### NLM IO\n",
        "- The input to the neural network is a k-gram of words w1:k.\n",
        "- The output is a probability distribution over the next word.\n",
        "- The k context words are treated as a word window. Each word is associated with an\n",
        "embedding vector\n",
        "- The input x is fed into a neural network with 1 or more hidden layers:\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_11 = \"\"\" \n",
        "\n",
        "### Training NLM\n",
        "- The training examples are simply word k-grams from the corpus\n",
        "- The identities of the first k-1 words are used as features, and the last word is used as\n",
        "the target label for the classification.\n",
        "- Conceptually, the model is trained using cross-entropy loss.\n",
        "\n",
        "### Advantages\n",
        "- Better results. They achieve better preplexity scores than SOTA n-gram LMs.\n",
        "- Larger N. NN LMs can scale to much larger orders of n. This is achievable because\n",
        "parameters are associated only with individual words, and not with n-grams.\n",
        "- They generalize across contexts.\n",
        "- A by-product of training are word embeddings\n",
        "\n",
        "### Neural Probabilistic LM\n",
        "- 1. Use a vector space model where the words are vectors with real\n",
        "values ℝm. m=30, 60, 100. This gives a way to compute word\n",
        "similarity.\n",
        "- 2. Define a function that returns a joint probability of words in a\n",
        "sequence based on a sequence of these vectors.\n",
        "- 3. Simultaneously learn the word representations and the probability\n",
        "function from data.\n",
        "- Seeing one of the cat/dog sentences allows them to increase the\n",
        "probability for that sentence and its combinatorial # of “neighbor”\n",
        "sentences in vector space.\n",
        "\n",
        "### Get dense vectors\n",
        "- Train a classifier\n",
        "1. Treat the target word and a neighboring context word as positive examples.\n",
        "2. Randomly sample other words in the lexicon to get negative samples.\n",
        "3. Use logistic regression to train a classifier to distinguish those two cases.\n",
        "4. Use the weights as the embeddings.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_12 = \"\"\" \n",
        "\n",
        "### Dense vectors\n",
        "- Short vectors may be easier to use as features in machine learning (fewer\n",
        "weights to tune)\n",
        "- Dense vectors may generalize better than storing explicit counts\n",
        "- They may do better at capturing synonymy: car and automobile are synonyms; but are distinct dimensions in sparse\n",
        "vectors. a word with car as a neighbor and a word with automobile as a\n",
        "neighbor should be similar, but aren't. \n",
        "- In practice, they work better\n",
        "\n",
        "### Word2Vec\n",
        "- Learn embeddings as part of the process\n",
        "of word prediction. Capture relational meaning like man-woman, uncle-aunt.\n",
        "- Train a classifier to predict neighboring\n",
        "words\n",
        "- Inspired by neural net language models.\n",
        "In so doing, learn dense embeddings for\n",
        "the words in the training corpus.\n",
        "- Advantages:\n",
        "Fast, easy to train (much faster than SVD)\n",
        "Available online in the word2vec package\n",
        "Including sets of pretrained embeddings!\n",
        "\n",
        "### Skip-Gram Task\n",
        "- One option of Word2Vec\n",
        "- Skip-gram with negative sampling\n",
        "1. Treat the target word and a neighboring context\n",
        "word as positive examples.\n",
        "2. Randomly sample other words in the lexicon to get\n",
        "negative samples\n",
        "3. Use logistic regression to train a classifier to\n",
        "distinguish those two cases\n",
        "4. Use the weights as the embeddings\n",
        "- Given a tuple (t,c) = target, context. Return probability that c is a real context word. \n",
        "- P(−|t,c) = 1−P(+|t,c)\n",
        "\n",
        "#### Compute P(+|t,c)\n",
        "- Intuition:\n",
        "• Words are likely to appear near similar words\n",
        "• Model similarity with dot-product!\n",
        "• Similarity(t,c) ≈ t ∙ c\n",
        "\n",
        "#### Embedding for Word2Vec\n",
        "- We need embeddings for t and c to do the equation above.\n",
        "- Word2vec learns them automatically!\n",
        "- It starts with an initial set of embedding vectors and then iteratively shifts\n",
        "the embedding of each word w to be more like the embeddings of words\n",
        "that occur nearby in texts, and less like the embeddings of words that\n",
        "don’t occur nearby.\n",
        "- For training data, +/- 2 word window.\n",
        "- FOr each positive example, create k negative examples using noise words.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "#### Choosing noise words\n",
        "- Could pick w according to their unigram frequency P(w)\n",
        "\n",
        "#### Learning classifier\n",
        "- Iterative process\n",
        "- start with 0 or random weights\n",
        "- Then adjust the word weights to make the positive pairs more likely and the negative pairs less likely\n",
        "over the entire training set.\n",
        "- For training set, try to maximize the similarity of the target word, context word\n",
        "pairs (t,c) drawn from the positive data\n",
        "- And try to Minimize the similarity of the (t,c) pairs drawn from the\n",
        "negative data.\n",
        "\n",
        "#### Solving analogies with embeddings\n",
        "- a:a∗ as b:b∗, a* and b* are hidden vectors.\n",
        "- Compare by word window\n",
        "- b∗ should be similar to the vector b − a + a∗\n",
        "- b* - b shares same direction with a* - a, ignoring distances\n",
        "\n",
        "\n",
        "#### Cultural bias\n",
        "- Embedding reflects cultural bias\n",
        "- To measure the bias, use Implicit Association test\n",
        "- \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 70,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "8142bc7a-b552-4941-ab1c-c5cfcc03a2bb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 71,
      "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 \n### Word meaning\n1. Synonyms – words that have similar meanings\n2. Antonyms – words that have opposite meanings\n3. Connotations – words that are positive or negative\n4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\npurchasing event\n5. Support for entailment\n\n### Term Document Matrix\n- Each column vector represents a document\n- Each row vector represents a term\n- Value in cell is based on how often that term occurred in that document\n- Length of document vectors is the size of the vocabulary\n- Measure how similar two documents are by comparing their column vectors\n- Compare row vector to know which one is more positive or negative. \n- Normalize word vectors to get more accurate representation of sentiment, divided by its L2 length. \n- Cosine does L2 normalization too. Cosine angle between vectors tell about similarity, larger the less similar. \n\n### Term term matrix / Term context matrix\n- Word X Word matrix\n- Length of vector is |V|\n- Value in cell indicates how often the X word appears in a context window surrounding Y word\n- Context window is w-2, w-2, targetword, w+1, w+2\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \n\n\n### TF-IDF\n#### Term frequency\n- How often a word occurred in a document\n#### Inverse document frequency\n- 1 over the number of documents that it occurred in\n#### Space VS dense vectors\n- Co-occurrence matrix (weighted by TFIDF or mutual information)\n1. Long (length |V| = 50000+)\n2. Sparse (most elements are zeros)\n- Alternative: Learn vectors that are short (length 200~1000) and dense (most elements are non-zero)\n\n### Language modeling\n- Goal is to learn a function that returns the joint probability\n- Primary difficulty:\n1. There are too many parameters to accurately estimate. This is sometimes called the “curse of dimensionality”\n2. In n-gram-based models we fail to generalize to related words / word sequences that we have observed.\n- Deal with unseen sequences (new combination of n words) by back-off or smoothing/interpolation.  \n\n### Neural Language models\n- Neural Language models have several advantages over n-gram LMs:\n1. They don’t need smoothing\n2. They can handle much longer histories.\n3. They can generalize over contexts of similar words.\n4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n- Disadvantage: slower to train than traditional n-gram LMs\n- Steps:\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n3. Simultaneously learn the word vectors and the parameters of the function.\n- The word vectors are low-dimensional (d=30 to d=100) dense vectors, like we’ve seen\nbefore.\n- The probability function is expressed the product of conditional probabilities of the\nnext word given the previous word, using a multi-layer, feed forward neural network.\n- Output layer, hidden layer, projection layer, input layer, input words.\n\n#### NLM IO\n- The input to the neural network is a k-gram of words w1:k.\n- The output is a probability distribution over the next word.\n- The k context words are treated as a word window. Each word is associated with an\nembedding vector\n- The input x is fed into a neural network with 1 or more hidden layers:\n\n\n \n\n## SLP Chapter 6.11 Bias and Embeddings\n \n\n### Training NLM\n- The training examples are simply word k-grams from the corpus\n- The identities of the first k-1 words are used as features, and the last word is used as\nthe target label for the classification.\n- Conceptually, the model is trained using cross-entropy loss.\n\n### Advantages\n- Better results. They achieve better preplexity scores than SOTA n-gram LMs.\n- Larger N. NN LMs can scale to much larger orders of n. This is achievable because\nparameters are associated only with individual words, and not with n-grams.\n- They generalize across contexts.\n- A by-product of training are word embeddings\n\n### Neural Probabilistic LM\n- 1. Use a vector space model where the words are vectors with real\nvalues ℝm. m=30, 60, 100. This gives a way to compute word\nsimilarity.\n- 2. Define a function that returns a joint probability of words in a\nsequence based on a sequence of these vectors.\n- 3. Simultaneously learn the word representations and the probability\nfunction from data.\n- Seeing one of the cat/dog sentences allows them to increase the\nprobability for that sentence and its combinatorial # of “neighbor”\nsentences in vector space.\n\n### Get dense vectors\n- Train a classifier\n1. Treat the target word and a neighboring context word as positive examples.\n2. Randomly sample other words in the lexicon to get negative samples.\n3. Use logistic regression to train a classifier to distinguish those two cases.\n4. Use the weights as the embeddings.\n\n\n\n \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \n\n### Dense vectors\n- Short vectors may be easier to use as features in machine learning (fewer\nweights to tune)\n- Dense vectors may generalize better than storing explicit counts\n- They may do better at capturing synonymy: car and automobile are synonyms; but are distinct dimensions in sparse\nvectors. a word with car as a neighbor and a word with automobile as a\nneighbor should be similar, but aren't. \n- In practice, they work better\n\n### Word2Vec\n- Learn embeddings as part of the process\nof word prediction. Capture relational meaning like man-woman, uncle-aunt.\n- Train a classifier to predict neighboring\nwords\n- Inspired by neural net language models.\nIn so doing, learn dense embeddings for\nthe words in the training corpus.\n- Advantages:\nFast, easy to train (much faster than SVD)\nAvailable online in the word2vec package\nIncluding sets of pretrained embeddings!\n\n### Skip-Gram Task\n- One option of Word2Vec\n- Skip-gram with negative sampling\n1. Treat the target word and a neighboring context\nword as positive examples.\n2. Randomly sample other words in the lexicon to get\nnegative samples\n3. Use logistic regression to train a classifier to\ndistinguish those two cases\n4. Use the weights as the embeddings\n- Given a tuple (t,c) = target, context. Return probability that c is a real context word. \n- P(−|t,c) = 1−P(+|t,c)\n\n#### Compute P(+|t,c)\n- Intuition:\n• Words are likely to appear near similar words\n• Model similarity with dot-product!\n• Similarity(t,c) ≈ t ∙ c\n\n#### Embedding for Word2Vec\n- We need embeddings for t and c to do the equation above.\n- Word2vec learns them automatically!\n- It starts with an initial set of embedding vectors and then iteratively shifts\nthe embedding of each word w to be more like the embeddings of words\nthat occur nearby in texts, and less like the embeddings of words that\ndon’t occur nearby.\n- For training data, +/- 2 word window.\n- FOr each positive example, create k negative examples using noise words.\n\n \n\n## Module 13 Lecture Notes\n \n### Classifier components\n- ML classifiers require a training corpus of M observations input/output pairs xi yi.\n1. A feature representation of the input. For each input observation xi, there will be vector of features x1..xn.\n2. A classification function that computes the estimated class y cap via p(y|x)\n3. An objective function for learning, usually involving minimizing error on training examples.\n4. An algorithm for optimizing the objective function.\n\n#### Sentiment classifier\n- Output positive 1 or negative 0\n- Estimate P(y=1 |x) give a vector of features x1,...,xn. \n- Logistic regression solves this task by learning from a training set, a vector of weights and bias term\n- z = w*x + b\n- z = sum of wixi + b\n- Each x has a weight, value * weight = product, sum all products to get final z.\n- Then use sigmoid function, sigmoid(z) to get final one.\n\n#### Learning in losgistic regression\n- Require 2 components to learn params (weights + bias) via learning. \n1. Loss function/objective function, tells us distance between the system output and the gold output. We use cross-entropy loss.\n2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function.\n\n#### Loss functions\n- Determine for some observation x how close the classifier output ycap = sigmoid(w*x + b) is to the correct output (y, which is 0 or 1)\n- L(ycap, y) = how much ycap differs from the true y\n- One example is mean squared error\n- We use loss function that prefers correct class labels of training example to be more likely.\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximise log probabilities of true labels in training data.\n- The resulting loss function is negative log likelihood loss, more commonly called cross entropy loss.\n- We want loss to be smaller if model's estimate is close to correct, and we want the loss be bigger if it is confused.\n\n#### Gradient descent\n- Find good parameters. Find good settings for weights and bias by minimizing loss function. \n- Gradient descent is a method that finds minimum of a function by figuring out in which direction the function's slope is rising the most steeply, and moving in th opposite direction.\n- Can find minimum iteratively since convex.\n- The magnitude of amount to move in gradient descent is value of slope weighted by a learning rate n.\n- Higher/faster learning rate means we should move w more on each step.\n- The gradient is difference between true y and estimate for x, multiplied by corresponding input value xj.\n\n\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "d7f188f9-2c15-4ca5-f3e8-2dd786fd6a84"
      },
      "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": 72,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 17.1 Sequential Decision Problems' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n- Agent has some available action a. There may be uncertainty about the current state, so we’ll assume that the agent assigns a probability P(s)\n\to each possible current state s.\n- There may also be uncertainty about the action outcomes; the transition model is given by P(s'|s,a)\n- We are interested in outcome s', so probability of reaching s' by doing a in current state is P(Result(a)=s').\n- P(Result(a)=s') = summation of P(s)P(s'|s,a), this requires perception, learning, knowledge representation, and inference.\n- Computing this itself requires a causal model of world. Many actions to consider. computing the outcome utilities \n\\may itself require further searching or planning because an agent may not know how good a state is until it knows where it can get to from that state. \n\n### Decision theory\n- Decision theory deals with choosing among actions based on the desirability of their immediate outcomes.\n- The agent’s preferences are captured by a utility function U(s),which assigns a single number to express the desirability of a state.\n- The expected utility of an action given the evidence, EU(a) is just the average utility value of the outcomes, weighted by the probability that the outcome occurs.\n- It does provide the beginnings of a basic mathematical framework that is general enough to define the AI problem.\n### MEU\n- The MEU principle could be seen as a prescription for intelligent behavior, AI needs quantities, max U over actions, but AI problem is not solved.\n- The MEU principle formalizes the general notion that an intelligent agent should “do the right thing,” but does not operationalize that advice.\n- The MEU principle has a clear relation to the idea of performance measures.\n- If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). \n- This is the central justification for the MEU principle itself. \n- The performance measure gives a score for a history—a sequence of states. Thus it is applied retrospectively after an agent completes a sequence of actions. The utility function applies to the very next state, so it can be used to guide actions step by step.\n\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 \n- MEU is not the only rational way to make decisions. \n- A&B can be states of world. \n\n### Constraints on rational preferences\n- Symbol in pic.\n- Think of the set of outcomes for each action as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1,...,Sn that occur with probabilities p1,...,pn is\n- L=[p1,S1;p2,S2;...;pn,Sn]\n- Each outcome  of a lottery can be either an atomic state or another lottery. \n1. Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable. That is, the agent cannot avoid deciding.\n2. TRANSITIVITY: If A prefers B, B prefers C, then A prefers C.\n3. Continuity: If lottery B between A and C in preference some probability p for which RA will be indifferent between getting B for sure and lottery that yields A with p and C with 1-p.\n4. Substitutability:  If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. Holds regardless of p and other outcomes in lotteries. \n5. Monotonicity: Two lotteries have the same two possible outcomes, A&B. If agent prefers A to B,then the agent must prefer the lottery that has a higher probability for A.\n6. Decomposability: Compound lotteries can be reduced to simpler ones using the laws of probability. \n- These constraints are known as the axioms of utility theory. Each axiom can be motivated by showing that an agent that violates it will exhibit patently irrational behavior in some situations. \n\n### Rational preferences lead to utility\n- Notice that the axioms of utility theory are really axioms about preferences—they say nothing about a utility function. \n1. Existence of utility function: If an agent’s preferences obey the axioms of utility, then there exists a function U such that U(A) > U(B) iff A is preferred to B, and U(A) = U(B) iff agent is indifferent between A and B.\n2. Expected utility of a lottery: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n- In other words, once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined. \n- The preceding theorems establish that (assuming the constraints on rational preferences) a utility function exists for any rational agent. The theorems do not establish that the utility function is unique. \n- It is important to remember that the existence of a utility function that describes an agent’s preference behavior does not necessarily mean that the agent is explicitly maximizing that utility function in its own deliberations. \n- By observing a rational agent’s behavior, an observer can learn about the utility function that represents what the agent is actually trying to achieve.\n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \n\n## Utility Functions\n- Utility functions map from lotteries to real numbers.\n\n### Utility assessment and utility scales\n- A scale for utility can be established by fixing the utilities of any two particular outcomes, just as we fix a temperature scale by fixing the freezing point and boiling point of water.\n- Normalize utility, best = 1, worst = 0. Ask agent choose standard lottery [p, u1; (1-p),u2]. P is adjusted until agent is indifferent between S and the standard lottery. That will be utility of S.\n- Use micromort and QALY to value life. \n\n### Utility of money\n- Agents exhibits monotonic preference for money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n- Money lottery problem. To determine what to do, we need to assign utilities to the outcome states. Utility is not directly proportional to monetary value, because the utility for your first million is very high (or so they say), whereas the utility for an additional million is smaller. \n- In a pioneering study of actual utility functions, Grayson (1960) found that the utility of money was almost exactly proportional to the logarithm of the amount. \n- If we restrict our attention to the positive part of the curves, where the slope is decreasing, then for any lottery , the utility of being faced with that lottery is less than the utility of being handed the expected monetary value of the lottery as a sure thing.\n- That is, agents with curves of this shape are risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n- On the other hand, in the “desperate” region at large negative wealth in Figure 16.2(b), the behavior is risk-seeking. \n- For gambles with small sums, therefore, we expect risk neutrality.\n\n### Expected utility and post-decision disappointment\n- The rational way to choose the best action, a* , is to maximize expected utility.\n- If everything correct, on average, we will get the utility we expect if the whole process is repeated many times.\n- In reality, however, our model usually oversimplifies the real situation, either because we don’t know enough, or because the computation of the true expected utility is too difficult.\n- We assumed estimates are unbiased. In that case, it still seems reasonable to choose the action with the highest estimated utility and to expect to receive that utility, on average, when the action is executed.\n- Unfortunately, the real outcome will usually be significantly worse.\n- It is a straightforward matter to calculate the distribution of the maximum of the k estimates and hence quantify the extent of our disappointment.\n- When k gets larger, disappointment gets higher in terms of more std deviation.\n\n\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \n\n#### Certainty effect reasons\n1. First, people prefer to reduce computational burden; by choosing certain outcomes, they don’t have to compute with probabilities. But the effect persists even when the computations involved are very easy ones.\n2. Second, people may distrust the legitimacy of the stated probabilities. In the presence of distrust, it might be better to go for the sure thing. Distrust others flip coins.\n3. People may be accounting for their emotional state as well as their financial state. People know they would experience regret.\n- Yet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is framing effect. \n- People feel more comfortable making relative utility judgments rather than absolute ones.\n- If human informants insist on contradictory preference judgments, there is nothing that automated agents can do to be consistent with them. Fortunately, preference judgments made by humans are often open to revision in the light of further consideration.\n\n\n## Sequential Decision Problems\n- MDP more like real world. MDPs have been studied in several fields, including AI, operations research, economics, and control theory.\n#### Agent grids\n- The outcome is stochastic, so write as P(s'|s,a) for p reaching s' if a is done in state s.\n- We will assume that transitions are Markovian: the probability of reaching s' from s depends onl on s and not history of earlier states.\n- To complete the definition of the task environment, we must specify the utility function for the agent. Because the decision problem is sequential, the utility function will depend on a sequence of states and actions—an environment history—rather than on a single state.\n- Every transition from s to s' via a, agent receives reward R(s,a,s'), bounded by +- Rmax.\n- A sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process, or MDP, and consists of a set of states (initial state S0). A set of actions of actions in each state. A transition model P(s'|s,a), and a reward function R(s,a,s').\n- Methods for solving MDPs usually involve dynamic programming.\n\n#### Solution: Policy (pie)\n- No fixed action sequence can solve the problem, because the agent might end up in a state other than the goal.\n- Solution is policy. Therefore, a solution must specify what the agent should do for any state that the agent might reach.\n- Policy is symbol pie. pie(s) is action recommended by policy pie for state s.\n- No matter what the outcome of the action, the resulting state will be in the policy, and the agent will know what to do next.\n- The quality of a policy is therefore measured by the expected utility of the possible environment histories generated by that policy.\n- Represents the agent function explicitly. A description of a simple reflex agent, computed from the information used for a utility-based agent.\n- Often have multiple optimal policies.\n\n#### Utility over time\n- Finite or infinite horizon.\n- With a finite horizon, an optimal action in a given state may depend on how much time is left. So nonstationary policy used.\n- “Infinite horizon” does not necessarily mean that all state sequences are infinite; it just means that there is no fixed deadline.\n- If infinite, potential difficulty is if environment no terminal state/agent never reaches one, all environment histories are infinitely long and utilities with additive undiscounted rewards is finite.\n- Discount factory gamma between 0 and 1. \n- Discount make sense due to preference of early rewards, uncertainty about true rewards. \n- A discount factor of gamma is equivalent to adding a probability  of accidental termination at every time step, independent of the action taken.\n- Agent’s preferences between state sequences are stationary. Means if you prefer a future, preference same no matter when future starts.\n- If gamma < 1, rewards bounded by +- Rmax, utility is finite.\n- If environment contains terminal state and if proper policy, gamma can be 1.\n- Infinite sequences compred in terms of averge reward obtained per time step. But analysis is complex.\n\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n\n#### Optimal policies and the utilities of states\n- Utility of a given history is the sum of discounted rewards\n- Compare policies thru expected utilities obtained when executing them.\n- A remarkable consequence of using discounted utilities with infinite horizons is that the optimal policy is independent of the starting state\n- Action sequence wont be independent. \n- True utility of a state is the expected sum of discounted rewards if the agent executes an optimal policy. Write as U(s).\n- The utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action. \n- Use bellman equation to calculate utilities of state.\n- Optimal policy extracted from Q-function by argmax(Q functions)\n\n\n#### Rewards scales\n- U(s) becomes U'(s)=mU(s) + b, m > 0. Repalce U(s) with reward function. \n- TWO MDPs have same optimal policies if only differ in reward functions.\n- The flexibility afforded by the shaping theorem means that we can actually help out the agent by making the immediate reward more directly reflect what the agent should do.\n\n#### Representing MDPs\n- Big 3 dimensional tables of size |S|^2 |A|. O(|S||A|)\n- Can represent MDPs by extending dynamic Bayesian networks with decision, reward, and utility nodes to create dynamic decision networks.\n- DNN has complexity advantage over atomic representations and can model quite substantial real-world problems.\n\n\n\n## Algorithms for MDPs\n#### Value Iteration\n- Propagating information through the state space by means of local updates\n- The Bellman equation is the basis of the value iteration algorithm for solving MDPs.\n- n possible states means n possible bellman equations, 1 for each state. \n- n equations conatins n unknowns, the state utilities. \n- Equations are non-linear due to max. So cannot solved by linear algebra.\n- We start with arbitrary initial values for the utilities, calculate the right-hand side of the equation, and plug it into the left-hand side—thereby updating the utility of each state from the utilities of its neighbors. We repeat this until we reach an equilibrium.\n- Ui(s) is utility value for state s at ith iteration. It is Bellman Update.\n- The update is assumed to be applied simultaneously to all the states at each iteration.\n- If applied infinitely, guaranteed to reach equilibrium. \n- Contraction. A contraction has only one fixed point; if there were two fixed points they would not get closer together when the function was applied, so it would not be a contraction. When the function is applied to any argument, the value must get closer to the fixed point, so repeated application reaches fixed point in the limit.\n- Measure distances between utility vectors by max norm.\n- Bellman update function beocmes Ui+1 = BUi with Bellman update operator B applied to all states.\n- Can use contraction property to analyze rate of convergence. \n- Terminal condition is |Ui+1 - U| < e\n\n\n \n\n## Module 8 Lecture Notes\n \n\n#### Policy iteration\n- Possible to get an optimal policy even when the utility function estimate is inaccurate.\n- If one action is clearly better than all others, then the exact magnitude of the utilities on the states involved need not be precise.\n- Done by policy evaluation and policy improvement. \n1. Policy evaluation: Given a policy piei, calculate Ui = U piei, the utility of each state if piei were to be executed.\n2. Policy improvement: Calculate a new MEU policy piei+1 using onestep lookahead based on Ui.\n- The algorithm terminates when the policy improvement step yields no change in the utilities.\n- O(n^3)\n-  Instead, we can perform some number of simplified value iteration steps (simplified because the policy is fixed) to give a reasonably good approximation of the utilities.\n- This is modified policy iteration. \n- Asynchronous policy iteration: Pick any subset of states and apply either kind of updating above.\n- The freedom to choose any states to work on means that we can design much more efficient heuristic algorithms\n\n\n#### Linear programming\n- General approach for formulating constrained optimization problems, and there are many industrial-strength LP solvers available.\n- The basic idea of the formulation is to consider as variables in the LP the utilities U(s) of each state s. In LP language, that means we seek to minimize U(s) for all s.\n- This creates a connection from dynamic programming to linear programming, for which algorithms and complexity issues have been studied in great depth.\n- LP solver seldom efficient as dp. \n- Polynomial time sounds  good, but number of states is large. \n\n#### Online algorithms for MDPs\n- Value iteration and policy iteration are offline algorithms. They generate an optimal solution for the problem, which can then be executed by a simple agent.\n- Offline not possible to solve large MDPs. \n- Simplification of the Expectiminimax algorithm for game trees with chance nodes.\n- Expectimax algorithm builds a tree of alternating max and chance nodes. An evaluation function can be applied to the nonterminal leaves of the tree, or they can be given a default value. A decision can be extracted from the search tree by backing up the utility values from the leaves, taking an average at the chance nodes and taking the maximum at the decision nodes.\n- e-horizon useful when discount factor not too close to 1. \n\n\n\n\n## Module 8 Definitions\n* **Transition model** - describes the outcome of each action in each state.\n* **Principle of maximum expected utility (meu)** - a rational agent should choose the action that maximizes the agent’s expected utility\n* **Value function** - in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\n* **Ordinal utility function** - value function\n* **Preference elicitation** - involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n* **Normalized utilities** - see pic. Best u = 1, worst u = 0.\n* ** micromort** - a one in a million chance of death. Value of life.\n* **Qaly** - Quality-adjusted life year. Patients are willing to accept a shorter life expectancy to avoid a disability.\n* **Monotonic preference** - Prefer more to less, with other things equal.\n* **Certainty equivalent ** - Value an agent will accept in lottery of that lottery. Like $400 confirm, not the expected value $500.\n* **Insurance premium** - Diff between EMV and certainty equivalent\n* ** risk-neutral** - agent with linear curve\n* **Unbiased** - E(estimate of a - actual) = 0\n* **Optimizer’s curse** - This tendency for the estimated expected utility of the best choice to be too high\n* **Normative theory** - how a rational agent should act\n* **Descriptive theory** - describes how actual agents—for example, humans—really do act\n* **Allais paradox** - Normative anlysis disagree. There is no utility function that is consistent with these choices\n* **Certainty effect** - Explain irrational preferences. people are strongly attracted to gains that are certain.\n* **Ambiguity aversion** - Most people elect the known probability rather than the unknown unknowns\n* **Anchoring effect** - $200 no one will buy, give $55 discount. \n* **Framing effect** - Wording of problem gives different preference. Like 90% survival > 10% death.\n* **Sequential decision problems** - the agent’s utility depends on a sequence of decisions\n* **Stochastic** - Outcome randomly determined\n* **Markovian** - Does not depend on history.\n* **Policy** - a solution must specify what the agent should do for any state that the agent might reach\n* **Optimal policy** - policy that yields the highest expected utility. Pie*\n* **Finite horizon** - Fixed time N after which nothing matters, like game over.\n* **Nonstationary policy** - Policy that depends on the time\n* **Stationary policy** - Optimal action depends only on the current state\n* **Proper policy** - Guaranteed to reach terminal state. Can use gamma = 1.\n* **Q-function** - E(U) of taking a given action in a given state.\n* **Action-utility function** - Q-function\n* **Contraction** - MDP value iteration converges.\n* **Contraction function exp** - When applied to two different inputs in turn, produces two output values that are “closer together,\n* **Max norm** - measures the “length” of a vector by the absolute value of its biggest component\n* **Policy loss** - Most the agent can lose by executing piei than pie*\n\n\n## WARNING: Your summary of 'AIMA Chapter 22.4 Generalization in Reinforcement Learning' is too long!\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n \n### Bandit\n- An n-armed bandit has n levers. Behind each lever is a fixed but unknown probability distribution of winnings; each pull samples from that unknown distribution.\n- Ubiquitous tradeoff between exploitation of the current best action to obtain rewards and exploration of previously unknown states and actions to gain information.\n- Many definitions of bandit problem. \n1. Each arm is Markov reward process, an MDP with only one possible action. \n2. Overall bandit problem is an MDP.\n\nAn important generalization of the bandit process is the bandit superprocess or BSP, in which each arm is a full Markov decision process in its own right, rather than being a Markov reward process with only one possible action. All other properties remain the same: the arms are independent, only one (or a bounded number) can be worked on at a time, and there is a single discount factor.\n\n### Learning from Rewards\n- An agent interacts with the world and periodically receives rewards that reflect how well it is doing.\n- Goal is maximize the expected sum of rewards, same as MDP.\n- Reinforcement learning differs from “just solving an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. It may not know the transition model or the reward function, and it has to act in order to learn more.\n- Reward function is concise ad easy to specify.\n- Can be general for simulated enviornments, as long as correct reward signals given.\n\n#### Model based reinforcement learning\n- The agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act. The model may be initially unknown, in which case the agent learns the model from observing the effects of its actions, or it may already be known.\n- In partially observable environments, the transition model is also useful for state estimation\n- Model-based reinforcement learning systems often learn a utility function defined in terms of sum of rewards from state s onward.\n\n#### Model free reinforcement learning\n- The agent neither knows nor learns a transition model for the environment. Instead, it learns a more direct representation of how to behave. This comes in one of two varieties:\n1. Action-utility learning: Q learning. Denote sum of rewards from s if a is taken. Agent choose action by finding highest Q value.\n2. Policy search: Agent learns a policy pie(s) that maps directl from states to actions. A reflex agent.\n\n\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n \n\n\n### Passive reinforcement learning\n- The agent’s policy is fixed and the task is to learn the utilities of states (or of state–action pairs); this could also involve learning a model of the environment.\n- Fully observable environment with a small number of actions and states, in which an agent already has a fixed policy pie(s) that determines its actions. \n- The passive learning task is similar to the policy evaluation task.\n- The difference is that the passive learning agent does not know the transition model P(s'|s,a) and reward fucntion R(s,a,s').\n\n### Begin\n- The agent executes a set of trials in the environment using its policy pie.\n- In each trial, the agent starts in state (1,1) and experiences a sequence of state transitions until it reaches one of the terminal states.\n- Each transition is annotated with both the action taken and the reward received at the next state. The object is to use the information about rewards to learn the expected utility \n associated with each nonterminal state.\n- The utility is defined to be the expected sum of (discounted) rewards obtained if policy  is followed.\n\n#### Direct utility estimation\n- Reduce reinforcement learning to a standard supervised learning problem in which each example is a (state, reward-to-go) pair.\n- It ignores an important constraint: The utility of a state is determined by the reward and the expected utility of the successor states.\n- By ignoring the connections between states, direct utility estimation misses opportunities for learning.\n- Direct utility estimation as searching for  in a hypothesis space that is much larger than it needs to be.\n- Violates Bellman, so converges very slowly.\n\n#### Adaptive dynamic programming\n- Takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solving the corresponding Markov decision process using dynamic programming.\n- For a passive learning agent, this means plugging the learned transition model and the observed rewards to calculate the utilities of the states.\n- The environment is fully observable, so learning transition model is easy. \n- Can use modified policy iteration, the model usually changes only slightly with each observation, the value iteration process can use the previous utility estimates as initial values and typically converge very quickly.\n- The ADP agent is limited only by its ability to learn the transition model. Hard to deal with large state spaces.\n- Provides standards against which to measure any other reinforcement learning algorithms.\n\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n\n\n#### Temporal-difference learning\n- Use the observed transitions to adjust the utilities of the observed states so that they agree with the constraint equations.\n- Apply temporary update to utility score if too low or high. \n- Needs learning rate parameter alpha. Decreases as number of times a state has been visited increases, then will converge to correct value. \n- Because this update rule uses the difference in utilities between successive states (and thus successive times), it is often called the temporal-difference (TD) equation.\n- All temporal-difference methods work by adjusting the utility estimates toward the ideal equilibrium that holds locally when the utility estimates are correct. \n- First, notice that the update involves only the observed successor, whereas the actual equilibrium conditions involve all possible next states.\n- the average value of Upie(s) will converge to the correct quantity in the limit, even if the value itself continues to fluctuate.\n\n#### Difference between TD and ADP\n- Different with ADP. TD adjusts a state to agree with its observed successor, whereas ADP adjusts the state to agree with all of the successors that might occur, weighted by their probabilities.\n- This difference disappears when the effects of TD adjustments are averaged over a large number of transitions, because the frequency of each successor in the set of transitions is approximately proportional to its probability. A more important difference is that whereas TD makes a single adjustment per observed transition, ADP makes as many as it needs to restore consistency between the utility estimates U and the transition model .\n- Thus, TD can be viewed as a crude but efficient first approximation to ADP.\n- Each adjustment made by ADP could be seen, from the TD point of view, as a result of a pseudoexperience generated by simulating the current transition model. It is possible to extend the TD approach to use a transition model to generate several pseudoexperiences—transitions that the TD agent can imagine might happen, given its current model. For each observed transition, the TD agent can generate a large number of imaginary transitions.\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \n\n#### Generate efficient version of ADP with TD\n- One possible approach to generating reasonably good answers quickly is to bound the number of adjustments made after each observed transition. One can also use a heuristic to rank the possible adjustments so as to carry out only the most significant ones. \n- The prioritized sweeping heuristic prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n- Using heuristics like this, approximate ADP algorithms can learn roughly as fast as full ADP, in terms of the number of training sequences, but can be orders of magnitude more efficient in terms of total computation.\n- An approximation algorithm can use a minimum adjustment size that decreases as the transition model becomes more accurate. This eliminates the very long runs of value iteration that can occur early in learning due to large changes in the model.\n\n\n### Active Reinforcement Learning\n- An active learning agent gets to decide what actions to take.\n- Begin with ADP.\n- First, the agent will need to learn a complete transition model with outcome probabilities for all actions, rather than just the model for the fixed policy. The learning mechanism used by Passive-ADP-Agent will do just fine for this. \n- Next, we need to take into account the fact that the agent has a choice of actions. The utilities it needs to learn are those defined by the optimal policy; they obey the Bellman equations\n- These equations can be solved to obtain the utility function  using the value iteration or policy iteration algorithm.\n- Having obtained a utility function  that is optimal for the learned model, the agent can extract an optimal action by one-step look-ahead to maximize the expected utility.\n\n### GLIE\n- One simple way is to have the agent choose a random action at time step t with probability 1/t and to follow the greedy policy otherwise.\n- While this does eventually converge to an optimal policy, it can be slow.\n- A better approach would give some weight to actions that the agent has not tried very often, while tending to avoid actions that are believed to be of low utility.\n- This can be implemented by altering the constraint equation so that it assigns a higher utility estimate to relatively unexplored state–action pairs.\n- Has exploration function f. It determines how greed (preference for high values of utility u) is traded off against curiosity (preference for actions that have not been tried often and have a low count n).\n- f increases in u and decreases in n. \n- The fact that U+ rather than U appears on the right-hand side of Equation is very important. As exploration proceeds, the states and actions near the start state might well be tried a large number of times. \n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n\n#### Approaches for safe exploration\n1. Bayesian reinforcement learning\n- assumes a prior probability P(h) over hypotheses h about what the true model is.\n- The posterior probability P(h|e) is obtained in the usual way by Bayes’ rule given the observations to date. \n- Then, if the agent has decided to stop learning, the optimal policy is the one that gives the highest expected utility.\n- Let Upieh be the expected utility, averaged over all possible start states, obtained by executing policy pie in model h.\n- When continue to learn in future, finding optimal policy is harder, because agent must consider effects of future observations on its beliefs about the transition model.\n- Problem becomes exploration POMDP. Should solve this before entering real world to get a complete strategy that tells the agent what to do next given any possible percept sequence.\n- Unable to prevent untimely death. \n2. Robust control theory\n- Allows for a set of possible models H without assigning probabilities to them, and defines an optimal robust policy as one that gives the best outcome in the worst case over H.\n- The robust control approach can be considered as a game between the agent and an adversary, where the adversary gets to pick the worst possible result for any action, and the policy we get is the minimax solution for the game.\n- Related to Bayesian approach, because set H will be the set of models that exceed some likelihood threshold on P(h|e).\n- The problem with the worst-case assumption is that it results in overly conservative behavior.\n- First way to improve is record series of actions by an experienced teacher, so that the system will act reasonably from the start, and can learn to improve from there.\n- A second way is for a human to write down constraints on what a system can do, and have a program outside of the reinforcement learning system enforce those constraints.\n\n\n### Temporal-difference Q-learning\n- The most obvious change is that the agent will have to learn a transition model so that it can choose an action based on U(s) via one-step look-ahead.\n- TD Q-learning agent does not need a transition model either for learning or for action selection.\n- Avoids the need for a model by learning an action-utility function Q(s,a) instead of a utility function U(s)\n- Knowing the Q-function enables the agent to act optimally simply by choosing argmaxa Q(s,a), with no need for look-ahead based on a transition model.\n- Model-free methods can be applied even in very complex domains because no model need be provided or learned.\n- No means to look into future, so it may have difficulty when rewards are sparse and long action sequences must be constructed to reach them.\n- Off-policy learning algorithm.\n- Answer the question “What would this action be worth in this state, assuming that I stop using whatever policy I am using now, and start acting according to a policy that chooses the best action (according to my estimates)?”\n\n\n### SARSA, similar to Q-learning\n- On-policy algo.\n- Answer the question “What would this action be worth in this state, assuming I stick with my policy?”\n- SARSA updates with the Q-value of the action a' that is actually taken.\n- State, action, reward, state, action.\n- SARSA is appropriate if the overall policy is even partly controlled by other agents or programs, in which case it is better to learn a Q-function for what will actually happen rather than what would happen if the agent got to pick estimated best actions. \n\n\n### Generalization in Reinforcement Learning\n- Backgammon is simpler than most real-world applications, yet it has about 10^20 states.\n- Reinforcement learnin algo learn like 20 vales that is a good approximation to the true utility function.\n- Sometimes this approximate utility function is combined with look-ahead search to produce more accurate decisions.\n- Adding look-ahead search means that effective behavior can be generated from a much simpler utility function approximator that is learnable from far fewer experiences.\n- Function approximation makes it practical to represent utility (or Q) functions for very large state spaces, but more importantly, it allows for inductive generalization: the agent can generalize from states it has visited to states it has not yet visited.\n\n\n\n\n## Module 9 Lecture Notes\n \n\n### Hierarchical reinforcement learning\n- Cope with very long action sequences. Break them up into a few smaller pieces, and then break those into smaller pieces still, and so on until the action sequences are short enough to make learning easy.\n- Begins with a partial program that outlines a hierarchical structure for the agent’s behavior.\n- The partial-programming language for agent programs extends any ordinary programming language by adding primitives for unspecified choices that must be filled in by learning.\n- The partial program can be arbitrarily complicated, as long as it terminates.\n- We simply provide the trivial partial program that allows the agent to keep choosing any action from A(s), the set of actions that can be executed in the current state s.\n- The learning process converts the partial agent program into a complete program by learning how each choice should be made.\n- Each of these choices invokes a subroutine that may itself make further choices, all the way down to primitive actions that can be executed directly. \n- The theoretical foundations of HRL are based on the concept of the joint state space, in which each state  is composed of a physical state  and a machine state .\n- The machine state is defined by the current internal state of the agent program: the program counter for each subroutine on the current call stack, the values of the arguments, and the values of all local and global variables.\n- Effective method for learning complex behaviors.\n\n\n### Policy search\n- The simplest of all the methods.\n- The idea is to keep twiddling the policy as long as its performance improves, then stop.\n- Policy pie is function that maps states to actions, we are interested primarily in parameterized representations of pie that have far fewer parameters than there are states in the state space.\n- We could represent pie by a collection of parameterized Q-functions, one for each action, and take the action with the highest predicted value\n- Each Q-function could be a linear function. Or a nonlinear function such as a deep neural network\n- Policy search will then adjust the parameters  to improve the policy.\n- But process not same as Q-learning. \n- It finds value of feature that results in good performance and not the optimal Q-function in Q-learning. Values found can be very different.\n- Problem: The policy is a discontinuous function of the parameters when the actions are discrete.\n- There will be values of  such that an infinitesimal change in feature causes the policy to switch from one action to another.\n- This means that the value of the policy may also change discontinuously, which makes gradient-based search difficult. For this reason, policy search methods often use a stochastic policy representation.\n- Can use softmax function. Normalize. \n- When the environment (or the policy) is nondeterministic, things get more difficult.\n\n### Unreliable result from undeterministic policy\n- The problem is that the total reward for each trial may vary widely, so estimates of the policy value from a small number of trials will be quite unreliable; trying to compare two such estimates will be even more unreliable.\n- One solution is simply to run lots of trials, measuring the sample variance and using it to determine that enough trials have been run to get a reliable indication of the direction of improvement.\n- Unfortunately, this is impractical for many real problems in which trials may be expensive, time-consuming, and perhaps even dangerous.\n\n \n\n## Module 9 Definitions\n* **Stopping time** - Pull first arm T times, T is stopping time. \n* **Gittins index** - Reward achieved through a stochasitic process. \n* **Direct utility estimation** - utility of state is expected total reward from that state onward and each trial provides a sample of this quantity for state visited.\n* **Temporal-difference equation** - Temporal-difference learning's equation.\n* **Prioritized sweeping** - Generate efficient version of ADP with TD section.\n* **Greedy agent** - takes the action that it currently believes to be optimal at each step.\n* **Absorbing state** - No actions have any effect and no rewards are received\n* **Exploration pomdp** - belief states are distributions over models\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n* **Catastrophic forgetting** - see 22_4 ATDL\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n### Acting under Uncertainty\n- Logical agents keep track of a belief state, and generating a contingency plan that handles every possible eventuality that its sensors may report during execution.\n- This works on simple problem, but has drawbacks:\n1. The agent must consider every possible explanation for its sensor observations, no matter how unlikely. This leads to a large belief-state full of unlikely possibilities\n2. A correct contingent plan that handles every eventuality can grow arbitrarily large and must consider arbitrarily unlikely contingencies.\n3. Sometimes there is no plan that is guaranteed to achieve the goal—yet the agent must act. It must have some way to compare the merits of plans that are not guaranteed.\n- Agent's knowledge cannot guarantee any of these outcomes to achieve, but can provide some degree of belief that they will be achieved.\n- A rational right decision: depends on both the relative importance of various goals and the likelihood that, and degree to which, they will be achieved.\n\n### Rule making\n- Make rules logically exhaustive. \n- Agent’s knowledge can at best provide only a degree of belief in the relevant sentences.\n- Logic to cope with domains like medical diagnosis fails due to:\n1. Laziness: It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n2. Theorectical ignorance: Medical science has no complete theory for the domain.\n3. Practical ignorance: Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n- Main dealing with degree of belief is probability theory.\n- A logical agent believes each sentence to be true or false or has no opinion, whereas a probabilistic agent may have a numerical degree of belief between 0 (for sentences that are certainly false) and 1 (certainly true).\n- So epistemological commitments are different. \n\n### Uncertainty and rational decisions\n- To make such choices, an agent must first have preferences among the different possible outcomes of the various plans.\n- We use utility theory to represent preferences and reason quantitatively with them.\n- The utility of a state is relative to an agent.\n- The fundamental idea of decision theory is that an 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- The above line is principle of maximum expected utility MEU. \n- Belief state includes possibilties and probabilities for world state. \n### \n\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \n### Basic probability Notation\n- The possible worlds are mutually exclusive and exhaustive.\n- Probabilities like P(Total = 11) are unconditional or prior probabilities.\n- Usually interested in conditional or posterior probability, situation with evidence. Rolling double given first dice is 5.\n- When making decisions, an agent needs to condition on all the evidence it has observed.\n- It is also important to understand the difference between conditioning and logical implication.\n- P(Cavity|toothache) = 0.6 means whenevr toothache is true and no other info, cavity is 60%.\n\n### The language of propositions in probability assertions\n- Range of Total for two dice is set {2,...,12}\n- Probability density functions (sometimes called pdfs) differ in meaning from discrete distributions.\n- PDFs uniform between 18C to 26C means 100% within this 8C and 50% 4C-wide region.\n- Comma used for distribution for multiple variables. Like P(Weather, Cavity), probability or weather AND cavity.\n\n### Probability axioms and their reasonableness\n- The basic axioms of probability imply certain relationships among the degrees of belief that can be accorded to logically related propositions.\n\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n### Inference Using Full Joint Distributions\n- For probabilistic inference, we use full joint distribution as the knowledge base from which answers to all questions may be derived.\n- Unconfitional/Marginal probability is P(A)\n\n### full joint distribution\n- Does not scale well. \n- O(2^n)\n- Each of the probability has to be estimated separately, astronomical number.\n- Seldom a practical tool for building reasoning systems. \n- Should be viewed as the theoretical foundation on which more effective approaches may be built.\n\n\n\n## AIMA Chapter 12.4 Independence\n \n### Independence\n- Independence assertions can help in reducing the size of the domain representation and the complexity of the inference problem.\n- Unfortunately, clean separation of entire sets of variables by independence is quite rare. \n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n### Bayes’ Rule and Its Use\n- Bayes' rule underlies most modern AI systems for probabilistic inference.\n- Diagnostic knowledge is often more fragile than causal knowledge.\n- O(2^n) possible combinations.\n- In general, for n symptoms that are all conditionally independent given Cavity, the size of the representation grows as O(n) instead of O(2^n).\n- That means that conditional independence assertions can allow probabilistic systems to scale up; moreover, they are much more commonly available than absolute independence assertions.\n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n### Naive Bayes Models\n- Often used (as a simplifying assumption) in cases where the “effect” variables are not strictly independent given the cause variable.\n- The naive Bayes model is sometimes called a Bayesian classifier, a somewhat careless usage that has prompted true Bayesians to call it the idiot Bayes model.\n- In practice, naive Bayes systems often work very well, even when the conditional independence assumption is not strictly true.\n- Naive Bayes models are widely used for language determination, document retrieval, spam filtering, and other classification tasks.\n- Not for medical diagnosis, where the actual values of the posterior probabilities really matter.\n\n### Naive equation steps (See pic)\n-  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. The run time of this calculation is linear in the number of observed effects and does not depend on the number of unobserved effects (which may be very large in domains such as medicine). We will see in the next chapter that this is a common phenomenon in probabilistic inference: evidence variables whose values are unobserved usually “disappear” from the computation altogether\n\n### Text classification with naive Bayes\n- given a text, decide which of a predefined set of classes or categories it belongs to.\n- The task is to classify each sentence into a Category. The major sections of newspaper.\n- naive Bayes consist of prior prbabilities P(Category) and conditional probabilities P(HasWordi|Category).\n- To categorize a new document, we check which key words appear in the document and then apply Equation to obtain the posterior probability distribution over categories.\n-  If we have to predict just one category, we take the one with the highest posterior probability\n- The naive Bayes model assumes that words occur independently in documents, with frequencies determined by the document category.\n- This independence assumption is clearly violated in practice.\n- The violation of independence usually means that the final posterior probabilities will be much closer to 1 or 0 than they should be; in other words, the model is overconfident in its predictions.\n- On the other hand, even with these errors, the ranking of the possible categories is often quite accurate.\n\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n### Unigram model\n- Simplest case\n\n### Bigram model\n- Condition on the previous word\n\n### N-gram model\n- In general, insufficient model of language\n- Because language has long-distance dependencies\n- But can often get away with N-gram model\n\n### Problems for MLE\n- Test VS Train set not same. Train does not contain set. So assign 0.\n- Out of vocabulary items (OOV).\n- Fixed lexicon L of size V\n- Avoid zeroes with smoothing.\n\n### Practical issues\n- We do everything in log space to avoid underflow. Adding is also faster than multiplying. \n\n \n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states that it might be in\n* **Laziness** - Too much work required to do exhaustive search, or too hard, so cant do it. \n* **Epistemological commitments** - See 12_1 rule making.\n* **Theory of probability** - Provides a way of summarizing the uncertainty that comes from our laziness and ignorance, and solves qualification problem.\n* **Utility theory** - every state has a degree of usefulness/utility, to an agent and that the agent will prefer states with higher utility\n* **Decision theory** - probability theory + utility theory\n* **Probability model** - Associates a numerical probability  with each possible world\n* **Unconditional or prior probabilities** - Refer to degrees of belief in propositions in the absence of any other information.\n* **Evidence** - Some information that has already been revealed. Like first dice already showing 5.\n* **Random variables** - Names begin with an uppercase letter.function that maps from the domain of possible worlds  to some range\n* **Probability density function** - define the probability that a random variable takes on some value x as a paramaterized function of x\n* **Probabilistic inference** - the computation of posterior probabilities for query propositions given observed evidence\n* ** unconfitional/marginal probability** - P(A) alone.\n* **Marginalization** - Sum up probabilities for each possible value of the other variables, thereby taking them out of the equation.\n* **Text classification** - given a text, decide which of a predefined set of classes or categories it belongs to.\n* **Posterior probability erm** - conditional probability given the relevant evidence or background\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \n### Representing Knowledge in an Uncertain Domain\n#### Bayesian network\n- represent the dependencies among variables\n- Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely\n- A directed graph in which each node is annotated with quantitative probability information\n- Once the topology of the Bayes net is laid out, we need only specify the local probability information for each variable, in the form of a conditional distribution given its parents.\n- The full joint distribution for all the variables is defined by the topology and the local probability information.\n- The syntax of a Bayes net consists of a directed acyclic graph with some local probability information attached to each node. \n\n#### Full specification of Bayesian network\n- Each node corresponds to a random variable, which may be discrete or continuous.\n- Directed links or arrows connect pairs of nodes. If there is an arrow from node X to node Y, x is said\nto be a parent of Y. he graph has no directed cycles and hence is a directed acyclic graph, or DAG.\n- Each node X, has associated probability information delta(Xi|Parents(Xi)), delta is feature, that quantifies the effect of the parents on the node using a finite number of parameters.\n\n#### conditional probability table\n- The local probability information attached to each node \n- Each row in a CPT contains the conditional probability of each node value for a conditioning case.\n- A conditioning case is just a possible combination of values for the parent nodes—a miniature possible world.\n- Each row must sum to 1, because the entries represent an exhaustive set of cases for the variable.\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n### Joint distribution semantics\n- Each entry in the joint distribution is represented by the product of the appropriate elements of the local conditional distributions in the Bayes net.\n- parents(Xi) denotes values of Parents(Xi) that appears in x1,...,xn.\n\n### A method for constructing Bayesian networks\n- First, we rewrite the entries in the joint distribution in terms of conditional probability, using the product rule.\n- Actually just chain rule.\n\n### Runtime\n- In general, noisy logical relationships in which a variable depends on k parents can be described\nusing O(k) parameters instead of O(2^k)\n\n### Bayesian nets with continuous variables\n- Many real-world problems involve continuous quantities, such as height, mass, temperature, and money. By definition, continuous variables have an infinite number of possible values, so it is impossible to specify conditional probabilities explicitly for each value.\n- One way to handle is with discrtization. \n- Like temperature is below 0, 0 to 100, above 100.\n- Tradeoff between loss of accuracy and large CPTs which can lead to slow run times.\n- Another approach is to define a continuous variable using one of the standard families of probability density functions.\n\n### hybrid Bayesian network\n- To specify a hybrid network, we have to specify two new kinds of distributions\n- the conditional distribution for a continuous variable given discrete or continuous parents\n- and the conditional distribution for a discrete variable given continuous parents\n\n### linear–Gaussian conditional distribution\n- A network containing only continuous variables with linear–Gaussian distributions has a joint distribution that is a multivariate Gaussian distribution over all the variables.\n- Furthermore, the posterior distribution given any evidence also has this property.\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n### The variable elimination algorithm\n- The idea is simple: do the calculation once and save the results for later use. This is a form of dynamic programming. \n- Variable elimination works by evaluating expressions in right-to-left order or bottom up.\n- Intermediate results are stored, and summations over each variable are done only for those portions of the expression that depend on the variable.\n\n \n\n## Module 11 Lecture Notes\n \n- Models are always simplifications, may not account for every variable and inetractions. \n- Two variables are independent if P(x,y) = P(x)P(y)\n- Bayes' net's joint distribution may have further conditional independence that is not detectable until you inspect its specific distribution.\n\n#### Bayes net semantics\n- A set of nodes, one per variable X\n- A directed, acyclic graph\n- A conditional distribution for each node. A colelction of distributions over X, one for each combination of parents' values. P(X|a1,...,an)\n- Topology + local conditional probabilities \n\n### Casuality\n- Bayes' nets reflect true casual patterns. Easy to think about.\n- BNs need not actually be casual. Sometimes no casual net exisst over domain. End up with arrows reflect correlation, not causation.\n- Arrow means topology may happen to encode casual structure or really encodes conditional independence.\n\n### Size\n- 2^n for joint distribution over N boolean variables\n- N-node net if nodes have up to k parents O(N* 2^{k+1})\n\n### Assumptions\n- P(Xi|x1... xi-1) = P(xi | parents(Xi))\n\n### Independence\n- D-separation gives precise conditional independence guarantees from graph alone\n- If one or more path is active, the independence not guaranteed.\n- If all paths are active, then independence is guaranteed.\n- A path is active if each triple is active. \n\n### Inference\n- Calculating some useufl quantity from a joint probability distribution.\n- To infer by enumeration given evidence e, query Q, hidden vriables H (all variables). Want P(Q|all evidences)\n1. Select entries consistent with evidence\n2. Sum out H(hidden variable) to get joint of query and evidence\n3. Normalize by multiplying 1/Z. Z = summation of P(Q, evidences) for all q.\n- Given unlimited time, inference in BNs is easy\n- Inference by enumeration slow because you join up whole joint distribution before you sum out hidden variables.\n- Advaced technique: Variable elimination. Interleave joining and marginalizing. Still NP-hard, but much faster.\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n* **Topology ** - the set of nodes and links—specifies the conditional independence relationships that hold in the domain,\n* **Arrow** - X has direct influence on Y, causes should be parents of effects\n* **Semantics ** - defines how the syntax corresponds to a joint distribution over the variables of the network\n* **Conditionally independent** - Each variable is conditionally independent of its non-descendants, given its parents.\n* **Moral graph** - Add links between any unlinked pair of nodes that share a common child;\n* ** ancestral subgraph** - XYZ and their ancestorys\n* **Context-specific independence** - if a variable is conditionally independent of some of its parents given certain values of others.\n* **Discretization** - dividing up the possible values into a fixed set of intervals\n* **Hybrid bayesian network** - A network with both discrete and continuous variables\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n \n#### Linear separators\n- Use support vector machine to find line of best linear fit\n- Mazimising the margin, good according to intuition, theory, practice\n- Only support vector matter, others ignorable\n- SVMs are MIRA where you optimize over all examples at once.\n\n#### Comparing NB and Perceptrons/MIRA\n- NB builds a model training data, gives prediction probabilities, strong assumptions about feature independence, one pass through data\n- Perceptrons/MIRA: Makes less assumptions about data, mistake-driven learning, multiple passes through data(prediction), often more accurate\n\n#### Perceptron\n- Many inputs each with a weight, goes to weighted sum, and then activation function with threshold to give output.\n- Output is 0 if sum of weight <= threshold. 1 if more than threshold.\n- Used for all kinds of classification problems\n- Inputs are features representing what we want to classify\n- Feature values for inputs are fixed, but we can choose different weight vectors.\n- A complex network of perceptrons could make quite subtle decisions\n\n#### Non-linear separators\n- Data that is linearly seprable works out great for linear decision rules.\n- General idea is that original feature space can always be mapped to some higher dimensional feature space where training set is separable.\n\n#### Activation functions\n- Non-linear function\n- y = a = f(z), y is output of neural network, a is activation function output\n- 3 commonly used non-linear functions for the f above are sigmoid function, tanh and rectified linear unit ReLU\n- Sigmoid: y = 1/(1+e^{-z})\n\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n \n## Perceptrons\n#### linear classifiers\n- Inputs are feature values\n- Each feature has weight\n- Sum is activation\n- Activationw (x) = w * f(x) = sum of wi * fi(x)\n- If activation +ve, output+1, -ve output -1.\n\n#### Binary decision rule\n- In space of feature vectors, examples are points, any weght vector is hyperplane.\n- One side is y=+1 when w*f(x)>=0, other is y=-1 when w*f(x) < 0.\n- Start with weight = 0\n- For each training instance, classify current weights, if correct (y=y*), no change, if wrong, adjust weight vector.\n- w = w + y* X f. \n\n#### Multiclass decision rule\n- A weight vector for each class. wy\n- Score(activation) of a class y: wy * f(x)\n- Prediction highest score wins. y = argmaxy of wy*f(x)\n- Steps\n1. Start with all weights = 0\n2. Pick up training examples one by one\n3. Predict with current weights y = argmaxy of wy*f(x)\n4. If correct, no change. If Wrong, lower score of wrong answer, raise score of right answer.\n- wy = wy - f(x), wy* = wy* + f(x)\n\n#### Properties of perceptions\n- Separability\n- Convergence\n- Mistake bound\n\n#### Problems\n- Noise: if data isnt separable, weights might thrash. Averaging weight vectors over time can help.\n- Mediocre generlization: Finds a barely separating solution\n- Overtaining: test/held-out accuracy usually rises then falls. A kind of overfitting. \n\n#### Fix perceptron\n- Adjust weight update to mitigate effects\n- MIRA*: choose update size that fixes current mistake, minimize change to w\n- Minimum of t is not 0. It is where equality holds.\n\n#### Maximum step size\n- Bad to make too large updates\n- Example may be labeled incorrectly\n- May not have enough features\n- Solution is cap the maximum possible value of t with some constant C.\n- Corresponds to an optimization that assumes non-separable data\n- Usually converges faster than perceptron\n- Usually better on noisy data\n\n\n \n\n## Module 12 Lecture Notes\n \n### Spam classification\n- Setup with large collection of example emails, labeled smap or ham. \n- Attributes used to make the ham/spam decision.\n### Digit recognition\n- Input is image/pixel grids\n- Setup with large collection of example images, each labeled with a digit\n\n### Model based classification\n- Model based approach is to build a model like Bayes' net, where both label and features are random variable.\n- Instatiate any observed features\n- Query for distribution of label conditioned on features\n- Challenge is structure to use and how to learn param.\n\n### Naive Bayes for Digits\n- One feature variable Fij for each grid position i,j.\n- Feature values are on/off, based on whether intensity of more or less than 0.5 in underlying image.\n- Each input maps to a feature vector. Like F0,0 = 0, F0,1 = 1.\n\n### NB for text\n- Bag-of-wordsNB: Wi is word at position i is feature. Features conditionally independent given label. Insensitive to word order.\n- Each Wi is identically distributed. \n- Bestto do in homogenous cases like all features are words\n\n### General naive bayes\n- Total num of parameters is linear in number of features.\n- Simple\n- Specify how each feature depends on the class\n- We need inference method and estimate of local conditional probability tables..\n- Need P(Y), the prior over labels. P(Fi|Y) for each feature.\n\n### Inference for Naive Bayes\n- Get joint probability of label and evidence for each label\n- Sum to get probability of evidence\n- Normalize by dividing step 1 by step 2\n\n#### Training data\n- Labeled instances data like training/held out/test set\n- Features: Attribute-value pairs which characterize each x\n- Experiment cycle: Learn param on training set, tune hyperparameters on held-out set, compute accuracy test set\n#### Held-out data\n- Evaluation accuracy: fraction of instances predicted correctly\n#### Test data\n- Overfitting and generalization.\n- Need to smooth or regularize estimates\n\n### Parameter estimation\n- Estimate distribution of random variable thru elicitation or empirically\n- Laplace smoothing, k is length of prior\n- Laplace for conditionals (smooth each condition independently)\n- Linear interpolation\n\n### Do about errors\n- Need more features, add info source as new variables in NB model\n\n\n\n\n \n\n## Module 12 Definitions\n* **Naive bayes** - Assume all features are independent effects of the label.\n* **Overfitting** - Fit training data very closely, but not generalizing well.\n* **Elicitation** - Ask a human\n* **Empirically param estimation** - count(x) / total samples is empiracal rate\n* **Laplace smoothing** - Pretend you saw every outcome once more than you actually did\n* **Linear interpolation** - Get empirical P(X) from data\n* **Baseline** - Help determine how hard the task is, how good accuracy is. For research, use strong baseline.\n* **Confidence** - Represent how sure the classififer is of the classification. Any probmodels have confidences. No guarantee correct.\n* **Weak calibration** - Higher confidence higher accruacy. \n* **Strong calibration** - Confidence predicts accuracy. \n* **Separability** - True if some param get training set perfectly correct\n* **Convergence** - If training is separable, perceptron will eventually converge\n* **Mistake bound** - Maximum num of mistakes (binary case) related to the margin or degree of separability. Mistake <k/d^2\n* **Tanh function** - The tanh function is a variant of the sigmoid function and maps outlier values toward the mean.\n* **Relu** - ReLU activation function is an activation function defined as the positive part of its argument\n* **Relu2** - A piecewise linear function that will output the input directly if it is positive, otherwise, it will output zero.\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 \n\n### Logistic regression\n- Like the Perceptron, logistic regression uses a vector of weights and a bias term.\n- z = w*x + b\n- Instead of outputting z directly, logistic regression transforms it with the sigmoid\nfunction σ(z).\n\n### Sigmoid neurons\n- Problem: a small change in the weights or bias of any single perceptron in the network\ncan causes the output to completely flip from 0 to 1.\n- This is solution.\n- output = sigma(w*x + b)\n- sigma(z) = 1/ (1+ e^-z)\n- Smoothness of sigma means that small changes in the weights wj and in the bias b will\nproduce a small change the output from the neuron.\n- Δoutput is a linear function of the changes Δwj and Δb\n- This makes it easy to choose small changes in the weights and biases to achieve any\ndesired small change in the output\n\n### Feed Forward Neural Network\n- The simplest kind of NN\n- Multilayer network, all units are usually fully-connected, and no cycles.\n- The outputs from each layer are passed to units in the next higher layer, and no\noutputs are passed back to lower layers.\n- A single hidden unit has parameters w (the weight vector) and b (the bias scalar).\n- We represent the parameters for the entire hidden layer by combining the weight\nvector wi and bias bi for each unit i into a single weight matrix W and a single bias\nvector b for the whole layer.\n- The advantage of using a single matrix W for the weights of the entire layer is the\nhidden layer computation can be done efficiently with simple matrix operations.\n- The computation has three steps:\n1. multiplying the weight matrix by the input vector x,\n2. adding the bias vector b, and\n3. applying the activation function g (such as Sigmoid)\n- The output of the hidden layer, the vector h, is thus the following, using the sigmoid\nfunction σ: h = σ(Wx+b)\n- Like the hidden layer, the output layer has a weight matrix U.\nIts weight matrix is multiplied by its input vector (h) to produce the intermediate output z. z = Uh\n- Here are the final equations for a feedforward network with a single hidden layer,\nwhich takes an input vector x, outputs a probability distribution y, and is parameterized\nby weight matrices W and U and a bias vector b:\n- h = σ(Wx+b)\n- z = Uh\n- y = softmax(z)\n- Like with logistic regression, softmax normalizes the output and turns it into a\nprobability distribution.\n\n#### Training neural network\n- Need loss function, cross entropy loss.\n- An optimization algorithm, gradient descent.\n- A way of computing the gradient of loss function, error propagation.\n\n#### Computation graphs\n- Although backpropagation was invented for neural nets, it is related to general\nprocedure called backward differentiation, which depends on the notion of\ncomputation graphs.\n- A computation graph represents the process of computing a mathematical expression.\nThe computation is broken down into separate operations. Each operation is a node in\na graph.\n\n \n\n## SLP Chapter 7.7 Training the neural language model\n \n\n#### Mini-batch training\n- Stochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\n- An alternate is batch training, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\n- A commonly used compromise is mini-batch training, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n#### Regularization\n- Regularization is a way to penalize large weights. A regularization term is added to\nthe loss function.\n- Overfitting is a problem with many machine learning models. Overfitting results in\npoor generalization and poor performance on unseen test set.\n- In logistic regression, if a feature only occurs in one class then it will get a high weight.\nSometimes we are just modelling noisy factors that just accidentally correlate with the\nclass.\n- Lasso regression uses L1 regularization\n- Ridge regression uses L2 regularization\n\n#### Multinomial logistic regression\n- Instead of binary classification, we often want more than two classes. For sentiment\nclassification we might extend the class labels to be positive, negative, and neutral.\n- We want to know the probability of y for each class c ∈ C, p(y = c|x).\n- To get a proper probability, we will use a generalization of the sigmoid function\ncalled the softmax function.\n\n#### Softmax function\n- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of\nvalues normalized into probabilities.\n\n \n\n## Module 13 Lecture Notes\n \n### Classifier components\n- ML classifiers require a training corpus of M observations input/output pairs xi yi.\n1. A feature representation of the input. For each input observation xi, there will be vector of features x1..xn.\n2. A classification function that computes the estimated class y cap via p(y|x)\n3. An objective function for learning, usually involving minimizing error on training examples.\n4. An algorithm for optimizing the objective function.\n\n#### Sentiment classifier\n- Output positive 1 or negative 0\n- Estimate P(y=1 |x) give a vector of features x1,...,xn. \n- Logistic regression solves this task by learning from a training set, a vector of weights and bias term\n- z = w*x + b\n- z = sum of wixi + b\n- Each x has a weight, value * weight = product, sum all products to get final z.\n- Then use sigmoid function, sigmoid(z) to get final one.\n\n#### Learning in losgistic regression\n- Require 2 components to learn params (weights + bias) via learning. \n1. Loss function/objective function, tells us distance between the system output and the gold output. We use cross-entropy loss.\n2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function.\n\n#### Loss functions\n- Determine for some observation x how close the classifier output ycap = sigmoid(w*x + b) is to the correct output (y, which is 0 or 1)\n- L(ycap, y) = how much ycap differs from the true y\n- One example is mean squared error\n- We use loss function that prefers correct class labels of training example to be more likely.\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximise log probabilities of true labels in training data.\n- The resulting loss function is negative log likelihood loss, more commonly called cross entropy loss.\n- We want loss to be smaller if model's estimate is close to correct, and we want the loss be bigger if it is confused.\n\n#### Gradient descent\n- Find good parameters. Find good settings for weights and bias by minimizing loss function. \n- Gradient descent is a method that finds minimum of a function by figuring out in which direction the function's slope is rising the most steeply, and moving in th opposite direction.\n- Can find minimum iteratively since convex.\n- The magnitude of amount to move in gradient descent is value of slope weighted by a learning rate n.\n- Higher/faster learning rate means we should move w more on each step.\n- The gradient is difference between true y and estimate for x, multiplied by corresponding input value xj.\n\n\n\n\n \n\n## Module 13 Definitions\n* **Decision boundary** - That 0.5 for >0.5 is 1, below 0.5 is 0.\n* **Convex** - A convex function has 1 minimum, wont be stuck. In LR, loss function is convex.\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 \n### Word meaning\n1. Synonyms – words that have similar meanings\n2. Antonyms – words that have opposite meanings\n3. Connotations – words that are positive or negative\n4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\npurchasing event\n5. Support for entailment\n\n### Term Document Matrix\n- Each column vector represents a document\n- Each row vector represents a term\n- Value in cell is based on how often that term occurred in that document\n- Length of document vectors is the size of the vocabulary\n- Measure how similar two documents are by comparing their column vectors\n- Compare row vector to know which one is more positive or negative. \n- Normalize word vectors to get more accurate representation of sentiment, divided by its L2 length. \n- Cosine does L2 normalization too. Cosine angle between vectors tell about similarity, larger the less similar. \n\n### Term term matrix / Term context matrix\n- Word X Word matrix\n- Length of vector is |V|\n- Value in cell indicates how often the X word appears in a context window surrounding Y word\n- Context window is w-2, w-2, targetword, w+1, w+2\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \n\n\n### TF-IDF\n#### Term frequency\n- How often a word occurred in a document\n#### Inverse document frequency\n- 1 over the number of documents that it occurred in\n#### Space VS dense vectors\n- Co-occurrence matrix (weighted by TFIDF or mutual information)\n1. Long (length |V| = 50000+)\n2. Sparse (most elements are zeros)\n- Alternative: Learn vectors that are short (length 200~1000) and dense (most elements are non-zero)\n\n### Language modeling\n- Goal is to learn a function that returns the joint probability\n- Primary difficulty:\n1. There are too many parameters to accurately estimate. This is sometimes called the “curse of dimensionality”\n2. In n-gram-based models we fail to generalize to related words / word sequences that we have observed.\n- Deal with unseen sequences (new combination of n words) by back-off or smoothing/interpolation.  \n\n### Neural Language models\n- Neural Language models have several advantages over n-gram LMs:\n1. They don’t need smoothing\n2. They can handle much longer histories.\n3. They can generalize over contexts of similar words.\n4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n- Disadvantage: slower to train than traditional n-gram LMs\n- Steps:\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n3. Simultaneously learn the word vectors and the parameters of the function.\n- The word vectors are low-dimensional (d=30 to d=100) dense vectors, like we’ve seen\nbefore.\n- The probability function is expressed the product of conditional probabilities of the\nnext word given the previous word, using a multi-layer, feed forward neural network.\n- Output layer, hidden layer, projection layer, input layer, input words.\n\n#### NLM IO\n- The input to the neural network is a k-gram of words w1:k.\n- The output is a probability distribution over the next word.\n- The k context words are treated as a word window. Each word is associated with an\nembedding vector\n- The input x is fed into a neural network with 1 or more hidden layers:\n\n\n \n\n## SLP Chapter 6.11 Bias and Embeddings\n \n\n### Training NLM\n- The training examples are simply word k-grams from the corpus\n- The identities of the first k-1 words are used as features, and the last word is used as\nthe target label for the classification.\n- Conceptually, the model is trained using cross-entropy loss.\n\n### Advantages\n- Better results. They achieve better preplexity scores than SOTA n-gram LMs.\n- Larger N. NN LMs can scale to much larger orders of n. This is achievable because\nparameters are associated only with individual words, and not with n-grams.\n- They generalize across contexts.\n- A by-product of training are word embeddings\n\n### Neural Probabilistic LM\n- 1. Use a vector space model where the words are vectors with real\nvalues ℝm. m=30, 60, 100. This gives a way to compute word\nsimilarity.\n- 2. Define a function that returns a joint probability of words in a\nsequence based on a sequence of these vectors.\n- 3. Simultaneously learn the word representations and the probability\nfunction from data.\n- Seeing one of the cat/dog sentences allows them to increase the\nprobability for that sentence and its combinatorial # of “neighbor”\nsentences in vector space.\n\n### Get dense vectors\n- Train a classifier\n1. Treat the target word and a neighboring context word as positive examples.\n2. Randomly sample other words in the lexicon to get negative samples.\n3. Use logistic regression to train a classifier to distinguish those two cases.\n4. Use the weights as the embeddings.\n\n\n\n \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \n\n### Dense vectors\n- Short vectors may be easier to use as features in machine learning (fewer\nweights to tune)\n- Dense vectors may generalize better than storing explicit counts\n- They may do better at capturing synonymy: car and automobile are synonyms; but are distinct dimensions in sparse\nvectors. a word with car as a neighbor and a word with automobile as a\nneighbor should be similar, but aren't. \n- In practice, they work better\n\n### Word2Vec\n- Learn embeddings as part of the process\nof word prediction. Capture relational meaning like man-woman, uncle-aunt.\n- Train a classifier to predict neighboring\nwords\n- Inspired by neural net language models.\nIn so doing, learn dense embeddings for\nthe words in the training corpus.\n- Advantages:\nFast, easy to train (much faster than SVD)\nAvailable online in the word2vec package\nIncluding sets of pretrained embeddings!\n\n### Skip-Gram Task\n- One option of Word2Vec\n- Skip-gram with negative sampling\n1. Treat the target word and a neighboring context\nword as positive examples.\n2. Randomly sample other words in the lexicon to get\nnegative samples\n3. Use logistic regression to train a classifier to\ndistinguish those two cases\n4. Use the weights as the embeddings\n- Given a tuple (t,c) = target, context. Return probability that c is a real context word. \n- P(−|t,c) = 1−P(+|t,c)\n\n#### Compute P(+|t,c)\n- Intuition:\n• Words are likely to appear near similar words\n• Model similarity with dot-product!\n• Similarity(t,c) ≈ t ∙ c\n\n#### Embedding for Word2Vec\n- We need embeddings for t and c to do the equation above.\n- Word2vec learns them automatically!\n- It starts with an initial set of embedding vectors and then iteratively shifts\nthe embedding of each word w to be more like the embeddings of words\nthat occur nearby in texts, and less like the embeddings of words that\ndon’t occur nearby.\n- For training data, +/- 2 word window.\n- FOr each positive example, create k negative examples using noise words.\n\n \n\n## Module 13 Lecture Notes\n \n### Classifier components\n- ML classifiers require a training corpus of M observations input/output pairs xi yi.\n1. A feature representation of the input. For each input observation xi, there will be vector of features x1..xn.\n2. A classification function that computes the estimated class y cap via p(y|x)\n3. An objective function for learning, usually involving minimizing error on training examples.\n4. An algorithm for optimizing the objective function.\n\n#### Sentiment classifier\n- Output positive 1 or negative 0\n- Estimate P(y=1 |x) give a vector of features x1,...,xn. \n- Logistic regression solves this task by learning from a training set, a vector of weights and bias term\n- z = w*x + b\n- z = sum of wixi + b\n- Each x has a weight, value * weight = product, sum all products to get final z.\n- Then use sigmoid function, sigmoid(z) to get final one.\n\n#### Learning in losgistic regression\n- Require 2 components to learn params (weights + bias) via learning. \n1. Loss function/objective function, tells us distance between the system output and the gold output. We use cross-entropy loss.\n2. An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function.\n\n#### Loss functions\n- Determine for some observation x how close the classifier output ycap = sigmoid(w*x + b) is to the correct output (y, which is 0 or 1)\n- L(ycap, y) = how much ycap differs from the true y\n- One example is mean squared error\n- We use loss function that prefers correct class labels of training example to be more likely.\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximise log probabilities of true labels in training data.\n- The resulting loss function is negative log likelihood loss, more commonly called cross entropy loss.\n- We want loss to be smaller if model's estimate is close to correct, and we want the loss be bigger if it is confused.\n\n#### Gradient descent\n- Find good parameters. Find good settings for weights and bias by minimizing loss function. \n- Gradient descent is a method that finds minimum of a function by figuring out in which direction the function's slope is rising the most steeply, and moving in th opposite direction.\n- Can find minimum iteratively since convex.\n- The magnitude of amount to move in gradient descent is value of slope weighted by a learning rate n.\n- Higher/faster learning rate means we should move w more on each step.\n- The gradient is difference between true y and estimate for x, multiplied by corresponding input value xj.\n\n\n\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}