{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": " Felicity_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": "50c1bcea-ea15-4f5c-e4b8-6438e35a2e99"
      },
      "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": 309,
      "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": "8705ed8b-22a2-489f-f488-e217331c9f3e"
      },
      "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": 310,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 311,
      "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",
        "Chapter 16 is concerned with episodic decision problems (utility of each action\\\n",
        " is well known.)\n",
        "\n",
        "There is uncertainty about current state and action outcomes. Probabilities are\\\n",
        "assigned to the states P(s), and to the action outcomes via a transition model\\\n",
        "P(s'|s, a) -  the probability action a on s will result in s'. \n",
        "\n",
        "$P(={RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ is the prob of reaching s'\\\n",
        "by doing a on all possible current states. \n",
        "\n",
        "**Utility Function** - a number which indicates desireability of state.\\n\n",
        "**Expected Utility** - average utility value of outcomes, weighted by its probability.\\\n",
        "$EU(a) = \\sum_{s'}T(s,a,s')U(s′)$\\n\n",
        "**Maximum Expected Utility (MEU)** - agent should choose action that maximises expected utility.\\\n",
        "If it reflects the performance measure, then the agent will achieve the highest possible\\\n",
        "performance score, averaged over all possible environments).\n",
        "action = argmax EU(a)\\n\n",
        "\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" \n",
        "**Lottery**\\n\n",
        "- Lottery L where Si has probability pi: L=[p1,S1:p2,S2:...pn,Sn].\\n\n",
        "**Rational preferences**\\n\n",
        "- If the agent has rational preferences, then the agent has a utility function and we can compute the expected utility of a lottery.\\n\n",
        "- But if the agent has a utility function describing its preferences, that doesn't mean \\\n",
        "that the agent is maximising the utility function in its decision  making. \\n\n",
        "**Constraints on Rational Preferences**\n",
        "A and B are sets of outcomes/lotteries, list of outcomes with probabilities.\n",
        "A ≻ B : agent prefers A over B.\n",
        "A ∼ B : agent is indifferent between A and B.\n",
        "A ≻∼ B  : agent prefers A over B or is indifferent between them.\n",
        "**Axioms of Utility Theory**\n",
        "**Orderability** - Agent must rate/indicate preferences. Cannot avoid deciding.\\n\n",
        "**Transitivity** - (A ≻ B)∧(B ≻C) ⇒ (A ≻C)\\n\n",
        "**Continuity** - If A ≻ B ≻ C, then B and A will occur with probability b, and \\\n",
        "C with probability 1 - p. $A≻B≻C⟹∃p s.t. [p,A;1-p,C]\\sim B[p,A;1−p,C]∼B$\\n\n",
        "**Subsitutability** - If A ~ B, then you can replace them in more complex lotteries.\\\n",
        "$A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]$\\n\n",
        "**Monotoncity** - If two lotteries have the same possible outcomes A andn B, but the agent prefers\\\n",
        "A, then the agent must also prefer the loterry that has the higher probability for A.\\n\n",
        "$A≻B⟹(p>q \\iff [p,A;1-p,B] \\succ [q,A;1-q,B])(p>q⟺[p,A;1−p,B]≻[q,A;1−q,B])$\\n\n",
        "**Decomposability** - Compound lotteries can be reduced to simpler ones; Compress two into one\\n\n",
        "$[p,A; 1− p, [q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]$\\n\n",
        "\n",
        "**Existence of Utility Function/What must a utility function have** - If preferences obey the axioms above, then\\\n",
        "U(A) >U(B) ⇔ A ≻ B and U(A) =U(B) ⇔(iff) A ∼ B.\n",
        "\n",
        "**Expected Utility of a Lottery** -The utility of a lottery is the sume of the \\\n",
        "probability of each outcomes times the utility of that outcome.\\n\n",
        " U([p1,S1; . . . ; pn,Sn]) = $\\sum_{i}p_{i}$U(Si) .\\n\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "**Preference Elicitation** - Using observed preferences on choices to work out\\\n",
        "utility function.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "Chapter 17 is concered with sequential decision problems (utlity depends on\\\n",
        "sequence of actions)\\n\n",
        "\n",
        "**MDP** - has: states, initial state, actions, transition model T(s,a,s'), reward function\\\n",
        "R(s,a,s'). The solution must specify what the agent should do at any state it might\\\n",
        "result in. The transition model is Markovian iff the probability of reach the next state \\\n",
        "only depnds on the current state.\\n\n",
        "**Actions** - cannot be fixed; MDP environment is stochastic, so we need an action \\\n",
        "for each possible state we might enter. \\n\n",
        "**Policy** is measured by expected utility of possible environment histories. \\n\n",
        "**Finite Horizon** - There is a fixed time N where the game is over; ie. no changes in utility.\\n\n",
        "**Infinite Horizon** - No deadline when to find the solution. Note that there can be\\\n",
        "finite state sequences in an infinite horizon MDP with a terminal state. Solutions to Infinite horizon problems are stationary\\n\n",
        "**Non-stationary** - A policy that depends on time (eg. in a finite horizon the optimal solution\\\n",
        "may depend on how much time there is left.)\\n\n",
        "- MDP solvers usually use dynamic programming (value iteration, policy iteration)\\n\n",
        "- MDPs cannot be solved with a fixed set of actions: stochastic environment means that we need an action for each possible state we might enter; no definitive path\\n\n",
        "- Large MDPs must be solved online algorithms, so can't use value/policy iteration.\\n\n",
        "\n",
        "**Additive discounted rewards** - Utility of a history is the sum of discounted rewards:\\n\n",
        "U_h([s0,a0, s1,a1, s2, . . .]) = R(s0,a0, s1)+γR(s1,a1, s2)+γ2R(s2,a2, s3)+···\\n\n",
        "**Discount Factor** - number between [0,1]; Describes preference for current vs. future rewards. Makes sense\\\n",
        "because people generally prefer short-term rewards, and its more economical to obtain them faster.\\\n",
        "It also reduces chance of infinities\\n\n",
        "\n",
        "**Bellman Equation** - Equation defining relationship between utility of a state, and the utility of its neighbours:\\n\n",
        "the utility of a state is the expected reward for the next transition plus the discounted utility of the next state.\\n\n",
        "$U_{i}(s) = max_{a∈A(s)}\\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γU_{i}(s′)] $.\\n\n",
        "- Bellman equation uses dynamic programming: express utlity of a state recursively as the utility of its neighbours\\n\n",
        "**Bellman Update** - A contraction by a factor of γ on utility vectors. Sets the utlity of a state iteratively using Bellman Equation\\n\n",
        "$U_{i+1}(s) = max_{a∈A(s)}\\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γU_{i}(s′)] $.\\n\n",
        "\n",
        "**Q-function // action-utility function**: Q(s,a) is the expected utility of taking a given action in a given state.\\n\n",
        "**Optimal Policy** - π∗(s) = argmax_a Q(s,a)\\n\n",
        "The expected total reward for action a, is the immediate reward plus the \\\n",
        "discounted utility of s': $Q(s,a) = \\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γ max_{a'}Q(s′,a′)]$\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "**Value Iteration for solving MDPs** \\n\n",
        "- Value iteration works because the update formula shifts information locally; updated utiltiy \\\n",
        "of a state informs direct neighbours, and so on.\\n\n",
        "- Step 1: Start with arbitrary intial values for each state\\n\n",
        "- Step 2: Apply bellman update\\n\n",
        "- Step 3: iteratively use step 2 until we reach equillibrium\n",
        "- For each n possible states, then there are n Bellman equations.\\\n",
        "Each of the n equations contain n unknown utilities of the states.\\n\n",
        "If we apply the Bellman update in value iteration an infinite number of times, then \\\n",
        "the utilities are guaranteed to reach an equillibrium. \\n\n",
        "Value iteration converges to an equillibrium exponentially fast. This is because \\\n",
        "each iteration reduces error by some gamma, after k iterations that is gamma^k.\\n\n",
        "**Contraction** - Part of the proof of convergence for the value iteration algorithm. \\\n",
        "function of one argument/fixed point. Apply this function to two different inputs, \\\n",
        "the two output values are closer together by some constant factor, compared to the original \\\n",
        "inputs. \\n\n",
        "**Max Norm** - measures lenght of a vector by the absolute value of its biggest component.\\n\n",
        "\n",
        "\n",
        "**Policy Iteration for solving MDPs*\\n\n",
        "- We can get an optimal policy with an inaccurate utility function. The exact utilities don't matter, as long as they are sufficiently \\\n",
        "positive/in favour of what the optimal policy dictates.\\n\n",
        "- Step 1 **Policy Evaluation** - given a policy $\\pi_{i}$ , calculate the utility \\\n",
        "of each state if $\\pi_{i}$ was excuted. $U_{i} = U^{\\pi_{i}}$.]\\n\n",
        "Do this by using the bellman equation  with an action a fixed by the policy. We can expect to solve a system of n variables in \\\n",
        "O(n^3) time.\n",
        "$U_{i}(s) =\\sum_{s'}P(s′ |s, \\pi_{i}(s))[R(s,\\pi_{i}(s), s′)+γU_{i}(s′)] $.\\n\n",
        "- Step 2 **Policy Improvement** - Calculate MEU (maximum expected utlity) policy $\\pi_{i+1}$ using one-step look ahead.\\n\n",
        "- Stop when there is no change in utilties.\\n\n",
        "\n",
        "**Linear Programming** - Variables: Utlities U(s) of each state s. You want to minimise: \\\n",
        "$U(s) \\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+γU(s')]$ for every state s and action a.\\n\n",
        "- Solved in polynomial time, but not as efficient as dynamic programming for MDPs.\\n\n",
        "- But can still solve MDPs.\\n\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"  \n",
        "MDPs are sequential , non deterministic decisions problems, \\\n",
        "for fully observable environments, \\ with a stochastic (random probability) \\\n",
        "transition model, with additive rewards. USE EXPECTIMAX to solve.\\\n",
        "\n",
        "Required: states, actions, transition function, rewards, start/end state.\n",
        "\n",
        "**Transition Function** T(s,a,s') returns probability that action a on s will result\\\n",
        "in s'. T(s,a,s') = P(s' | s,a). \n",
        "\n",
        "**Policy** 𝝿(s) = a tells agent what action to take at state s. This is the solution.\\\n",
        "Optimal solution is 𝝿*. Same policy executed many times on agent can result in\\\n",
        "a different sequence of actions/score (due to probability). \n",
        "\n",
        "\n",
        "Use an **expected utility function** to calc sum of rewards given sequence of actions.\\\n",
        "Value/utility of a state V*(s) is the max of all q-state values (max Q*(s,a)).\n",
        "\n",
        "$$Q*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V*(s')]$$\n",
        "\n",
        "**Discounting** = Balance between trying to maximise the sum of rewards by picking\\\n",
        "rewards now or later. Multiple discount/fraction after each level. Helps\\\n",
        "algorithm converge/prevent infinite rewards.\n",
        "\n",
        "**Prevent infinite rewards**\n",
        "1) Finite Horizon (aka. depth limited search); terminate\\\n",
        "after T steps until change is small. \n",
        "2) Discounting\n",
        "\n",
        "**Time Limited Values** - $V_{k}(s)$ is the optimal value of s if the game ends in \\\n",
        "k or more steps (ie. depth-k expectimax from s)\n",
        "\n",
        "**Value Iteration** - $O(S^{2}A)$\\n\n",
        "1. Start with $V_{0}(s) = 0$.\n",
        "2. Given a vector V_{k}(s) of values, perform expectimax on each state\n",
        "3. $V_{k+1}(s) = max_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V*(s')]$\n",
        "4. Repeat till convergence\n",
        "**Problems with value iteration** - slow, \"max\" at each state rarely changes, \\\n",
        "policy converges way before values.\\n\n",
        "\n",
        "**Policy Iteration** - converge much faster in certain conditions\\n\n",
        "1. Policy Evaluation - calculate utilities given some fixed policy until convergence \\\n",
        "3. $V_{k+1}(s)^{\\pi_{i}} = \\sum_{s'} T(s,\\pi_{i}(s),s')[R(s,\\pi_{i}(s),s') + \\gamma V_{k}^{\\pi_{i}}(s')]$\\n\n",
        "2. Policy Improvement - Update policy using one-step-look-ahead with converged utilities \\\n",
        "as future values. Repeat till convergence. $\\pi_{i+1}(s) = argmax_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}^{\\pi_{i}}(s')]$\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\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",
        "\"utility function\": \"assigns single number to express desirability of a state\",\n",
        "\"performance measure\": \"Performance measure gives a score for a history; doesn't guide future actions like a utility function\",\n",
        "\"Maximum Expected Utlity\": \"a rational agent should choose the actions that maximizes the agent's expected utility; This doesn't actually solve the problem\",\n",
        "\"transition model\": \"describes outcome of each action each state\",\n",
        "\"markovian transition model\": \"probability of reaching next state only depends on current state\",\n",
        "\"utility function for lottery\" : \"$U([p_{1},S_{1};...p_{n},S_{n}])=∑_{i}p_{1}U(S_{i})$\",\n",
        "\"policy\": \"solution to a stochastic problem, specifying what an agent to do at each state. Describes a simple reflex agent.\",\n",
        "\"optimal policy\": \"π maximizes the expected utility of the actions taken by the agent.\",\n",
        "\"Asynchronous policy iteration\": \"updates only a subset of states; better efficiency since we can use herusitics to pick states to update\",\n",
        "\"A⪰B\": \"agent prefers A over B, or is indifferent about them\",\n",
        "\"V(s)\": \"Utility of starting at state s, and acting optimally after\",\n",
        "\"Q(s,a)\": \"expected utility of a q state (s,a). Having taken action a from state s, and acting optimally afterwards\",\n",
        "\"contraction\": \"to show that value iteration converges\",\n",
        "\"Markov Property\": \"Given the present state, the future and past are independent.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 312,
      "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": "4ea25419-6ed7-4b24-f4e2-dad0cd0845c8"
      },
      "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": 313,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nChapter 16 is concerned with episodic decision problems (utility of each action is well known.)\n\nThere is uncertainty about current state and action outcomes. Probabilities areassigned to the states P(s), and to the action outcomes via a transition modelP(s'|s, a) -  the probability action a on s will result in s'. \n\n$P(={RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ is the prob of reaching s'by doing a on all possible current states. \n\n**Utility Function** - a number which indicates desireability of state.\n\n**Expected Utility** - average utility value of outcomes, weighted by its probability.$EU(a) = \\sum_{s'}T(s,a,s')U(s′)$\n\n**Maximum Expected Utility (MEU)** - agent should choose action that maximises expected utility.If it reflects the performance measure, then the agent will achieve the highest possibleperformance score, averaged over all possible environments).\naction = argmax EU(a)\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**Lottery**\n\n- Lottery L where Si has probability pi: L=[p1,S1:p2,S2:...pn,Sn].\n\n**Rational preferences**\n\n- If the agent has rational preferences, then the agent has a utility function and we can compute the expected utility of a lottery.\n\n- But if the agent has a utility function describing its preferences, that doesn't mean that the agent is maximising the utility function in its decision  making. \n\n**Constraints on Rational Preferences**\nA and B are sets of outcomes/lotteries, list of outcomes with probabilities.\nA ≻ B : agent prefers A over B.\nA ∼ B : agent is indifferent between A and B.\nA ≻∼ B  : agent prefers A over B or is indifferent between them.\n**Axioms of Utility Theory**\n**Orderability** - Agent must rate/indicate preferences. Cannot avoid deciding.\n\n**Transitivity** - (A ≻ B)∧(B ≻C) ⇒ (A ≻C)\n\n**Continuity** - If A ≻ B ≻ C, then B and A will occur with probability b, and C with probability 1 - p. $A≻B≻C⟹∃p s.t. [p,A;1-p,C]\\sim B[p,A;1−p,C]∼B$\n\n**Subsitutability** - If A ~ B, then you can replace them in more complex lotteries.$A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]$\n\n**Monotoncity** - If two lotteries have the same possible outcomes A andn B, but the agent prefersA, then the agent must also prefer the loterry that has the higher probability for A.\n\n$A≻B⟹(p>q \\iff [p,A;1-p,B] \\succ [q,A;1-q,B])(p>q⟺[p,A;1−p,B]≻[q,A;1−q,B])$\n\n**Decomposability** - Compound lotteries can be reduced to simpler ones; Compress two into one\n\n$[p,A; 1− p, [q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]$\n\n\n**Existence of Utility Function/What must a utility function have** - If preferences obey the axioms above, thenU(A) >U(B) ⇔ A ≻ B and U(A) =U(B) ⇔(iff) A ∼ B.\n\n**Expected Utility of a Lottery** -The utility of a lottery is the sume of the probability of each outcomes times the utility of that outcome.\n\n U([p1,S1; . . . ; pn,Sn]) = $\\sum_{i}p_{i}$U(Si) .\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n**Preference Elicitation** - Using observed preferences on choices to work oututility function.\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nChapter 17 is concered with sequential decision problems (utlity depends onsequence of actions)\n\n\n**MDP** - has: states, initial state, actions, transition model T(s,a,s'), reward functionR(s,a,s'). The solution must specify what the agent should do at any state it mightresult in. The transition model is Markovian iff the probability of reach the next state only depnds on the current state.\n\n**Actions** - cannot be fixed; MDP environment is stochastic, so we need an action for each possible state we might enter. \n\n**Policy** is measured by expected utility of possible environment histories. \n\n**Finite Horizon** - There is a fixed time N where the game is over; ie. no changes in utility.\n\n**Infinite Horizon** - No deadline when to find the solution. Note that there can befinite state sequences in an infinite horizon MDP with a terminal state. Solutions to Infinite horizon problems are stationary\n\n**Non-stationary** - A policy that depends on time (eg. in a finite horizon the optimal solutionmay depend on how much time there is left.)\n\n- MDP solvers usually use dynamic programming (value iteration, policy iteration)\n\n- MDPs cannot be solved with a fixed set of actions: stochastic environment means that we need an action for each possible state we might enter; no definitive path\n\n- Large MDPs must be solved online algorithms, so can't use value/policy iteration.\n\n\n**Additive discounted rewards** - Utility of a history is the sum of discounted rewards:\n\nU_h([s0,a0, s1,a1, s2, . . .]) = R(s0,a0, s1)+γR(s1,a1, s2)+γ2R(s2,a2, s3)+···\n\n**Discount Factor** - number between [0,1]; Describes preference for current vs. future rewards. Makes sensebecause people generally prefer short-term rewards, and its more economical to obtain them faster.It also reduces chance of infinities\n\n\n**Bellman Equation** - Equation defining relationship between utility of a state, and the utility of its neighbours:\n\nthe utility of a state is the expected reward for the next transition plus the discounted utility of the next state.\n\n$U_{i}(s) = max_{a∈A(s)}\\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γU_{i}(s′)] $.\n\n- Bellman equation uses dynamic programming: express utlity of a state recursively as the utility of its neighbours\n\n**Bellman Update** - A contraction by a factor of γ on utility vectors. Sets the utlity of a state iteratively using Bellman Equation\n\n$U_{i+1}(s) = max_{a∈A(s)}\\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γU_{i}(s′)] $.\n\n\n**Q-function // action-utility function**: Q(s,a) is the expected utility of taking a given action in a given state.\n\n**Optimal Policy** - π∗(s) = argmax_a Q(s,a)\n\nThe expected total reward for action a, is the immediate reward plus the discounted utility of s': $Q(s,a) = \\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γ max_{a'}Q(s′,a′)]$\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n**Value Iteration for solving MDPs** \n\n- Value iteration works because the update formula shifts information locally; updated utiltiy of a state informs direct neighbours, and so on.\n\n- Step 1: Start with arbitrary intial values for each state\n\n- Step 2: Apply bellman update\n\n- Step 3: iteratively use step 2 until we reach equillibrium\n- For each n possible states, then there are n Bellman equations.Each of the n equations contain n unknown utilities of the states.\n\nIf we apply the Bellman update in value iteration an infinite number of times, then the utilities are guaranteed to reach an equillibrium. \n\nValue iteration converges to an equillibrium exponentially fast. This is because each iteration reduces error by some gamma, after k iterations that is gamma^k.\n\n**Contraction** - Part of the proof of convergence for the value iteration algorithm. function of one argument/fixed point. Apply this function to two different inputs, the two output values are closer together by some constant factor, compared to the original inputs. \n\n**Max Norm** - measures lenght of a vector by the absolute value of its biggest component.\n\n\n\n**Policy Iteration for solving MDPs*\n\n- We can get an optimal policy with an inaccurate utility function. The exact utilities don't matter, as long as they are sufficiently positive/in favour of what the optimal policy dictates.\n\n- Step 1 **Policy Evaluation** - given a policy $\\pi_{i}$ , calculate the utility of each state if $\\pi_{i}$ was excuted. $U_{i} = U^{\\pi_{i}}$.]\n\nDo this by using the bellman equation  with an action a fixed by the policy. We can expect to solve a system of n variables in O(n^3) time.\n$U_{i}(s) =\\sum_{s'}P(s′ |s, \\pi_{i}(s))[R(s,\\pi_{i}(s), s′)+γU_{i}(s′)] $.\n\n- Step 2 **Policy Improvement** - Calculate MEU (maximum expected utlity) policy $\\pi_{i+1}$ using one-step look ahead.\n\n- Stop when there is no change in utilties.\n\n\n**Linear Programming** - Variables: Utlities U(s) of each state s. You want to minimise: $U(s) \\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+γU(s')]$ for every state s and action a.\n\n- Solved in polynomial time, but not as efficient as dynamic programming for MDPs.\n\n- But can still solve MDPs.\n\n \n\n## Module 8 Lecture Notes\n  \nMDPs are sequential , non deterministic decisions problems, for fully observable environments, \\ with a stochastic (random probability) transition model, with additive rewards. USE EXPECTIMAX to solve.\nRequired: states, actions, transition function, rewards, start/end state.\n\n**Transition Function** T(s,a,s') returns probability that action a on s will resultin s'. T(s,a,s') = P(s' | s,a). \n\n**Policy** 𝝿(s) = a tells agent what action to take at state s. This is the solution.Optimal solution is 𝝿*. Same policy executed many times on agent can result ina different sequence of actions/score (due to probability). \n\n\nUse an **expected utility function** to calc sum of rewards given sequence of actions.Value/utility of a state V*(s) is the max of all q-state values (max Q*(s,a)).\n\n$$Q*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V*(s')]$$\n\n**Discounting** = Balance between trying to maximise the sum of rewards by pickingrewards now or later. Multiple discount/fraction after each level. Helpsalgorithm converge/prevent infinite rewards.\n\n**Prevent infinite rewards**\n1) Finite Horizon (aka. depth limited search); terminateafter T steps until change is small. \n2) Discounting\n\n**Time Limited Values** - $V_{k}(s)$ is the optimal value of s if the game ends in k or more steps (ie. depth-k expectimax from s)\n\n**Value Iteration** - $O(S^{2}A)$\n\n1. Start with $V_{0}(s) = 0$.\n2. Given a vector V_{k}(s) of values, perform expectimax on each state\n3. $V_{k+1}(s) = max_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V*(s')]$\n4. Repeat till convergence\n**Problems with value iteration** - slow, \"max\" at each state rarely changes, policy converges way before values.\n\n\n**Policy Iteration** - converge much faster in certain conditions\n\n1. Policy Evaluation - calculate utilities given some fixed policy until convergence 3. $V_{k+1}(s)^{\\pi_{i}} = \\sum_{s'} T(s,\\pi_{i}(s),s')[R(s,\\pi_{i}(s),s') + \\gamma V_{k}^{\\pi_{i}}(s')]$\n\n2. Policy Improvement - Update policy using one-step-look-ahead with converged utilities as future values. Repeat till convergence. $\\pi_{i+1}(s) = argmax_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}^{\\pi_{i}}(s')]$\n\n\n\n\n\n\n\n\n\n## Module 8 Definitions\n* **Utility function** - assigns single number to express desirability of a state\n* **Performance measure** - Performance measure gives a score for a history; doesn't guide future actions like a utility function\n* **Maximum expected utlity** - a rational agent should choose the actions that maximizes the agent's expected utility; This doesn't actually solve the problem\n* **Transition model** - describes outcome of each action each state\n* **Markovian transition model** - probability of reaching next state only depends on current state\n* **Utility function for lottery** - $U([p_{1},S_{1};...p_{n},S_{n}])=∑_{i}p_{1}U(S_{i})$\n* **Policy** - solution to a stochastic problem, specifying what an agent to do at each state. Describes a simple reflex agent.\n* **Optimal policy** - π maximizes the expected utility of the actions taken by the agent.\n* **Asynchronous policy iteration** - updates only a subset of states; better efficiency since we can use herusitics to pick states to update\n* **A⪰b** - agent prefers A over B, or is indifferent about them\n* **V(s)** - Utility of starting at state s, and acting optimally after\n* **Q(s,a)** - expected utility of a q state (s,a). Having taken action a from state s, and acting optimally afterwards\n* **Contraction** - to show that value iteration converges\n* **Markov property** - Given the present state, the future and past are independent.\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",
        "**n-armed bandit** - a slot machine with n arms/levers.\\n\n",
        "- Tradeoff between exploitation of best current action, or exploration of \\\n",
        "unknown states to potentially gain more information/better rewards.\\n\n",
        "- Every arm $M_{i}$ is a Markov reward process MRP (an MDP with oinly one possible action) \\\n",
        "and is a distribution over sequences of reward Random Variables.\\n\n",
        "- Has states, transtion model, and reawrd function. \n",
        "\n",
        "**one-armed bandit**\\n\n",
        "- One arm MRP that produces rewards R0, R1, R2...,  and costs λ for each pull.\\n\n",
        "- Stopping time T is the number of times you pull the arm.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "**Passive Learning** - similar to the policy evaluation task. Difference is that \\\n",
        "passive learning agent doesn't know the transition model and the reward function. \\n\n",
        "**Direct utility estimation** - idea that utility of a state is the expected \\\n",
        "total reward from that state onward. It ignores connections between state, thus it \\\n",
        "converges slowly. Using direct utilty estimation turns reinforcement learning problem into a \\\n",
        "supervised learning problem. The examples used are of the form (state, reward to go). \\n\n",
        "The Bellman equations provide a relationship \\\n",
        "between current states and future states which confer additional information \\\n",
        "ignored by direct utility estimation.\n",
        "\n",
        "**Adaptive Dynamic Programming (ADP)**\\n\n",
        "- Uses direct utlity estimation to use the bellman equation.s\\n\n",
        "- learns utility function, transition model, and reward function\\n\n",
        "- For passive learning agent, plug in learned transition model $P(s'|s, \\pi(s))$ \\\n",
        "and observed rewards function $R(s, \\pi(s), s')$ to calcualte utilities of states. \\n\n",
        "- Or you can use modified policy iteration - update the utility estimates after each \\\n",
        "change to learned model / adjust a state to agree with all possible successors.\\n\n",
        "\n",
        "**Temporal Difference Learning (TD)**\\n\n",
        "- - Use observed transitions to adjust utlities of the observed states, such that \\\n",
        " they agree with constraint equations. TD's adjust a state to agree with the \\\n",
        " successor in the current trial. Compared to ADP, TD kind of a first order approx. \\\n",
        " It is more efficient, but less powerful.\\n\n",
        " - It is called Temporal Difference because the update equation finds the \\\n",
        " difference in utilities betwen successive states/times. \\n\n",
        " -Update equation: $U^{\\pi}(s) = (1-α)U^{\\pi}(s) + α[R(s,\\pi(s),s') + γU^{\\pi}(s')]$\\n\n",
        " - The new utility $U^{\\pi}(s)$ for a state is the old utility $U^{\\pi}(s)$, \\\n",
        " pus the new information from the next state $[R(s,\\pi(s),s') + γU^{\\pi}(s')]$, \\\n",
        " weighted by learning rate α.\\n\n",
        " - A transition model is not needed to perform updates\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "**greed** - preference for utility\\n\n",
        "-**curiosity** - prefer actions that have not been tried \\n\n",
        "- If an agent’s exploration function values curiosity, N(s,a) for a state s\\\n",
        " and an action a would be low. N(s,a) is the number of times an action a have been \\\n",
        " tried in state s. \n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "**Reinforcement Learning** - Here you still have a set of states, actions, \\\n",
        "transition model and a reward function. You are still looking for a policy. \\\n",
        "Difference is you may not know the transition function, or reward function, \\\n",
        "therefore you have to try actions and states to learn. Reinforcement Learning \\\n",
        "is ONLINE (no teacher/labeled examples, learn from experience). MDPs are OFFLINE.\\n\n",
        "- in reinforcement learning, the agent is the MDP. They are not given an MDP to solve\\n\n",
        "- Reward functions are concise (+ 1, -1, etc.), whereas labeled examples are complex\\n\n",
        "\n",
        "\n",
        "**Model based learning**\\n\n",
        "1. First we need to learn the empirical MDP model. \\\n",
        "For each state s and action a, count the number of times an outcome s' appears\\n\n",
        "2. Normalise to give an estimate of transition T(s,a,s')\n",
        "3. Discover R(s,a,s') when we experience (s,a,s')\n",
        "4. Solve using value iteration\n",
        "\n",
        "**Passive reinforcement learning**\\n\n",
        "Given a fixed input policy, you want to learn the state utlities. Similar to policy evalution. but we are not given the \\\n",
        "transition or reward function. You have no choice about what actions to take, \n",
        "execute and learn from experience; Online planning. \\n\n",
        "\n",
        "**Direct Evaluation** - No knowledge of T and R \\n\n",
        "The goal is the compute values for each state under a policy. Follow the policy. \\ \n",
        "Every time you visit a state, sum up the discounted rewards and average them.\\n\n",
        "**Problems with Direct Evaluation** - Takes a long time, each state is learned \\\n",
        "seperately, waste information on state connections.\\n\n",
        "\n",
        "**Temporal Difference Learning** -  modified policy evaluation; Running average\\n\n",
        "Update V(s) every time we experience transition (s,a,s',r). This way, more likely \\\n",
        "outcomes s' will contribute updates more often. \\n\n",
        "Given a sample of V(s), update V(s) to be $V^{\\pi}(s) = (1-\\alpha)V^{\\pi} + (\\alpha)$sample\\n\n",
        "\n",
        "\n",
        "**Active Reinforcement learning (QLearning)**\n",
        "1. Start with base case $Q_{0}(s,a) = 0$\n",
        "2. Given $Q_{k}$  calcualte the depth k+1 q-values for all q-states\n",
        "Learn the Q(s,a) value as you go. Receive a sample (s,a,s',r), and consider your \\\n",
        "old estimate Q(s,a). sample estimate = $R(s,a,s') + \\gamma max_{a}Q(s',a')$. \\\n",
        "Interpolate and incooperate your new estimate to the running average: \\n\n",
        "$Q(s,a) = (1- α )Q(s,a) + \tα * sample$.\n",
        "\n",
        "**Exploration**\n",
        "- 2 Options: To force exploration, with small probability e, act randomly. With probability \\\n",
        "1-e, act on current policy. OR you could gradually lower epsilon over time.\n",
        "**Exloration Function**\\n\n",
        "Explore areas where 'badness' is not yet determined. Given an estiamte u, and visit count \\\n",
        "n, f(u,n) = u + k/n. \\n\n",
        "Use this in Q-Update: $Q(s,a) = R(s,a,s') +  \\gamma max f(Q(s',a'), N(s',a'))$\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"exploration\" : \"Try unknown actions to learn/get info\",\n",
        "\"exploitation\" : \"Use what you know\",\n",
        "\"Regret\" : \"Making mistakes even if you use your best guess/relative goodness of exploration methods\",\n",
        "\"Sampling\" : \"Try things repeatedly due to chance\",\n",
        "\"Difficulty\" : \"You are solving an unknown MDP, so its harder to learn\",\n",
        "\"off-policy learning\": \"Q-learning converges towards the correct/optimal policy, even if you are acting suboptimally\",\n",
        "\"regret\": \"Difference between your rewards, and optimal rewards; measure of total mistake cost\",\n",
        "\"sparse reward\": \"Agents don't receive any informative or useful reward signals in majority of states; Makes learning very hard\",\n",
        "\"Reward to go\": \"Given a policy, this is the total reward from a particular state onwards\",\n",
        "\"direct utility estimation\":\"idea that utility of a state is the expected total reward from that state onward.\"\n",
        "}"
      ],
      "execution_count": 314,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "08279216-cadf-4e7e-c760-8364eb4712d1"
      },
      "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": 315,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n**n-armed bandit** - a slot machine with n arms/levers.\n\n- Tradeoff between exploitation of best current action, or exploration of unknown states to potentially gain more information/better rewards.\n\n- Every arm $M_{i}$ is a Markov reward process MRP (an MDP with oinly one possible action) and is a distribution over sequences of reward Random Variables.\n\n- Has states, transtion model, and reawrd function. \n\n**one-armed bandit**\n\n- One arm MRP that produces rewards R0, R1, R2...,  and costs λ for each pull.\n\n- Stopping time T is the number of times you pull the arm.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n**Passive Learning** - similar to the policy evaluation task. Difference is that passive learning agent doesn't know the transition model and the reward function. \n\n**Direct utility estimation** - idea that utility of a state is the expected total reward from that state onward. It ignores connections between state, thus it converges slowly. Using direct utilty estimation turns reinforcement learning problem into a supervised learning problem. The examples used are of the form (state, reward to go). \n\nThe Bellman equations provide a relationship between current states and future states which confer additional information ignored by direct utility estimation.\n\n**Adaptive Dynamic Programming (ADP)**\n\n- Uses direct utlity estimation to use the bellman equation.s\n\n- learns utility function, transition model, and reward function\n\n- For passive learning agent, plug in learned transition model $P(s'|s, \\pi(s))$ and observed rewards function $R(s, \\pi(s), s')$ to calcualte utilities of states. \n\n- Or you can use modified policy iteration - update the utility estimates after each change to learned model / adjust a state to agree with all possible successors.\n\n\n**Temporal Difference Learning (TD)**\n\n- - Use observed transitions to adjust utlities of the observed states, such that  they agree with constraint equations. TD's adjust a state to agree with the  successor in the current trial. Compared to ADP, TD kind of a first order approx.  It is more efficient, but less powerful.\n\n - It is called Temporal Difference because the update equation finds the  difference in utilities betwen successive states/times. \n\n -Update equation: $U^{\\pi}(s) = (1-α)U^{\\pi}(s) + α[R(s,\\pi(s),s') + γU^{\\pi}(s')]$\n\n - The new utility $U^{\\pi}(s)$ for a state is the old utility $U^{\\pi}(s)$,  pus the new information from the next state $[R(s,\\pi(s),s') + γU^{\\pi}(s')]$,  weighted by learning rate α.\n\n - A transition model is not needed to perform updates\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n**greed** - preference for utility\n\n-**curiosity** - prefer actions that have not been tried \n\n- If an agent’s exploration function values curiosity, N(s,a) for a state s and an action a would be low. N(s,a) is the number of times an action a have been  tried in state s. \n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n**Reinforcement Learning** - Here you still have a set of states, actions, transition model and a reward function. You are still looking for a policy. Difference is you may not know the transition function, or reward function, therefore you have to try actions and states to learn. Reinforcement Learning is ONLINE (no teacher/labeled examples, learn from experience). MDPs are OFFLINE.\n\n- in reinforcement learning, the agent is the MDP. They are not given an MDP to solve\n\n- Reward functions are concise (+ 1, -1, etc.), whereas labeled examples are complex\n\n\n\n**Model based learning**\n\n1. First we need to learn the empirical MDP model. For each state s and action a, count the number of times an outcome s' appears\n\n2. Normalise to give an estimate of transition T(s,a,s')\n3. Discover R(s,a,s') when we experience (s,a,s')\n4. Solve using value iteration\n\n**Passive reinforcement learning**\n\nGiven a fixed input policy, you want to learn the state utlities. Similar to policy evalution. but we are not given the transition or reward function. You have no choice about what actions to take, \nexecute and learn from experience; Online planning. \n\n\n**Direct Evaluation** - No knowledge of T and R \n\nThe goal is the compute values for each state under a policy. Follow the policy. \\ \nEvery time you visit a state, sum up the discounted rewards and average them.\n\n**Problems with Direct Evaluation** - Takes a long time, each state is learned seperately, waste information on state connections.\n\n\n**Temporal Difference Learning** -  modified policy evaluation; Running average\n\nUpdate V(s) every time we experience transition (s,a,s',r). This way, more likely outcomes s' will contribute updates more often. \n\nGiven a sample of V(s), update V(s) to be $V^{\\pi}(s) = (1-\u0007lpha)V^{\\pi} + (\u0007lpha)$sample\n\n\n\n**Active Reinforcement learning (QLearning)**\n1. Start with base case $Q_{0}(s,a) = 0$\n2. Given $Q_{k}$  calcualte the depth k+1 q-values for all q-states\nLearn the Q(s,a) value as you go. Receive a sample (s,a,s',r), and consider your old estimate Q(s,a). sample estimate = $R(s,a,s') + \\gamma max_{a}Q(s',a')$. Interpolate and incooperate your new estimate to the running average: \n\n$Q(s,a) = (1- α )Q(s,a) + \tα * sample$.\n\n**Exploration**\n- 2 Options: To force exploration, with small probability e, act randomly. With probability 1-e, act on current policy. OR you could gradually lower epsilon over time.\n**Exloration Function**\n\nExplore areas where 'badness' is not yet determined. Given an estiamte u, and visit count n, f(u,n) = u + k/n. \n\nUse this in Q-Update: $Q(s,a) = R(s,a,s') +  \\gamma max f(Q(s',a'), N(s',a'))$\n\n\n## Module 9 Definitions\n* **Exploration** - Try unknown actions to learn/get info\n* **Exploitation** - Use what you know\n* **Regret** - Making mistakes even if you use your best guess/relative goodness of exploration methods\n* **Sampling** - Try things repeatedly due to chance\n* **Difficulty** - You are solving an unknown MDP, so its harder to learn\n* **Off-policy learning** - Q-learning converges towards the correct/optimal policy, even if you are acting suboptimally\n* **Regret** - Difference between your rewards, and optimal rewards; measure of total mistake cost\n* **Sparse reward** - Agents don't receive any informative or useful reward signals in majority of states; Makes learning very hard\n* **Reward to go** - Given a policy, this is the total reward from a particular state onwards\n* **Direct utility estimation** - idea that utility of a state is the expected total reward from that state onward.\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",
        "**Product Rule** - P(a∧b) = P(a|b)P(b) .\\n\n",
        "**Maximum Expected Utility**\\n\n",
        "- Agent is raitonal iff it chooses the actions that yields the highest \\\n",
        "expected utility, averaged over all possible outcomes of the action. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\"\n",
        "**Independence between variables X and Y** - can be shown as P(X|Y) = P(X) or P(Y|X) = P(Y) or P(X,Y) = P(X)P(Y)\\n\n",
        " \"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "**Bayes Rule** - P(Y|X) = P(X|Y) P(Y)  / P(X).\\n\n",
        "Or otherwise if you want to find the cause: P(cause | effect) = P(effect|cause)P(cause) / P(effect).\\n\n",
        "P(effect|cause) is a causal direction relationship, and P(cause|effect) is a diagnostic direction relationship.\\n\n",
        "Diagnostic knowledge is more fragile than causal knowledge.\\n\n",
        "\n",
        "**Conditional Independence** - P(X,Y|Z) = P(X|Z) P(Y|Z).\\n\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "**Naive Bayes Model / Bayesian Classifier** - Simplified version in cases where 'effect' variables are not \\\n",
        "strictly independent from the given 'cause' variable.\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",
        "**Observed Variables (evidence)** - \n",
        "**Probability Mdoel** - associates probability P(w) with every world w. Possible worlds \\\n",
        "are the sample space\\n\n",
        "**Random Variables** - uncertain aspects of the world.\\n\n",
        "\n",
        "**Conditional Probability** : $P(a|b) = {P(a,b) / P(b)$\\n\n",
        "**Inference By Enumeration** - Split random variables into three variables. Given H1...Hr, Q, and e1..ek, where Q is the query variable,\\\n",
        " and e1..ek are evidence variables, and H1..Hr are hidden variables (not observed, or actively reasoned). \\n\n",
        " We want to find P(Q|e1...ek). \\n\n",
        " 1. First select the enries in joint probability table consistent with the evidence$\\sum_{h1...hr}P(Q, h1..hr,e1...ek)\\n\n",
        " 2. Marginalisation: sum out H (to remove it) to get joint distribution between query and evidence $P(Q,e1...ek) = \\sum_{h1...hr}P(Q,h1..hr,e1..ek)$\\n\n",
        " 3. Normalize to convert into probability distributon [0..1]. P(Q|e1..ek) = (1\\Z)P(Q, e1...ek). Where Z = $\\sum_{q}P(Q,e1...ek)$.\\n\n",
        "\n",
        "**Product Rule** - P(y)P(x|y) = P(x,y)\\n\n",
        "**Chain Rule** - P(x1,x2,x3) = P(x1)P(x2|x1)P(x3|x2,x1)\\n\n",
        "**Bayes Rule** - P(x|y) = [ P(y|x) / P(y) ] * P(x)\\n\n",
        "\n",
        "**Probabilistic Language Model (LM)** - Goal is to assign probability to sentence/sequence of words\\n\n",
        "eg. P(\"the underdog Phildelphia Eagles won\") = P(won|the underdog philadelphia eagles)\\n\n",
        "To solve this, you can use the **Markov Assumption**; Only use the previous k words/history to infer.\\\n",
        "eg. If k = 2, P(won|the underdog Philadelphia Eagles) ~~ P(won| Philadelphia Eagles)\n",
        "**N gram Models** - Unigram, bigram, trigram,... etc. These are okay, but insufficient because language has 'long distance dependencies'\\n\n",
        "\n",
        "**Estimating Bigram Probablilities** - Using the maximum likelihood estimate.\\n\n",
        "P(wi|wi-1) = count(wi-1, wi) / count(wi-1)\\n\n",
        "**Problem with MLE** - You can get zero probabilities with 'out of vocabulary' items. To deal with this \\\n",
        "replace any word not in the lexicon L with <unk>. Language Model computation is always \\\n",
        "represented in log-space/log probabilities. Problem is, if you multiply too many n-grams together, you can get \\\n",
        "numerical underflow. Solution is to add in log space instead. log(p1 * p2 * p3) = log(p1) +log(p2) + log(p3)\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"distribution\" : \"table of probabilities of values\",\n",
        "\"Joint distribution\": \"over a set of RVs, gives real numbers for each assignment P(X=x, Y=y,...)\",\n",
        "\"Events\": \"set of outcomes; Calculate probability of events using Joint distributions\",\n",
        "\"Marginal Distributions\": \"Sub tables that eliminate variables\",\n",
        "\"Marginalisation\": \"Collapse rows by summing up probabilities for an RV\",\n",
        "\"Conditional Probability\": \"P(a|b) reads as: Probability of a given b\",\n",
        "\"Probabilistic Inference\": \"Calculate probability from other known probabilities (either conditional, or update with new evidence)\",\n",
        "\"Unigram\" : \"no history is used in inference\",\n",
        "\"Bigram model\":\"1 history; P(wi|w1w2...wi-1) ~~ P(wi|wi-1)\",\n",
        "\"Markov Assumption\":\"Probability of a word depends on previous word(s)\",\n",
        "\"stationary\": \"conditional probability doesn't change over time\",\n",
        "}"
      ],
      "execution_count": 316,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "eed032c7-e479-4b8d-9c0c-3e7acdbb222b"
      },
      "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": 317,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n**Product Rule** - P(a∧b) = P(a|b)P(b) .\n\n**Maximum Expected Utility**\n\n- Agent is raitonal iff it chooses the actions that yields the highest expected utility, averaged over all possible outcomes of the action. \n\n\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n\n**Independence between variables X and Y** - can be shown as P(X|Y) = P(X) or P(Y|X) = P(Y) or P(X,Y) = P(X)P(Y)\n\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n**Bayes Rule** - P(Y|X) = P(X|Y) P(Y)  / P(X).\n\nOr otherwise if you want to find the cause: P(cause | effect) = P(effect|cause)P(cause) / P(effect).\n\nP(effect|cause) is a causal direction relationship, and P(cause|effect) is a diagnostic direction relationship.\n\nDiagnostic knowledge is more fragile than causal knowledge.\n\n\n**Conditional Independence** - P(X,Y|Z) = P(X|Z) P(Y|Z).\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n**Naive Bayes Model / Bayesian Classifier** - Simplified version in cases where 'effect' variables are not strictly independent from the given 'cause' variable.\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**Observed Variables (evidence)** - \n**Probability Mdoel** - associates probability P(w) with every world w. Possible worlds are the sample space\n\n**Random Variables** - uncertain aspects of the world.\n\n\n**Conditional Probability** : $P(a|b) = {P(a,b) / P(b)$\n\n**Inference By Enumeration** - Split random variables into three variables. Given H1...Hr, Q, and e1..ek, where Q is the query variable, and e1..ek are evidence variables, and H1..Hr are hidden variables (not observed, or actively reasoned). \n\n We want to find P(Q|e1...ek). \n\n 1. First select the enries in joint probability table consistent with the evidence$\\sum_{h1...hr}P(Q, h1..hr,e1...ek)\n\n 2. Marginalisation: sum out H (to remove it) to get joint distribution between query and evidence $P(Q,e1...ek) = \\sum_{h1...hr}P(Q,h1..hr,e1..ek)$\n\n 3. Normalize to convert into probability distributon [0..1]. P(Q|e1..ek) = (1\\Z)P(Q, e1...ek). Where Z = $\\sum_{q}P(Q,e1...ek)$.\n\n\n**Product Rule** - P(y)P(x|y) = P(x,y)\n\n**Chain Rule** - P(x1,x2,x3) = P(x1)P(x2|x1)P(x3|x2,x1)\n\n**Bayes Rule** - P(x|y) = [ P(y|x) / P(y) ] * P(x)\n\n\n**Probabilistic Language Model (LM)** - Goal is to assign probability to sentence/sequence of words\n\neg. P(\"the underdog Phildelphia Eagles won\") = P(won|the underdog philadelphia eagles)\n\nTo solve this, you can use the **Markov Assumption**; Only use the previous k words/history to infer.eg. If k = 2, P(won|the underdog Philadelphia Eagles) ~~ P(won| Philadelphia Eagles)\n**N gram Models** - Unigram, bigram, trigram,... etc. These are okay, but insufficient because language has 'long distance dependencies'\n\n\n**Estimating Bigram Probablilities** - Using the maximum likelihood estimate.\n\nP(wi|wi-1) = count(wi-1, wi) / count(wi-1)\n\n**Problem with MLE** - You can get zero probabilities with 'out of vocabulary' items. To deal with this replace any word not in the lexicon L with <unk>. Language Model computation is always represented in log-space/log probabilities. Problem is, if you multiply too many n-grams together, you can get numerical underflow. Solution is to add in log space instead. log(p1 * p2 * p3) = log(p1) +log(p2) + log(p3)\n\n\n\n## Module 10 Definitions\n* **Distribution** - table of probabilities of values\n* **Joint distribution** - over a set of RVs, gives real numbers for each assignment P(X=x, Y=y,...)\n* **Events** - set of outcomes; Calculate probability of events using Joint distributions\n* **Marginal distributions** - Sub tables that eliminate variables\n* **Marginalisation** - Collapse rows by summing up probabilities for an RV\n* **Conditional probability** - P(a|b) reads as: Probability of a given b\n* **Probabilistic inference** - Calculate probability from other known probabilities (either conditional, or update with new evidence)\n* **Unigram** - no history is used in inference\n* **Bigram model** - 1 history; P(wi|w1w2...wi-1) ~~ P(wi|wi-1)\n* **Markov assumption** - Probability of a word depends on previous word(s)\n* **Stationary** - conditional probability doesn't change over time\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" \n",
        "**Bayesian Network** - To represent the dependencies among variables, a \\\n",
        "Bayesian Network is a directed acyclic graph. Every node represents an RV. \\\n",
        "Directed arrows between nodes infers parent information. Every node has \\\n",
        "probability information P(X_i } Parents(Xi)); ie. a conditional probability table. \\\n",
        "Topology specifies conditional independence of nodes. \n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "- Each variable is conditionally independent of its non-descendants, given its parents.\\n\n",
        "\n",
        "**Check if X is conditionally independent of Y, given Z**\\n\n",
        "- Create ancestral subgraph of X,Y,Z and ancestors\\n\n",
        "- Create moral subgraph from this: add edges between all unlinked pairs of nodes that \\\n",
        "share common child\\n\n",
        "- Turn into undirected graph\n",
        "- If Z blocks all paths between X and Y - then Z d-separates X and Y, then X is \\\n",
        "conditionally indpependent of Y given Z. \n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "**Bayes' Nets / Graphical Models** - Describe complex joint distributions (models) using simple, \\\n",
        "local distributions (conditional probabilities). This is to avoid using full joint \\\n",
        "distriution tables as probabilistic models (they're too big anyways, hard to estimate unless its few variables at a time).\\n\n",
        "\n",
        "**Graphical model notation** - Nodes (variables), Arcs (interations, influence, encode conditional independence), \\\n",
        "For each random variable X, there is a set of nodes. Bayes' net is a **directed, acyclic graph**. Each node \\\n",
        "has a conditional distribution for every parent value (nodes pointing in). P(x1,x2,...xn) = MULT_{i=1..n} P(xi|parents(Xi))\\n\n",
        "\n",
        "**Causality** - Simple Bayes' nets reflect causal patterns. Directed arrows encode causality and conditional independence. \n",
        "\n",
        "**Size of BN** - Size of joint distribution over N boolean vars is $2^{n}$. N-node BN where each node has up to k parents is of size $O(N * 2^{k+1})$. \\n\n",
        "\n",
        "**D-Separation**\n",
        "**Causal Chains** - Given X -> Y -> Z, is X guaranteed indpendent of Z given Y? Yes P(z|x,y) = P(z|y). Evidence along the chain \"blocks\" the influence.\\n\n",
        "**Common Cause** - Given Y->X and Y->Z, is X and Z independent of Y? Yes P(z|x,y) = P(z|y). Similar cause blocks influence between effects.\\n\n",
        "**Common Effect** - Given X -> Z and Y->Z. X and Y are independent. BUT X and Y are not independent given Z. \\n\n",
        "\n",
        "**Active and Inactive Paths** - X and Y are conditionally independent given evidence variable Z if X and Y are \"d-separated\" by Z. \\\n",
        "If there are no active paths = independence. A path is active if each triple is active eg.:\\n\n",
        "causal chain A->B->C where B is unobserved\\n\n",
        "common cause A<-B->C where B is unobserved\\n\n",
        "common effect A->B<-C where B or one of its descendents is observed\\n\n",
        "\n",
        "- **PROCEDURE**. Shade all evidence nodes grey (ie. A⊥B | evidence nodes). Then visualise graph as undirected, and find all undirected paths between A and B. \\\n",
        "Along each of these undirected paths, check all trios. If any of these trios are inactive, then the whole undirected path is inactive. If all trios are active, then whole undirected path is active. \\\n",
        "If all undirected paths between A and B are inactive, then A is conditionally independent of B. \\n\n",
        "\n",
        "**Inference by Enumeration in Bayes' Net** - see example in handwritten sheet.\\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"locally structures sparse system\" : \"The structure grows linearly in complexity (rather thanexponentially)\",    \n",
        "\"Markov Blanket\": \"Variable is conditionally independent of all other nodes in the network (incl. parents,children, etc.)\",\n",
        "\"d-separates\": \"separation in the undirectd, moralised, ancestral subgraph\",\n",
        "\"deterministic node\": \"value is specified by the value of its parents\",\n",
        "\"Hybrid Bayesian Network\": \"network with discrete and continuous variables\"\n",
        "}\n"
      ],
      "execution_count": 318,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "fcfc2f64-f708-441f-a303-0fca22782837"
      },
      "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": 319,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \n**Bayesian Network** - To represent the dependencies among variables, a Bayesian Network is a directed acyclic graph. Every node represents an RV. Directed arrows between nodes infers parent information. Every node has probability information P(X_i } Parents(Xi)); ie. a conditional probability table. Topology specifies conditional independence of nodes. \n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- Each variable is conditionally independent of its non-descendants, given its parents.\n\n\n**Check if X is conditionally independent of Y, given Z**\n\n- Create ancestral subgraph of X,Y,Z and ancestors\n\n- Create moral subgraph from this: add edges between all unlinked pairs of nodes that share common child\n\n- Turn into undirected graph\n- If Z blocks all paths between X and Y - then Z d-separates X and Y, then X is conditionally indpependent of Y given Z. \n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n\n\n\n## Module 11 Lecture Notes\n\n**Bayes' Nets / Graphical Models** - Describe complex joint distributions (models) using simple, local distributions (conditional probabilities). This is to avoid using full joint distriution tables as probabilistic models (they're too big anyways, hard to estimate unless its few variables at a time).\n\n\n**Graphical model notation** - Nodes (variables), Arcs (interations, influence, encode conditional independence), For each random variable X, there is a set of nodes. Bayes' net is a **directed, acyclic graph**. Each node has a conditional distribution for every parent value (nodes pointing in). P(x1,x2,...xn) = MULT_{i=1..n} P(xi|parents(Xi))\n\n\n**Causality** - Simple Bayes' nets reflect causal patterns. Directed arrows encode causality and conditional independence. \n\n**Size of BN** - Size of joint distribution over N boolean vars is $2^{n}$. N-node BN where each node has up to k parents is of size $O(N * 2^{k+1})$. \n\n\n**D-Separation**\n**Causal Chains** - Given X -> Y -> Z, is X guaranteed indpendent of Z given Y? Yes P(z|x,y) = P(z|y). Evidence along the chain \"blocks\" the influence.\n\n**Common Cause** - Given Y->X and Y->Z, is X and Z independent of Y? Yes P(z|x,y) = P(z|y). Similar cause blocks influence between effects.\n\n**Common Effect** - Given X -> Z and Y->Z. X and Y are independent. BUT X and Y are not independent given Z. \n\n\n**Active and Inactive Paths** - X and Y are conditionally independent given evidence variable Z if X and Y are \"d-separated\" by Z. If there are no active paths = independence. A path is active if each triple is active eg.:\n\ncausal chain A->B->C where B is unobserved\n\ncommon cause A<-B->C where B is unobserved\n\ncommon effect A->B<-C where B or one of its descendents is observed\n\n\n- **PROCEDURE**. Shade all evidence nodes grey (ie. A⊥B | evidence nodes). Then visualise graph as undirected, and find all undirected paths between A and B. Along each of these undirected paths, check all trios. If any of these trios are inactive, then the whole undirected path is inactive. If all trios are active, then whole undirected path is active. If all undirected paths between A and B are inactive, then A is conditionally independent of B. \n\n\n**Inference by Enumeration in Bayes' Net** - see example in handwritten sheet.\n\n \n\n## Module 11 Definitions\n* **Locally structures sparse system** - The structure grows linearly in complexity (rather thanexponentially)\n* **Markov blanket** - Variable is conditionally independent of all other nodes in the network (incl. parents,children, etc.)\n* **D-separates** - separation in the undirectd, moralised, ancestral subgraph\n* **Deterministic node** - value is specified by the value of its parents\n* **Hybrid bayesian network** - network with 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 = \"\"\"\n",
        "**Forms of Learning**\n",
        "- Improve agent program by ML depends on the component to be improved, \\\n",
        "what prior knowledge the agent has, what data and feedback is avaliable.\\n\n",
        "- Possible components include transition function, percept sequence inferences, \\\n",
        "utility information, action-value information, etc.\\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\"\n",
        "**Supervised Learning**\n",
        "- Given training set of N input-output pairs generated by an unknown function \\\n",
        "of form (x1,y1), (x2,y2)...(xN,yN), find a function h that approximates the true function f. \\\n",
        "h **generalises** well when it can accurately predict the outputs of a test set.\\n\n",
        "h*, the best fit, can be found by $h* = argmax_{h \\in H} P(h|data)$. \\\n",
        "By bayes', this can also be written as $h* = argmax_{h \\in H} P(data|h)P(h)$.\\n\n",
        "\n",
        "**Best-fit function**- It's too hard to match the ground truth with continous \\\n",
        "valued outputs, so use a best-fit function. \n",
        "\n",
        "**Bias** - How often the predictive hypothesis deviates from the expected value \\\n",
        "when averaged over different training sets. EG. hypothesis space of linear functions \\\n",
        "has strong bias because straight lines. Piece wise linear function is low bias. \\n\n",
        "\n",
        "**under fitting** - predictive hypothesis doesn't find a pattern in the data.\\n\n",
        "**over fitting** - predictive hypotehsis focuses too hard on particular training set, \\\n",
        "that it doesn't perform well on unseen data.\\n\n",
        "**Variance** - The amount the hypothesis changes because of fluctuations in training data. \\n\n",
        "**Bias-Variance Tradeoff** - low-bias hypothesis can fit training data simpler/better, but low-variance can generalise better\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\" \n",
        "**Decision Tree** - represents a function that maps vector of attribute values to a singular output/decision.\\n\n",
        "Each node represents a test applied to an input attribute value, and each outgoing branch is a possible value, \\\n",
        "and leaf nodes are the value to be returned. \\n\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" \n",
        "**Gradient Descent**\\n\n",
        "- To minimise Loss. Choose any starting point in the weight space and compute the \\\n",
        "gradient. Find the steepest downhill direction, and update/move in that direction. Repeat until we \\\n",
        "converge ona point in weight space with minimal local loss. \\n\n",
        "- wi = wi - a * gradient * loss(w)\n",
        "- This uses a **step size/learning rate** - either a constant, or it can decay over time. \n",
        "**Stochastic Gradient Descent**\\n\n",
        "-randomly select small number of training examples at each step\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "**Naive Bayes'**\\n\n",
        "- probabilistic classifier. For document d, and classes $c \\in C$, the classifier \\\n",
        "return class c^, the estimate of the correct class. \\n\n",
        "- c^ = argmax P(c|d) over all $c\\in C$.\\n\n",
        "**Bayesian Inference**\\n\n",
        "- estimate of the correct class/classification becomes c^ = argmax P(d|c)P(c) \\n\n",
        "- P(c) is the prior probability\\n\n",
        "- P(d|c) is the likelihood of the document\\n\n",
        "- Naive Bayes is **generative** \\n\n",
        "- **Naive Bayes' Assumption** - Probabilties P(f_i | c) are independent given class \\\n",
        "c, such that P(f1,f2,...fn | c) = P(f1|c)P(f2|c)...P(fn|c).\\n\n",
        "\n",
        "- **Unknown Words** - words that are in test data but not in vocabulary (because it \\\n",
        "did not appear in training data at all). Simply ignore them/remove from test document/0 probability\\n\n",
        "**Stop Words** - Frequent words such as 'the' and 'a'. Sort and the top 10-100 words are \\\n",
        "'stop words'. Remove these stop words from training and test documents\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\"\n",
        "**Binary Multiomial Naive Bayes (Binary NB)**\\n\n",
        "- \n",
        "\"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "\n",
        "**Linear Classifiers**\\n\n",
        "- INPUT: feature values with weights. Activation is the sum of the weight vector \\\n",
        "and the feature values.\\n\n",
        "\n",
        "**Binary Decision Rule**\\n\n",
        "-\n",
        "\n",
        "**Multiclass decision rule** \\n\n",
        "- For multiple classes, we'll have for each: a weight vector w_y, a score/activation \\\n",
        " of a class dot(w_y, f(x)), and whichever score is highest wins.\\n\n",
        " **learning**\\n\n",
        " - Start with weights = 0\\n\n",
        " - Predict the current weights y= arg max_y dot(w_y, f(x))\\n\n",
        "- if the prediction is wrong, lower the score of the wrong answer, and increase the score \\\n",
        "of the correct answer by f(x).\n",
        "\n",
        "**Problems with perceptrons**\n",
        "- NOISE: If not separable, thrashing might happen; using averaged weight vectors \\\n",
        "over time will help\\n\n",
        "- Could settle with a mediocre/barely separating solution rip\\n\n",
        "- Overtraining/over fitting: accuracy rises and then falls after too many iterations.\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"classification\" : \"when output of learning problem is a finite set of values (like labels)\",\n",
        "\"regression\" : \"when output is numbers, or floats, or integers\" ,\n",
        "\"supervised learning\": \"agent observes provided input-output pairs, and learns a function\",\n",
        "\"Unsupervised learning\": \" agent learns patterns of input without any feedback typically in form of clustering\",\n",
        "\"Decision Boundary\": \"Line/surface that separates two classes\",\n",
        "\"Linear Separator\": \"A linear decision boundary\",\n",
        "\"Linearly Separable\":  \"data that is split by linear decision boundary\", \n",
        "\"Perceptron Learning rule\": \"the weights are updated when the actual output does not match the hypothesis output.\",\n",
        "\"perceptron\": \"linear classifier with a hard threshold\",\n",
        "\"Mistake bound\": \"maximum number of mistakes (binary case) related to the margin or degree of separabilty ; mistakes < k/ d^2\",\n",
        "\"exploratory data analysis\": \"examine data with visulaisations and statistical tests\",\n",
        "\"entropy\": \"Measure of the uncertaining of an RV. More info, less entropy\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 320,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d087fa5f-49b9-4756-b23c-ad30280a5dc7"
      },
      "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": 321,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n**Forms of Learning**\n- Improve agent program by ML depends on the component to be improved, what prior knowledge the agent has, what data and feedback is avaliable.\n\n- Possible components include transition function, percept sequence inferences, utility information, action-value information, etc.\n\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n**Supervised Learning**\n- Given training set of N input-output pairs generated by an unknown function of form (x1,y1), (x2,y2)...(xN,yN), find a function h that approximates the true function f. h **generalises** well when it can accurately predict the outputs of a test set.\n\nh*, the best fit, can be found by $h* = argmax_{h \\in H} P(h|data)$. By bayes', this can also be written as $h* = argmax_{h \\in H} P(data|h)P(h)$.\n\n\n**Best-fit function**- It's too hard to match the ground truth with continous valued outputs, so use a best-fit function. \n\n**Bias** - How often the predictive hypothesis deviates from the expected value when averaged over different training sets. EG. hypothesis space of linear functions has strong bias because straight lines. Piece wise linear function is low bias. \n\n\n**under fitting** - predictive hypothesis doesn't find a pattern in the data.\n\n**over fitting** - predictive hypotehsis focuses too hard on particular training set, that it doesn't perform well on unseen data.\n\n**Variance** - The amount the hypothesis changes because of fluctuations in training data. \n\n**Bias-Variance Tradeoff** - low-bias hypothesis can fit training data simpler/better, but low-variance can generalise better\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n**Decision Tree** - represents a function that maps vector of attribute values to a singular output/decision.\n\nEach node represents a test applied to an input attribute value, and each outgoing branch is a possible value, and leaf nodes are the value to be returned. \n\n\n\n\n \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 \n**Gradient Descent**\n\n- To minimise Loss. Choose any starting point in the weight space and compute the gradient. Find the steepest downhill direction, and update/move in that direction. Repeat until we converge ona point in weight space with minimal local loss. \n\n- wi = wi - a * gradient * loss(w)\n- This uses a **step size/learning rate** - either a constant, or it can decay over time. \n**Stochastic Gradient Descent**\n\n-randomly select small number of training examples at each step\n\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n**Naive Bayes'**\n\n- probabilistic classifier. For document d, and classes $c \\in C$, the classifier return class c^, the estimate of the correct class. \n\n- c^ = argmax P(c|d) over all $c\\in C$.\n\n**Bayesian Inference**\n\n- estimate of the correct class/classification becomes c^ = argmax P(d|c)P(c) \n\n- P(c) is the prior probability\n\n- P(d|c) is the likelihood of the document\n\n- Naive Bayes is **generative** \n\n- **Naive Bayes' Assumption** - Probabilties P(f_i | c) are independent given class c, such that P(f1,f2,...fn | c) = P(f1|c)P(f2|c)...P(fn|c).\n\n\n- **Unknown Words** - words that are in test data but not in vocabulary (because it did not appear in training data at all). Simply ignore them/remove from test document/0 probability\n\n**Stop Words** - Frequent words such as 'the' and 'a'. Sort and the top 10-100 words are 'stop words'. Remove these stop words from training and test documents\n\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\n**Binary Multiomial Naive Bayes (Binary NB)**\n\n- \n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n\n**Linear Classifiers**\n\n- INPUT: feature values with weights. Activation is the sum of the weight vector and the feature values.\n\n\n**Binary Decision Rule**\n\n-\n\n**Multiclass decision rule** \n\n- For multiple classes, we'll have for each: a weight vector w_y, a score/activation  of a class dot(w_y, f(x)), and whichever score is highest wins.\n\n **learning**\n\n - Start with weights = 0\n\n - Predict the current weights y= arg max_y dot(w_y, f(x))\n\n- if the prediction is wrong, lower the score of the wrong answer, and increase the score of the correct answer by f(x).\n\n**Problems with perceptrons**\n- NOISE: If not separable, thrashing might happen; using averaged weight vectors over time will help\n\n- Could settle with a mediocre/barely separating solution rip\n\n- Overtraining/over fitting: accuracy rises and then falls after too many iterations.\n\n\n\n\n## Module 12 Definitions\n* **Classification** - when output of learning problem is a finite set of values (like labels)\n* **Regression** - when output is numbers, or floats, or integers\n* **Supervised learning** - agent observes provided input-output pairs, and learns a function\n* **Unsupervised learning** -  agent learns patterns of input without any feedback typically in form of clustering\n* **Decision boundary** - Line/surface that separates two classes\n* **Linear separator** - A linear decision boundary\n* **Linearly separable** - data that is split by linear decision boundary\n* **Perceptron learning rule** - the weights are updated when the actual output does not match the hypothesis output.\n* **Perceptron** - linear classifier with a hard threshold\n* **Mistake bound** - maximum number of mistakes (binary case) related to the margin or degree of separabilty ; mistakes < k/ d^2\n* **Exploratory data analysis** - examine data with visulaisations and statistical tests\n* **Entropy** - Measure of the uncertaining of an RV. More info, less entropy\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 = \"\"\" \n",
        "**Cross Entropy Loss Function**\\n\n",
        " \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "**Classifier Components**\n",
        "- Machine learning classifiers need training data set: M observations with input-output pairs $(x^{i}, y^{i})$\n",
        "- Feature representation (vector of features for each input $[x_{1},x_{2},...x_{n}])$. \\\n",
        "Each feature could be a definition of what to count, or whatever is needed to help classify. Every feature is weighted by importance. The weights are learned.\\n\n",
        "- classification function (estimates class y^ via p(y|x)), \\n\n",
        "- objective function to minimise error on training samples\\n\n",
        "- algorithm for optimising the ojective function (eg. SGD).\\n\n",
        "\n",
        "**Sentiment Classifier** - classifying text whether it is positive(1) or negative(0)\\n\n",
        "- take input oservation x with feature vector with n different elements. \\n\n",
        "**Logistic Regression** - learns from a training set, weights, and bias term. \\\n",
        "Logistic regression is a network with just one weight layer and a sigmoid output. We want to estimate \\\n",
        "P(y=1 | x), ie. given the input x, probability that the text is positive. $z = w \\cdot x + b$.\\n\n",
        "- range of z is -inf and +inf, so to have it range from [0, 1], we need to use the **sigmoid function**\\n\n",
        "- sigmoid function si $y = 1 / (1 + e^{-z})$ converts the range to 0 to 1 for probabilities.\\n\n",
        "- eg. $P(y=1) = \\sigma(w \\cdot x + b) = 1 / ( 1 + e^{-w \\cdot x + b})$\\n\n",
        "\n",
        "**Decision Boundary**\n",
        "- After transforming with sigmoid class, use a decision boundary to decide if we return positive, \\\n",
        "or negative.\\n\n",
        "- ie. $\\hat{y} = {1 if P(y=1|x) > 0.5$, else 0}\\n\n",
        "\n",
        "**Loss Function** - The distance betwen the system output and the gold output. Use Cross Entropy Loss.\\n\n",
        "- $L(\\hat{y},y)$ = how much y^ differs from true y. \\n\n",
        "**Cross Entropy Loss**\\n\n",
        "- Maximise the correct class labels of the training example. Choose parameters weight and bias that \\\n",
        "maximise the log probabilities of the true labels in trainig data. \\n\n",
        "- $P(y|x) =  \\hat{y}^{y}(1=\\hat{y})^{1-y}$, where correct label y can only be 0 or 1. When y is 1, then we want y^ to be as close to 1 as possible.\\n\n",
        "- take the log of both sides, and negate for 'loss', $L_{CE}( \\hat{y}, y) = -[log P(y|x) = ylog \\hat y + (1-y)log(1- \\hat y)]$.\\n\n",
        "- substitute $\\hat{y} = \\sigma(w \\cdot x + b)$ in above equation.\\n\n",
        "\n",
        "- We want to minimise this negative log probability because if our model is close to correct, then CE loss is lower.\\n\n",
        "- If the prediction is incorrect, we want our CE loss to be higher\\n\n",
        "- Using log function ensures that as the probability of the correct answer is maximised, the probability of the incorrect answer is minimised.\\n\n",
        "\n",
        "**Loss of all training examples** -> log P(training labels) = $ - \\sum_{i=1}^{m} L_{CE}(\\hat{y}^{i}|y^{i})$\\n\n",
        "\n",
        "**Stochastic Gradient Descent SGD** - to update the parameters (weights, bias) of our model to minimise our loss function. \\n\n",
        "- Chooses a single random example at a time and updates the weights on that example\\n\n",
        "- Let $\\theta$ be the set of parameters in our model, ie. weight and bias terms. We want to find a setting of $\\theta$ that will minimise \\\n",
        "the average cross entropy loss.\\n\n",
        "- Gradient Descent finds the direction that is rising the most steeply/slope, and going in the opposite direction/downward.\\n\n",
        "- **convex** - just one minimum for logistic regression (no local minimum to get stuck in)\\n\n",
        "- **learning rate** - size of step we take $\\eta$; Of the learning rate is too big, you might accidently step over the global minimum, or find a local minimum.\\n\n",
        "- $w^{t+1} = w^{t} - \\eta d\\dw f(x;w)$\\n\n",
        "\n",
        "**Multi direction SGD**\n",
        "- For every weight in weight vector has a slope. Find the partial derivative of loss with respect to each weight. \\\n",
        "- $\\delta_{\\theta} L(f(s,\\theta),y)=$\\n\n",
        "- derivative of athe Loss CE function for one observation x and a single weight wi is: \\\n",
        "$[\\hat{y} / (w \\cdot x + b - y)] x$\n",
        "\n",
        "**Mini-batch training**\\n\n",
        "- **Batch training**: Compute gradient over an entire dataset. This gives a better estimate, but takes a long time. \\n\n",
        "- For **mini**  batch training, train on a batch of size 512 or 1024. All examples in batch processed in parallel, loss is accumulated.\\n\n",
        "\n",
        "**overfitting** - if a feature only occurs in one class then it will get a high weight, resulting in noise and overfitting/poor generalisation.\\n\n",
        "\n",
        "**Multiclass classification**\\n\n",
        "- Positive, negative, neutral\\n\n",
        "- Use a generalisation of the sigmoid called the **softmax function**\\n\n",
        "- take an input vector z, and outputs a vector of values normalised into probabilities\\n\n",
        "- Output is a probability distribution; sum up to 1.\\n\n",
        "\n",
        "**Neural Networks**\\n\n",
        "- A neural network with enough neurons and a nonlinear activation function can approximate \\\n",
        "a huge range of possible functions (\"feed forward neural network\")\\n\n",
        "- \"deep\" part of deep learning is the number of stacked hidden layers; this gives it it's power.\\n\n",
        "- **sigmoid neuron** - a regular perceptron outputs either 0 or 1. A small change in the weights or bias \\\n",
        "will cause the output to just flip in a 'step function' manner. Sigmoid neuron gives a smoother \\\n",
        "activiation function (gently change between 0 and 1).\\n\n",
        "**Activation Function** - Takes in the inputs and decides the outputs. \\n\n",
        "- y = a = f(z), where y is the output of the NN, and a is the activation value, and f(z) is the activation function.\\n\n",
        "- Three most common non-linear functions are sigmoid, tanh, and rectified linear unit (ReLU)\\n\n",
        "- ReLU - is close to linear\\n\n",
        "\n",
        "**Feed-Forward Neural network**\\n\n",
        "- A multilayer network (fully connected, no cycles)\\n\n",
        "- Outputs from each layer and fed forward to the next higher layer.\n",
        "\n",
        "**Training Neural Nets**\\n\n",
        "- Need a loss function, optmisation algorithm (Gradient Descent), method of computing \\\n",
        "gradient of loss function (**error back propagation**)\\n\n",
        "- Gradient of a logistic regression only gives correct updates for the last weight layer. \\n\n",
        "- Deep networks need to look back through earlier layers to compute gradients - error back propagation\\n\n",
        "**Error Back Propagation** - enables us to correctly update all layers inthe neural network, and learn the weights in our system\\n\n",
        "- **Backward differentiation**\\n\n",
        "- **computation graph** - break down math expression into separate operations (nodes in graph) \\\n",
        "eduges are inputs to the next operation. Used in forward pass (read left to right)\\n\n",
        "- Backwards differentiation uses the chain rule. Goal is to find the derivative with respet to the loss at each of the nodes \\\n",
        " If you want to find the derivative of the input, find the partial derivative of the \\\n",
        " intermediate nodes with respect to their parents, and chain rule from right to left. \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Overfitting\" : \"results in poor generalisation and poor performance on unseen test\",    \n",
        "\"Regularisation\": \"way of avoiding overfitting when you have a lot of weights; penalise large weights; add term to loss function\"\n",
        "}\n"
      ],
      "execution_count": 322,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "33aec9ee-47a9-4e4f-d41e-c0f00f9b3206"
      },
      "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": 323,
      "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 \n**Cross Entropy Loss Function**\n\n \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n**Classifier Components**\n- Machine learning classifiers need training data set: M observations with input-output pairs $(x^{i}, y^{i})$\n- Feature representation (vector of features for each input $[x_{1},x_{2},...x_{n}])$. Each feature could be a definition of what to count, or whatever is needed to help classify. Every feature is weighted by importance. The weights are learned.\n\n- classification function (estimates class y^ via p(y|x)), \n\n- objective function to minimise error on training samples\n\n- algorithm for optimising the ojective function (eg. SGD).\n\n\n**Sentiment Classifier** - classifying text whether it is positive(1) or negative(0)\n\n- take input oservation x with feature vector with n different elements. \n\n**Logistic Regression** - learns from a training set, weights, and bias term. Logistic regression is a network with just one weight layer and a sigmoid output. We want to estimate P(y=1 | x), ie. given the input x, probability that the text is positive. $z = w \\cdot x + b$.\n\n- range of z is -inf and +inf, so to have it range from [0, 1], we need to use the **sigmoid function**\n\n- sigmoid function si $y = 1 / (1 + e^{-z})$ converts the range to 0 to 1 for probabilities.\n\n- eg. $P(y=1) = \\sigma(w \\cdot x + b) = 1 / ( 1 + e^{-w \\cdot x + b})$\n\n\n**Decision Boundary**\n- After transforming with sigmoid class, use a decision boundary to decide if we return positive, or negative.\n\n- ie. $\\hat{y} = {1 if P(y=1|x) > 0.5$, else 0}\n\n\n**Loss Function** - The distance betwen the system output and the gold output. Use Cross Entropy Loss.\n\n- $L(\\hat{y},y)$ = how much y^ differs from true y. \n\n**Cross Entropy Loss**\n\n- Maximise the correct class labels of the training example. Choose parameters weight and bias that maximise the log probabilities of the true labels in trainig data. \n\n- $P(y|x) =  \\hat{y}^{y}(1=\\hat{y})^{1-y}$, where correct label y can only be 0 or 1. When y is 1, then we want y^ to be as close to 1 as possible.\n\n- take the log of both sides, and negate for 'loss', $L_{CE}( \\hat{y}, y) = -[log P(y|x) = ylog \\hat y + (1-y)log(1- \\hat y)]$.\n\n- substitute $\\hat{y} = \\sigma(w \\cdot x + b)$ in above equation.\n\n\n- We want to minimise this negative log probability because if our model is close to correct, then CE loss is lower.\n\n- If the prediction is incorrect, we want our CE loss to be higher\n\n- Using log function ensures that as the probability of the correct answer is maximised, the probability of the incorrect answer is minimised.\n\n\n**Loss of all training examples** -> log P(training labels) = $ - \\sum_{i=1}^{m} L_{CE}(\\hat{y}^{i}|y^{i})$\n\n\n**Stochastic Gradient Descent SGD** - to update the parameters (weights, bias) of our model to minimise our loss function. \n\n- Chooses a single random example at a time and updates the weights on that example\n\n- Let $\theta$ be the set of parameters in our model, ie. weight and bias terms. We want to find a setting of $\theta$ that will minimise the average cross entropy loss.\n\n- Gradient Descent finds the direction that is rising the most steeply/slope, and going in the opposite direction/downward.\n\n- **convex** - just one minimum for logistic regression (no local minimum to get stuck in)\n\n- **learning rate** - size of step we take $\\eta$; Of the learning rate is too big, you might accidently step over the global minimum, or find a local minimum.\n\n- $w^{t+1} = w^{t} - \\eta d\\dw f(x;w)$\n\n\n**Multi direction SGD**\n- For every weight in weight vector has a slope. Find the partial derivative of loss with respect to each weight. - $\\delta_{\theta} L(f(s,\theta),y)=$\n\n- derivative of athe Loss CE function for one observation x and a single weight wi is: $[\\hat{y} / (w \\cdot x + b - y)] x$\n\n**Mini-batch training**\n\n- **Batch training**: Compute gradient over an entire dataset. This gives a better estimate, but takes a long time. \n\n- For **mini**  batch training, train on a batch of size 512 or 1024. All examples in batch processed in parallel, loss is accumulated.\n\n\n**overfitting** - if a feature only occurs in one class then it will get a high weight, resulting in noise and overfitting/poor generalisation.\n\n\n**Multiclass classification**\n\n- Positive, negative, neutral\n\n- Use a generalisation of the sigmoid called the **softmax function**\n\n- take an input vector z, and outputs a vector of values normalised into probabilities\n\n- Output is a probability distribution; sum up to 1.\n\n\n**Neural Networks**\n\n- A neural network with enough neurons and a nonlinear activation function can approximate a huge range of possible functions (\"feed forward neural network\")\n\n- \"deep\" part of deep learning is the number of stacked hidden layers; this gives it it's power.\n\n- **sigmoid neuron** - a regular perceptron outputs either 0 or 1. A small change in the weights or bias will cause the output to just flip in a 'step function' manner. Sigmoid neuron gives a smoother activiation function (gently change between 0 and 1).\n\n**Activation Function** - Takes in the inputs and decides the outputs. \n\n- y = a = f(z), where y is the output of the NN, and a is the activation value, and f(z) is the activation function.\n\n- Three most common non-linear functions are sigmoid, tanh, and rectified linear unit (ReLU)\n\n- ReLU - is close to linear\n\n\n**Feed-Forward Neural network**\n\n- A multilayer network (fully connected, no cycles)\n\n- Outputs from each layer and fed forward to the next higher layer.\n\n**Training Neural Nets**\n\n- Need a loss function, optmisation algorithm (Gradient Descent), method of computing gradient of loss function (**error back propagation**)\n\n- Gradient of a logistic regression only gives correct updates for the last weight layer. \n\n- Deep networks need to look back through earlier layers to compute gradients - error back propagation\n\n**Error Back Propagation** - enables us to correctly update all layers inthe neural network, and learn the weights in our system\n\n- **Backward differentiation**\n\n- **computation graph** - break down math expression into separate operations (nodes in graph) eduges are inputs to the next operation. Used in forward pass (read left to right)\n\n- Backwards differentiation uses the chain rule. Goal is to find the derivative with respet to the loss at each of the nodes  If you want to find the derivative of the input, find the partial derivative of the  intermediate nodes with respect to their parents, and chain rule from right to left. \n\n\n\n \n\n## Module 13 Definitions\n* **Overfitting** - results in poor generalisation and poor performance on unseen test\n* **Regularisation** - way of avoiding overfitting when you have a lot of weights; penalise large weights; add term to loss function\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "**Language Model** - estimate the probabliity of a sequence of words given the preceeding k words\\n\n",
        "**Neural Language Models** - Don't need smoothing, handle longer histories, generlise over contexts of similar words \\\n",
        "and higher predictive accuracy than n-gram language models. BUT much slower. \\n\n",
        "- Associate every word in vocabulary with a vector-representation with real values - creating the idea of similarities between words\\n\n",
        "- Define joint probability function of a word sequence using these word vectors\\n\n",
        "- Concurrently learn word vectors and parameters of the function\\n\n",
        "- Probability function expressed using a multi-layer feed forward neural network (product of conditional probabilities of next word given previous word.)\\n\n",
        "\n",
        "- Input: k-gram of words $w_{1:k}$\\n\n",
        "- Output: probabliity distribution over the next word\\n\n",
        "- every word associated with an **embedding vector**\\n\n",
        "- **one hot vector** - a vector of length of vocabulary; index corresponding to word input is turned on. Learn a \\\n",
        "set of weights each word in the input layer one hot vector.\\n\n",
        "- Given a corupus, read every sequence of length K as a training item. k-1 items as input, k word as correct label. \\n\n",
        "- Train using cross entropy and back propogation\\n\n",
        "- We are basically constructing look up tables for probabliities of seeing a word given a history. \\n\n",
        "- NN Model learns how to generalise\\n\n",
        "\n",
        "- Structure is one hot vector -> [:mapping function] -> d dimensional learned vectors -[:input]-> feed forward neural network predicts word; see what words a similar to each other\\n\n",
        "\n",
        "**Lexical Semantic Models**\\n\n",
        "- How to represent the meaning of a word? Want to encode: synonms, antonyms, connotations, semantic roles, etc. \\n\n",
        "- Entailment : dog is a subset of animal; hierarchal reprsentation of words and \\\n",
        "their meanings. Based on math, handles logical operations, but this knowleedge must come from somewhere else/acquire for a long time.\\n\n",
        "\n",
        "**Vector space model**\\n\n",
        "- ABle to automatically extract knowledge from a large corpus. \\n\n",
        "- every word is represented as points in vector space; points that are close to each other mean the words are semanticlally similar.\\n\n",
        "- Synonym != similar; More words are similar ie. dogs and cats, tall and height\\n\n",
        "\n",
        "**Distributional Hypothesis**\n",
        "- relative frequency of words in environments. If A and B have similar environments/contexts, then they are synonyms\\n\n",
        "**Term-Document Matrix**\\n\n",
        "- Each column vector represents a document; Each row represents a term/word, a cell in the document represents how often that term has occured in the document. \\n\n",
        "- Length of the document/column vector is the size of the vocabulary; Document vectors can be sparce (mostly 0s, not all words in the english language are used)\\n\n",
        "- Document similarity: can be used for plagirism detection\\n\n",
        "- Comparing two row vectors: how similar two words are. Words that occur in similar sets of documents must be similar. \\n\n",
        "**Vector comparisons**\n",
        "- example: Consider table where A,B,C are words on each row, and then docX and docY are the column headers\\n\n",
        "- If comparing words A, B, C from two documents docX, docY, plot on x-y graph. For each word, plot point frequency (Ax, Ay), (Bx, By), ... Measure Euclidean distance between each point-> square root of Ax^2 + Ay^2\\n\n",
        "- (**Vector Length/L2 normalisation**) Normalise the euclidean distance, and then divide every word's row cell by this normalised value. Ax / |euclidean|, By / euclidean, ...\\n\n",
        "- Replot the graph with these normalised x and y values; We do this because now words that had lower frequency are now scaled so that it fits better in graph. \n",
        "- Distance measures how similar words are\\n\n",
        "\n",
        "**Cosine Distsance**\\n\n",
        "- Cosine angle betwen vectors tells how similar they are. Vectors spawn from origin to normalised x-y points. \\n\n",
        "- Cosine distance has vector length normalisation in it.\\n\n",
        "\n",
        "**Term-Term**\\n\n",
        "- Square Matrix; Every word is a column vector and a row vector. \\n\n",
        "- Lengt of row vector is now |V| isntead of number of documents. \\n\n",
        "- Ie. if we index into cell (abdicate, abandon),this cell value now indicates \\\n",
        "how often abandon appears in a context window surrounding abdicate\\n\n",
        "**context windows** -Find all instances of 'abdicate' in the corpus, then tally what \\\n",
        "words and the frequency of that word that happen +/- 2 words to the left or right around 'abdicate'.  \\n\n",
        "- **Dependency Parsing** You can adjust this for more complex contexts (subj-of-verb, adj-mod). \\\n",
        "You can tell things hold, when isntead of just +/- 2, meaning still holds for long distances\\n\n",
        "- **syntax to define a word's context** - Duty and responsibility have similar syntatic dsitributions (types of adjectives, etc.)\\n\n",
        "\n",
        "**Other than counting**\\n\n",
        "- Word counts can be super skewed towards (A, and, of, etc.), as the frequency of words in the english dictionary exponentially decreases\\n\n",
        "- To fix this, Transform these vectors using TF-IDF or PPMI\\n\n",
        "\n",
        "**TF-DF** - Term Frequency * inverse document frequency, \\n\n",
        "where term frequency is how often a word occured in a document, and inverse document frequency is 1/(number of documents that it occured in)\\n\n",
        "\n",
        "**Sparse v. Dense Vector**\\n\n",
        "- Sparse: msot elements in 0\\n\n",
        "- Long: |V| = 50,000+\\n\n",
        "- Short: |V| = 200-100\\n\n",
        "- Dense: most elements are non zero\\n\n",
        "\n",
        "- How to we get dense vectors? : train a classifer!\\n\n",
        "- Get positive examples: target word and neighbouring context words\\n\n",
        "- Get negative examples: randomly sample other words\\n\n",
        "- Use logistic regression to train classifier to tell positive and negative apart\\n\n",
        "- Use these weights as **embeddings**\\n\n",
        "\n",
        "- **Word2Vec**\\n\n",
        "- Predict each neighbour word in a context window (C = +/- 2)\\n\n",
        "-Positive examples want to get a high probability; and vice versa for negative examples\\n\n",
        "- Plug into neural network \\n\n",
        "\n",
        "- Embeddedings capture relational meanings. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"corpus\" : \"large collection of texts\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 324,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "396004e7-4aae-43c4-e56c-910740038dee"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 325,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n**Language Model** - estimate the probabliity of a sequence of words given the preceeding k words\n\n**Neural Language Models** - Don't need smoothing, handle longer histories, generlise over contexts of similar words and higher predictive accuracy than n-gram language models. BUT much slower. \n\n- Associate every word in vocabulary with a vector-representation with real values - creating the idea of similarities between words\n\n- Define joint probability function of a word sequence using these word vectors\n\n- Concurrently learn word vectors and parameters of the function\n\n- Probability function expressed using a multi-layer feed forward neural network (product of conditional probabilities of next word given previous word.)\n\n\n- Input: k-gram of words $w_{1:k}$\n\n- Output: probabliity distribution over the next word\n\n- every word associated with an **embedding vector**\n\n- **one hot vector** - a vector of length of vocabulary; index corresponding to word input is turned on. Learn a set of weights each word in the input layer one hot vector.\n\n- Given a corupus, read every sequence of length K as a training item. k-1 items as input, k word as correct label. \n\n- Train using cross entropy and back propogation\n\n- We are basically constructing look up tables for probabliities of seeing a word given a history. \n\n- NN Model learns how to generalise\n\n\n- Structure is one hot vector -> [:mapping function] -> d dimensional learned vectors -[:input]-> feed forward neural network predicts word; see what words a similar to each other\n\n\n**Lexical Semantic Models**\n\n- How to represent the meaning of a word? Want to encode: synonms, antonyms, connotations, semantic roles, etc. \n\n- Entailment : dog is a subset of animal; hierarchal reprsentation of words and their meanings. Based on math, handles logical operations, but this knowleedge must come from somewhere else/acquire for a long time.\n\n\n**Vector space model**\n\n- ABle to automatically extract knowledge from a large corpus. \n\n- every word is represented as points in vector space; points that are close to each other mean the words are semanticlally similar.\n\n- Synonym != similar; More words are similar ie. dogs and cats, tall and height\n\n\n**Distributional Hypothesis**\n- relative frequency of words in environments. If A and B have similar environments/contexts, then they are synonyms\n\n**Term-Document Matrix**\n\n- Each column vector represents a document; Each row represents a term/word, a cell in the document represents how often that term has occured in the document. \n\n- Length of the document/column vector is the size of the vocabulary; Document vectors can be sparce (mostly 0s, not all words in the english language are used)\n\n- Document similarity: can be used for plagirism detection\n\n- Comparing two row vectors: how similar two words are. Words that occur in similar sets of documents must be similar. \n\n**Vector comparisons**\n- example: Consider table where A,B,C are words on each row, and then docX and docY are the column headers\n\n- If comparing words A, B, C from two documents docX, docY, plot on x-y graph. For each word, plot point frequency (Ax, Ay), (Bx, By), ... Measure Euclidean distance between each point-> square root of Ax^2 + Ay^2\n\n- (**Vector Length/L2 normalisation**) Normalise the euclidean distance, and then divide every word's row cell by this normalised value. Ax / |euclidean|, By / euclidean, ...\n\n- Replot the graph with these normalised x and y values; We do this because now words that had lower frequency are now scaled so that it fits better in graph. \n- Distance measures how similar words are\n\n\n**Cosine Distsance**\n\n- Cosine angle betwen vectors tells how similar they are. Vectors spawn from origin to normalised x-y points. \n\n- Cosine distance has vector length normalisation in it.\n\n\n**Term-Term**\n\n- Square Matrix; Every word is a column vector and a row vector. \n\n- Lengt of row vector is now |V| isntead of number of documents. \n\n- Ie. if we index into cell (abdicate, abandon),this cell value now indicates how often abandon appears in a context window surrounding abdicate\n\n**context windows** -Find all instances of 'abdicate' in the corpus, then tally what words and the frequency of that word that happen +/- 2 words to the left or right around 'abdicate'.  \n\n- **Dependency Parsing** You can adjust this for more complex contexts (subj-of-verb, adj-mod). You can tell things hold, when isntead of just +/- 2, meaning still holds for long distances\n\n- **syntax to define a word's context** - Duty and responsibility have similar syntatic dsitributions (types of adjectives, etc.)\n\n\n**Other than counting**\n\n- Word counts can be super skewed towards (A, and, of, etc.), as the frequency of words in the english dictionary exponentially decreases\n\n- To fix this, Transform these vectors using TF-IDF or PPMI\n\n\n**TF-DF** - Term Frequency * inverse document frequency, \n\nwhere term frequency is how often a word occured in a document, and inverse document frequency is 1/(number of documents that it occured in)\n\n\n**Sparse v. Dense Vector**\n\n- Sparse: msot elements in 0\n\n- Long: |V| = 50,000+\n\n- Short: |V| = 200-100\n\n- Dense: most elements are non zero\n\n\n- How to we get dense vectors? : train a classifer!\n\n- Get positive examples: target word and neighbouring context words\n\n- Get negative examples: randomly sample other words\n\n- Use logistic regression to train classifier to tell positive and negative apart\n\n- Use these weights as **embeddings**\n\n\n- **Word2Vec**\n\n- Predict each neighbour word in a context window (C = +/- 2)\n\n-Positive examples want to get a high probability; and vice versa for negative examples\n\n- Plug into neural network \n\n\n- Embeddedings capture relational meanings. \n\n\n## Module 14 Definitions\n* **Corpus** - large collection of texts\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": {
        "id": "T3cm1WV542_a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7b600cea-06fc-470e-b5d3-07f2e09a1257"
      },
      "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": 326,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nChapter 16 is concerned with episodic decision problems (utility of each action is well known.)\n\nThere is uncertainty about current state and action outcomes. Probabilities areassigned to the states P(s), and to the action outcomes via a transition modelP(s'|s, a) -  the probability action a on s will result in s'. \n\n$P(={RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ is the prob of reaching s'by doing a on all possible current states. \n\n**Utility Function** - a number which indicates desireability of state.\n\n**Expected Utility** - average utility value of outcomes, weighted by its probability.$EU(a) = \\sum_{s'}T(s,a,s')U(s′)$\n\n**Maximum Expected Utility (MEU)** - agent should choose action that maximises expected utility.If it reflects the performance measure, then the agent will achieve the highest possibleperformance score, averaged over all possible environments).\naction = argmax EU(a)\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**Lottery**\n\n- Lottery L where Si has probability pi: L=[p1,S1:p2,S2:...pn,Sn].\n\n**Rational preferences**\n\n- If the agent has rational preferences, then the agent has a utility function and we can compute the expected utility of a lottery.\n\n- But if the agent has a utility function describing its preferences, that doesn't mean that the agent is maximising the utility function in its decision  making. \n\n**Constraints on Rational Preferences**\nA and B are sets of outcomes/lotteries, list of outcomes with probabilities.\nA ≻ B : agent prefers A over B.\nA ∼ B : agent is indifferent between A and B.\nA ≻∼ B  : agent prefers A over B or is indifferent between them.\n**Axioms of Utility Theory**\n**Orderability** - Agent must rate/indicate preferences. Cannot avoid deciding.\n\n**Transitivity** - (A ≻ B)∧(B ≻C) ⇒ (A ≻C)\n\n**Continuity** - If A ≻ B ≻ C, then B and A will occur with probability b, and C with probability 1 - p. $A≻B≻C⟹∃p s.t. [p,A;1-p,C]\\sim B[p,A;1−p,C]∼B$\n\n**Subsitutability** - If A ~ B, then you can replace them in more complex lotteries.$A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]$\n\n**Monotoncity** - If two lotteries have the same possible outcomes A andn B, but the agent prefersA, then the agent must also prefer the loterry that has the higher probability for A.\n\n$A≻B⟹(p>q \\iff [p,A;1-p,B] \\succ [q,A;1-q,B])(p>q⟺[p,A;1−p,B]≻[q,A;1−q,B])$\n\n**Decomposability** - Compound lotteries can be reduced to simpler ones; Compress two into one\n\n$[p,A; 1− p, [q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]$\n\n\n**Existence of Utility Function/What must a utility function have** - If preferences obey the axioms above, thenU(A) >U(B) ⇔ A ≻ B and U(A) =U(B) ⇔(iff) A ∼ B.\n\n**Expected Utility of a Lottery** -The utility of a lottery is the sume of the probability of each outcomes times the utility of that outcome.\n\n U([p1,S1; . . . ; pn,Sn]) = $\\sum_{i}p_{i}$U(Si) .\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n**Preference Elicitation** - Using observed preferences on choices to work oututility function.\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nChapter 17 is concered with sequential decision problems (utlity depends onsequence of actions)\n\n\n**MDP** - has: states, initial state, actions, transition model T(s,a,s'), reward functionR(s,a,s'). The solution must specify what the agent should do at any state it mightresult in. The transition model is Markovian iff the probability of reach the next state only depnds on the current state.\n\n**Actions** - cannot be fixed; MDP environment is stochastic, so we need an action for each possible state we might enter. \n\n**Policy** is measured by expected utility of possible environment histories. \n\n**Finite Horizon** - There is a fixed time N where the game is over; ie. no changes in utility.\n\n**Infinite Horizon** - No deadline when to find the solution. Note that there can befinite state sequences in an infinite horizon MDP with a terminal state. Solutions to Infinite horizon problems are stationary\n\n**Non-stationary** - A policy that depends on time (eg. in a finite horizon the optimal solutionmay depend on how much time there is left.)\n\n- MDP solvers usually use dynamic programming (value iteration, policy iteration)\n\n- MDPs cannot be solved with a fixed set of actions: stochastic environment means that we need an action for each possible state we might enter; no definitive path\n\n- Large MDPs must be solved online algorithms, so can't use value/policy iteration.\n\n\n**Additive discounted rewards** - Utility of a history is the sum of discounted rewards:\n\nU_h([s0,a0, s1,a1, s2, . . .]) = R(s0,a0, s1)+γR(s1,a1, s2)+γ2R(s2,a2, s3)+···\n\n**Discount Factor** - number between [0,1]; Describes preference for current vs. future rewards. Makes sensebecause people generally prefer short-term rewards, and its more economical to obtain them faster.It also reduces chance of infinities\n\n\n**Bellman Equation** - Equation defining relationship between utility of a state, and the utility of its neighbours:\n\nthe utility of a state is the expected reward for the next transition plus the discounted utility of the next state.\n\n$U_{i}(s) = max_{a∈A(s)}\\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γU_{i}(s′)] $.\n\n- Bellman equation uses dynamic programming: express utlity of a state recursively as the utility of its neighbours\n\n**Bellman Update** - A contraction by a factor of γ on utility vectors. Sets the utlity of a state iteratively using Bellman Equation\n\n$U_{i+1}(s) = max_{a∈A(s)}\\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γU_{i}(s′)] $.\n\n\n**Q-function // action-utility function**: Q(s,a) is the expected utility of taking a given action in a given state.\n\n**Optimal Policy** - π∗(s) = argmax_a Q(s,a)\n\nThe expected total reward for action a, is the immediate reward plus the discounted utility of s': $Q(s,a) = \\sum_{s'}P(s′ |s,a)[R(s,a, s′)+γ max_{a'}Q(s′,a′)]$\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \n**Value Iteration for solving MDPs** \n\n- Value iteration works because the update formula shifts information locally; updated utiltiy of a state informs direct neighbours, and so on.\n\n- Step 1: Start with arbitrary intial values for each state\n\n- Step 2: Apply bellman update\n\n- Step 3: iteratively use step 2 until we reach equillibrium\n- For each n possible states, then there are n Bellman equations.Each of the n equations contain n unknown utilities of the states.\n\nIf we apply the Bellman update in value iteration an infinite number of times, then the utilities are guaranteed to reach an equillibrium. \n\nValue iteration converges to an equillibrium exponentially fast. This is because each iteration reduces error by some gamma, after k iterations that is gamma^k.\n\n**Contraction** - Part of the proof of convergence for the value iteration algorithm. function of one argument/fixed point. Apply this function to two different inputs, the two output values are closer together by some constant factor, compared to the original inputs. \n\n**Max Norm** - measures lenght of a vector by the absolute value of its biggest component.\n\n\n\n**Policy Iteration for solving MDPs*\n\n- We can get an optimal policy with an inaccurate utility function. The exact utilities don't matter, as long as they are sufficiently positive/in favour of what the optimal policy dictates.\n\n- Step 1 **Policy Evaluation** - given a policy $\\pi_{i}$ , calculate the utility of each state if $\\pi_{i}$ was excuted. $U_{i} = U^{\\pi_{i}}$.]\n\nDo this by using the bellman equation  with an action a fixed by the policy. We can expect to solve a system of n variables in O(n^3) time.\n$U_{i}(s) =\\sum_{s'}P(s′ |s, \\pi_{i}(s))[R(s,\\pi_{i}(s), s′)+γU_{i}(s′)] $.\n\n- Step 2 **Policy Improvement** - Calculate MEU (maximum expected utlity) policy $\\pi_{i+1}$ using one-step look ahead.\n\n- Stop when there is no change in utilties.\n\n\n**Linear Programming** - Variables: Utlities U(s) of each state s. You want to minimise: $U(s) \\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+γU(s')]$ for every state s and action a.\n\n- Solved in polynomial time, but not as efficient as dynamic programming for MDPs.\n\n- But can still solve MDPs.\n\n \n\n## Module 8 Lecture Notes\n  \nMDPs are sequential , non deterministic decisions problems, for fully observable environments, \\ with a stochastic (random probability) transition model, with additive rewards. USE EXPECTIMAX to solve.\nRequired: states, actions, transition function, rewards, start/end state.\n\n**Transition Function** T(s,a,s') returns probability that action a on s will resultin s'. T(s,a,s') = P(s' | s,a). \n\n**Policy** 𝝿(s) = a tells agent what action to take at state s. This is the solution.Optimal solution is 𝝿*. Same policy executed many times on agent can result ina different sequence of actions/score (due to probability). \n\n\nUse an **expected utility function** to calc sum of rewards given sequence of actions.Value/utility of a state V*(s) is the max of all q-state values (max Q*(s,a)).\n\n$$Q*(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V*(s')]$$\n\n**Discounting** = Balance between trying to maximise the sum of rewards by pickingrewards now or later. Multiple discount/fraction after each level. Helpsalgorithm converge/prevent infinite rewards.\n\n**Prevent infinite rewards**\n1) Finite Horizon (aka. depth limited search); terminateafter T steps until change is small. \n2) Discounting\n\n**Time Limited Values** - $V_{k}(s)$ is the optimal value of s if the game ends in k or more steps (ie. depth-k expectimax from s)\n\n**Value Iteration** - $O(S^{2}A)$\n\n1. Start with $V_{0}(s) = 0$.\n2. Given a vector V_{k}(s) of values, perform expectimax on each state\n3. $V_{k+1}(s) = max_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V*(s')]$\n4. Repeat till convergence\n**Problems with value iteration** - slow, \"max\" at each state rarely changes, policy converges way before values.\n\n\n**Policy Iteration** - converge much faster in certain conditions\n\n1. Policy Evaluation - calculate utilities given some fixed policy until convergence 3. $V_{k+1}(s)^{\\pi_{i}} = \\sum_{s'} T(s,\\pi_{i}(s),s')[R(s,\\pi_{i}(s),s') + \\gamma V_{k}^{\\pi_{i}}(s')]$\n\n2. Policy Improvement - Update policy using one-step-look-ahead with converged utilities as future values. Repeat till convergence. $\\pi_{i+1}(s) = argmax_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}^{\\pi_{i}}(s')]$\n\n\n\n\n\n\n\n\n\n## Module 8 Definitions\n* **Utility function** - assigns single number to express desirability of a state\n* **Performance measure** - Performance measure gives a score for a history; doesn't guide future actions like a utility function\n* **Maximum expected utlity** - a rational agent should choose the actions that maximizes the agent's expected utility; This doesn't actually solve the problem\n* **Transition model** - describes outcome of each action each state\n* **Markovian transition model** - probability of reaching next state only depends on current state\n* **Utility function for lottery** - $U([p_{1},S_{1};...p_{n},S_{n}])=∑_{i}p_{1}U(S_{i})$\n* **Policy** - solution to a stochastic problem, specifying what an agent to do at each state. Describes a simple reflex agent.\n* **Optimal policy** - π maximizes the expected utility of the actions taken by the agent.\n* **Asynchronous policy iteration** - updates only a subset of states; better efficiency since we can use herusitics to pick states to update\n* **A⪰b** - agent prefers A over B, or is indifferent about them\n* **V(s)** - Utility of starting at state s, and acting optimally after\n* **Q(s,a)** - expected utility of a q state (s,a). Having taken action a from state s, and acting optimally afterwards\n* **Contraction** - to show that value iteration converges\n* **Markov property** - Given the present state, the future and past are independent.\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n**n-armed bandit** - a slot machine with n arms/levers.\n\n- Tradeoff between exploitation of best current action, or exploration of unknown states to potentially gain more information/better rewards.\n\n- Every arm $M_{i}$ is a Markov reward process MRP (an MDP with oinly one possible action) and is a distribution over sequences of reward Random Variables.\n\n- Has states, transtion model, and reawrd function. \n\n**one-armed bandit**\n\n- One arm MRP that produces rewards R0, R1, R2...,  and costs λ for each pull.\n\n- Stopping time T is the number of times you pull the arm.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n**Passive Learning** - similar to the policy evaluation task. Difference is that passive learning agent doesn't know the transition model and the reward function. \n\n**Direct utility estimation** - idea that utility of a state is the expected total reward from that state onward. It ignores connections between state, thus it converges slowly. Using direct utilty estimation turns reinforcement learning problem into a supervised learning problem. The examples used are of the form (state, reward to go). \n\nThe Bellman equations provide a relationship between current states and future states which confer additional information ignored by direct utility estimation.\n\n**Adaptive Dynamic Programming (ADP)**\n\n- Uses direct utlity estimation to use the bellman equation.s\n\n- learns utility function, transition model, and reward function\n\n- For passive learning agent, plug in learned transition model $P(s'|s, \\pi(s))$ and observed rewards function $R(s, \\pi(s), s')$ to calcualte utilities of states. \n\n- Or you can use modified policy iteration - update the utility estimates after each change to learned model / adjust a state to agree with all possible successors.\n\n\n**Temporal Difference Learning (TD)**\n\n- - Use observed transitions to adjust utlities of the observed states, such that  they agree with constraint equations. TD's adjust a state to agree with the  successor in the current trial. Compared to ADP, TD kind of a first order approx.  It is more efficient, but less powerful.\n\n - It is called Temporal Difference because the update equation finds the  difference in utilities betwen successive states/times. \n\n -Update equation: $U^{\\pi}(s) = (1-α)U^{\\pi}(s) + α[R(s,\\pi(s),s') + γU^{\\pi}(s')]$\n\n - The new utility $U^{\\pi}(s)$ for a state is the old utility $U^{\\pi}(s)$,  pus the new information from the next state $[R(s,\\pi(s),s') + γU^{\\pi}(s')]$,  weighted by learning rate α.\n\n - A transition model is not needed to perform updates\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n**greed** - preference for utility\n\n-**curiosity** - prefer actions that have not been tried \n\n- If an agent’s exploration function values curiosity, N(s,a) for a state s and an action a would be low. N(s,a) is the number of times an action a have been  tried in state s. \n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n**Reinforcement Learning** - Here you still have a set of states, actions, transition model and a reward function. You are still looking for a policy. Difference is you may not know the transition function, or reward function, therefore you have to try actions and states to learn. Reinforcement Learning is ONLINE (no teacher/labeled examples, learn from experience). MDPs are OFFLINE.\n\n- in reinforcement learning, the agent is the MDP. They are not given an MDP to solve\n\n- Reward functions are concise (+ 1, -1, etc.), whereas labeled examples are complex\n\n\n\n**Model based learning**\n\n1. First we need to learn the empirical MDP model. For each state s and action a, count the number of times an outcome s' appears\n\n2. Normalise to give an estimate of transition T(s,a,s')\n3. Discover R(s,a,s') when we experience (s,a,s')\n4. Solve using value iteration\n\n**Passive reinforcement learning**\n\nGiven a fixed input policy, you want to learn the state utlities. Similar to policy evalution. but we are not given the transition or reward function. You have no choice about what actions to take, \nexecute and learn from experience; Online planning. \n\n\n**Direct Evaluation** - No knowledge of T and R \n\nThe goal is the compute values for each state under a policy. Follow the policy. \\ \nEvery time you visit a state, sum up the discounted rewards and average them.\n\n**Problems with Direct Evaluation** - Takes a long time, each state is learned seperately, waste information on state connections.\n\n\n**Temporal Difference Learning** -  modified policy evaluation; Running average\n\nUpdate V(s) every time we experience transition (s,a,s',r). This way, more likely outcomes s' will contribute updates more often. \n\nGiven a sample of V(s), update V(s) to be $V^{\\pi}(s) = (1-\u0007lpha)V^{\\pi} + (\u0007lpha)$sample\n\n\n\n**Active Reinforcement learning (QLearning)**\n1. Start with base case $Q_{0}(s,a) = 0$\n2. Given $Q_{k}$  calcualte the depth k+1 q-values for all q-states\nLearn the Q(s,a) value as you go. Receive a sample (s,a,s',r), and consider your old estimate Q(s,a). sample estimate = $R(s,a,s') + \\gamma max_{a}Q(s',a')$. Interpolate and incooperate your new estimate to the running average: \n\n$Q(s,a) = (1- α )Q(s,a) + \tα * sample$.\n\n**Exploration**\n- 2 Options: To force exploration, with small probability e, act randomly. With probability 1-e, act on current policy. OR you could gradually lower epsilon over time.\n**Exloration Function**\n\nExplore areas where 'badness' is not yet determined. Given an estiamte u, and visit count n, f(u,n) = u + k/n. \n\nUse this in Q-Update: $Q(s,a) = R(s,a,s') +  \\gamma max f(Q(s',a'), N(s',a'))$\n\n\n## Module 9 Definitions\n* **Exploration** - Try unknown actions to learn/get info\n* **Exploitation** - Use what you know\n* **Regret** - Making mistakes even if you use your best guess/relative goodness of exploration methods\n* **Sampling** - Try things repeatedly due to chance\n* **Difficulty** - You are solving an unknown MDP, so its harder to learn\n* **Off-policy learning** - Q-learning converges towards the correct/optimal policy, even if you are acting suboptimally\n* **Regret** - Difference between your rewards, and optimal rewards; measure of total mistake cost\n* **Sparse reward** - Agents don't receive any informative or useful reward signals in majority of states; Makes learning very hard\n* **Reward to go** - Given a policy, this is the total reward from a particular state onwards\n* **Direct utility estimation** - idea that utility of a state is the expected total reward from that state onward.\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n**Product Rule** - P(a∧b) = P(a|b)P(b) .\n\n**Maximum Expected Utility**\n\n- Agent is raitonal iff it chooses the actions that yields the highest expected utility, averaged over all possible outcomes of the action. \n\n\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n\n**Independence between variables X and Y** - can be shown as P(X|Y) = P(X) or P(Y|X) = P(Y) or P(X,Y) = P(X)P(Y)\n\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n**Bayes Rule** - P(Y|X) = P(X|Y) P(Y)  / P(X).\n\nOr otherwise if you want to find the cause: P(cause | effect) = P(effect|cause)P(cause) / P(effect).\n\nP(effect|cause) is a causal direction relationship, and P(cause|effect) is a diagnostic direction relationship.\n\nDiagnostic knowledge is more fragile than causal knowledge.\n\n\n**Conditional Independence** - P(X,Y|Z) = P(X|Z) P(Y|Z).\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n**Naive Bayes Model / Bayesian Classifier** - Simplified version in cases where 'effect' variables are not strictly independent from the given 'cause' variable.\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**Observed Variables (evidence)** - \n**Probability Mdoel** - associates probability P(w) with every world w. Possible worlds are the sample space\n\n**Random Variables** - uncertain aspects of the world.\n\n\n**Conditional Probability** : $P(a|b) = {P(a,b) / P(b)$\n\n**Inference By Enumeration** - Split random variables into three variables. Given H1...Hr, Q, and e1..ek, where Q is the query variable, and e1..ek are evidence variables, and H1..Hr are hidden variables (not observed, or actively reasoned). \n\n We want to find P(Q|e1...ek). \n\n 1. First select the enries in joint probability table consistent with the evidence$\\sum_{h1...hr}P(Q, h1..hr,e1...ek)\n\n 2. Marginalisation: sum out H (to remove it) to get joint distribution between query and evidence $P(Q,e1...ek) = \\sum_{h1...hr}P(Q,h1..hr,e1..ek)$\n\n 3. Normalize to convert into probability distributon [0..1]. P(Q|e1..ek) = (1\\Z)P(Q, e1...ek). Where Z = $\\sum_{q}P(Q,e1...ek)$.\n\n\n**Product Rule** - P(y)P(x|y) = P(x,y)\n\n**Chain Rule** - P(x1,x2,x3) = P(x1)P(x2|x1)P(x3|x2,x1)\n\n**Bayes Rule** - P(x|y) = [ P(y|x) / P(y) ] * P(x)\n\n\n**Probabilistic Language Model (LM)** - Goal is to assign probability to sentence/sequence of words\n\neg. P(\"the underdog Phildelphia Eagles won\") = P(won|the underdog philadelphia eagles)\n\nTo solve this, you can use the **Markov Assumption**; Only use the previous k words/history to infer.eg. If k = 2, P(won|the underdog Philadelphia Eagles) ~~ P(won| Philadelphia Eagles)\n**N gram Models** - Unigram, bigram, trigram,... etc. These are okay, but insufficient because language has 'long distance dependencies'\n\n\n**Estimating Bigram Probablilities** - Using the maximum likelihood estimate.\n\nP(wi|wi-1) = count(wi-1, wi) / count(wi-1)\n\n**Problem with MLE** - You can get zero probabilities with 'out of vocabulary' items. To deal with this replace any word not in the lexicon L with <unk>. Language Model computation is always represented in log-space/log probabilities. Problem is, if you multiply too many n-grams together, you can get numerical underflow. Solution is to add in log space instead. log(p1 * p2 * p3) = log(p1) +log(p2) + log(p3)\n\n\n\n## Module 10 Definitions\n* **Distribution** - table of probabilities of values\n* **Joint distribution** - over a set of RVs, gives real numbers for each assignment P(X=x, Y=y,...)\n* **Events** - set of outcomes; Calculate probability of events using Joint distributions\n* **Marginal distributions** - Sub tables that eliminate variables\n* **Marginalisation** - Collapse rows by summing up probabilities for an RV\n* **Conditional probability** - P(a|b) reads as: Probability of a given b\n* **Probabilistic inference** - Calculate probability from other known probabilities (either conditional, or update with new evidence)\n* **Unigram** - no history is used in inference\n* **Bigram model** - 1 history; P(wi|w1w2...wi-1) ~~ P(wi|wi-1)\n* **Markov assumption** - Probability of a word depends on previous word(s)\n* **Stationary** - conditional probability doesn't change over time\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \n**Bayesian Network** - To represent the dependencies among variables, a Bayesian Network is a directed acyclic graph. Every node represents an RV. Directed arrows between nodes infers parent information. Every node has probability information P(X_i } Parents(Xi)); ie. a conditional probability table. Topology specifies conditional independence of nodes. \n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n- Each variable is conditionally independent of its non-descendants, given its parents.\n\n\n**Check if X is conditionally independent of Y, given Z**\n\n- Create ancestral subgraph of X,Y,Z and ancestors\n\n- Create moral subgraph from this: add edges between all unlinked pairs of nodes that share common child\n\n- Turn into undirected graph\n- If Z blocks all paths between X and Y - then Z d-separates X and Y, then X is conditionally indpependent of Y given Z. \n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n\n\n\n## Module 11 Lecture Notes\n\n**Bayes' Nets / Graphical Models** - Describe complex joint distributions (models) using simple, local distributions (conditional probabilities). This is to avoid using full joint distriution tables as probabilistic models (they're too big anyways, hard to estimate unless its few variables at a time).\n\n\n**Graphical model notation** - Nodes (variables), Arcs (interations, influence, encode conditional independence), For each random variable X, there is a set of nodes. Bayes' net is a **directed, acyclic graph**. Each node has a conditional distribution for every parent value (nodes pointing in). P(x1,x2,...xn) = MULT_{i=1..n} P(xi|parents(Xi))\n\n\n**Causality** - Simple Bayes' nets reflect causal patterns. Directed arrows encode causality and conditional independence. \n\n**Size of BN** - Size of joint distribution over N boolean vars is $2^{n}$. N-node BN where each node has up to k parents is of size $O(N * 2^{k+1})$. \n\n\n**D-Separation**\n**Causal Chains** - Given X -> Y -> Z, is X guaranteed indpendent of Z given Y? Yes P(z|x,y) = P(z|y). Evidence along the chain \"blocks\" the influence.\n\n**Common Cause** - Given Y->X and Y->Z, is X and Z independent of Y? Yes P(z|x,y) = P(z|y). Similar cause blocks influence between effects.\n\n**Common Effect** - Given X -> Z and Y->Z. X and Y are independent. BUT X and Y are not independent given Z. \n\n\n**Active and Inactive Paths** - X and Y are conditionally independent given evidence variable Z if X and Y are \"d-separated\" by Z. If there are no active paths = independence. A path is active if each triple is active eg.:\n\ncausal chain A->B->C where B is unobserved\n\ncommon cause A<-B->C where B is unobserved\n\ncommon effect A->B<-C where B or one of its descendents is observed\n\n\n- **PROCEDURE**. Shade all evidence nodes grey (ie. A⊥B | evidence nodes). Then visualise graph as undirected, and find all undirected paths between A and B. Along each of these undirected paths, check all trios. If any of these trios are inactive, then the whole undirected path is inactive. If all trios are active, then whole undirected path is active. If all undirected paths between A and B are inactive, then A is conditionally independent of B. \n\n\n**Inference by Enumeration in Bayes' Net** - see example in handwritten sheet.\n\n \n\n## Module 11 Definitions\n* **Locally structures sparse system** - The structure grows linearly in complexity (rather thanexponentially)\n* **Markov blanket** - Variable is conditionally independent of all other nodes in the network (incl. parents,children, etc.)\n* **D-separates** - separation in the undirectd, moralised, ancestral subgraph\n* **Deterministic node** - value is specified by the value of its parents\n* **Hybrid bayesian network** - network with discrete and continuous variables\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n**Forms of Learning**\n- Improve agent program by ML depends on the component to be improved, what prior knowledge the agent has, what data and feedback is avaliable.\n\n- Possible components include transition function, percept sequence inferences, utility information, action-value information, etc.\n\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n**Supervised Learning**\n- Given training set of N input-output pairs generated by an unknown function of form (x1,y1), (x2,y2)...(xN,yN), find a function h that approximates the true function f. h **generalises** well when it can accurately predict the outputs of a test set.\n\nh*, the best fit, can be found by $h* = argmax_{h \\in H} P(h|data)$. By bayes', this can also be written as $h* = argmax_{h \\in H} P(data|h)P(h)$.\n\n\n**Best-fit function**- It's too hard to match the ground truth with continous valued outputs, so use a best-fit function. \n\n**Bias** - How often the predictive hypothesis deviates from the expected value when averaged over different training sets. EG. hypothesis space of linear functions has strong bias because straight lines. Piece wise linear function is low bias. \n\n\n**under fitting** - predictive hypothesis doesn't find a pattern in the data.\n\n**over fitting** - predictive hypotehsis focuses too hard on particular training set, that it doesn't perform well on unseen data.\n\n**Variance** - The amount the hypothesis changes because of fluctuations in training data. \n\n**Bias-Variance Tradeoff** - low-bias hypothesis can fit training data simpler/better, but low-variance can generalise better\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n**Decision Tree** - represents a function that maps vector of attribute values to a singular output/decision.\n\nEach node represents a test applied to an input attribute value, and each outgoing branch is a possible value, and leaf nodes are the value to be returned. \n\n\n\n\n \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 \n**Gradient Descent**\n\n- To minimise Loss. Choose any starting point in the weight space and compute the gradient. Find the steepest downhill direction, and update/move in that direction. Repeat until we converge ona point in weight space with minimal local loss. \n\n- wi = wi - a * gradient * loss(w)\n- This uses a **step size/learning rate** - either a constant, or it can decay over time. \n**Stochastic Gradient Descent**\n\n-randomly select small number of training examples at each step\n\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n**Naive Bayes'**\n\n- probabilistic classifier. For document d, and classes $c \\in C$, the classifier return class c^, the estimate of the correct class. \n\n- c^ = argmax P(c|d) over all $c\\in C$.\n\n**Bayesian Inference**\n\n- estimate of the correct class/classification becomes c^ = argmax P(d|c)P(c) \n\n- P(c) is the prior probability\n\n- P(d|c) is the likelihood of the document\n\n- Naive Bayes is **generative** \n\n- **Naive Bayes' Assumption** - Probabilties P(f_i | c) are independent given class c, such that P(f1,f2,...fn | c) = P(f1|c)P(f2|c)...P(fn|c).\n\n\n- **Unknown Words** - words that are in test data but not in vocabulary (because it did not appear in training data at all). Simply ignore them/remove from test document/0 probability\n\n**Stop Words** - Frequent words such as 'the' and 'a'. Sort and the top 10-100 words are 'stop words'. Remove these stop words from training and test documents\n\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\n**Binary Multiomial Naive Bayes (Binary NB)**\n\n- \n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n\n**Linear Classifiers**\n\n- INPUT: feature values with weights. Activation is the sum of the weight vector and the feature values.\n\n\n**Binary Decision Rule**\n\n-\n\n**Multiclass decision rule** \n\n- For multiple classes, we'll have for each: a weight vector w_y, a score/activation  of a class dot(w_y, f(x)), and whichever score is highest wins.\n\n **learning**\n\n - Start with weights = 0\n\n - Predict the current weights y= arg max_y dot(w_y, f(x))\n\n- if the prediction is wrong, lower the score of the wrong answer, and increase the score of the correct answer by f(x).\n\n**Problems with perceptrons**\n- NOISE: If not separable, thrashing might happen; using averaged weight vectors over time will help\n\n- Could settle with a mediocre/barely separating solution rip\n\n- Overtraining/over fitting: accuracy rises and then falls after too many iterations.\n\n\n\n\n## Module 12 Definitions\n* **Classification** - when output of learning problem is a finite set of values (like labels)\n* **Regression** - when output is numbers, or floats, or integers\n* **Supervised learning** - agent observes provided input-output pairs, and learns a function\n* **Unsupervised learning** -  agent learns patterns of input without any feedback typically in form of clustering\n* **Decision boundary** - Line/surface that separates two classes\n* **Linear separator** - A linear decision boundary\n* **Linearly separable** - data that is split by linear decision boundary\n* **Perceptron learning rule** - the weights are updated when the actual output does not match the hypothesis output.\n* **Perceptron** - linear classifier with a hard threshold\n* **Mistake bound** - maximum number of mistakes (binary case) related to the margin or degree of separabilty ; mistakes < k/ d^2\n* **Exploratory data analysis** - examine data with visulaisations and statistical tests\n* **Entropy** - Measure of the uncertaining of an RV. More info, less entropy\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 \n**Cross Entropy Loss Function**\n\n \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n**Classifier Components**\n- Machine learning classifiers need training data set: M observations with input-output pairs $(x^{i}, y^{i})$\n- Feature representation (vector of features for each input $[x_{1},x_{2},...x_{n}])$. Each feature could be a definition of what to count, or whatever is needed to help classify. Every feature is weighted by importance. The weights are learned.\n\n- classification function (estimates class y^ via p(y|x)), \n\n- objective function to minimise error on training samples\n\n- algorithm for optimising the ojective function (eg. SGD).\n\n\n**Sentiment Classifier** - classifying text whether it is positive(1) or negative(0)\n\n- take input oservation x with feature vector with n different elements. \n\n**Logistic Regression** - learns from a training set, weights, and bias term. Logistic regression is a network with just one weight layer and a sigmoid output. We want to estimate P(y=1 | x), ie. given the input x, probability that the text is positive. $z = w \\cdot x + b$.\n\n- range of z is -inf and +inf, so to have it range from [0, 1], we need to use the **sigmoid function**\n\n- sigmoid function si $y = 1 / (1 + e^{-z})$ converts the range to 0 to 1 for probabilities.\n\n- eg. $P(y=1) = \\sigma(w \\cdot x + b) = 1 / ( 1 + e^{-w \\cdot x + b})$\n\n\n**Decision Boundary**\n- After transforming with sigmoid class, use a decision boundary to decide if we return positive, or negative.\n\n- ie. $\\hat{y} = {1 if P(y=1|x) > 0.5$, else 0}\n\n\n**Loss Function** - The distance betwen the system output and the gold output. Use Cross Entropy Loss.\n\n- $L(\\hat{y},y)$ = how much y^ differs from true y. \n\n**Cross Entropy Loss**\n\n- Maximise the correct class labels of the training example. Choose parameters weight and bias that maximise the log probabilities of the true labels in trainig data. \n\n- $P(y|x) =  \\hat{y}^{y}(1=\\hat{y})^{1-y}$, where correct label y can only be 0 or 1. When y is 1, then we want y^ to be as close to 1 as possible.\n\n- take the log of both sides, and negate for 'loss', $L_{CE}( \\hat{y}, y) = -[log P(y|x) = ylog \\hat y + (1-y)log(1- \\hat y)]$.\n\n- substitute $\\hat{y} = \\sigma(w \\cdot x + b)$ in above equation.\n\n\n- We want to minimise this negative log probability because if our model is close to correct, then CE loss is lower.\n\n- If the prediction is incorrect, we want our CE loss to be higher\n\n- Using log function ensures that as the probability of the correct answer is maximised, the probability of the incorrect answer is minimised.\n\n\n**Loss of all training examples** -> log P(training labels) = $ - \\sum_{i=1}^{m} L_{CE}(\\hat{y}^{i}|y^{i})$\n\n\n**Stochastic Gradient Descent SGD** - to update the parameters (weights, bias) of our model to minimise our loss function. \n\n- Chooses a single random example at a time and updates the weights on that example\n\n- Let $\theta$ be the set of parameters in our model, ie. weight and bias terms. We want to find a setting of $\theta$ that will minimise the average cross entropy loss.\n\n- Gradient Descent finds the direction that is rising the most steeply/slope, and going in the opposite direction/downward.\n\n- **convex** - just one minimum for logistic regression (no local minimum to get stuck in)\n\n- **learning rate** - size of step we take $\\eta$; Of the learning rate is too big, you might accidently step over the global minimum, or find a local minimum.\n\n- $w^{t+1} = w^{t} - \\eta d\\dw f(x;w)$\n\n\n**Multi direction SGD**\n- For every weight in weight vector has a slope. Find the partial derivative of loss with respect to each weight. - $\\delta_{\theta} L(f(s,\theta),y)=$\n\n- derivative of athe Loss CE function for one observation x and a single weight wi is: $[\\hat{y} / (w \\cdot x + b - y)] x$\n\n**Mini-batch training**\n\n- **Batch training**: Compute gradient over an entire dataset. This gives a better estimate, but takes a long time. \n\n- For **mini**  batch training, train on a batch of size 512 or 1024. All examples in batch processed in parallel, loss is accumulated.\n\n\n**overfitting** - if a feature only occurs in one class then it will get a high weight, resulting in noise and overfitting/poor generalisation.\n\n\n**Multiclass classification**\n\n- Positive, negative, neutral\n\n- Use a generalisation of the sigmoid called the **softmax function**\n\n- take an input vector z, and outputs a vector of values normalised into probabilities\n\n- Output is a probability distribution; sum up to 1.\n\n\n**Neural Networks**\n\n- A neural network with enough neurons and a nonlinear activation function can approximate a huge range of possible functions (\"feed forward neural network\")\n\n- \"deep\" part of deep learning is the number of stacked hidden layers; this gives it it's power.\n\n- **sigmoid neuron** - a regular perceptron outputs either 0 or 1. A small change in the weights or bias will cause the output to just flip in a 'step function' manner. Sigmoid neuron gives a smoother activiation function (gently change between 0 and 1).\n\n**Activation Function** - Takes in the inputs and decides the outputs. \n\n- y = a = f(z), where y is the output of the NN, and a is the activation value, and f(z) is the activation function.\n\n- Three most common non-linear functions are sigmoid, tanh, and rectified linear unit (ReLU)\n\n- ReLU - is close to linear\n\n\n**Feed-Forward Neural network**\n\n- A multilayer network (fully connected, no cycles)\n\n- Outputs from each layer and fed forward to the next higher layer.\n\n**Training Neural Nets**\n\n- Need a loss function, optmisation algorithm (Gradient Descent), method of computing gradient of loss function (**error back propagation**)\n\n- Gradient of a logistic regression only gives correct updates for the last weight layer. \n\n- Deep networks need to look back through earlier layers to compute gradients - error back propagation\n\n**Error Back Propagation** - enables us to correctly update all layers inthe neural network, and learn the weights in our system\n\n- **Backward differentiation**\n\n- **computation graph** - break down math expression into separate operations (nodes in graph) eduges are inputs to the next operation. Used in forward pass (read left to right)\n\n- Backwards differentiation uses the chain rule. Goal is to find the derivative with respet to the loss at each of the nodes  If you want to find the derivative of the input, find the partial derivative of the  intermediate nodes with respect to their parents, and chain rule from right to left. \n\n\n\n \n\n## Module 13 Definitions\n* **Overfitting** - results in poor generalisation and poor performance on unseen test\n* **Regularisation** - way of avoiding overfitting when you have a lot of weights; penalise large weights; add term to loss function\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n**Language Model** - estimate the probabliity of a sequence of words given the preceeding k words\n\n**Neural Language Models** - Don't need smoothing, handle longer histories, generlise over contexts of similar words and higher predictive accuracy than n-gram language models. BUT much slower. \n\n- Associate every word in vocabulary with a vector-representation with real values - creating the idea of similarities between words\n\n- Define joint probability function of a word sequence using these word vectors\n\n- Concurrently learn word vectors and parameters of the function\n\n- Probability function expressed using a multi-layer feed forward neural network (product of conditional probabilities of next word given previous word.)\n\n\n- Input: k-gram of words $w_{1:k}$\n\n- Output: probabliity distribution over the next word\n\n- every word associated with an **embedding vector**\n\n- **one hot vector** - a vector of length of vocabulary; index corresponding to word input is turned on. Learn a set of weights each word in the input layer one hot vector.\n\n- Given a corupus, read every sequence of length K as a training item. k-1 items as input, k word as correct label. \n\n- Train using cross entropy and back propogation\n\n- We are basically constructing look up tables for probabliities of seeing a word given a history. \n\n- NN Model learns how to generalise\n\n\n- Structure is one hot vector -> [:mapping function] -> d dimensional learned vectors -[:input]-> feed forward neural network predicts word; see what words a similar to each other\n\n\n**Lexical Semantic Models**\n\n- How to represent the meaning of a word? Want to encode: synonms, antonyms, connotations, semantic roles, etc. \n\n- Entailment : dog is a subset of animal; hierarchal reprsentation of words and their meanings. Based on math, handles logical operations, but this knowleedge must come from somewhere else/acquire for a long time.\n\n\n**Vector space model**\n\n- ABle to automatically extract knowledge from a large corpus. \n\n- every word is represented as points in vector space; points that are close to each other mean the words are semanticlally similar.\n\n- Synonym != similar; More words are similar ie. dogs and cats, tall and height\n\n\n**Distributional Hypothesis**\n- relative frequency of words in environments. If A and B have similar environments/contexts, then they are synonyms\n\n**Term-Document Matrix**\n\n- Each column vector represents a document; Each row represents a term/word, a cell in the document represents how often that term has occured in the document. \n\n- Length of the document/column vector is the size of the vocabulary; Document vectors can be sparce (mostly 0s, not all words in the english language are used)\n\n- Document similarity: can be used for plagirism detection\n\n- Comparing two row vectors: how similar two words are. Words that occur in similar sets of documents must be similar. \n\n**Vector comparisons**\n- example: Consider table where A,B,C are words on each row, and then docX and docY are the column headers\n\n- If comparing words A, B, C from two documents docX, docY, plot on x-y graph. For each word, plot point frequency (Ax, Ay), (Bx, By), ... Measure Euclidean distance between each point-> square root of Ax^2 + Ay^2\n\n- (**Vector Length/L2 normalisation**) Normalise the euclidean distance, and then divide every word's row cell by this normalised value. Ax / |euclidean|, By / euclidean, ...\n\n- Replot the graph with these normalised x and y values; We do this because now words that had lower frequency are now scaled so that it fits better in graph. \n- Distance measures how similar words are\n\n\n**Cosine Distsance**\n\n- Cosine angle betwen vectors tells how similar they are. Vectors spawn from origin to normalised x-y points. \n\n- Cosine distance has vector length normalisation in it.\n\n\n**Term-Term**\n\n- Square Matrix; Every word is a column vector and a row vector. \n\n- Lengt of row vector is now |V| isntead of number of documents. \n\n- Ie. if we index into cell (abdicate, abandon),this cell value now indicates how often abandon appears in a context window surrounding abdicate\n\n**context windows** -Find all instances of 'abdicate' in the corpus, then tally what words and the frequency of that word that happen +/- 2 words to the left or right around 'abdicate'.  \n\n- **Dependency Parsing** You can adjust this for more complex contexts (subj-of-verb, adj-mod). You can tell things hold, when isntead of just +/- 2, meaning still holds for long distances\n\n- **syntax to define a word's context** - Duty and responsibility have similar syntatic dsitributions (types of adjectives, etc.)\n\n\n**Other than counting**\n\n- Word counts can be super skewed towards (A, and, of, etc.), as the frequency of words in the english dictionary exponentially decreases\n\n- To fix this, Transform these vectors using TF-IDF or PPMI\n\n\n**TF-DF** - Term Frequency * inverse document frequency, \n\nwhere term frequency is how often a word occured in a document, and inverse document frequency is 1/(number of documents that it occured in)\n\n\n**Sparse v. Dense Vector**\n\n- Sparse: msot elements in 0\n\n- Long: |V| = 50,000+\n\n- Short: |V| = 200-100\n\n- Dense: most elements are non zero\n\n\n- How to we get dense vectors? : train a classifer!\n\n- Get positive examples: target word and neighbouring context words\n\n- Get negative examples: randomly sample other words\n\n- Use logistic regression to train classifier to tell positive and negative apart\n\n- Use these weights as **embeddings**\n\n\n- **Word2Vec**\n\n- Predict each neighbour word in a context window (C = +/- 2)\n\n-Positive examples want to get a high probability; and vice versa for negative examples\n\n- Plug into neural network \n\n\n- Embeddedings capture relational meanings. \n\n\n## Module 14 Definitions\n* **Corpus** - large collection of texts\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}